다이나믹 프로그래밍

송현준·2022년 12월 1일

알고리즘 자료구조 책정리

알고리즘, 자료구조

목록 보기

8/12

다이나믹 프로그래밍

한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘
메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법
동적 계획법이라고 표현하기도 한다.

피보나치 수열

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시이다.
피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다.

점화식 표현

수열 { $a_n$ }이 있을 때 수열에서 각 항을 $a_n$ 이라고 부른다고 가정하면 다음과 같이 표현할 수 있다.
$a_{n+2} = f(a_{n+1}, a_n) = a_{n+1} + a_n$
좀 더 기본 예시 1, 2, 3, ... 과 같이 이어지는 등차수열의 점화식
$a_{n+1} = f(a_n) = a_n + 1$
결과적으로 앞서 언급했던 피보나치 수열에서는 첫 번째 항과 두 번째 항의 값이 모두 1이기 때문에 최종적으로 피보나치 수열을 나타낼 때에는 다음과 같이 정의할 수 있다.
$a_n = a_{n-1} + a_{n-2}$ , $a_1 = 1$ , $a_2 = 1$
- n번째 피보나치 수 = (n - 1)번째 피보나치 수 + (n - 2)번째 피보나치 수
- 단 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1
피보나치 함수 소스코드
```
# 피보나치 함수(Fibonacci Function)를 재귀 함수로 구현
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)$ 의 지수 시간이 소요한다.

단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다. 이러한 문제를 다이나믹 프로그래밍으로 사용하면 효율적으로 해결할 수 있다.

다이나믹 프로그래밍 조건

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

피보나치 수열은 이러한 조건을 만족하는 대표 문제이다.

다이나믹 프로그래밍 구현

메모이제이션(Memoization) 기법

한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을의미
값을 저장하는 방법이므로 캐싱(caching)이라고 한다.

피보나치 수열 소스코드(재귀적)

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x) :
	# 종료 조건(1 혹은 2일 때 1을 반환)
	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))

정리

다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만풀어 문제를 효율적으로 해결하는 알고리즘 기법
다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.
한 번 해결했던 문제를 다시금 해결한다는 특징 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결이 됐던 것이니까 다시 해결할 필요가 없다고 반환하는 것이다.

다이나믹 프로그래밍은 시간복잡도 $O(N)$
왜냐하면 f(1)을 구한 다음 그 값이 f(2)를 푸는 데 사용되고, f(2)의 값이 f(3)를 푸는 데 사용되는 방식으로 이어지기 때문이다.

# 시간복잡도가 O(N)이라는 것을 확인

d = [0] * 100

def fibo(x) :
    print('f(' + str(x) + ')', end=' ')
    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]

fibo(6)

f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4)

이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해경하기 위해 작은 문제를 호출한다고 하여 탐다운(Top-Down) 방식이라고 한다.

반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 바텀업(Bottom-Up)방식이라고 한다.

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피봐치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수 반복문으로 구현
for i in range93, n + 1) :
	d[i] = d[i-1] + d[i-2]

print(d[n])

다이나믹 프로그래밍 문제 푸는 법

주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는것이다.
특정한 문제를 완전 탐색 알고리즘으로 접근했을 떄 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인한다.
일단 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 (탑다운) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선한다.
또한 가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 바텀업 방식으로 구현하는 것을 권장한다. 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문이다.