개발자 준비중인 블로그

학부시절 알고리즘에서 제일 어려웠던 것으로 기억하는 알고리즘이다 지금도 알고리즘 문제를 보면 수많은 문제들이 있으며 여러 방법으로 응용이 가능한 방식이다. 1. 개요 Dynamic Programming (DP) 복잡한 문제를 간단하게 여러개의 문제로 나누어 이를 점화식으로 만들어 재귀구조로 문제를 해결하는 방식을 말한다. 주로 최적값 문제를 해결할 때에 사용한다. 가장 대표적인 문제를 뽑자면, 피보나치 수와 최단경로, 행렬 곱셉들이 있다. 문제를 여러게로 나누어 풀기 때문에 분할 정복과 비슷하지만 문제를 나누는 방식에서 그 차이가 들어난다. 분할정복의 경우 각 문제의 중복이 없게 분할한다. 즉, 각 문제들이 독립적으로 분리되어 있다. 하지만 동적 계획법의 경우는 문제 분할 시 중복이 존재하며, 이를 위해..