DP - 동적 계획법

✏️ 핵심 이론

📍 DP 의 원리와 구현 방식

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.
3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다.
   • 이 방식을 메모이제이션 기법이라고 한다.
4. DP 는 Top - Down 방식과 Bottom - Up 방식으로 구현할 수 있다.

📍 DP 사용방법 - 피보나치 수열

• DP 를 사용하는 대표적인 알고리즘으로 피보나치 수열이 있다.

1. 동적 걔획법으로 풀 수 있는지 확인하기
   • 피보나치 수열은 앞의 두 자리의 합에 의해 수열이 만들어지는 방식이다.
   • 예를들어 6번째 수열은 4번째 + 5번째 로 구할 수 있고,
     이 방식을 작은 문제로 나눠도 수열의 값은 항상 같기 때문에 DP 로 해결할 수 있다.
2. 점화식 세우기
   • 점화식을 세울 땐 논리적으로 전체 문제를 나누고,
     전체 문제와 부분 문제 간의 인과 관계를 파악하는 훈련이 필요하다.
     - 인과 관계를 구하는 방법은 다양한 방식이 있지만 가장 큰 문제를 해결하기 위해 필요한 작은 문제들이 이미 해결되었다고 치고 구하면 수월하다.
     - 예를들어 피보나치 6번째 수열을 구해야 한다면,
     5번째까지 구해졌다 치고 점화식을 찾는 방법이다.

// 피보나치 수열의 점화식
D[N] = D[N - 1] + D[N - 2]

1. 메모이제이션 원리 이해하기

   • 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장한다.
   • 같은 문제가 나왔을 때 다시 계산하지 않고, DP 테이블의 값을 이용하는 방법을 뜻한다.

2. Top - Down 구현 방식 이해하기

   • 위에서부터 아래로 문제를 파악하는 방식이다.
   • 주로 재귀 함수 형태로 구현된다.
   • 코드의 가독성이 좋고, 이해하는데 편하다는 장점이 있다.

   ⚠️ 재귀 함수의 형태로 구현됐기 때문에 재귀의 깊이가 너무 깊어지면 런타임 오류가 발생할 수 있다.

   • 하지만 코딩테스트에서 이 부분까지 고려해야 되는 난이도는 잘 없기 때문에 다른 부분에 문제가 있을 확률이 매우 크다.