[고급 알고리즘] Dynamic Programming

1. Dynamic Programming

• 복잡한 문제를 여러개의 문제로 나누어 푸는 알고리즘 입니다.

 

조건

• 부분 문제 반복과 최적 부분 구조를 가지고 있는 문제에 적용할 수 있습니다.

 

중복 부분문제 구조 (Overlapping subproblems)

• 문제를 작은 부분 문제들로 나누었을 때, 이러한 부분 문제들로 구성된 현상입니다.
• Memoization: 작은 문제들의 해를 저장 및 재사용함으로써 중복계산을 방지할 수 있습니다.

 

최적 부분문제 구조 (Optimal substructure)

• 전체 문제의 해가 부분 문제의 해로부터 구성될 수 있는 성질을 의미합니다.
• 부분 문제와 전체 문제간에 의존성이 존재합니다.
  
  • 이러한 의존성을 점화식으로 도출하여 전체 해를 작은 문제의 해의 조합으로 표현할 수 있습니다.
  • 작은 문제부터 해결해 나가면서, 점차적으로 문제의 해를 도출해 나갑니다.
• 부분 문제의 해를 이용하여 전체 문제의 해를 구할 수 있습니다.

 

풀이 방식

top-down (recursion)

• 지연 계산
  • 문제를 해결하는 과정에서 하위 문제가 필요할 때만, 특정 하위 문제를 계산하고 결과를 저장하여 재사용합니다.
• 장점
  • 필요한 하위 문제만 계산하므로 불필요한 계산을 줄일 수 있습니다.
  • 재귀적으로 작성하므로, 직관적이고 이해하기 쉬운 코드를 작성할 수 있습니다.
• 단점
  • 재귀 호출 시, 오버헤드가 발생합니다.
  • 깊은 재귀로 스택 오버플로우 에러가 발생할 수 있습니다.

 

bottom-up (iteration)

• dp 테이블 사용
  • 가장 작은 하위 문제부터 시작하여 차례대로 모든 하위 문제를 해결해 나갑니다.
  • 이 때 계산한 하위 문제의 해를 dp 테이블에 저장하여 전체 문제를 구성할 때까지 재사용합니다.
• 장점
  • 누락없이 모든 하위 문제를 해결할 수 있습니다.
• 단점
  • 필요하지 않은 하위문제의 계산까지 실행하므로, 필요한 해만 구할 경우 비효율적일 수 있습니다.

 

2. 적용 과정

문제 분할

• 주어진 문제를 작은 부분 문제로 나눕니다.

 

점화식 도출

• 각 부분 문제와 전체 해 간의 관계를 나타내는 수학적 식을 정의합니다.

 

메모이제이션 테이블 정의

dp 배열 정의

• 부분 문제의 해를 저장할 자료구조를 정의합니다. (크기, 차수) 

 

인덱스 의미 정하기

• dp 배열의 각 인덱스가 어떤 의미를 가질 지 정의합니다. (점화식과 밀접하게 연관됩니다)

 

초기값 정하기

• 점화식의 계산을 시작하기 위한 초기값을 설정합니다. (반복적인 연산의 기점이 됩니다)

 

부분 문제 해결 및 저장

결과 재사용

결과 조합 및 전체해 도출

 

 

 

출처

• Wiki - 동적계획법
• BaaaaaaaarkingDog - Dynamic Programming