[항해 99 코테 챌린지] 다이나믹 프로그래밍

다이나믹 프로그래밍(Dynamic Programming)이란?

복잡한 문제를 작은 하위 문제로 나누어 해결한 결과를 저장(memoization)하고 이를 재활용하여 효율적으로 문제를 해결하는 알고리즘 설계 기법이다.

Memoization

메모이제이션(Memoization)은 계산 결과를 저장해 중복 계산을 방지하는 기법이며, 다이내믹 프로그래밍에서 자주 사용된다. 주로 탑다운 방식에서 사용된다.

(바텀업에서 사용되는건 테이블이라 하는데 내가 보기엔 비슷...)

 

탑다운(Top-Down) 과 바텀업(Bottom-Up)

탑다운

상위 문제에서 하위 문제를 뽑아내어 해결하는 방식이며, 3 = 1 + 2 와 같이 문제 해결의 주안점을 위에서 아래로 쳐다보는 식으로 둔다.

재귀를 통해 문제를 해결하며, 기존에 미리 계산한 결과를 재사용하는 메모이제이션 기법을 사용해 수행 시간 및 횟수를 줄일 수 있다.

바텀업

작은 문제부터 순서대로 계산해 큰 문제를 해결하는 방식이며, 1 + 2 = 3 와 같이 문제 해결의 주안점을 아래서 위로 쳐다보는 식으로 둔다. 반복문을 통해 문제 해결을 한다. 테이블을 통해 현재 계산한 값을 저장해 놓을 수 있다. 

피보나치 수열

각 숫자가 앞의 두 숫자의 합으로 이루어진 수열이다. 

 

• 첫 번째 수: 0
• 두 번째 수: 1
• 이후: F(n)=F(n−1)+F(n−2)

 

백준 1003 번 문제에서 풀어볼 수 있다.

 

일반 재귀로 사용하게 되면 예를 들어 아래와 같은 상황일때 중복으로 함수를 실행하는 구간이 있어서(같은숫자) 최적화가 필요해 바텀업 방식을 쓰거나, 메모이제이션을 가미해야 한다.

 

1003 번 문제 코드풀이

# 탑다운
import sys
input = sys.stdin.readline
N = int(input())
count = [0,0];
dp = [0 for i in range(41)];
def fibo(n):
    if(dp[n]): return dp[n];
    if(n == 0):
        dp[n] = [0, 1, 0];
        return dp[n]
    elif(n == 1):
        dp[n] = [1, 0, 1];
        return dp[n]
    else:
        f1 = fibo(n - 1) 
        f2 = fibo(n - 2)
        dp[n] = [f1[0] + f2[0], f1[1] + f2[1], f1[2] + f2[2]]
        return dp[n]
for _ in range(N):
    M = int(input())
    ret = fibo(M)
    print(f'{ret[1]} {ret[2]}')

# 바텀업
import sys
input = sys.stdin.readline
N = int(input())
dp = [[0,0,0] for i in range(41)];
def fibo2(n):
    cnt = 0
    while(cnt <= n):
        if(cnt == 0):
            dp[cnt] = [0, 1, 0];
        elif(cnt == 1):
            dp[cnt] = [1, 0, 1];
        else:
            f1 = dp[cnt - 1]
            f2 = dp[cnt - 2]
            dp[cnt] = [f1[0] + f2[0], f1[1] + f2[1], f1[2] + f2[2]]
        cnt += 1
    return dp[n]

for _ in range(N):
    M = int(input())
    ret = fibo2(M)
    sys.stdout.write(f'{ret[1]} {ret[2]}\n')