[이코테] chap8. 다이나믹 프로그래밍

최적의 해를 구하기에 시간이 너무 많이 걸리거나 메모리 공간이 많이 필요한 문제가 있다.
이는 컴퓨터의 연산 속도, 메모리 공간에 대한 제약이 걸려 효율적인 알고리즘이 필요하다.

다만, 이런 문제들 중에서도 메모리 공간을 약간 더 사용하여, 속도를 비약적으로 높이는 방법이 있는데 이 중 대표적인 방법이 다이나믹 프로그래밍(Dynamic Programming)기법(동적 계획법)이다.

다이나믹 프로그래밍이란?

한번 해결된 부분 문제의 정답을 메모리에 기록하여, 한번 계산한 답은 다시 계산하지 않도록 하는 문제 해결법 이다.

다이나믹 프로그래밍은 *점화식을 그대로 코드로 옮겨 구현할 수 있다.
(점화식: 인접한 항들 사이의 관계식)

대표적인 예시 문제가 피보나치 수열 문제이다.

피보나치 함수 코드

# 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

print(fibo(7))

위 사진만 보더라도 n이 커질수록 수행 시간이 기하급수적으로 늘어난다.
빅오 표기법으로는 $O(2^N)$의 지수 시간이 소요된다고 한다.

이를 해결하기 위해 보면 같은 함수를 계속 불러내는 것을 확인할 수 있다.
사진의 경우 f(4)를 총 3번 부르고 있다. 즉, f(n)에서 n이 커질수록 반복해서 호출하는 수가 많아진다. 

그러므로 이런 문제는 반복 계산을 줄여주는 다이나믹 프로그래밍을 사용하면 효율적이다.

다이나믹 프로그래밍은 다음 조건을 만족해야 사용 가능하다.
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 

피보나치 수열은 위 2개의 조건을 만족하므로, 이 문제를 *메모이제이션(Memorizations)기법을 사용해 해결해보자.
(*메모이제이션: DP를 구현하는 방법 중 한 종류.
이전에 계산된 결과를 일시적으로 기록해 값을 저장하는 방법, 캐싱(caching)이라고도 한다. 한번 구한 정보를 리스트에 저장하는 것.)

구현 방법 2가지

1. 재귀 함수를 이용한, 탑다운(Top-Down) 방식 (하향식)
2. 단순 반복문을 이용한, 보텀업(Bottom-Up) 방식 (상향식)

보통 재귀함수의 오버헤드를 줄이기 위해 보텀업 방식으로 구현하는 것을 권장한다.

Top-Down 방식

재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식.

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건(1 혹은 2일 때 1을 반환)
    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]

print(fibo(99))

Bottom-Up 방식

단순히 반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식.

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

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

추가 특징

• bottom-up 방식에서 사용되는 결과 저장용 리스트를 'DP 테이블'이라 부른다.
• 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.
  • memoization(top-down)과 dp table(bottom-up) 의 차이
    • memoization에 해당하는 dp[] 배열은 단순한 캐시 값 저장을 의미한다(어디서든 불려지는 값에 대한 캐시)
    • dp table에 해당하는 dp[]는 작은 원소부터 시작하여 큰 원소의 값을 구하기 위해 사용되는 것을 의미한다
• 탑다운 방식인 재귀는 실제로 큰 수가 들어오면 recursion depth 관련 오류가 발생할 수 있다. -> sys 라이브러리의 setrecursionlimit()함수로 재귀 제한 완화가 가능하다는 것을 알아놓자.

후기

• 코테에서의 DP문제는 대체로 간단히 나오므로 책의 수준까지 풀어도 괜찮다.
• 문제 푸는 첫 단계는 주어진 문제가 DP임을 알아차리는게 중요하다.
  하지만 이는 쉽지 않으므로,
  특정한 문제를 완전 탐색 알고리즘으로 접근 -> 시간이 매우 오래 걸림
  -> DP 적용 가능한 조건인지 확인(중복 확인) -> 가능하다면 단순히 재귀함수로만 구현한 다음 탑다운 방식을 사용하는 것도 방법임.
  +) 가능하다면 보텀업 방식으로 구현하는 것을 권장한다.