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

 

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

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함
• 두가지 방법
  • top-down (하향식)
  • bottom-up (상향식)
• 동적계획법이라고도 부름
  • 동적?
    • (자료구조) 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당
    • (다이나믹 프로그래밍) 별다른 의미 없이 사용된 단어

 

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

(1) 최적 부분 구조 (Optimal Substructure)

• 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제 해결 가능

(2) 중복되는 부분 문제 (Overlapping Sub-problem)

• 동일한 작은 문제를 반복적으로 해결해야함

 

3. 다이나믹 프로그래밍 문제 : 피보나치 수열

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

• 점화식 : 인접한 항들 사이의 관계식
• 피보나치 수열의 점화식
• $$ a_n=a_{n-1}+a_{n-2} , a_1=1, a_2=1 $$
• 프로그래밍에서는 수열(sequence)를 배열이나 리스트를 이용해 표현

예시 : n번째 피보나치 수 f(n)라고 할 때 f(4)를 구하는 과정

 

• 재귀함수를 사용
• f(3), f(2) → f(4)
• f(2),f(1) → f(3)

 

 

 

1) 단순 재귀함수 사용

피보나치 수열 : 단순 재귀 소스코드 (Python)

# 피보나치 함수를 재귀함수로 구현
def fibo(x):
	if x==1 or x==2:
		return 1
	return fibo(x-1) + fibo(x-2)

print(fibo(4))  # 3

단순 재귀 자바 코드

import java.util.*;

public class Main {
	// 피보나치 함수를 재귀함수로 구현
	public static int fibo(int x) {
		if (x==1 || x==2) {
			return 1;
		}
		return fibo(x-1) + fibo(x-2);
	}

	public static void main(String[] args) {
		System.out.println(fibo(4));
	}
}   // 3

피보나치 수열의 시간복잡도 분석

• 단순 재귀 함수로 구현 → 지수 시간 복잡도를 가짐
• f(2)가 여러번 호출(중복되는 부분 문제)
• 시간 복잡도
  • 세타표기법
    • $$ \theta(1.618...^N) $$
  • 빅오 표기법
    • $$ O(2^N) $$
    • 빅오 표기법을 기준으로 f(30)을 계산하기 위해 10억가량의 연산을 수행해야함

2) 다이나믹 프로그래밍 사용

DP 사용 조건 확인

1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있음
2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결

→ 피보나치 수열은 사용조건을 만족

 

메모이제이션(Memoization)

한 번 계산한 결과를 메모리 공간에 메모하는 기법

• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
• 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 함
• 이전에 계산된 결과를 일시적으로 놓는 넓은 개념
  • 다이나믹 프로그래밍에 국한된 개념은 아님
  • 한번 계산된 결과를 담아놓기만 하고 DP를 위해 활용안해도 됨

동작 과정

• 이미 계산된 결과를 메모리에 저장하면 다음과 같이 색칠된 노드만 처리됨

• 실제 호출되는 함수에 대해서만 확인하면 다음과 같이 방문함

 

(메모리제이션) 피보나치 수열 함수의 시간복잡도

$$ O(N) $$

 

호출될 때마다 함수를 출력하는 코드

d = [0]*100

# 피보나치 수열을 재귀함수로 구현(top-down 다이나믹 프로그래밍)
def fibo(x):
	print('f('+str(x)+')', end=' ')
	if x==1 or x==2:
		return 1
	# 이미 계산한 적 있는 문제라면 그대로 반환
	if d[x]!=0:   # DP테이블의 값을 확인
		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)

 

(1) 해결방법1 Top-Down(하향식) : 메모이제이션(Memoization)

• 재귀함수를 사용
• 원리
  • 큰 문제를 해결하기 위해 작은 문제들을 재귀적으로 호출하여 작은 문제가 모두 해결되었을 때 큰 문제의 답도 얻을 수 있음
  • 한번 계산된 결과값을 저장하기위해 메모이제이션 기법을 사용

파이썬 코드

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

# 피보나치 수열을 재귀함수로 구현(top-down 다이나믹 프로그래밍)
def fibo(x):
	# 종료 조건(1 혹은 2일 때 1을 반환)
	if x==1 or x==2:
		return 1
	# 이미 계산한 적 있는 문제라면 그대로 반환
	if d[x]!=0:   # DP테이블의 값을 확인
		return d[x]
	# 아직 계산하지 않는 문제라면 점화식에 따라서 피보나치 결과 반환
	d[x] = fibo(x-1) + fibo(x-2)
	return d[x]

print(fibo(99))

 

(2) 해결방법2 Bottom-Up(상향식)

• 반복문을 사용
• 다이나믹 프로그래밍의 전형적인 형태
• 결과 저장용 리스트 : DP 테이블
• 원리
  • 아래쪽에서부터 작은 문제를 해결해나가면서 먼저 계산했던 문제의 값을 활용하여 다음 문제에 활용

파이썬 코드

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

# 첫번째 피보나치 수와 두번째 피보나치 수는 1 (시작항의 값)
d[1]=1
d[2]=1
n=99

# 피보나치 함수 반복문으로 구현(bottom-up 다이나믹 프로그래밍)
for i in range(3,n+1):
	d[i]=d[i-1]+d[i-2]

print(d[n])

 

4. 다이나믹 프로그래밍 vs 분할 정복

공통점

• 모두 최적 부분 구조를 가질 때 사용할 수 있음
• 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결가능

차이점 : 부분 문제의 중복

• 다이나믹 프로그래밍 : 각 부분 문제들이 서로 영향을 미치며 부분문제가 중복됨
• 분할 정복 : 동일한 부분 문제가 반복적으로 계산되지 않음

예시 : 분할정복(퀵정렬)

• 한 번 기준 원소(Pivot)가 자리르 변경해서 자리를 잡으면 그 기준 원소의 위치는 바뀌지 않음
• 분할 이후 해당 피벗을 다시 처리하는 부분문제는 호출하지 않음

5 7 9 0 3 1 6 2 4 8
분할 완료
1 4 2 0 3 5 6 9 7 8

• 한번 분할완료되면 5는 다시 호출되지 않음

 

---

출처 : https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6