다이나믹 프로그래밍
컴퓨터를 사용한 문제 해결에 있어서, 일반적으로 효율적인 설계라 함은 연산속도나 메모리 공간을 줄여나가는 것이다. 그러나 본 장에서 배울 다이나믹 프로그램과 같이, 조금의 메모리 공간을 더 할애하여 비약적인 성능을 끌어낼 수 있는 경우도 존재한다. 이를 동적 계획법이라고도 부르며, 프로그래밍에서 사용되는 동적 할당의 의미와는 다르다는 것을 인지할 필요가 있다.
다이나믹 프로그래밍의 대표적인 유형으로는 피보나치 수열이 존재한다. 이전 두 항의 합을 현재 항으로 설정하는 특징을 갖는 수열이다.
수학적인 표현으로 점화식을 사용하지만, 프로그래밍에서는 배열이나 리스트를 사용한다. 파이썬에서는 리스트를 사용한다. 이를 구현하기 위해서는 재귀 함수를 사용하면 된다.
재귀 함수를 이용한 피보나치 수열 구현
def fibo(x):
if x==1 or x==2:
return 1
return fibo(x-1)+fibo(x-2)
print(fibo(4))그러나 이와 같이 코드를 구성하면 연산량 측면에서 굉장히 비효율적이다. O(2**n)의 지수 시간이 소요되는 해당 수식에서, n=30만 되어도 10억 번의 연산을 수행하여야 한다. 같은 함수라도 필요할 때 마다 새롭게 구하기 때문에 굉장히 비효율적인 연산이 이루어지는 것을 알 수 있다. 그럼 이제 다이나믹 프로그래밍을 이용해보자.
다이나믹 프로그램은 해당 조건을 만족하는 경우 사용할 수 있다.
1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있다.
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]
print(fibo(99))
보텀업 방식을 통해서도 피보나치 수열을 구현할 수 있다. 초기 다이나믹 리스트의 값을 지정해준 후 (ex. d[1] =1, d[2] =2) 반복문을 통해 원하는 번째의 수 n만큼 돌려 결과를 도출해낸다.
정리하자면 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 한 번 구한 값은 저장해놓고 필요할 때 꺼내써 계산 측면에서 효율을 꾀하는 방법의 알고리즘이다. 이를 통해 상수 시간의 시간 복잡도를 갖는 문제로 연산량이 훨씬 줄어들게 된다.
여기서 말하는 큰 문제를 작게 나눈다는 것은 무슨 뜻일까? 퀵 정렬에서도 배운 적이 있는데, 정렬 과성에서 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 하는 분할 정복 알고리즘과 유사하다. 차이점이 있다면 '부분 문제의 중복' 여부이다. DP에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복되지만, 퀵 정렬에서의 분할 정복 알고리즘은 특정 위치에 한 번 자리를 잡게 되면 그 기준 원소의 위치는 바뀌지 않게 된다. 다시 처리하는 부분 문제를 호출하지 않는 것이다.
탑다운 방식과 보텀업 방식
다이나믹 프로그래밍은 재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 탑다운 방식과, 단순 반복문을 이용해 작은 문제부터 순차적으로 답을 도출하는 보텀업 방식으로 나눌 수 있다.
보텀업 방식을 이용한 다이나믹 프로그래밍이 일반적이며, 메모이제이션은 탑다운 방식에 국한되어 사용한다. 정확히 말하면 메모이제이션이라는 넓은 개념에 탑다운을 이용한 다이나믹 프로그래밍 방식이 포함되는 것이다.
실전에서의 문제 해결
당연하게도 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이다.
일단 재귀 함수를 통해 비효율적인 완전 탐색 프로그램을 작성한 뒤에, 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 확인할 필요가 있다.
참고
이것이 코딩테스트다 (나동빈 저)
