유니 코드

다이나믹 프로그래밍(DP)에 대해서 정리를 해보려고 한다. DP는 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 코딩 테스트 빈출 유형 중 하나이다. DP란?! 간단한 여러 개의 문제로 전체 문제를 나누어 푸는 방법을 말한다. (작은 문제의 답을 구한 후 어딘가에 메모해 놓고, 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제를 구해야한다면 앞서 메모한 결과값을 이용한다.) 대표적인 예로는 피보나치 수 구하기이다. 50번째 피보나치 수를 구해야 한다고 가정하자. P(50) = P(49) + P(48)이기 때문에 50번째 피보나치 수를 구하는 대신에 49번째, 48번째 수를 구하는 것으로 대체할 수 있다. 이런 방식으로 작은 문제에 대한 답을 구하고 이를 통해 더 큰 문제의 답을 구하는..