Dynammic Programming

연산속도, 메모리 공간을 최대로 활용할 수 있게끔 하는 알고리즘이 있다. 특히, 다이나믹 프로그래밍은 메모리 공간을 약간 더 사용해 값을 저장해두는 것으로 연산속도를 비약적으로 증가하는 알고리즘이다. 2가지 방법으로 구현 가능하다. 각각 Top down(재귀함수) Bottom up(반복문)을 사용한 방법이다. 원래, 프로그래밍에서 다이나믹은 "실행도중에"라는 의미를 가지고 있다. 특히 다이나믹 할당 (동적할당)은 프로그램 실행 중 필요한 메모리를 할당하는 기법을 의미한다. 하지만! dynammic programming은 전혀 다른 의미라는 것을 명심하자.

Dynammic Programming을 위한 조건

• 큰 문제를 작은 문제로 나눌 수 있어야 한다.
• 큰 문제의 정답을 구하는 과정이 작게 나눈 문제의 정답을 구하는 과정과 동일해야한다.

피보나치 수열과 Dynammic Programming

피보나치 수열은, Dynammic programming을 적용하기 가장 적합한 예시이다. 피보나치 수열은, 이전 두 항의 합이 현재의 항 값이 되는 수열이다. 이를 점화식으로 간결하게 표현할 수 있다.

$a_1$ 과 $a_2$의 값이 1이라고 한다면 아래와 같은 수열이 만들어진다.

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)
    
print(fibo(6))

위는 python으로 $a_1$ 과 $a_2$의 값이 1인 피보나치 수열의 6번째 항의 값을 출력하는 과정이다.
해당 재귀함수 코드의 호출과정은 아래와 같이 이루어진다.

동일한 함수가 여러번 호출되는것을 알 수 있다. fibo(n)에서 n이 커질수록 반복해서 호출하는 수가 많아진다. 이는 $O(2^N)$의 지수 시간이 소요된다고 표현한다. N이 30만 되어도 10억 가량의 연산을 수행해야한다. 이처럼 반복해서 호출되는 함수를 다이나믹 프로그래밍을 사용해 효율적으로 해결하는 것이다.

메모이제이션(Memoization)기법을 사용해서 해결할 수 있다. 이는 Dynammic Programming 기법 중 하나이다. 한번 구한 결과를 특정 메모리 공간에 저장해두고 다시 그 함수가 호출될 경우 저장했던 결과를 그대로 가져오는 것이다. 우리가 흔히 아는 캐싱이다. (캐싱은 자주 사용되는 데이터를 복사하여 가까운 경로에 따로 저장해두는 것이다)

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

빨간색으로 x쳐둔 함수호출은 1을 반환하고 끝나거나 아니면 따로 저장해둔 리스트에서 값을 가오기 때문에 사실상 호출되지 않는다고 이해하자.

Dynammic Programming과 분할정복

결론적으로, Dynammic Programming은 쿤문제를 작게 나누고, 같은 문제면 한 번씩만 풀어서 문제를 효율적으로 해결하는 알고리즘이다. 퀵정렬(분할정복)에서도 큰 문제를 작게 나눈다. 하지만, 둘에는 큰 차이가 있다. Dynammic Programming은 문제들이 서로 영향을 미친다는 것이다.

퀵정렬의 경우, 한 기준 원소가 자리를 잡게 되면 위치가 바뀌지않는다. 또한, pivot을 다시 처리하지 않는다. 하지만, Dynammic Programming은 한 번 해결한 문제여도 다시 해결한다. 작게 분할한 특정 부분의 문제에 대한 답을 내놓고, 이미 답이 나왔으니 다시 해결할 필요가 없다고 반환한다.

Top-down , Bottom-up

두 방법 모두 Dynammic Programming을 통해서 문제를 해결하는 방법이다. 각각 Top-down은 재귀함수를, Bottom-up은 반복문을 활용한다. 재귀함수는 재귀함수의 스택 크기가 제한적일 가능성이 있고, 컴퓨터 시스템에서 함수를 다시 호출했 때 메모리 상에 적재되는 일련의 과정을 따라야 하기 때문에 오버헤드가 발생할 수 있다. 따라서, 재귀함수보단 반복문을 사용한 Bottom-up 방식을 사용하면 더 성능이 좋게 구현할 수 있다. Top down 방식은 큰 문제 해결을 위해 작은것을 호출해나가는 방식이고, Bottom up 방식은 작은 문제부터 차근차근 해결해나가면서 답을 구하는 방식이다. 위에서 구현한 fibo 재귀함수와 다르게 아래는 반복문을 사용한 방법이다

d=[0]*100
d[1]=1
d[2]=1
n=99
for i in range(3,n+1):
	d[i]=d[i-1]+d[i-2]
    
print(d[n])

Bottom-up 방식은 결과값을 따로 저장해두는 메모이제이션(Memoization)기법을 사용할 필요가 없다.

먼저 완전탐색을 하는 방향으로 탐색 알고리즘을 구현한다. 만약 코드 자체의 동작시간이 오래걸리면, DP를 적용할 수 있는지 앞서 설명한 두 기준으로 확인하고, Top-down 혹은 Bottom-up 방식으로 구현하는 것이 효율적으로 문제를 해결할 수 있다.

Reference

이것이 취업을 위한 코딩 테스트다 with 파이썬