- Dynamic Programming
- Greedy Algorithm
Dynamic Programming 동적 프로그래밍
Bottom-up approach(상향식 접근방법)의 일종으로, 쉽게 말해 문제의 일부분을 풀이한 다음, 그 결과를 재활용하는 방법(memoization). ‘기억하며 풀기’라고 이해하면 쉽다.
① 문제를 하위 문제로 나눌 수 있어야 함 ② 하위 문제의 결과 값으로 상위 문제의 결과 값을 구할 수 있어야 함 ③ overlapping subproblems: 하위 문제들이 중복되어야 함
→ principle of optimality(최적성의 원리: 주어진 문제에 대한 최적해는 주어진 문제의 소문제에 대한 최적해로 구성됨)가 반드시 성립하여야 함
divide-and-conquer와의 유사점과 차이점 확인할 것: 분할정복 방법은 소문제들이 모두 독립이므로 해를 재사용할 수 없는 문제에도 사용할 수 있다.
→ 그러므로 만약 fibonacci sequence를 분할정복으로 푼다면 매번 fib(x)의 값을 계산하게 되므로 리소스 낭비가 발생하나, DP로 해결한다면 이미 테이블에 저장되어 있는 해를 가져와 사용할 수 있을 것이다.
memoization: top-down approach, 재귀, 필요한 순간 계산하여 그 값만 저장, memo/cache에 값을 저장(caching)
tabulation: bottom-up, 반복, 당장 필요하지 않은 것까지 포함해 모든 값과 과정을 계산하고 저장, dp table에 값을 저장(주로 array)
Greedy 탐욕법
(알고리즘이라는 단어가 붙어 있으나 설계 기법에 가까움) heuristic method(발견법, 최선/최적의 답보다 단계적으로 빠르게 해결하는 데 초점을 두는 방법론)의 일종으로, 가장 직관적인 알고리즘 설계
특징 연산 시간이 빠름, 최악의 결과는 아님(근사해를 가짐)
한계 찾아낸 해가 global optimum이 아닐 수 있음(최소비용=최소가중치 O, 최단경로=최적해 보장 X) cf. backtracking(되추적): greedy의 반대 개념 → brute-force attack(무차별대입법, 가능한 모든 값을 넣어보는 방식) 다음으로 시간이 오래 걸릴 것이라고 예측할 수 있음
사례 TSP(외판원 문제)
cf. class-N, NP-completeness
단, 액면가가 임의로 주어지는(=‘일반적인 경우’의) 동전 거스름돈 문제는 greedy로 최적해를 얻지 못한다.
❓문제에 최적인 알고리즘이 무엇인지 어떻게 알 수 있을까?
① 단순 구현, brute force 등의 아이디어로 접근을 시도 ② 완전탐색을 이용했을 때 시간 복잡도가 높아지는 경우라면: greedy 도전 ③ 1, 2 후 해결하지 못하였다면 DP (DP → 재귀 적용 → 코드 개선: DP table 등 적용)
Uploaded by Notion2Tistory v1.1.0