알고리즘 - 16 동적 프로그래밍

재귀적 해법

- 큰 문제에 닮은 꼴의 작은 문제가 깃듬

- 잘쓰면 보약, 못쓰면 맹독

 -> 관계 중심적으로 파악함으로써 문제를 간명하게 볼 수 있음

 -> 재귀적 해법을 사용하면 심한 중복 호출이 일어나는 경우가 있음

 

 

재귀적 해법이 바람직한 경우

- 퀵/병합 정렬 등 정렬 알고리즘

- 계승 구하기

- 그래프의 dfs 깊이 우선 검색

 

재귀적 해법이 치명적인 경우

- 피보나치 수 구하기

- 행렬 곱샘 최적 순서 구하기

 

동적 프로그램이의 기원

- 미국의 수학자 리처드 벨만이 1940년대 사용하던 용어

- 큰 문제안에 작은 문제가 중첩되어 있는 문제를 해결하는데 사용하는 방법을 동적 계획법이라 이름 붙임

- dynamic 이란 말은 벨만이 이런 알고리즘의 시가변적이며 다단계적인 특성을 나타내기 위해 채택한 용어

- programming 이란 단어는 공군 내에서도 워드프로세스 교육이나 군수 물자 운송 등에 이용되는 단어였기 때문에 사용하는데 아무 제약이 없었던 것임

 

 

동적 프로그래밍이란

- 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고, 이를 재귀 호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 재귀적 중복을 해결하는 방법

- 재귀적 중복을 해결하기 위해, 적절한 저장 방법으로 중복 호추르이 비효율성을 제거 한 것

 

 

동적 프로그래밍 조건

- 최적 부분 구조를 이루어야함

- 재귀적으로 구현했을때 중복 호출로 심각한 비효율이 발생함

 

 

동적 프로그래밍 전략

- 기본적으로 분할 정복 알고리즘과 비슷

- 동적 프로그래밍을 사용하는 알고리즘 역시 주어진 문제를 부분 문제로 나누어 각 부분문제의 답을 계산하고, 이 계산한 결과 값을 이용해 원래 문제의 답을 산출하기 때문

 

 

분할 정복 알고리즘과의 차이점

- 분할 정복 알고리즘 : 원래 문제를 부분 문제로 나눔

- 동적 프로그래밍 : 주어진 부분 문제 정담답을 저장 해둔 뒤 동일 문제를 이용 할 때 저장해둔 정답을 바로 산출하여 이용함(속도 향상)

 

 

 

피보나치 수의 정의

- f(n) = f(n-1) + f(n-2)

- f(1) = f(2) = 1

- n의 피보나치 수는 n-1의 피보나치 수와 n-2의 수를 포함함

-> 최적 부분 구조 : 이처럼 큰 문제의 해답에 작은 문제의 해답이 포함 된 경우

 

 

피보나치 수를 구하는 재귀 알고리즘

fib(n)
{
  if (n = 1 or n = 2)
     then return 1;
     else return (fib(n - 1) + fib(n - 2));
}

-> 중복 호출이 많이 발생

 

 

피보나치 수열의 재귀 알고리즘 call tree

- fib(3)을 구할떄는 fib(2)와 fib(1)이 필요

- fib(4)을 구할때 fib(2)가 2번 호출

- fib(5)는 fib(2)가 3번 호출

- fib(6)을 구할때는 fib(2)가 6번 호출

 

중복 호출이 증가하는 정도

- 중복 호출 회수 자체가 다시 피보나치 수열을 이름

- 증가 속도 : Omega(2^{n/2}) -> 지수 함수적

 

동적 프로그래밍을 이용한 해법

- 접근 방법 : 중복되는 호출 결과를 한번만 구해 저장해 놓았다가 나중에 다시 사용

- ex : fib(3)을 처음 호출하고 결과를 얻었으면 이것을 어딘가에 저장해두고 나중에 fib(3)이 필요하면 저장된 것을 이용

 

 

피보나치 수열과 동적 프로그래밍 조건

- 최적 부분 구조를 이루어야 함 -> 만족

- 재귀적으로 구현했을때 중복 호출로 심각한 비효율이 발생함 -> 만족

=> 동적 프로그래밍이 그 해결책

 

 

 

피보나치 수를 구하는 동적 프로그래밍 해법 유사 코드

fibonacci(n)
{
   f(1) <- f(2) <- 1;
   for i <- 3 to n
      f[i] <- f[i-1] + f[i-2];
   return f[n];
}

=> Theta(n) 시간에 끝난다.