[Algorithm] 다이나믹 프로그래밍

1. 다이나믹 프로그래밍이란? 

메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이다.  

이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

구현은 일반적으로 탑다운, 보텀업 이 두가지 방식으로 구성된다.

주의) 자료구조에서 dynamic allocation(동적 할당)과 무관한 의미로 사용됨.

 

어떤 경우 필요할까?

가장 대표적인 예시로 피보나치 수열이 있다. 

 

피보나치 수열의 점화식은 아래와 같다. 

 

n번째 피보나치 수는 (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수이며, 1번째와 2번째 피보나치수는 1임을 뜻한다.

 

n번째 피보나치 수를 f(n)이라고 할 때 4번째 피보나치 수 f(4)를 구하는 과정은 다음과 같다.

 

코드 구현)

 

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

print(fibo(4))

 

 

위 방식의 코드는 쉽지만, 심각한 문제점이 있다. f(n) 함수에서 n이 커지면 커질수록 수행시간이 기하급수적으로 늘어난다.

O(2^n)의 지수 시간이 소요되는데 n=30이면 약 10억 가량의 연산을 수행해야한다.

 

f(6)일때의 호출 과정만 봐도 f(3)의 함수가 3번이나 반복되어 호출되는 것을 확인할 수 있다. (f(100)을 호출하려면 연산횟수는 약 1,000,000,000,000,000,000,000,000,000,000번이다. )

 

이럴 때 다이나믹 프로그래밍을 사용하면 효과적이다 ! 

 

2. 다이나믹 프로그래밍의 조건 및 구현

다이나믹 프로그램을 사용하기 위해서는 두가지 조건을 만족해야한다.

1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있다.

2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결한다. 

 

피보나치 수열을 다이나믹 프로그램을 사용해서 해결해보자.

메모제이션 방법을 사용하면 용이한데, 메모제이션이란 구현 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 말하며, 다이나믹 프로그래밍을 구현하는 방법 중 하나이다.

 

 

메모제이션을 이용한 피보나치 구현 

1. top down 방식 (= 하향식)

 

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))

 

이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍을 구현하는것을 큰 문제를 해결하기 위해 작은 문제를 호출한다고하여 top-down 방식이라고한다. 

f(1)을 구한 다음 그 값이 f(2)를 푸는데 사용되고, f(2)의 값이 f(3)을 푸는데 사용되므로 시간 복잡도는 O(N)이 된다. 

 

2. bottom up 방식 (=상향식)

 

d = [0] * 100

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

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

print(d[i])

 

이처럼 반복문을 사용하여 작은 문제부터 차근 차근 답을 도출하는 방식을 보텀업 방식이라고한다. 

* 보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 불리며, 메모제이션은 탑다운 방식에 국한되는 개념이다.

* 메모제이션은 이전에 계산된 결과를 일시적으로 기록해놓은 넓은 개념을 의미하므로, 다이나믹 프로그래밍과 별도의 개념이다. 한번 계산된 결과를 어딘가에 담아두고 (메모제이션) 다이나믹 프로그래밍을 위해 사용하지 않을 수도 있음. 

* top down 보다 bottom up이 더 효과적임.

 

 

+ 코테에서 그렇게 어렵지 않은 난이도로 출제된다고함. 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면, 중복 여부를 확인하여  다이나믹 프로그래밍을 적용할 수 있는지 체크해보자. 

 

참고) 이것이 코딩테스트다.