DP(Dynamic Programming), 동적계획법

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

- 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.

- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

- 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(하향식(Top Down), 상향식(Bottom up))으로 구성된다.

 

    * 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란?

- 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법' 을    의미한다.       

- 반면, 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어이다.

 

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

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

- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

2. 중복되는 부분 문제(Overlapping Subproblem)

-  동일한 작은 문제를 반복적으로 해결해야 한다.

 

다이나믹 프로그래밍으로 효과적으로 해결할 수 있는 대표적인 문제에는 피보나치 수열이 있다.

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

실행결과
>> 3

 

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

- 단순 재귀함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 된다.

- 다음과 같이 f(2)가 여러 번 호출 되는 것을 확인할 수 있다.(중복의 문제)

빅오 표기법( O(2 ** N) ) 을 기준으로 f(30)을 계산하기 위해 약 10억가량의 연산을 수행해야 한다. 이것은 동일한 작은 문제를 반복적으로 수행해야하기 때문인데, 이 점은 다이나믹 프로그래밍의 사용 조건을 만족한다.

 

---

Top Down 방식의 다이나믹 프로그래밍

- 메모이제이션(Memoization)

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

   - 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.

   - 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고 한다.

 

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

# 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
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))

실행 결과
>> 218922995834555169026

 

 

Bottom Up 방식의 다이나믹 프로그래밍

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

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
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])

실행결과
>> 218922995834555169026

 

---

이처럼 이미 계산된 결과를 활용하면 다음과 같이 색칠된 노드만 처리할 것을 기대할 수 있다.

 

참고

나동빈님의 유툽!

https://www.youtube.com/c/dongbinna/videos