[ 알고리즘 기법 ] DP(Dynamic Programming) 개념 정리

 

DP(Dynamic Programming)란,

• 작은 부분 문제의 정답을 결합해 전체 문제의 정답을 구하는 알고리즘 기법이다.
• DP는 일반적으로 최적화 문제를 해결하기 위한 기법으로 사용된다.
        - 최적화 문제란, 여라가지 가능한 해 중에서 가장 좋은 해를 찾는 문제를 말한다.

 

DP 알고리즘 핵심

중복되는 문제들이 존재한다고 가정해 보자,

DP는 이러한 중복 부분 문제들을 한번만 계산하고, 이후에는 이전에 계산한 값을 이용하여 전체 문제를 해결한다.

 

 

DP 알고리즘 특징

1. 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 최적해를 이용해서 큰 문제의 최적해를 구할 수 있다.
2. 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다.

이러한 특징을 이용하여 DP 알고리즘은 문제의 해를 구하는 과정에서 작은 부분 문제들의 해를 이용하여 큰 문제를 해결한다.

따라서, DP 알고리즘은 보통 작은 크기의 부분 문제들을 해결한 후, 이를 이용하여 큰 문제를 해결한다.

이를 상향식 접근법 이라고 부르기도 한다.

 

 

code로 나타내보자.

DP는 이전에 계산된 값을 저장해두었다가 다시 사용하는 기법이다.

예를 들어서, 피보나치 수열을 계산하는 경우를 생각해보자.

function fibonacci(n) {
  const memo = [0, 1]; // DP 테이블
  
  for (let i = 2; i <= n; i++) {
    memo[i] = memo[i - 1] + memo[i - 2]; // 이전 값들을 이용하여 현재 값을 계산
  }
  
  return memo[n];
}

이 코드에서 memo 배열은 이전에 계산한 값을 저장해두는 DP 테이블이다.

반복문을 통해서 memo 배열을 채워나가면서, 이전 값들을 이용하여 현재 값을 계산한다.

DP를 사용하면 일반적으로 반복문을 중첩하여 구현하게 된다.

이중 반복문을 사용하여 2차원 DP 테이블을 만들어서 문제를 해결하는 경우도 가능하다.

 

정리

DP는 문제를 작은 부분 문제로 나누어 해결하고, 그 부분 문제의 해를 저장하고 재활용하여 전체 문제의 해를 구하는 알고리즘이다.

이 때, 중복되는 부분 문제들이 많이 존재하기 때문에 이를 저장해 놓는 메모리 공간이 필요하는 점이 중요하다.

 

따라서, DP를 구현할 때는, 작은 부분 문제의 해를 저장하는 1차원 또는 2차원 배열을 선언하고, 반복문을 이용하여

작은 부분 문제들을 해결하면서 저장해 나가는 방법을 사용한다.

이 때, 각 부분 문제의 해는 미리 계산하여 저장해 놓거나 필요할 때 계산하여 저장할 수 있다.

 

DP는 매우 다양한 문제에 적용될 수 있으며, 이를 구현하는 방법도 다양하다.

따라서 DP문제를 풀 때는 문제에 맞는 적절한 점화식을 세우고, 이를 이용하여 배열을 채우는 방법도 고민해 보는 것이 중요하다.