dp(dynamic programming) 동적 계획법 문제 유형 설명 및 해결법 (파이썬)

1. dp란 

  dp, dynamic programming의 줄임말이다. dp는 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 또한 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이라고 흔히 말한다.

  dp의 핵심은 앞서 말한 수행 시간 효율성의 비약적 향상인데 이는 '메모이제이션'이라는 기법을 이용해 이미 계산된 결과(작은 문제)를 별도의 메모리에 저장해 다시 계산하지 않고 필요한 경우 사용하는 방식이다. 이 기법을 사용하면 시간복잡도가 훨씬 줄어들기에 수행 시간 효율성이 비약적으로 향상한다.

---

2. dp 문제 유형 

  dp문제의 조건은 두가지이다.

1. 최적 부분 구조 

  큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

2. 중복되는 부분 문제

  동일하게 반복되는 작은 문제로 해결해야한다.

 

  예를 들어 피보나치 수열을 떠올려보자. 피보나치 수열 특성상 f(10) (f(n)을 피보나치 수열의 n번째 숫자라고 하자)는 f(8)과 f(9)를 더한 값이고 또 f(8)과 f(9)를 구하기 위해서는 그전의 두 피보나치값을 더해야한다. 이 과정에서 구하는 피보나치 수의 값이 여러번 겹치기도 한다. 

 이를 해결하기 위해 사용하는 문제해결기법이 바로 dp이다!! f(10)이라는 큰 문제를 해결하기 위해 f(9)와 f(8), 즉 작은 문제를 구해야하고 이 작은 문제의 답을 모아 큰 문제인 f(10)을 해결하므로 최적 부분 구조 조건을 만족하고 구하는 과정에서 동일하게 반복되는 값이 있으므로 중복되는 부분 문제 조건 또한 만족한다. 

 

 dp문제의 특징은 아이디어가 중요하다는 것이다-! 그 아이디어가 어떻게 적용하여 문제를 풀 수 있을까?

---

3. dp 문제 해결법

  dp문제의 해결은 대부분 dp식, 즉 점화식을 잘 세우는 것이 중요하다-!-! 

1. 주어진 문제가 dp문제 유형이 맞는지 확인하고, 최종적으로 구할 큰 문제가 뭔지 확인한다.

2. 작은 문제들과 큰 문제 사이의 관계를 점화식의 형태로 나타내 보자. 

3. top-down 방식 혹은 bottom-up 방식을 통해 문제를 풀어나가자.

 +) 탑다운 방식(하향식)은 메모이제이션을 통한 재귀함수를 이용한 방식이고 보톰업방식(상향식)은 결과 저장용 리스트인 dp테이블을 통해 반복문으로 문제를 해결하는 방식이다.

 

  방금 전 소개했던 피보나치 수열을 dp를 통해 한번 해결해보겠다.

1. dp문제 유형인 것은 확인이 완료되었고 최종적으로 구할 큰 문제는 f(10)임을 확인했다.

2. 점화식을 세워보자-!

 f(n) = f(n-1) + f(n-2) (n>=3) , f(1)=1, f(2)= 2

3-(1) 먼저 top-down 방식을 통해 해결해보자.

# 피보나치 by 탑다운(메모이제이션)
n = int(input())
d = [0]*(n+1)    # 한 번 계산된 결과를 메모이제이션하기 위해 리스트를 초기화함

def fibo(n) :  # 피보나치 함수를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
    if n == 1 or n == 2 : # 종료 조건
        return 1
    if d[n] != 0 :  # 이미 계산한 적 있으면 그대로 반환
        return d[n]
    d[n] = fibo(n-1) + fibo(n-2)        # 아직 계산하지 않았으면 점화식에 의해 피보나치 결과 반환
    return d[n]
print(fibo(n))

3-(2) 이번엔 botton-up 방식을 통해 해결해보자.

# 피보나치 by 보텀업(상향식)
n = int(input())
d = [0]*(n+1)       # 결과 저장을 위해 dp테이블 초기화함

d[1] = 1            # 첫번째와 두번째 피보나치 수는 1로 이미 설정함
d[2] = 1

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

print(d[n])

---

  대략적인 dp문제 소개 및 dp문제 해결법을 소개해보았다. 막상 코딩하는 부분은 적지만 아이디어를 떠올리기가 무척 힘든 dp문제에 관해 열심히 공부해본 후 포스팅을 이어나가겠다-!