코드잇의 알고리즘의 정석 수업을 수강하고 정리한 글입니다.
정확하지 않거나 빠트린 내용이 있을 수 있기 때문에 강의를 수강하시길 권장합니다.

Dynamic Programming의 조건

1. 최적 부분 구조 (Optimal Substructure) 인가?
2. 중복되는 부분 문제 (Overlapping Subproblems)가 있는가?

우리가 풀어야 하는 문제가 최적 부분 구조를 갖고있고, 중복되는 부분 문제들이 있을 수 있다. 이러한 비효율을 해결하기 위한 알고리즘 패러다임이 다이나믹 프로그래밍이다.

다이나믹 프로그래밍을 이해하기에 앞서 최적 부분 구조와 중복되는 부분문제에 대해서 먼저 살펴본다.

1. 최적 부분 구조

최적 부분 구조가 있다는건?

부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것이다

예시1. 피보나치 수 문제

부분문제인 $fib(4)$와 $fib(3)$의 최적의 답을 이용해서 기존문제인 $fib(5)$의 최적의 답을 구했다. 따라서 피보나치 문제는 최적 부분 구조를 갖는다고 볼 수 있다.

예시2. 최단 경로 찾기

서울→부산으로 가는 최단 경로를 풀기 위해서는 서울→H, 서울→I, 서울→J로가는 최단 경로 문제의 답이 필요하다.

부분문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구했다. 따라서 이 문제도 최적 부분 구조를 갖는다.

2. 중복되는 부분문제

다시 한번 피보나치 문제를 보자. $fib(5)$의 문제를 풀기 위해서는 $fib(4)$와 $fib(3)$의 솔루션이 필요하다고 했다. 그리고 계속해서 부분문제를 나누다보면 아래와 같이 부분문제들이 존재한다.

그림 자세히 보면 중복되는 부분문제가 있다. $fib(3)$, $fib(2)$, $fib(1)$은 두번 계산된다. 이를 중복되는 부분 문제(Overlapping Subproblem)이라고 한다. 이번 장에서 다이나믹 프로그래밍을 통해 이를 해결할 것이다.

중복되지 않은 부분문제 (None-overlapping Subproblem)

문제를 부분문제로 나눈다고해서 항상 중복되는 부분문제가 존재하는것은 아니다. 합병 정렬(merge-sort)을 보자.

# 기존 문제
merge_sort([16, 11, 6, 13, 1, 4, 10, 7])

