[알고리즘: DP] Dynamic Programming

1. 동적 계획법 개념

DP는 어렵게 접근할 필요가 없이, 전체 문제 내에 작은 규칙들 확인하여 작은 부분 문제들을 해결하고, 이를 통해 전체 문제를 해결하는 방법이다.

 

이때, 동적 계획법을 적용하였을 때 좋은 상황은 아래와 같이 정의할 수 있다.

• 작은 문제들이 규칙을 이루고 있고, 자주 등장한다.
• 큰 문제를 풀기 위해서는 작은 문제들을 풀고 난 이후 해결할 수 있다. 

이와 같이 전체를 보면 해답이 안 보이는 문제 혹은 너무 복잡한 문제를 효율적으로 풀기 위한 방법이라고 보면 될 것 같다.

 

문제를 해결하는 관점에서 보았을 때 두 가지 관점으로 바라볼 수 있다.

• 작은 문제들을 해결함으로써 큰 문제를 해결할 수 있는 최적 부분 구조(optimal substructure)
• 큰 문제로 나누었을 때 작은 문제 규칙이 발생하는 중복 부분 문제(overlapping subproblems)

2. 문제 풀이식 세우기

DP에서 작은 문제를 해결하기 위해 식을 세우게된다.

이때, 작은 문제들의 상황에 맞춰 아래 식들을 정의하여 사용할 수 있다. 

2-1. 점화식

2-2. 재귀식

 

동일한 규칙을 가진 작은 문제들을 해결하고자 할 때 재귀식을 작성하여 효율적으로 풀어낼 수 있다.

이때 재귀식은 아래와 같은 규칙을 정의해야 한다.

• 반복 조건을 설정한다.
• 종료조건을 설정한다.

이와 같은 조건으로 재귀식을 세운다면 문제없이 작은 문제들을 해결하여 큰 문제를 해결해 낼 수 있다.

다만, 재귀함수를 작성할 경우 스택 메모리 자원을 크게 사용할 수 있다는 문제점을 가지고 있다.

 

이를 해결하기 위해서는 아래와 같은 방법들을 고려해 볼 수 있다.

• 반복문 사용
• 메모이제이션 사용

이때, 반복문은 말 그대로 재귀함수를 통해 반복되는 것을 반복문을 활용하는 것으로 변경하여, 추가적인 메모리 활용을 최대한 방지하는 방법이다.

 

그럼 재귀식에서의 메모이제이션은 무엇일까?

2-2-1. 재귀식의 메모이제이션

우리가 재귀식을 활용하여 함수를 작성하면, 해당 재귀가 몇 번 반복되는지 알 수 있는 경우가 존재한다.

 

예를 들어보자면 팩토리얼을 예로 들어볼 수 있다.

만약 팩토리얼 5와 팩토리얼 10을 구하고자 할 때, 메모이제이션을 하지 않는다면, 팩토리얼 10을 구하고자 할 때 5에 대한 연산이 재귀식을 통해 타고 들어가게 될 것이다.

 

하지만, 팩토리얼 5의 연산값을 저장하고 있다면, 이미 연산이 되어있어 팩토리얼 5를 연산할 재귀함수의 메모리를 절약할 수 있다.