[알고리즘] DP (Dynamic Programming, 동적계획법)

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

큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법

조건

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

   큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우를 의미

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

   동일한 작은 문제를 반복적으로 해결해야 하는 경우

탑다운 vs 보텀업

탑다운 (Top-Down) 방식

• 큰 문제를 해결하기 위해 작은 문제를 호출함
• 재귀 함수를 이용
• 메모이제이션은 탑다운에 국한되어 사용되는 표현

예시) 피보나치 수열

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
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]

보텀업 (Bottom-Up) 방식

• 작은 문제부터 차근차근 답을 도출함
• 반복문을 이용
• 결과 저장용 리스트는 DP 테이블이라고 부름

예시) 피보나치 수열

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

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

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

메모이제이션(Memoization) 기법

• 다이나믹 프로그래밍을 구현하는 방법 중 한 종류
• 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
• 캐싱(Caching)이라고도 함
• 보통 탑다운 방식에 국한되어 사용되는 표현

구현

• 한번 구한 정보를 리스트에 저장
• 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때는 이미 구한 정답을 그대로 리스트에서 가져옴

분할정복과 동적계획법 차이점

분할 정복과 동적 프로그래밍은 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같다.

차이점은, 분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며, 동일한 중복이 일어나면 동적 프로그래밍을 쓴다는 것이다.