알고리즘) 다이나믹 프로그래밍

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

이미 계산된 작은 문제의 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록

-> 일반적으로 탑 다운(하향식)과 바텀 업(상향식) 두가지 방식으로 구성

 

다이나믹 프로그래밍 -> 동적 계획법

자료구조의 동적 할당과는 다르게 전혀 의미 없이 동적 이라는 수식어가 붙은 경우

동적 할당 => 프로그램이 실행되는 도중에 필요한 메모리를 할당하는 것

 

다이나믹 프로그래밍의 사용 조건

1. 최적 부분 구조 

큰 문제를 작은 문제로 나눌 수 있다. 작은 문제를 해결하면 큰 문제도 해결할 수 있는 경우

2. 중복되는 부분 문제

동일한 작은 문제를 반복적으로 해결하는 경우

 

대표적으로 피보나치 수열이 있다

 

1, 1, 2, 3, 5, 8, 13..

점화식이란 인접한 항들 사이의 관계식

 

피보나치 수열의 점화식 => an = an-1 + an-2

재귀함수로 구현할 수 있다

수열을 배열이나 리스트로 표현 가능

 

재귀함수로 피보나치 수열을 해결하면 지수 시간 복잡도

중복되는 부분 문제를 많이 갖기 때문

피보나치 수열의 시간 복잡도

세타 포기법 : 세타(1.618^N)

빅오 표기법 : O(2^N)

f(100)만 되어도 풀 수 없는 문제가 됨

 

1, 2 모든 조건을 만족한다

 

탑 다운 방식 - 메모이제이션 (재귀함수로 큰 수 부터)

한 번 계산한 결과를 메모리 공간에 메모

값을 기록해 놓기 때문에 캐싱이라고 한다

다이나믹 프로그래밍의 전형적인 형태는 바텀 업 (for문으로 작은 수 부터 계산)

결과 저장용 리스트는 DP 테이블이라고 부른다

메모이제이션은 다이나믹 프로그래밍에 국한된것은 아니지만 메모이제이션을 사용하여 탑 다운 방식을 구현 가능

 

메모이제이션 기법을 이용하면 실질적 연산이 색칠된 노드만 일어나게 된다

 

 

6 - 5 - 4 - 3 - 2 - 1 - 2 - 3 - 4

의 순서로 실행됨

시간복잡도는 O(N)의 상수 시간

 

다이나믹 프로그래밍 vs 분할 정복 (퀵 정렬)

큰 문제를 작은 문제로 나눌 수 있으며, 문제의 답을 모아 큰 문제가 해결될 경우 사용

-> 다이나믹 프로그래밍은 부분 문제가 중복될 경우

-> 분할 정복은 중복되지 않을 경우

 

다이나믹 프로그래밍에 접근하는 방법

-> 가장 먼저 그리디, 구현, 완전 탐색으로 해결할 수 있는지

-> 시간 복잡도가 너무 소요될 것으로 예상되면 다이나믹 프로그래밍 고려  

-> 일단 재귀 구현 후 (탑 다운) 작은 문제의 답이 재사용될 경우 코드 개선