DP 개념

0. 사전 지식

- 분할정복 알고리즘(합병정렬) : https://min-99.tistory.com/18

- 분할정복 알고리즘(최근접 점 찾기) : https://min-99.tistory.com/23

- 분할정복 알고리즘 주의할점 : https://min-99.tistory.com/24

=> 분할정복에 대한 개념과 분할 정복의 주의할점을 알아야 DP문제를 제대로 이해하고, 분할정복 알고리즘으로 풀어야 하는 문제와 DP 문제를 구분할 수 있습니다. 

 

1. DP(Dynamic Programming, 동적 계획법) 란?

- 하나의 큰 문제를 작은 문제로 나누어 해결하는 기법을 의미합니다.

- DP가 되려면, 아래의 2가지 조건이 모두 성립해야만 합니다.

 

2. DP 조건

1) 🥇 최적 부분 구조 (Optimal Substructure)
-> 최소, 최대를 구하라는 문제가 많습니다. 또는 작은 부분 해를 더해서 문제의 답을 찾는 형태로 되어 있습니다. 

 

2) 🔁 중복되는 부분 문제 (Overlapping Subproblems)

-> 중복되는 부분 문제의 해답을 저장(메모이제이션)을 통해서 풀수 있어야 합니다. 

 

	🥇 최적 부분 구조 O	🥇 최적 부분 구조 X
🔁 중복개선 O	DP 알고리즘	(비효율적인) 단순 재귀
🔁 중복개선 X	단순 분할 정복 알고리즘	..? (이런 코드는 짜지 않으시길 추천 드립니다)

 

 

3. 하나의 큰 문제를 작은 문제로 나누어 해결하는 기법 => 이 설명은 분할 정복에도 해당되는거 아닌가요?  단순히 중복 개선으로 DP냐 분할정복 알고리즘이냐를 판별하나요? 

 

[DP와 분할 정복의 결정적 차이]

구분	동적 계획법 (DP)	분할 정복 (Divide and Conquer)
작은 문제의 중복	중복되는 부분 문제 (O) => 서로 중복되거나 연관이 있음	중복되는 부분 문제 (X) => 서로 독립적
해결 전략	작은 문제의 해를 저장하고 재활용 (메모이제이션)	작은 문제의 해를 합쳐서 전체 해를 만듦 (재귀)
목적	주로 최적화 (최대/최소) 문제	정렬, 검색 등 비최적화 문제
대표 예시	피보나치 수열, 계단 오르기	병합 정렬 (Merge Sort), 퀵 정렬 (Quick Sort)

 

=> "하나의 큰 문제를 작은 문제로 나누어 해결한다"는 공통점을 가지고 있어서 혼동될 수 있을 것 같습니다. 하지만. 두 기법은 작은 문제를 다루는 방식에서 결정적인 차이가 있습니다. 

 

1) 🧠 동적 계획법 (Dynamic Programming)

 

DP는 문제를 작은 문제로 나누는 것 같지만, 이 작은 문제들은 서로 중복되거나 연관되어 있습니다. 

- DP는 이 중복되는 부분 문제를 한 번만 계산하고 그 결과를 메모리(DP 테이블)에 저장해 두었다가 재사용합니다. 이것이 바로 DP의 핵심적인 특징입니다. 

 

따라서, DP는 단순히 나누어 해결하는 것을 넘어. 중복 계산을 피하여 효율을 극대화하는 기법이라고 정의하는 것이 정확합니다. 

 

 

2) 🤝 분할 정복 (Divide and Conquer)

 

분할 정복은 문제를 서로 독립적인 작은 문제로 나눕니다. 작은 문제가 해결되면, 그 해답을 다시 합쳐서 전체 문제의 해답을 얻습니다. 작은 문제들이 겹치지 않기 때문에 중간 결과를 저장할 필요가 없습니다. 

 

 

4. DP 문제를 풀기 위해서는 점화식을 세울 수 있어야 합니다. 

- 피보나치 수열과 계단오르기 문제로 먼저 점화식을 세우는 연습을 진행하길 추천 드립니다. 
*계단오르기 문제 : n개의 계단까지 도달하는 모든 경우의 수를 구하는 문제입니다. (이동은 +1칸 또는 +2칸만 가능)

점화식 : DP[n] = DP[n-1] + DP[n-2]

 

• (n-1)번째 계단에서 1칸 올라오는 경우:  DP[n-1]
• (n-2)번째 계단에서 2칸 올라오는 경우:  DP[n-2]
  

=> 점화식을 구하기 위해서 저는 주로 1~5번까지의 경우의 수를 구해봅니다!