[자료구조 알고리즘] Dynamic Programming (동적계획법)

1. 개요

Dynamic Programming, 즉 동적계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것이다. 즉, 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하는 것이다.

 

2. DP를 쓰는 이유

일반적인 재귀 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 것이다.

예를 들어 피보나치 수열을 살펴보자. 피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하면 f(n) = f(n-1) + f(n-2)이다.

위 피보나치 수열 함수 트리를 보면 f(n-1), f(n-2)에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고 이로 인해 호출되는 함수의 횟수는 기하급수적으로 증가한다.

그러나 한 번 구한 작은 문제의 결과값을 저장해두고 재사용한다면 매우 효율적으로 문제를 해결할 수 있게 된다. 시간복잡도를 기준으로 아래와 같이 개선이 가능하다. 

O(n^2) -> O(f(n))으로 개선 (다항식 수준으로, 문제에 따라 다름)

 

3. DP의 사용 조건

DP가 적용되기 위해서는 2가지 조건을 만족해야 한다.

1) Overlapping Subproblems (겹치는 부분 문제)

2) Optimal Substructure (최적 부분 구조)

 

① Overlapping Subproblems (겹치는 부분 문제)

DP는 기본적으로 문제를 나누고 그 문제의 결과값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다. 

 

② Optimal Substructure(최적 부분 구조)

부분 문제의 최적 결과값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 

A -> B까지의 가장 짧은 경로를 찾고자 하는 경우를 예시로 들 때, 중간에 X가 있을 때 (A -> X) + (X -> B)가 많은 경로 중 가장 짧은 경로라면 전체 최적 경로도 A -> X -> B가 정답이 된다.

 

4. DP 사용하기

DP는 특정한 경우에 사용하는 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰일 수 있다. 일반적으로 DP를 사용하기 전에는 아래의 과정을 거쳐 진행할 수 있다.

1) DP로 풀 수 있는 문제인지 확인 2) 문제의 변수 파악 3) 변수 간 관계식 생성 (점화식) 4) 메모하기 (memoization or tabulation) 5) 기저 상태 파악하기 6) 구현하기

 

① DP로 풀 수 있는 문제인지 확인

위에서 쓴 조건들이 충족되는 문제인지를 한 번 체크해보는 것이 좋다. 보통 특정 데이터 내 최대화, 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많다.

 

② 문제의 변수 파악

DP는 현재 변수에 따라 그 결과값을 찾고 그것을 전달하여 재사용하는 것을 거친다. 즉, 문제 내 변수의 개수를 알아내야 한다는 것이다. 이것을 영어로 'state'를 결정한다고 한다.

옐를 들어, 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다. 

 

③ 변수 간 관계식 만들기

변수들에 의해 결과값이 달라지지만 동일한 변수값인 경우 결과는 동일하다. 또한 우리는 그 결과값을 그대로 이용할 것이므로 관계식을 만들어낼 수 있어야 한다. 그러한 식을 점화식이라고 부르며, 그를 통해 짧은 코드 내에서 반복/재귀를 통해 문제가 자동으로 해결되도록 구축할 수 있게 된다.

 

④ 메모하기

변수 간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장해야 한다. 이것을 메모한다고 하여 Memoization이라고 부른다.

변수값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다.

 

⑤ 기저 상태 파악하기

여기까지 진행하였으면, 가장 작은 문제의 상태를 알아야 한다. 보통 몇 가지 예시를 직접 손으로 테스트하여 구성하는 경우가 많다.

피보나치 수열을 예시로 들면, f(0) = 0, f(1) = 1과 같은 방식이다. 이후 두 가지 숫자를 더해가며 값을 구하지만 가장 작은 문제는 저 2개로 볼 수 있다.

해당 기저 문제에 대해 파악 후 미리 배열 등에 저장해두면 된다. 이 경우, 피보나치 수열은 매우 간단했지만 문제에 따라 좀 복잡할 수 있다.

 

⑥ 구현하기

개념, DP를 사용하는 조건, DP 문제를 해결하는 과정도 익혔으니 실제로 어떻게 사용할 수 있는지를 알아보고자 한다. DP는 2가지 방식으로 구현할 수 있다.

1) Bottom-Up (Tabulation 방식) -> 반복문 사용

2) Top-Down (Memoization 방식) -> 재귀 사용

 

① Bottom-Up 방식

이는 아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식이다.

메모를 위해 dp라는 배열을 만들었고 이것이 1차원이라 가정했을 때, dp[0]가 기저 상태이고, dp[n]을 목표 상태라고 하자. Bottom-up은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.

그런데 Tabulation은 뭘까? 반복을 통해 dp[0]부터 하나하나씩 채우는 과정을 'table-filling'하며, 이 Table에 저장된 값에 직접 접근하여 재활용하므로 Tabulation이라는 명칭이 붙었다.

 

② Top-Down 방식

이는 dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과값을 재귀를 통해 전이시켜 재활용하는 방식이다. 이 때, 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있던 내역을 꺼내서 활용하면 된다. 그래서 가장 최근의 값을 메모해 두었다고 하여 Memoization이라고 부른다.

 

 

이 포스팅은 https://hongjw1938.tistory.com/47을 참고하여 작성하였습니다.