🍀 Knowledge/알고리즘
[알고리즘] 동적 계획 알고리즘(DP) 유형 별 문제 모음
분할 정복 알고리즘은 반으로 나누는 것이 핵심이었다. 정확히는 분할할 수 없을 때까지 분할하여 간단한 문제부터 접근하였다. 굉장히 자주 사용하며, 좋은 알고리즘이다. 하지만, 분할하며 생기는 부분 문제들이 중복되어도 다시 사용하지 않는다. 이미 구한 문제를 또 푸는 것은 지루하고 시간이 드는 일이다. 유형마다 다르겠지만, 분할정복도 마찬가지일 것이다. 따라서 중복된 문제를 굳이 다시 풀지 않는 테크닉이 필요하다. 그리고 그 방법이 바로 "DP 알고리즘", Dynamic Programming 인 것이다. DP 알고리즘은 미리 최소 부분 문제들의 해를 구한다. 이는 논리적으로 생각했을 때 매우 당연하다고 여겨지는 것들이다. 또한 이 해를 이용하여 최소 부분 문제보다 더 큰 부분 문제를 풀어야 한다. 즉, 부..
