[WEEK04] 동적 프로그래밍

동적 프로그래밍

동적 프로그래밍

동적 프로그래밍은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. 부분 문제 반복(Overlapping subproblems)과 최적 부분 구조(Optimal substructure)를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 다이나믹 프로그래밍은 크게 상향식 방식의 메모이제이션(Memoization)과 하향식 방법의 바텀 업(Bottom-Up) 방식이 있다.

※ 일반적인 프로그래밍 분야에서 동적(Dynamic)의 의미는?

• 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다.

• 반면에 DP에서 Dynamic은 별다른 의미가 없다. 알고리즘을 만든 사람도 멋있다는 이유로 Dynamic이란 단어를 프로그래밍에 결합했다.

메모이제이션(Memoization)

기억되어야 할 것이라는 뜻의 라틴어에서 파생된 단어로, 컴퓨터 프로그램이 동일한 계산을 반복적으로 해야 할 때, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 전체적인 실행 속도를 빠르게 해주는 기법으로 동적 계획법(DP)의 핵심이 되는 기술이다.

메모이제이션 기법을 사용한 피보나치수열 알고리즘

import sys
n = int(sys.stdin.readline())
dp = [0] * (n+1)

def fibo(x):
    if x == 1 or x == 2:
        return 1
    if dp[x] != 0:
        return d[x]
    dp[x] = fibo(x -1) + fibo(x -2)
    return dp[x]

print(fibo(n))

바텀 업(Bottom-Up)

바텀 업은 가장 작은 문제들로부터 답을 구해가며 전체 문제의 답을 찾는 방식이다. 상향식이라고도 불린다. 재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있는 장점이 있다.

바텀 업 기법을 사용한 피보나치수열 알고리즘

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

d[0] = 1 # a_1 = 1
d[1] = 1 # a_2 = 1

# 바텀 업 방식: 반복문 활용
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

n = 99
print("fibo({}): {}".format(n, fibo(n)))

동적 프로그래밍 백준 문제 Github 링크
백준 동적 프로그래밍 관련 문제