다이나믹 프로그래밍(DP) 알고리즘 [심화]

1. DP 알고리즘

• DP 알고리즘은 재귀적인 구조(관계식)를 찾아 문제를 효율적으로 해결하는 알고리즘

• 따라서, DP 알고리즘에 있어 중요한 것은 재귀적인 구조(관계식)를 찾는 것

• 내가 생각한 DP 알고리즘이 타당한지 판단하는 법
• DP 관계식이 타당한가?
: DP 테이블의 정의에 대해 DP 관계식이 논리에 오류가 없어야 한다.
• 초기값을 구할 수 있는가?
: DP 테이블의 초기값을 구할 수 있어야 한다.

• DP 알고리즘의 시간 복잡도 계산
⇒ DP 테이블의 크기 x 한 번 갱신하는 데 걸리는 연산

• 예제) 백준 11048

2. DP 알고리즘을 구현하는 방법

• 재귀적인 구조를 찾았다면, 찾은 구조에 알맞는 DP Table을 완성하면 된다.

• DP Table을 완성하면 답을 구할 수 있으며, DP Table을 완성하는 방법은 크게 두 가지로 나뉜다.
1. Bottom-Up 방식
: 작은 부분부터 완성하는 방식으로, 보통 반복문을 이용하여 DP Table을 완성한다.
2. Top-Down 방식
: 큰 부분(구하고자 하는 값)을 기준으로 DP Table의 필요한 부분만 구하는 방식으로, 재귀함수를 이용한다.

• Bottom-Up 방식과 Top-Down 방식 중에 뭐가 더 좋은가요?
• 대부분의 문제는 두 가지 방식 모두 사용할 수 있으므로 선호하는 방식으로 풀면 된다.
• DP Table 전체를 완성해야 하는 경우에는 Bottom-Up 방식의 풀이가 더 좋다.
• DP Table의 일부만 완성해도 되는 경우에는 Top-Down 방식의 풀이가 더 좋을 수 있다.

3. DP 문제를 잘 풀려면 어떻게 해야 할까?

• DP 문제가 어려운 이유
• DP를 이용하여 문제를 해결하려면 문제의 재귀적인 구조(관계식)를 찾아야 하기 때문이다.
(= 적절한 형태의 DP Table 구조를 설계하는 과정이 DP를 처음 배울 때는 쉽지 않음)
 

• DP 문제를 푸는 실력 키우기
• 문제를 DP로 해석하는 능력을 키워야 함.
• 따라서, 다음과 같은 과정을 여러번 연습하는 것이 필요함.
1. 문제에서 적절한 DP Table 구조를 설계
2. DP 식을 정의하고 타당한지 판단
3. DP 식의 초기값을 구할 수 있는지 판단