Hayden's Archive
[알고리즘] 다이나믹 프로그래밍(Dynamic Programming) 본문
* 다이나믹 프로그래밍 = 동적 계획법
- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
* 큰 문제를 작은 문제로 나누는 알고리즘
1) 다이나믹 프로그래밍(Dynamic Programming)
2) 분할 정복(Divide & Conquer = D&C)
-> 공통점 : 큰 문제를 작은 문제 여러개로 나눠서 푼다.
-> 차이점 : 다이나믹 프로그래밍은 큰 문제를 작은 문제로 나눴을 때 중복이 가능 / 분할 정복은 큰 문제를 작은 문제로 여러개로 나눴을 때 절대로 중복이 일어나지 않는다.
* 다이나믹으로 풀 수 있는 문제의 속성
1) Overlapping Subproblem : 겹치는 부분(작은) 문제 (큰 문제를 여러개의 작은 문제로 나눈 다음 다시 그 답을 이용해서 원래 문제를 푼다. 이 작은 문제들이 중복이 되면 첫번째 다이나믹으로 풀 수 있다.)
예 : 피보나치 수열
큰 문제 Fn을 구하기 위해 작은 문제 Fn-1과 Fn-2로 나누어서 각각의 정답을 구한 다음에 두 개를 더해서 원래 문제를 푸는 방식.
큰 문제 : N번째 피보나치 수를 구하는 문제
작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제
2) Optimal Substructure : 최적 부분 구조.(문제의 정답을, 작은 문제의 정답을 통해서 구할 수 있다. )
큰 문제와 작은 문제는 같은 방법으로 풀 수 있음 -> 문제를 작은 문제로 쪼갤 수 있다.
예 : 서울에서 부산까지 가는 가장 빠른 방법
서울->대전->대구->부산으로 정했는데, 알고 보니 대전에서 부산까지는 대전->대구->부산보다 대전->울산->부산이 더 빠르다. 그러면 서울에서 부산까지 가는 방법도 서울->대전->울산->부산이 됨.
-> 어떤 문제의 정답을 작은 문제의 정답에서 구한 것
다이나믹 프로그래밍에서...
문제의 정답이 변하지 않을 때 그 문제를 여러번 푸는 것은 비효율적
어떤 문제의 정답을 한번 구했다면 그 정답을 어딘가에 메모해둠(Memorization. 배열에 저장)
다음부터는 그 정답을 이용함.
다이나믹 구현방식
1. Top-down : 큰 문제부터 문제를 쪼개 가면서 작은 문제를 만들고 다시 합쳐가면서 원래 문제를 푸는 방식. 주로 재귀 사용.
2.Bottom-up : 작은 문제들을 모아서 큰 문제 하나 만들고, 다시 작은 문제들을 모아서 큰 문제 하나 만들고, 이렇게 하나씩 쌓아가는 것. 주로 반복문 사용해서 구현.
관련 코드 포스팅
hayden-archive.tistory.com/315
