Tutorial 동적계획법(Dynamic Programming) timer 1초 memory 512MB

[동적계획법 ( DP - Dynamic Programming)]

1. 리처드 벨만(Richard E. Bellman)이 최적화 문제를 연구하던 중 문제해결에 사용한 방법으로 해를 구하는 과정이 여러단계에 걸쳐 시가변적으로 이루진 것을 두고 Dynamic Programming(동적계획법)이라 명명하였다고 전해진다. - wikipedia-

2. 문제 해결에 필요한 모든 경우를 고려하여 탐색하는데 중복탐색을 최소화하는 방법이다.​

3. 주어진 문제를 보다 작은 문제로 분할하여 부분문제의 해를 구하여 저장하고 더 큰 문제를 해결하는데 저장된 결과​를 재사용하는 방법이다.

4. 동적계획법으로 고려해 볼 수 있는 문제는 다음 두 가지 특성을 만족한다.

  (1) 최적 부분 구조(Optimal Substructure - Principle of Optimality) : 주어진 문제의 최적해는 부분문제의 최적해를 포함한다.

  (2) 겹치는 부분 문제(Overlapping Subproblems) : 하나의 작은 부분문제를 서로다른 큰 문제들이 중복 참조한다.

5. 관련 문제와 알고리즘

  (1) 0-1배낭문제(0-1 Knapsack Problem)

  (2) 동전바꿔주기(Coin Change)

  (3) 최장증가부분서열(LIS - Longest Increasing Subsequence)

  (4) 최장공통부분서열(LCS - Longest Common Subsequence)

  (5) 계란 떨어뜨리기 퍼즐(Egg Dropping Puzzle)

  (6) 행렬곱셈최적순서(Matrix Chain Multiplication)

  (7) 벨만-포드 알고리즘(Bellman-Ford Algorithm)

  (8) 다익스트라 알고리즘(Dijkstra Algorithm)

  (9) 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)

     등 많은 예들이 있다.

6. 문제 풀기 과정

  (1) 최적부분구조에 따른 순환적인 성질을 상태정의 해본다.

  (2) 상태정의를 기반으로 점화식을 구한다.

  (3) 프로그램을 작성하고 테스트한다.

7. 설계 방법

  (1) 상향식 (Bottom-up) 설계 - 작은 문제에서 큰 문제로 접근 : 반복문을 이용하여 구현한다.

  (2) 하향식 (Top-down) 설계 - 큰 문제에서 작은 문제로 접근 : 재귀함수를 이용하여 구현하며 이 방법을 memoization 이라고 한다.

8. 접근 방법  

(1) 받아 오기 : 이전 단계로부터 현재 단계의 값을 구하기

  (2) 뿌려 주기 : 현재 단계에서 다음 단계의 값을 구하기​ 

[피보나치 수열을 통한 이해]

1. 피보나치 수열의 점화식은 다음과 같다.

(1) N = 1, 2 이면 fibo(N) = 1.
  (2) N > 2 이면 fibo(N) = fibo(N - 2) + fibo(N-1).

2. 동적계획법 문제의 2가지 특징을 확인해 보자.

  (1) 최적부분구조 : fibo(N)의 해는 부분 문제인 fibo(N-2), fibo(N-1)의 해를 포함한다.
  (2) 겹치는 부분 문제 : 아래 그림을 보면 fibo(4), fibo(5), fibo(6) 은 fibo(3)의 해를 중복참조하고 있다.

 [문제]

정수 N을 입력받아 N번째 피보나치 수를 구하는 프로그램을 작성하시오. ( 3 <= N <= 100,000)

결과값을 너무 클수 있으므로 10억7로 나눈 나머지를 구하시오.