1. DP (다이나믹 프로그래밍)DP(다이나믹 프로그래밍)은 주어진 문제를 더 작은 하위 문제들로 나누어 해결한 후, 그 해를 저장하고 재활용하여 전체 문제의 해를 구하는 방법이다. DP를 사용하는 이유는 큰 문제를 하위 문제들로 쪼개어 해결함으로써 중복 계산을 피하고 효율적으로 문제를 해결할 수 있기 때문이다. (시간 복잡도 또한 줄어든다.) 1.1 DP 사용조건DP에는 2가지 사용조건이 있다.중복되는 하위 문제 : 큰 문제를 작은 문제로 나눌 수 있음최적 부분 구조 : 작은 문제에서 구한 정답이 큰 문제에서도 동일한 정답인 경중복되는 하위 문제와 최적 부분 구조에 대한 추가적인 설명이 필요한 경우 아래 접은 글을 참고하면 된다.더보기1.1.1  중복되는 하위 문제(Overlapping Subprobl..