* 복습 겸 기록을 위해 작성한 포스트 입니다. 1. DP란, 결국 완전탐색의 일종이다. 또한 점화식을 만들 수 있어야 한다. N번째 값에 대한 어떠한 연산이 N-1 값에 대한 동일한 연산, N-2 값에 대한 동일한 연산으로 나뉠 수 있어야 한다. 어떠한 연산을 함수 f(N) 이라고 하면, f(N) = a1 * f(N-1) + a2 * f(N-2) + ... (for 임의의 상수 a1, a2,...) 형태로 표현되어야 한다. 이렇게 생각해볼 수 있는 문제들을 풀때 Dynamic Programming 기법을 사용하는 것이다. 2. DP의 조건 1. 참조 투명성을 가져야 한다. 2. 겹치는 부분 문제(연산)가 존재해야 한다. 3. 최적 부분 구조를 가지고 있어야 한다. 1번 조건인 참조 투명성은, 문제를 해..