DP

중복되는 연산을 줄이자

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

다이나믹 프로그래밍 기법은 메모리 공간을 약간 더 사용하는 대신 연산 속도를 비약적으로 증가시킬 수 있는 장점을 취하는 방법이다. 동적 계획법이라 불리는 이것은 TopDown과 BottomUP 2가지 방식이 있다.

피보나치 수열

피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다.

n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
단, 1번째와 2번째 피보나치 수는 1

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가 여러 번 호출되는 것을 확인할 수 있다.
f(n)에서 n이 커지면 커질수록 반복해서 호출하는 수가 많아진다.

이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다. 이러한 문제는 바로 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다.

다만 다이나믹 프로그래밍을 사용하려면 아래의 조건이 만족해야 한다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

메모이제이션

메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.
메모이제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다.

TopDown 방식 : 큰 문제를 해결하기 위해 작은 문제 호출

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
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))

d라는 배열에 어떤 값을 담을 지 잘 결정해야한다!!!

다이나믹 프로그래밍을 적용했을 때의 피보나치 수열 알고리즘의 시간 복잡도는 O(N)이다.
왜냐하면 f(1)을 구한 다음 그 값이 f(2)를 푸는 데 사요오디고, f(2)의 값이 f(3)을 푸는 데 사용되는 방식으로 이어지기 때문이다.
한 번 구한 결과는 다시 구해지지 않는다.

정리하자면 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

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

사실 큰 문제를 작게 나누는 방법은 퀵 정렬에서도 소개된 적 있다.
퀵 정렬을 정렬을 수행할 때 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 한다.
이는 분할 정복 알고리즘으로 분류된다.
다이나믹 프로그래밍과 분할 정복의 차이는점은, 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.

BottomUp 방식 : 단순히 반복문을 활용하여, 작은 문제부터 차근차근 답 도출

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

다이나믹 프로그래밍의 전형적인 형태는 BottomUp 방식이다. 이 방식에서 사용되는 결과 저장용 리스트는 'DP table' 이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다. 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념이다. 한 번 계산된 결과를 어딘가에 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.

가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 바텀업 방식으로 구현하는 것을 권장한다.
시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다.

참고

해당 블로그는 나동빈님의 '이것이 취업을 위한 코딩 테스트다. with 파이썬' 교재와 유튜브 강의를 참고하여 작성되었습니다.