[알고리즘] 동적프로그래밍(DP)

동적 프로그래밍

동적 프로그래밍(Dynamic Programming)이란?

문제의 크기를 변화하면서 정답을 계산하는데,
작은 문제의 결과를 이용해서 큰 문제의 정답을 빠르게 계산하는 알고리즘

쉽게 말하면 답의 재활용, 또는 기억하며 풀기 라고 할 수있겠다.

 

답을 구하기 위해서 했던 계산을 반복해야하는 종류의 문제의 구조를 '최적 부분 구조'라고 부른다.

동적 프로그래밍은 이런 문제에서 큰 효과를 발휘한다.

ex. 피보나치 수열

 

피보나치 수열을 통해 동적 프로그래밍의 형태를 보면

 

Top-down 방식

피보나치 수열을 구하는 함수 fib()

fib(1) = fib(2) =  1

fib(N) = fib(N-1) + fib(N-2)

6번째 피보나치 수열을 구하면

fib(6)

= fib(5) + fib(4)

= fib(4) + fib(3) + fib(3) + fib(2)

= fib(3) + fib(2) + fib(2) + fib(1) + fib(2) + fib(1) + fib(2)

= fib(2) + fib(1) + fib(2) + fib(2) + fib(1) + fib(2) + fib(1) + fib(2)

이런 과정을 거친다.

 

Bottom-up 방식

피보나치 수열을 저장하는 배열  fib[]

fib[1] = fib[2] = 1

fib[N] = fib[N-1] + fib[N-2]

 

6번째 피보나치 수열을 구하면fib[1] = fib[2] = 1fib[3] = fib[1] + fib[2]fib[4] = fib[2] + fib[3]fib[5] = fib[3] + fib[4]fib[6] = fib[4] + fib[5]

이런 과정을 거친다.

이 방식을 쓰면 O(n)의 시간 복잡도로 구할 수 있다.

 

동적프로그래밍을 선택하는 과정 
1. 가장먼저 완전탐색 접근을 시도해본다.
2. 경우가 지나치게 많아서 안될 것 같다.
3. 이럴 때 모든 경우를 빠르게 탐색하는 방법으로 동적프로그래밍을 사용해본다.

 

 

[ 알고리즘과 문법을 공부한 내용을 정리해보는 공간입니다. 부족한 부분이나 잘못된 부분 지적해주시면 감사하겠습니다.]