[Python] 동적계획법 (Dynamic Programming)

💡 Dynamic Programming(DP)

다이나믹 프로그래밍(dp)알고리즘은 간단하게는 필요한 계산 값을 저장해두었다가 재사용하는 알고리즘이다.
어떤 큰 문제를 풀 때 여러개의 작은 문제로 나눠서 해결하고 그 결과를 저장해 놓은 후 이 결과값들을 문제 풀 때 사용하는 방법이다.
즉, 작은 문제들로 나눠서 풀 때 풀었던 문제는 다시 풀지 않는 방법이다!

분할 정복 알고리즘과 비슷하다고 느낄 수 있는데 분할 정복 알고리즘은 단순히 작은 여러개의 문제를 풀었던 같은 문제더라도 계속해서 풀지만 동적게획법은 중복 문제는 풀지 않고 저장해놨던 결과값을 가져오기 때문에 더 효율적이라고 할 수 있다.
결과값들을 저장하기 때문에 메모리 공간을 좀 더 사용하지만 시간적인 측면에서는 시간을 획기적으로 줄일 수 있다.

📌 동적계획법 사용 조건

dp알고리즘을 사용하기 위해서는 두 가지 조건이 필요하다.

1. 최적 부분 구조 (Optimal Substructure)
   문제의 최종 해결 방법은 부분 문제의 최적 문제 해결 방법으로 구성된다. 문제를 해결하는 모든 단계에 대해서 해당 단계의 최적해가 도출되어야 한다.
   Ex) 부분 문제에서 A에서 B까지 최단 경로 X를 구했을 때 이 X는 모든 문제에서의 최단 경로
2. 겹치는 부분 문제 (Overlapping Subproblems)
   동일한 작은 문제들이 중복되어 사용되는 경우 사용이 가능하다. 큰 문제를 나눠 작은 문제들을 재사용할 수 있어야 dp알고리즘을 사용하는 데에 의미가 있다.

💡 동적계획법 적용 방식

동적계획법에는 Top-Down방식과 Bottom-Up방식 이렇게 두 가지 방식이 존재한다.

Top-Down

하향식 방법으로, N의 결과값을 찾기 위해 위에서부터 출발하여 제일 작은 문제까지 내려간 다음 결과값을 재사용해서 올라가는 방식이다. 이미 계산을 완료한 것은 메모제이션 해두었다가 재사용하여 큰 문제에서 사용한다.

Memozation?
메모제이션(Memozation)이란 한 번 구한 계산 결과를 메모리 공간에 메모해두고, 같은 식을 다시 호출하면 메모한 결과 그대로 가져오는 기법이다.

Bottom-Up

상향식 방법으로, 가장 작은 문제들부터 답을 구하여 큰 문제를 해결하는 방식이다. 재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있다는 장점이 있다! 반복문을 통해 제일 작은 문제부터 결과를 테이블에 채워나가고 이 테이블에 저장된 결과를 사용하는 방법으로 Tabulation이라고 부른다.

dp알고리즘의 전형적인 형태는 이 Bottom-Up 방식이다!
이 방법은 단순 반복문을 이용해 구현할 수 있다.

Example - [피보나치 수열]

제일 대표적인 예시로 피보나치 수열 문제에 대해서 알아보자!
피보나치 수열은 재귀 알고리즘 혹은 동적계획법으로 풀 수 있는 대표적인 문제이다.

먼저 재귀 알고리즘을 사용해서 푸는 경우이다.

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

간단히 피보나치 점화식을 재귀로 작성하면 위의 코드처럼 작성할 수 있다.

💡 Top-Down (하향식, Memozation)

그렇다면 동적계획법을 사용해서 먼저 Top-Down 방법으로 코드를 작성해보자.

# 메모제이션을 위한 리스트
memo = [0]*100

# 피보나치 수열 (Top-Down)
def fibo(x):
  # fibo(1)=fibo(2)=0
  if x==1 or x==2:
    return 1

  # 이미 계산한 적있는 문제라면 memo에서 찾아서 리턴
  # 0이 아니라면 계산된 값이 저장되어 있는 것
  if memo[x] != 0:
    return memo[x]

  # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과값 계산
  # memozation에 저장 후 리턴
  memo[x] = fibo(x-1)+fibo(x-2)
  return memo[x]

💡 Bottom-Up (상향식, Tabulation)

Bottom-Up 방법으로 코드를 작성해보자.

# 작은 문제부터 해결해서 저장할 dp테이블 생성
dp = [0]*100

# fibo(1)=fibo(2)=0
# 1과 2의 함수값은 저장해놓고 시작
dp[1]=1
dp[2]=1
n=99

# 피보나치 수열을 반복문으로 구현(Bottom-Up)
# 작은 문제부터 차례대로 반복문을 사용해서 dp테이블을 채워나감
for i in range(3, n+1):
  dp[i] = dp[i-1]+dp[i-2]

🧐 풀어보면 좋을 문제들

단계별로 풀어보기 - 동적계획법
[BOJ]알고리즘 수업-피보나치 수1