[Algorithm] DP

DP, Dynamic Programing

• 완전 검색을 하는데 더 스마트하게 하는 방법이라고 할 수 있다
• DP = Recursive + Memoization
• 점화식으로 표현할 수 있다

피보나치 수열

• F(n+2) = F(n+1) + F(n)
• 피보나치 수열을 재귀함수로 구현하면 엄청난 중복 호출이 존재한다
• 각 값을 계산하자마자 저장해놓고 다음부터는 꺼내쓴다면 중복 호출이 사라진다

수학적 귀납법

어떤 등식이 모든 n에 대하여 성립함을 보일 때 가능한 모든 n을 등식에 대입해서 증명할 수는 없다. 이때 사용하는 방법이 수학적 귀납법이다. 수학적 귀납법은 주어진 등식이 n = 1 일 때 성립함(귀납 기본, induction base)을 증명하고, n일 때 성립한다고 가정(귀납 가정, induction hypothesis)한 뒤 n+1일 때 성립함을 증명(귀납 단계, induction step)하는 것이다. 이러한 증명이 완료되면 모든 n에 대해 등식이 성립함을 보일 수 있다.

동적 계획 알고리즘

DP는 위와 같이 귀납법을 만족하는 점화식을 찾아서 recursive와 memoization을 활용해 문제를 해결하는 방식이다. Memoization은 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 중복 계산을 줄여 전체적인 실행 속도를 빠르게 하는 기술이다.

DP 알고리즘은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다. 문제를 해결할 때 먼저 작은 부분 문제들의 해를 구하고 이를 이용하여 보다 큰 크기의 부분 문제를 해결해 나가며 최종적으로 원래 주어진 문제를 해결하는 방법을 사용한다.

DP를 적용할 수 있는 문제는 두가지 요건을 필수로 가지고 있어야 한다.

1. 최적 부분 문제 구조(Optimal substructure): DP를 효율적으로 적용하기 위해선 문제가 최적화의 원칙(Principle of Optimality)을 만족해야 한다. 최적화의 원칙이란 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것이다. DP 방법이 작은 해의 최적 해를 통해 큰 문제의 최적화를 구하기 때문에 최적화의 원칙을 만족하는 문제가 아니라면 DP를 적용할 수 없다.

2. 중복 부분 문제 구조(Overlapping sbproblems): DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해를 이용하여 순환적으로 큰 문제를 해결한다. 이때 순환적인 관계를 명시적으로 표현하기 위해 점화식을 사용한다. 이러한 순환적인 성질 때문에 이전에 계산된 작은 문제의 해가 다른 문제에서 필요하게 되는데(Overlapping subproblems) 이를 위해 이미 해결된 작은 문제들의 해들을 어떤 저장 공간에 저장한다. 저장된 작은 문제들의 해는 필요할 때마다 다시 계산하는 과정 없이 참조할 수 있기 때문에 중복된 계산을 피하게 만들어준다.

3. 최적해 구조의 특성 파악
4. 최적해의 값을 재귀적으로 정의
5. 상향식 방법으로 최적해의 값을 계산