다이나믹 프로그래밍 DP

다이나믹 프로그래밍 = 동적 계획법 = DP

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

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

-다이나믹 프로그래밍의 구현은 일반적으로 탑다운, 바텀업 방식으로 구성된다.

(일반적인 프로그래밍에서의 동적: 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당). 여기서는 다른 의미로 쓰인다.

 

조건

1.최적 부분 구조 (optimal substructure)

-큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답이 모이면 큰 문제를 해결할 수있다.

 

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

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

 

예시

*점화식 : 인접한 항들 사이의 관계식 (⇒ 배열이나 리스트를 이용해 표현)

1.피보나치 수열

-점화식

재귀 구현

def fibo(x):
	if x==1 or x == 2:
		return 1
	return fibo(x-1)+fibo(x-2)

⇒ 시간 복잡도가 엄청 크다.O(2^N) (중복되는 부분 문제가 너무 많다)

⇒ DP 조건을 만족하므로 DP로 해결할 수 있다. (최적 부분 구조, 중복되는 부분 문제)

 

메모이제이션

-한 번 계산된 결과를 메모리 공간에 메모한다.

-캐싱(Caching)이라고도 한다.

탑다운 vs 바텀업

• 탑다운 (하향식 = 메모이제이션 방식)

-재귀적으로 호출하고 작은 문제들이 해결되면 큰 문제를 해결 가능.

• 바텀업 (상향식)

-아래쪽에서 작은 문제를 하나씩 해결해 가면서 먼저 계산했던 문제들의 값을 활용해 다음 문제를 차례대로 해결

-DP 테이블이라고 불림. (파이썬에서는 list)

# 탑다운 방식
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]

⇒ 리스트에 값을 저장해놓고 사용.

# 바텀업 방식
d=[0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1]=1
d[2]=1
n=99 #원하는 값

#바텀업 DP
for i in range(3,n+1):
	d[i]=d[i-1]+d[i-2]

⇒ 작은 문제부터 차례대로 구해나가는 과정.

시간복잡도

O(N)

DP와 분할 정복의 차이점

둘다 최적 부분 구조를 가질 때 사용할 수 있다. (큰 문제를 작은 문제로 나누고 작은 문제의 답이 큰 문제를 해결할 수 있을 경우)

하지만 차이점은 부분 문제의 중복

-DP는 문제들이 서로 영향을 미치며 부분 문제가 중복

-분할 정복은 동일한 부분 문제가 반복적으로 계산 X

⇒ 퀵 정렬에서는 한번 분할이 이루어진 이후 같은 피봇은 다시 처리하지 않음.

 

문제를 풀때 접근하는 방법

1. 주어진 문제가 DP 유형인지 파악
2. 가장 먼저 그리디, 구현, 완탐으로 검토 → 풀이 방법이 떠오르지 않으면 DP 고려 (완탐이 너무 오래걸리면?)
3. 작은 문제로 나눌 수 있고 이게 해결할 수 있으면
4. 재귀를 먼저 작성하고 메모이제이션 사용
5. 기본 유형으로 코테에서 많이 사용된다. (특히, 면접)

 

 

참고자료

www.youtube.com/watch?v=5Lu34WIx2Us&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98