알고리즘 - 동적 계획법(DP, Dynamic Programming)

동적 계획법(DP, Dynamic Programming)

---

동적 계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻한다.

 

동적 계획법의 원리와 구현 방식

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.

2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야 한다.

3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 DP 테이블을 이용한다. 이를 메모이제이션(Memoization) 기법이라고 하고, 시간 복잡도 측면에서 유리하다.

4. 동적 계획법은 탑-다운 방식과, 바텀-업 방식으로 구현할 수 있다.

 

아래의 핵심 이론은 동적 계획법의 기초적인 예제인 피보나치 수열로 설명한다.

동적 계획법 핵심 이론

1. 동적 계획법으로 풀 수 있는지 확인하기.

먼저 큰 문제를 작은 문제로 나눌 수 있고 그 값이 일정한지 확인한다.

피보나치 수열을 예시로 들면

6번째 피보나치 수열을 구하기 위해서는 5번째 피보나치 수열과 4번째 피보나치 수열을 합한다. -- 작은 문제로 나눈다.

5번째 피보나치 수열과 4번째 피보나치 수열을 합했을 경우 항상 일정한 값이 나온다 -- 값이 일정하다.

 

2. 점화식 세우기

논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악해야 하는데 피보나치 수열로 인과 관계를 파악해보면

1번째 ~ 5번째까지 수열을 구했다고 가정하고 6번째 수열에 관한 인과 관계를 파악해보면 5번째 피보나치 수열과 4번째 피보나치 수열을 합해야 된다는 것을 알 수 있다.

인과 관계를 파악하고 점화식을 세우면 -- 6번째 피보나치 수열 = 5번째 피보나치 수열 + 4번째 피보나치 수열 -- 점화식을 만들 수 있다.

점화식을 세우고 나서 일반화 과정을 거쳐 식을 정리한다.

점화식 일반화: 6번째 피보나치 수열 = 5번째 피보나치 수열 + 4번째 피보나치 수열 --> D[N] = D[N - 1] + D[N - 2]

 

3. 메모이제이션 원리 이해하기

부분 문제를 풀었을 때 문제를 DP 테이블에 저장해 놓고 같은 문제가 나올 경우 재계산하지 않고 DP 테이블의 값을 이용하는 것을 의미한다.

DP 테이블 값 이용하기

 

4. 탑 - 다운 구현 방식 이해하기

탑-다운 방식

위에서부터 문제를 파악해 내려오는 방식으로 재귀 함수 형태로 코드를 구현한다.

가독성이 좋고 이해하기 쉽지만, 재귀 함수 형태로 구현되기 때문에 재귀의 깊이가 매우 깊어질 경우 런타임 에러가 발생할 수 있다.

 

5. 바텀 - 업 구현 방식 이해하기

바텀-업 방식

가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식이다.

기본적으로 for 문을 통해서 구현한다.

 

탑 - 다운 방식과 바텀 - 업 방식은 차이점이 거의 없고 본인이 좀 더 편한 방식이나 문제에 따라 두 방식 중 1개를 선택해 사용하면 된다.