[알고리즘] 동적 계획법 Dynamic Programming

동적 계획법 (DP)

• 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 해결하고 그 결과를 저장하여 다시 큰 문제를 해결하는 알고리즘, 문제 해결 패러다임
• 상향식 접근법, 최하위 해답을 구하고 이를 이용하여 상위 문제를 풀어감
• Memorization 기법 사용
  • 프로그램 실행 시 이전 계산 값(작은 문제)을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술임
• 큰 문제를 작은 문제로 쪼개서 답을 저장하고 재활용 하기에 '기억하며 풀기' 라고도 불림
  
  • ex) 피보나치 수열

• 재귀함수와 다른 점은 \((F_{2}\) 가 여러번 사용되는데 동적 계획법은 저장하여 다시 계산하지 않고 재귀함수는 하나하나 다 계산하여 시간이 오래 걸린다
• \( O(n^{2}) \to O(f(n)) \)

 

---

분할 정복

• 큰 문제를 작은 문제로 나누어서 각각을 풀면서 다시 합볍하여 문제의 답을 얻는 알고리즘
• 하양식 접근법으로, 상위의 해답을 구하기 위해 문제를 쪼갬
  • 일반적으로 재귀함수로 구현함
• 문제를 쪼갤 때, 부분 문제는 서로 중복되지 않음
  • ex) 병합 정렬, 퀵 정렬

---

공통점 차이점

공통점

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

차이점

• 동적 계획법은 부분 문제가 중복 되어, 상위 문제 해결 시에 재활용 되고 Memorization 기법을 사용함
• 분할 정복은 부분 문제가 서로 중복 되지 않고 Memorization 기법을 사용하지 않음

---

Dynamic Programming 구현

피보나치 Recursive call

def fibo(num):
    if num <= 1:
        return num
    return fibo(num-1) + fibo(num-2)

피보나치 Dynamic Programming

def fidp(num):
    # Memorization
    cache = [0 for _ in range(num+1)]
    cache[0] = 0
    cache[1] = 1
    
    for i in range(2, num+1):
        cache[i] = cache[i-1]+cache[i-2]
    return cache[num]