안녕

문제)

다들 이항 계수 아시죠? \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)입니다. 이때 n!를 계산하기 매우 힘드므로, 재귀 관계식을 이용하여 다음과 같이 정리할 수 있습니다. \(\binom{n}{k}=\left\{\begin{matrix} \binom{n-1}{k-1}+\binom{n-1}{k} & 0

1. 동적 계획법이란? DP (Dynamic Programming)는 코딩 테스트의 절반 이상을 차지하는 알고리즘이라 봐도 무방합니다. DP는 분할 정복과 매우 유사합니다. 하지만 분할 정복은 top-down 방식을 이용하고, DP는 bottom-up 방식을 이용합니다. 가장 작은 instance의 답을 먼저 구하여 저장하고, 필요하면 꺼내 쓰는 '동적 계획'입니다. 여기서 계획이란 문제 해결을 위한 배열(테이블)을 구축한다는 뜻입니다. DP 알고리즘의 개발 절차는 다음과 같습니다. 문제의 instance의 해답을 구하는 재귀 관계식을 세운다. (top-down approach, Divide and Conquer 방식) 작은 instance부터 해결하는 bottom-up 방법으로 전체 instance에 ..