동적 프로그래밍 (Dynamic Programming)

동적 프로그래밍(Dynamic Programming)은 복잡한 문제를 간단한 하위 문제로 분할하여 해결하는 알고리즘 설계 기법이다. 이러한 기법은 하위 문제의 해결 방법을 저장하고 재활용하여 중복 계산을 피하며 효율적인 해결책을 찾아낸다. 동적 프로그래밍은 최적 부분 구조(Optimal Substructure)와 중복 부분 문제(Overlapping Subproblems)라는 두 가지 특성을 갖고 있다. 최적 부분 구조는 주어진 문제의 최적 해결책이 하위 문제의 최적 해결책들로부터 구성될 수 있다는 것을 의미하며, 중복 부분 문제는 작은 하위 문제들 사이에 중복되는 계산이 존재한다는 것을 의미한다.

Baekjoon - Dynamic Programming

동적 프로그래밍은 다음과 같이 두가지 방법이 있다.

---

Memoization

Memoization은 Top-down(하향식) 방식으로 동작한다. 재귀적인 방식을 사용하여 문제를 작은 하위 문제로 분할하고, 메모 배열에 결과 값을 저장하여 중복 계산을 피한다.

# Top-Down
dpList = [[False, 0]] * 11
dpList[0] = [True, 0]
dpList[1] = [True, 1]

def memoization(n, dpList):
    if dpList[n][0] == False:
        dpList[n] = [True, memoization(n-1, dpList) + memoization(n-2, dpList)]
    return dpList[n][1]
    
result = memoization(10, dpList) # 55

---

Tabulation

Tabulation은 Bottom-up(상향식) 방식으로 동작한다. 반복문을 사용하여 작은 하위 문제부터 시작하여 큰 문제를 해결한다.

# Bottom-up
def tabulation(n):
    dpList = [0, 1]
    for i in range(2,n+1):
        dpList.append(dpList[i-1] + dpList[i-2])
    return dpList[n]
    
result = tabulation(10) # 55