# 부분 문제
merge_sort([16, 11, 6, 13])
merge_sort([1, 4, 10, 7]

합병 정렬의 부분문제를 푸는 과정은 서로 독립적인걸 알 수 있다. (중복되지 않는다)

3. Dynamic Programming

앞서 최적 부분 구조와 중복되는 부분 문제에 대해 살펴보았다. 어떤 문제를 다이나믹 프로그래밍을 통해 개선할 수 있는는지 고민된다면 다음과 같이 생각하자.

최적 부분 구조가 있다. → 부분 문제들의 최적의 답을 이용해서 기존 문제를 풀 수 있다.(기존 문제를 부분 문제로 나눠서 풀 수 있다.) → 중복되는 부분문제들이 있을 수 있다.

이러한 중복되는 부분문제를 해결하는것이 Dynamic Programming이다.

Dynamic Programming: 한 번 계산한 결과를 버리지 않고 재활용하는 방식

Dynamic Programming 기법

1. Memoization
2. Tabulation

4. Memoization

Memoization은 중복되는 계산은 한번만 계산 후 메모하는 방법

피보나치 수에 적용하기

$fib(6)$에 대한 부분문제들을 아래와 같이 그려볼 수 있다. 좌측 하단부터 계산을 수행해보겠다.

1. $fib(3)$을 풀려면 $fib(2)$, $fib(1)$를 풀어야 한다. base case이다. 각각의 답을 cache에 저장한다.
2. $fib(3)$은 $fib(2)$와 $fib(1)$의 솔루션을 이용해서 풀 수 있다. 답을 cache에 저장한다.
3. $fib(4)$는 $fib(3)$과 $fib(2)$의 솔루션을 이용해서 풀 수 있다. $fib(3)$과 $fib(2)$의 답은 cache에서 가져온다. $fib(3)$과 $fib(2)$의 답을 이용해 $fib(4)$를 풀고 cache에 저장한다.
4. $fib(5)$는 $fib(4)$과 $fib(3)$의 솔루션을 이용해서 풀 수 있다. $fib(4)$과 $fib(3)$의 답은 cache에서 가져온다. $fib(4)$과 $fib(3)$의 답을 이용해 $fib(5)$를 풀고 cache에 저장한다.
5. $fib(6)$는 $fib(5)$과 $fib(4)$의 솔루션을 이용해서 풀 수 있다. $fib(5)$과 $fib(4)$의 답은 cache에서 가져온다. $fib(5)$과 $fib(4)$의 답을 이용해 $fib(6)$를 푼다.

우리는 각 부분문제를 한번씩만 풀었다. Memoization을 통해 중복되는 부분문제를 해결하였다.

5. Memoization을 이용해 피보나치 문제 풀이

문제

피보나치 수를 찾아주는 함수 fib_memo를 작성하라. Memoization방식으로 구현해야 한다.

def fib_memo(n, cache):
    # 코드를 작성하세요.

def fib(n):
    # n번째 피보나치 수를 담는 사전
    fib_cache = {}

    return fib_memo(n, fib_cache)

# 테스트
print(fib(10))
print(fib(50))
print(fib(100))

# 콘솔 출력
55
12586269025
354224848179261915075

풀이

4절의 피보나치에 적용하기 설명을 참고하자.

코드

def fib_memo(n, cache):
    # base case
    if n <= 2:
        return 1
    
    # 답이 cache에 있으면 가져온다.
    if cache.get(n):
        return cache.get(n)
    
    # 답을 cache에 저장
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]
    

def fib(n):
    # n번째 피보나치 수를 담는 사전
    fib_cache = {}

    return fib_memo(n, fib_cache)

# 테스트
print(fib(10))
print(fib(50))
print(fib(100))

6. Tabulation

우리는 앞서 Memoization을 이용해서 답을 구해보았다. Memoization과 Tabulation의 가장 큰 차이는 어느 값을 먼저 구하는가? 의 접근 방식이다.

다음 그림을 확인해 보자. 피보나치수 $f(6)$을 구하기 위해 $f(5)$를 구해야 하고, $f(5)$를 구하기 위해 $f(4)$를 구해야 했다. 이는 하향식 접근이라고 볼 수 있다.

Tabulation은 기본적으로 상향식 접근(bottom up)을 기반으로 한다.

다음 표를 보자.

$n$	$fib(x)$
1	1
2	1
3	2
4	3
5	5
6	8

$fib(1)$부터 테이블을 채워나가고 있다. 이렇게 하면 반복되는 문제를 수행하지 않아도 된다. 표를 채워나가는 방식이라고 해서 Tabulation이라고 한다.

보통 Memoization은 재귀를 기반으로 하고 Tabulation은 반복문을 기반으로 한다.

7. Tabulation을 이용한 피보나치 수열 문제 풀이

문제

n번째 피보나치 수를 찾아주는 함수 fib_tab을 작성하라. fib_tab은 tabulation방식으로 구현해야 한다.

def fib_tab(n):
    # 코드를 작성하세요.

# 테스트
print(fib_tab(10))
print(fib_tab(56))
print(fib_tab(132))

# 콘솔 출력
55
225851433717
1725375039079340637797070384

풀이

6장의 설명을 참고하자.

코드

def fib_tab(n):
    # base case에 해당하는 항은 채워놓는다.
    table = [0, 1, 1] 
    
    # n번째 피보나치 수까지 값을 채운다.
    for i in range(3, n+1):
        table.append(table[i-1] + table[i-2]) # 

    return table[n]
           
# 테스트
print(fib_tab(10))
print(fib_tab(56))
print(fib_tab(132))

# 콘솔 출력
55
225851433717
1725375039079340637797070384