코딩테스트
dp를 찾는 방법. [interval dp], 백준 11066번
dp는 상황을 나누고, 그 간의 관계를 파악하여 점화식 혹은 a=b와 같은 고정된 수식으로 표현하여 문제를 효율적으로 해결하는 방식이다. 예를 들어 동전이 연속으로 앞면이 나올 확률을 구한다고 생각해보자. 모든 상황은 결국 나누면 앞면, 뒷면 으로 나뉜다. 이를 수식으로 표현해보자. n-1 째까지 앞면 나올 확률 * 앞면 나올 확률 = n 째까지 앞면 나올 확률 즉 f(n-1)* 1/2 = f(n) 이라는 점화식을 구할 수 있다. dp는 이런 특정 행동 (동전을 던짐) 에 따른 관계의 변화를 수식으로 표현해서 구할 수 있다. (특정행동 n-1번 = 특정행동 n번 이런식으로 생각하면 쉽다.) 전에 knapsack 알고리즘에 대해서도 정리했었는데, dp라고 생각하고 식을 구해도 해결할 수 있다. 추가로 in..
