백준2 [ 알고리즘 ] 분할 정복 알고리즘(Divide and conquer algorithm) 분할 정복 알고리즘이란? 등차수열의 공식과 연관지어 생각해본다! 분할 정복 알고리즘은 문제를 나눌 수 없을 때 까지 작게 나누어서(Divide) 각각을 해결하여 정복(Conquer)하는 알고리즘이다. -이처럼, 분할 정복은 하위 문제를 재귀적으로 해결하기 때문에 하위 문제 각각은 원래 문제보다 범위가 작아야 하며 하위 문제는 각 문제마다 탈출 조건이 존재해야 합니다. 분할정복 알고리즘 설계 요령 (1) Divide : 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눈다.-> 이 과정이 가장 중요한 과정. (2) Conquer : 나누어진 하위 문제를 재귀적으로 해결한다. 즉 하위 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 탈출 조건으로 놓고 해결한다... 2021. 1. 18. [ 알고리즘 ] 동적 프로그래밍 =Dynamic Programming=동적계획법 동적 프로그래밍이란? 큰 문제를 여러 개의 하위 문제로 쪼개고, 이 하위 문제들을 먼저 해결한 후 이를 이용해서 더 큰 문제를 풀어나가는 방법이다. (=먼저 입력크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘이다) ▶ Bottom-up 방식 - 동적 프로그래밍은 각 하위 문제들이 서로 관계가 없을 때, 즉 서로 의존하지 않는 경우에만 쓸 수 있다. 동적 프로그래밍이 필요한 이유(배경) 예를들어 피보나치 수열을 보자. 피보나치 문제를 풀 때 재귀적 방법(Recursion)과 Dynamic Programming 방법이 있다. 재귀적 방법 def fi.. 2021. 1. 11. 이전 1 다음
