Kstone's DevSpire

Review : 동적 계획 알고리즘(Dynamic Programming)이란?동적 계획 알고리즘은 최적화 문제를 해결하는 알고리즘에 해당한다. 문제를 크게 세 단계로 나누어 해결하는데,1. 먼저 입력 크기가 작은 부분 문제들을 모두 해결해 그 값을 저장한다.2. 그 해들을 이용하여 보다 큰 크기의 부분 문제를 해결한다.3. 최종적으로 원래 주어진 입력의 문제를 해결한다.결국 큰 문제를 작은 문제로 쪼개서, 그 답을 저장해두고 재활용(기억하면서 풀기)한다는 것이다.얼핏보면 분할 정복 아니야? 라고 할 수 있지만, 분할 정복은 그 답을 저장해두지는 않는다.DP는 분할 정복 + 최적부분 구조를 합친 알고리즘이다. DP 알고리즘에는 부분 문제들 사이에 의존적 관계가 존재한다. ( D, E, G가 B를 해결하는데..

동적 계획 알고리즘(Dynamic Programming)이란?동적 계획 알고리즘은 최적화 문제를 해결하는 알고리즘에 해당한다. 문제를 크게 세 단계로 나누어 해결하는데,1. 먼저 입력 크기가 작은 부분 문제들을 모두 해결해 그 값을 저장한다.2. 그 해들을 이용하여 보다 큰 크기의 부분 문제를 해결한다.3. 최종적으로 원래 주어진 입력의 문제를 해결한다.결국 큰 문제를 작은 문제로 쪼개서, 그 답을 저장해두고 재활용(기억하면서 풀기)한다는 것이다.얼핏보면 분할 정복 아니야? 라고 할 수 있지만, 분할 정복은 그 답을 저장해두지는 않는다.DP는 분할 정복 + 최적부분 구조를 합친 알고리즘이다. 뭔지 모르겠다면 그리디와 분할 정복 포스트를 보고오자. 분할 정복을 사용하긴 하지만 크게 다른 점이 하나 있다. ..