[Algorithm] 다이나믹 프로그래밍 (Dynamic Programming)

현실 세계에는 컴퓨터를 활용하더라도 최적의 해를 구하기에 시간이나 메모리 공간이 매우 많이 필요한 문제가 있습니다. 따라서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 합니다.

어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 향상시킬 수 있는 방법이 있습니다. 그 중 하나가 바로 다이나믹 프로그래밍(Dynamic Programming)입니다.

 

다이나믹 프로그래밍은 동적 계획법이라고도 불리며, 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. 다이나믹 프로그래밍의 구현은 일반적으로 탑다운(Top-Down)과 보텀엄(Bottom-Up) 2가지 방식이 있습니다.

 

다이나믹 프로그래밍은 다음의 조건을 만족하는 문제를 해결할 때 사용할 수 있습니다.

1. 최적 부분 구조

  - 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있을 때

2. 중복되는 부분 문제

  - 동일한 작은 문제를 반복적으로 해결할 수 있을 때

 

예를 들어 피보나치 수열 문제의 경우, 시간 복잡도는 다음과 같습니다.

피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있기 때문에, 연산량이 굉장히 큽니다.

피보나치 수열은 위 조건을 만족하기 때문에 다이나믹 프로그래밍을 사용할 수 있습니다.

 

다이나믹 프로그래밍 방식 중 탑다운 방식은 메모이제이션(Memoization)입니다.

탑다운 방식은 쉽게 말하면, 재귀 함수를 이용하여 계산된 결과를 기록하는 방법입니다.

보텀업 방식은 반복문을 이용한 방법입니다.

다이나믹 프로그래밍은 코드를 보면서 이해하는 것이 더 쉬울 것 같습니다.

아래는 탑다운 방식을 이용한 피보나치 수열의 특정 항을 구하는 방법입니다.

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]


print(fibo(99))	#218922995834555169026

아래는 보텀업 방식을 이용한 피보나치 수열의 특정 항을 구하는 방법입니다.

d = [0] * 100

def fibo(x):
    d[1] = 1
    d[2] = 1

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

    return d[x]

print(fibo(99)) #218922995834555169026

보통 다이나믹 프로그래밍은 반복문을 이용한 보텀업 방식을 많이 사용합니다.

코드를 보면 n이 주어질 때마다 처음부터 계산하는 것이아니라 단순히 이전에 계산했던 결과를 저장해두고 사용한것이 전부입니다.

 

코딩테스트에서 주어진 문제가 다이나믹 프로그래밍 유형인지 파악하는 것이 가장 중요한데, 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토하고 만약 해결할 수 없다면 다이나믹 프로그래밍을 고려하는 것이 좋은 방법이 될 수 있습니다.

 

또한 코딩테스트에서 다이나믹 프로그래밍은 기본 유형으로 출제될 경우가 많기때문에(점화식을 생각하는 시간이 오래 걸리기 때문) 기본 유형을 집중적으로 연습하는 것이 좋습니다.

 

관련된 문제 '개미 전사'를 다이나믹 프로그래밍으로 풀어보겠습니다.

<문제>

 

<해설>

 

<구현>

n = 4
array = [1, 3, 1, 5]

d = [0] * 100

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

print(d[n - 1])

 

참고: https://www.youtube.com/watch?v=5Lu34WIx2Us&t=1353s