이것이 취업을 위한 코딩 테스트다를 참고하여 작성하였습니다.

🪆 동적 계획법이란?

DP라고도 자주 불리는 동적 계획법은, 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 문제 해결 방법이다.

🪆 동적 계획법을 사용하는 이유

피보나치 수열을 예시로 들어보자.

피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 수열이다.

현재의 항을 $a_n$이라고 하면, 피보나치 수열의 점화식은

이라고 표현할 수 있다.

이를 파이썬 코드로 구현할 때, 재귀 함수를 사용하면 간단하게 표현할 수 있다.

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

하지만, 이 방법의 시간 복잡도는 $O(n^2)$로 n이 커질수록 수행 시간이 기하급수적으로 늘어난다.
( n=30이 되면, 약 10억 가량의 연산을 수행해야 한다. )

그림을 보면 동일한 함수가 반복적으로 호출되는 것을 알 수 있다.
이렇게 반복적으로 사용되는 부분을 또 계산하지 않고, 리스트에 저장을 했다가 필요할 때 꺼내서 사용한다면 시간 복잡도를 $O(n)$만큼 줄일 수 있다.

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)

🪆 동적 계획법 사용 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.

DP는 기본적으로 큰 문제를 작은 문제로 나눈 뒤, 그 결과 값을 재활용하여 전체 답을 구한다.
그러므로 동일한 작은 문제가 반복하여 나타나는 경우 사용 가능하다

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

위 그림에서 A에서 B로 가는 최단 거리를 구한다고 가정해보자.
중간에 X가 있으므로, A에서 X로 가는 최단 거리와 X에서 B로 가는 최단 거리의 합이 전체 최단 거리이다.

이처럼 작은 문제에서 구한 결과가 전체 문제에 동일하게 적용되어야 한다.

🪆 동적 계획법을 사용한 문제 풀이 방법

1. DP로 풀 수 있는 문제인지 확인
2. 문제의 변수 파악
3. 점화식 만들기
4. 메모하기
5. 기저 상태 파악하기
6. 구현하기

1. DP로 풀 수 있는 문제인지 확인

• 앞서 말한 동적 계획법 사용 조건을 충족하는지 확인해보자
• 주로 특정 데이터를 최대화, 최소화하는 계산이나, 특정 조건을 충족하는 데이터를 세야 하는 경우 DP로 풀 수 있는 경우가 많다.

2. 문제의 변수 파악

• 재사용될 변수를 파악한다.
  • 피보나치 수 - 몇 번째 숫자인지
  • 문자열 간의 차이 - 문자열의 길이, 편집 거리
  • 배낭 문제 - index, 무게

3. 점화식 만들기

• 변수 간 관계를 찾아 관계식을 만든다.

4. 메모하기 (Memoization)

• 변수 값에 따른 결과를 저장할 배열을 만들어 배열 내에 저장한다.

5. 기저 상태 파악하기

• 가장 작은 문제의 상태를 파악한다.
  • ex) 피보나치 수열에서 0번째 항은 0, 1번째 항은 1

6. 구현하기

• Bottom-Up - 반복문 사용
  • 아래에서부터 계산을 수행하고 누적 시켜 큰 문제를 해결
  • dp[0]부터 시작하여 dp[n]까지 구하는 방법
• Top-Down - 재귀 사용
  • 위에서부터 바로 호출을 시켜 dp[0]까지 내려간 다음 재귀를 통해 전이시키는 방식

d = [0] * 100

# Bottom-Up
d[0] = 0
d[1] = 1

for i in range(2,100):
	d[i]=d[i-1]+d[i-2]
    
# Top-Down
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)

🪆 동적 계획법과 분할 정복(Divide-And-Conquer)의 차이점

분할 정복은, 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘이다.

문제를 작게 쪼개서 푼다는 점에서 공통점이 있다.
그러나,

• 동적 계획법은 부분 문제가 중복되어, 큰 문제를 풀 때 재활용됨
• 분할 정복은 부분 문제가 서로 중복되지 않음

이라는 점에서 차이점이 있다.