DP란 무엇인가
-
수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법( dynamic programming )이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.
-
큰 문제를 작은 문제로 나눌 수 있다.0
-
작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
dp 문제 해결법
dp문제의 해결은 대부분 dp식, 즉 점화식을 잘 세우는 것이 중요하다-!-!
-
주어진 문제가 dp문제 유형이 맞는지 확인하고, 최종적으로 구할 큰 문제가 뭔지 확인한다.
-
작은 문제들과 큰 문제 사이의 관계를 점화식의 형태로 나타내 보자.
-
top-down 방식 혹은 bottom-up 방식을 통해 문제를 풀어나가자.
+) 탑다운 방식(하향식)은 메모이제이션을 통한 재귀함수를 이용한 방식이고 보톰업방식(상향식)은 결과 저장용 리스트인 dp테이블을 통해 반복문으로 문제를 해결하는 방식이다.
방금 전 소개했던 피보나치 수열을 dp를 통해 한번 해결해보겠다.
-
dp문제 유형인 것은 확인이 완료되었고 최종적으로 구할 큰 문제는 f(10)임을 확인했다.
-
점화식을 세워보자-!
f(n) = f(n-1) + f(n-2) (n>=3) , f(1)=1, f(2)= 2
피보나치 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))### 피보나치 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])
진킴