[Algorithm] 다이나믹 프로그래밍 (동적 계획법)

Posted: 2023.05.11 Updated: 2023.05.11

다이나믹 프로그래밍

동적 계획법이라고도 부른다.
일반적으로 동적(Dynamic)이란 자료구조의 동적 할당(Dynamic Allocation)처럼 의미를 가지고 쓰인다. (동적 할당: 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법)
반면 다이나믹 프로그래밍에서 Dynamic 은 별 다른 의미 없이 사용되었다.

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.
이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
한 번 해결한 문제는 다시 해결하지 않음으로써 완전 탐색보다 시간 복잡도를 획기적으로 줄일 수 있다.

일반적으로 탑다운(하향식)과 보텀업 두 가지 방식으로 구성된다.

사용 조건

최적 부분 구조 (Optional Substructure)

큰 문제를 작은 문제로 나눌 수 있으며 작은 문제을 모아서 큰 문제를 해결할 수 있다.

중복되는 부분 문제 (Overlapping Subproblem)

동일한 작은 문제를 반복적으로 해결해야 한다.

메모이제이션 (Memoization)

다이나믹 프로그래밍을 구현하는 방법 중 하나이다.
한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.
같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
값을 기록해 놓는다는 점에서 캐싱(Cashing)이라고도 한다.

엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념이다.
즉, 다이나믹 프로그래밍에만 국한된 개념은 아니다.
다이나믹 프로그래밍을 구현할 때 하향식 방법으로 접근하여 이미 계산된 결과를 기록하고자 하면 메모이제이션을 사용하면 된다.

메모이제이션 방식은 탑다운 방식이며, 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.

피보나치 수열

다이나믹 프로그래밍을 활용하여 해결할 수 있는 대표적인 문제이다.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

각 항의 값은 앞에 있는 두 수의 합이다.
점화식(인접한 항들 사이의 관계식)을 통해 수학적으로 표현할 수 있다.

단순 재귀 소스코드

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지며 중복되는 부분 문제가 생긴다.

이러한 문제를 해결하기 위해 다이나믹 프로그래밍을 적용시킬 수 있는지 확인한다.
피보나치 수열은 큰 문제를 작은 문제로 나눌 수 있으며, 이 작은 문제가 반복적으로 해결되어야 하므로 다이나믹 프로그래밍을 사용할 수 있다.

탑다운 소스코드

d = [0] * 100

def fibo(x):
    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]

메모이제이션을 이용하는 경우 시간 복잡도는 $O(N)$ 이다.

보텀업 방식 소스코드

d = [0] * 100

d[1] = 1
d[2] = 2
n = 99

for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

보텀업 방식에서는 재귀함수를 사용하지 않기 때문에 초기값을 직접 초기화한다.

다이나믹 프로그래밍 VS 분할 정복

다이나믹 프로그래밍과 분할 정복은 모두 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 최적 부분 구조를 가질 때 사용할 수 있다.

다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복이다.
다이나믹 프로그래밍에서는 각 부분 문제들이 서로 영향을 미치며 중복된다.
그러나 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.
분할 정복의 예시인 퀵 정렬에서, 기준 원소(Pivot)이 한 번 자리가 변경되어 위치가 잡히면 그 기준 원소의 위치는 바뀌지 않고, 분할 이후 해당 기준 원소를 다시 처리하는 부분 문제를 호출하지 않게 된다.

퀵 정렬

다이나믹 프로그래밍 문제에 접근하는 방법

주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요하다.
문제를 해결하기 위해 어떤 알고리즘을 사용할 수 있는지 먼저 고민해보아야 한다.

가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토한다.
너무 많은 시간 복잡도가 소요되거나, 다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려한다.

일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성하고, (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선한다.

일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다.

Better Jeong