동적계획법(Dynamic Programming)과 대표 알고리즘 기초 소개
동적계획법 동적계획법은 어떠한 문제에 대한 최적해를 얻고자 할 때, 해당 문제에 대해 부분적으로 분할하여 작은 문제를 먼저 해결한 뒤, 각 부분에 대해 최적의 해답을 차례로 구해 가는 알고리즘이다. 말이 조금 어려운데, 전체 큰 해를 구하기 위해서 작은 해를 구한 뒤에 그걸 재활용해서 여기저기서 이용하면서 답을 찾아 가는 기법이다.동적계획법(Dynamic Programming)은 줄여서 DP라고도 부른다. 일반적으로 이름이 붙어진 알고리즘들이 구체적으로 문제를 해결하는 길을 제공하는 알고리즘이라면, 동적계획법은 구체적인 어떤 알고리즘을 지칭한다기보다는 문제를 해결하는 일종의 여러 방법들의 집합과도 같다. 문제를 해결하는 하나의 철학인 것이다. 한가지 큰 문제를 풀기 위해서 그 문제를 작은 문제들의 연장으..