동적 계획법 : DP(Dynamic Programming)

동적 계획법은 큰 문제를 작은 문제로 나누어 해결한 뒤, 그 결과를 저장하여 같은 문제를 다시 계산하지 않도록 하는 알고리즘 기법입니다. 즉, 이전에 계산한 값을 활용하여 중복 계산을 줄이는 것이 핵심입니다.

---

1. DP를 이해하기 위한 핵심 개념

1.1. 중복되는 작은 문제

DP를 사용할 수 있는 문제는 작은 문제들이 반복적으로 등장합니다. 예를 들어, 피보나치 수열을 재귀적으로 계산한다고 하면 다음과 같은 중복이 발생합니다.

 

피보나치 수열은 다음과 같은 점화식(재귀식)으로 정의됩니다.

 

예를 들어, F(5)를 구하는 과정을 보면

 

여기서 F(3), F(2) 같은 계산이 여러 번 반복되고 있습니다. 이런 중복된 계산을 피하기 위해 이전 결과를 저장하면 훨씬 효율적으로 해결할 수 있습니다.

 

1.2. 최적 부분 구조

큰 문제의 최적 해가 작은 문제의 최적 해로 구성될 수 있는 경우를 말합니다. 예를 들어, 피보나치 수열에서 F(n)을 구하려면 F(n-1)과 F(n-2)만 알면 됩니다. 즉, 작은 문제의 최적 해를 이용해 큰 문제를 해결할 수 있기에 DP를 적용할 수 있습니다.

---

2. DP의 핵심 기술 : 메모이제이션과 Bottom-up

2.1. 메모이제이션(Memoization, Top-Down)

• 재귀 방식으로 문제를 풀되, 한 번 계산한 값을 저장하여 다시 계산하지 않는 방식입니다.
• 보통 배열을 활용하여 저장합니다.
• 중복 계산을 방지하여 실행 속도를 획기적으로 줄일 수 있습니다.

2.2. Bottom-up

• 작은 문제부터 차례로 해결하여 배열에 저장하면서 최종 값을 계산하는 방식입니다.
• 반복문을 사용하여 구현하는 것이 일반적입니다.
• 메모이제이션 방식보다 코드가 직관적이며, 스택오버플로우를 방지할 수 있습니다.
• 반복문을 사용하여 성능이 더 안정적입니다.