알고리즘 : 동적계획법(Dynamic Programming)과 분할정복(Divide and Conquer)

출처 : 위키백과

 

정의

• 동적계획법 (DP)
• 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결하고 최종적으로 전체 문제를 해결하는 알고리즘
• 상향식 접근법, 가장 최하위 해답을 구한 후 저장하고 해당 결과값을 이용해서 상위·문제를 풀어가는 방식
• Memoization 기법 사용 (프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술)
• 문제를 잘게 쪼갤 때 부분 문제는 중복되어 재활용됨 (피보나치 수열)
  
  
• 분할 정복
• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 하향식 접근법, 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식 (일반적으로 재귀함수)
• 문제를 잘게 쪼갤 때 부분 문제는 서로 중복되지 않음 (병합정렬, 퀵 정렬 등)

 

공통점, 차이점

• 공통점 : 문제를 잘게 쪼개서 가장 작은 단위로 분할

- 차이점

- 동적 계획법
  - 부분 문제는 중복되어 상위 문제 해결 시 재활용됨
  - Memoization 기법 사용

- 분할 정복
  - 부분 문제는 서로 중복되지 않음
  - Memoization 기법 사용 안함