[파이썬] 동적 계획법(DP)과 분할 정복(DAC)

동적 계획법 (DP; Dynamic Programming)

• 입력 크기가 작은 문제들을 해결한 후, 해당 문제의 해를 활용해서 보다 큰 크기의 문제를 해결하며 최종적으로 전체 문제를 해결하는 알고리즘 (상향식 접근법)
• Memoization 기법(프로그램 실행시 이전에 계산한 값을 저장하고 재활용해서 전체 실행 속도를 높이는 기술)을 사용함
• 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용됨
• 예) 피보나치 수열

 

분할 정복 (DAC; Divide and Conquer)

• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘 (하향식 접근법)
• 일반적으로 재귀 함수로 구현함
• 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음
• 예) 병합 정렬, 퀵 정렬

 

(예제) 피보나치 수열

피보나치 수열 정의

재귀 함수 활용

동적 계획법 활용