[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

자료 출처: https://youtu.be/5Lu34WIx2Us

이전까지는 다이나믹 프로그래밍이 뭔지 아예 모르고 이름만 많이 들어봤었는데, 이 강의 덕에 개념이 잡혔다. 문제를 아주 많이 풀어봐야 할 것 같다.

1. 다이나믹 프로그래밍

한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘
메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법으로, 이미 계산된 결과는 별도의 메모리 영역에 저장한다.

 

조건

• 최적 부분 구조 (Optimal Substructure): 큰 문제를 작은 문제로 나눌 수 있는 경우. 즉, 작은 문제의 답을 모아 큰 문제를 해결할 수 있음
• 중복되는 부분 문제 (Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결해야 함

다이나믹 프로그래밍은 탑 다운 방식과 바텀 업 방식으로 나뉜다.

• 탑 다운: 재귀 함수를 이용하여 큰 문제를 해결하기 위한 작은 문제를 호출하는 방식. 메모이제이션(memoization)을 사용하는데, 이는 한 번 계산된 결과를 메모리 공간에 메모하는 기법으로 캐싱(caching)이라고도 한다. 시간 복잡도는 O(N)
• 바텀 업: 단순히 반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식. 결과를 저장하는 리스트는 DP 테이블

2. 다이나믹 프로그래밍 vs 분할 정복

분할 정복(퀵 정렬, 병합 정렬 등)과 다이나믹 프로그램의 차이는 두 번째 조건인 부분 문제의 중복에서 온다.

• 공통점: 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.
• 차이점: 각 부분의 문제들이 서로 영향을 주고 받으며 부분 문제가 중복되는 다이나믹 프로그래밍의 경우와 달리 분할 정복은 동일한 부분 문제가 반복적으로 계산되지 않는다.

3. 피보나치 수열 다이나믹 프로그래밍 소스코드 (탑다운, 바텀업)

피보나치 수열 탑다운 DP 소스코드

# 한 번 계산된 결과를 기록(memoization)하기 위해 리스트를 초기화함
d = [0] * 100

def fibo(x):
    if x == 1 or x == 2:
        return 1
    
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]
        
    # 아직 계산한 적 없는 문제라면 점화식에 따라 피보나치 결과 반환
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

피보나치 수열 바텀업 DP 소스코드

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

d[1] = 1
d[2] = 2
n = 99

# 재귀함수 대신 반복문
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

4. 다이나믹 프로그래밍 문제에 접근하는 방법

• 그리디, 구현, 완전탐색 등의 아이디어로 해결할 수 있는지 먼저 검토 → 떠오르지 않는다면 다이나믹 프로그래밍 고려해보기
• 우선 재귀함수로 비효율적인 완전탐색 프로그램을 작성한 후(top down), 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드 개선