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

동적 계획법(Dynamic Programming, DP)

• 작은 부분 문제들을 해결한 후, 해당 부분 문제들의 해를 활용하여 보다 큰 부분 문제를 해결하면서, 최종적으로 전체 문제를 해결하는 알고리즘
• 「상향식 접근법」으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
• Memoization 기법을 사용함

Memoization(메모이제이션)이란?
: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술

• 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨
  
  • 예: 피보나치 수열

---

분할 정복(Divide and Conquer)

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

---

DP와 분할 정복 비교

• 공통점: 문제를 잘게 쪼개서, 가장 단위로 분할
• 차이점
  • 동적 계획법
    • 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨
    • Memoization 기법 사용 (부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)
  • 분할 정복
    • 부분 문제는 서로 중복되지 않음
    • Memoization 기법 사용 안함

---

DP 알고리즘 이해

ex) 피보나치 수열

 

---

1) 재귀 호출로 구현: 과도한 중복 계산 발생

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

 

2) Memoization 기법: 각각의 계산 값을 별도의 저장 공간에 저장

fibo(0):0

fibo(1):1

fibo(2):1

fibo(3):2

fibo(4):3

fibo(5):5

fibo(6):8

fibo(7):13

fibo(8):21

fibo(9):34

 

3) 동적 계획법 활용

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]

이전 값을 저장해서 현재 문제를 해결하는 과정을 표현

 

Live Programming Mode - Python Tutor - Visualize Python and JavaScript code