동적프로그래밍 의 두가지 주요 특성, 중복부분 문제와 최적부분 구조의 차이점 통찰과 를 통해 DP를 푸는 흐름을 생각하기

 

서론

 

dp에서는 중복부분문제와 최적부문구조가 동시에 가능해야 DP 문제로 풀 수 있다.

• 중복 부분 문제 (Overlapping Subproblems):
  • 동일한 하위 문제를 여러 번 반복해서 푸는 특성
• 최적 부분 구조 (Optimal Substructure):
  • 문제를 작은 하위 문제들로 나누어 해결할 수 있고, 각 하위 문제의 최적해를 결합하여 전체 문제의 최적해를 구성할 수 있는 특성

 

그럼 여기서 의문이 하나 생길수도 있는데

중복부분문제라면 하위문제를 여러번 풀어야되는 문제라면 그 전의 최적부분 구조도 자연스럽게 따라오지않을까?

 

 

 

하지만 그렇지 않다 

 

 

 

1. 중복되는 부분 문제 (Overlapping Subproblems) - 효율성의 문제

이것은 큰 문제를 작은 문제로 나누었을 때, 같은 작은 문제가 반복적으로 나타나는 성질을 의미한다

• 대표적인 예시: 피보나치 수열 fib(5)를 구하려면 fib(4)와 fib(3)이 필요하다. fib(4)를 구하려면 fib(3)과 fib(2)가 필요하다.
• 여기서 fib(3)은 두 번 계산됩니다. 숫자가 커질수록 중복 계산은 기하급수적으로 늘어납니다. DP는 이렇게 중복되는 계산 결과를 한 번만 계산하고 저장해두는 방식(메모이제이션, Memoization)으로 풀이 속도를 비약적으로 향상시킨다

---

2. 최적 부분 구조 (Optimal Substructure) - 구조의 문제

이것은 문제의 전체 최적 해결책(Optimal Solution)이 부분 문제들의 최적 해결책들로 구성될 수 있는 구조를 의미.

• 대표적인 예시: 최단 경로 찾기 서울에서 부산까지 가는 최단 경로를 찾는다고 가정해 보자. 만약 그 최단 경로가 대전을 거쳐 간다면, 그 경로에 포함된 '서울에서 대전까지'의 경로 또한 반드시 최단 경로여야 한다. 만약 서울에서 대전까지 가는 더 짧은 경로가 있다면, 그 경로로 갈아타는 순간 전체 경로도 더 짧아지기 때문.

---

왜 하나가 다른 하나를 의미하지 않을까? (Counterexample)

그렇다면 왜 '중복되는 부분 문제'가 있다고 해서 '최적 부분 구조'가 보장되지 않을까? 두 속성이 독립적임을 보여주는 대표적인 반례가 있다.

• 반례: 중복 없는 최장 경로 (Longest Simple Path) 어떤 그래프에서 한 지점 A에서 다른 지점 D로 가는, 중간에 같은 지점을 두 번 방문하지 않는 가장 긴 경로를 찾는 문제를 생각해 보자.
  • A에서 D로 가는 최장 경로는 A -> B -> C -> D (길이 3) 라고 하자.
  • 이 문제의 부분 문제 중 하나는 'A에서 C로 가는 최장 경로'일 것.
  • 그런데 만약 A와 C 사이에 A -> E -> F -> C 와 같은 더 긴 경로(길이 3)가 존재한다면, A에서 C까지의 최적해(부분 문제의 최적해)는 A -> E -> F -> C가 된다.
  • 하지만 이 부분 문제의 최적해 A -> E -> F -> C는 전체 문제(A->D)의 최적해인 A -> B -> C -> D를 구성하는 데 아무런 도움이 되지 않는다. 오히려 부분 문제의 최적해가 전체 문제의 최적해를 구하는 데 방해가 될 수도 있다.

이처럼 부분 문제의 최적해가 전체 문제의 최적해에 포함되지 않는 경우가 존재하기 때문에 '최적 부분 구조'가 성립하지 않는다고 말한다. 이 문제는 부분 경로를 계산하는 '중복되는 부분 문제'는 가질 수 있지만, '최적 부분 구조'는 만족하지 않으므로 DP로 풀 수 없다.

---

결론

 

속성	핵심 질문	역할
중복되는 부분 문제	같은 계산을 또 해야 하는가?	효율성 (메모이제이션으로 해결)
최적 부분 구조	부분 문제의 최적해가 전체 문제의 최적해를 만드는가?	정확성/구조 (점화식을 세우는 근거)

 

 

 

 

 

 

만약 중복되는 부분문제가 아니고 최적부분 구조만 있다면 어떤 문제인가?

 

 

 

 

중복되는 부분 문제가 없다면 '분할 정복(Divide and Conquer)' 문제일 가능성이 매우 높다.

 

---

 분할 정복 (Divide and Conquer)

분할 정복은 다음 세 단계로 작동.

1. 분할 (Divide): 문제를 더 이상 쪼갤 수 없을 때까지 여러 개의 독립적인 작은 문제로 나눈다.
2. 정복 (Conquer): 가장 작은 단위의 문제를 해결한다.
3. 결합 (Combine): 해결된 작은 문제들의 답을 합쳐서 원래 문제의 답을 구합니다.

• 대표적인 예시: 병합 정렬 (Merge Sort)

---

 다이나믹 프로그래밍 vs. 분할 정복

구분	분할 정복 (Divide and Conquer)	다이나믹 프로그래밍 (Dynamic Programming)
부분 문제의 관계	서로 독립적 (겹치지 않음)	서로 의존적 (겹침)
핵심 아이디어	분할하고, 각각 해결한 뒤, 합친다.	한 번 계산한 결과는 기록(저장)하고 재활용한다.
주요 접근법	재귀를 이용한 하향식 (Top-down)	상향식 (Bottom-up) 또는 하향식+메모이제이션
대표 예시	병합 정렬, 퀵 정렬, 이진 탐색	피보나치 수열, 최장 공통 부분 수열(LCS), 배낭 문제

 

 

그러면 어떤 단계로 문제를 푸는게 좋을까 

 

DP 는 별게 아니다 최적부분구조와 중복되는 문제가 동시에 있을때 그냥 다이나믹 프로그래밍이라고 명명한 것이다 

때문에 핵심은 최적부분구조 -> 이전상태에서 현재상태가 비롯되는지 확인하는것이 가장 첫 단추 이다

 

 

---

 문제 해결을 위한 사고의 흐름

1단계: 문제를 쪼갤 수 있는가? (최적 부분 구조 확인)

가장 먼저 할 일은 "이 큰 문제를 더 작은 문제들의 답으로 표현할 수 있을까?"를 고민

2단계: 쪼갠 문제들이 겹치는가? (중복 부분 문제 확인)

3단계: (DP임을 확인) 테이블 정의하기

•    주어진 상황에 을 표현에 필요한 변수가 몇개 필요한가

4단계: 점화식 구하기

• 현재상태는 이전의 어떤 상태에서 비롯되는가
• 현재 상태가 다음상태에 끼치는 영향

5단계: 초기값 정하기

• 가장 작은 상태의서의 답을 정하기

6단계: 범위초과에유의하며 구현하기

---

 

정도를 DP문제를 처음 접해서 풀게되는 프로세스를 정의 할 수 있을 것이다.