[알고리즘] 동적계획법과 분할정복

정의

동적계획법

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

분할정복

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

공통점과 차이점

공통점

• 문제를 잘게 쪼개서, 가장 작은 단위로 분할

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

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

코드 예시

동적 계획법

def fibo_dp(num):
    cache = [ 0 for index in range(num + 1)]
    cache[0] = 0
    cache[1] = 1
    
    for index in range(2, num + 1):
        cache[index] = cache[index - 1] + cache[index - 2]
    return cache[num]