8-1. 다이나믹 프로그래밍

다이나믹 프로그래밍

• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과는 메모리에 저장하여 다시 계산하지 않도록 한다.
• DP의 구현은 탑다운(위에서 아래로), 보텀업(아래서 위로)으로 구성된다.
• 동적 계획법이라고도 한다.

1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결해야 한다.

 

DP 대표문제 (피보나치 수열)

1 1 2 3 5 8 13 21 34 55 ...

이 수열에서 알아낸 항들 사이의 관계식을 점화식이라고 한다.

계산되는 과정을 나타내는 표를 배열이나 리스트로 표현할 수 있다.

점화식으로 표현될 수 있는 구조는 재귀함수를 이용해 프로그램 상에 구현할 수 있다.

def fibo(x):
	if x == 1 or x ==2: # 재귀함수 종료 조건
    	return 1
    return fibo(x-1) + fibo(x-2)
    
print(fibo(4)) # 결과: 3

하지만 중복되는 부분이 많아 지수 시간 복잡도를 가지게 된다.

이 문제는 다이나믹 프로그래밍으로 해결할 수 있다. (위의 두 조건이 맞을 경우)

 

메모이제이션(memoization)

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

• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
• 값을 기록해 놓는다는 점에서 캐싱(caching)이라고도 한다. (→ 변수명: dp, d, cach, memo)

탑다운 방식(메모이제이션)은 하향식이라고도 하고, 보텀업 방식은 상향식이라고도 한다.

다이나믹 프로그래밍의 전형적 형태는 보텀업 방식이다.

메모이제이션은 다이나믹 프로그래밍에 국한된 개념이 아니라, 계산 결과를 일시적으로 기록해놓는 개념을 의미한다.

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

 

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

	다이나믹 프로그래밍	분할 정복 (퀵 정렬)
공통점	최적 부분 구조를 가질 때 사용 가능 (큰 문제를 작은 문제로 나누고, 작은 문제를 모아 큰 문제를 해결할 수 있음)
차이점	각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨	동일 부분 문제가 반복적으로 계산 되지 않음

 

문제 접근 방법

• DP 유형임을 파악하는 것이 중요
• 그리디, 구현, 완전 탐색으로 풀 수 있는지 먼저 검토
• 재귀 함수로 비효율적인 완전 탐색을 한 후에 작은 문제에서 구한 답이 큰 문제에서 사용될 수 있으면 탑다운 방식으로 풀어본다.