1. DP 알고리즘
•
DP 알고리즘은 재귀적인 구조(관계식)를 찾아 문제를 효율적으로 해결하는 알고리즘
•
따라서, DP 알고리즘에 있어 중요한 것은 재귀적인 구조(관계식)를 찾는 것
•
내가 생각한 DP 알고리즘이 타당한지 판단하는 법
◦
DP 관계식이 타당한가?
: DP 테이블의 정의에 대해 DP 관계식이 논리에 오류가 없어야 한다.
◦
초기값을 구할 수 있는가?
: DP 테이블의 초기값을 구할 수 있어야 한다.
•
DP 알고리즘의 시간 복잡도 계산
⇒ DP 테이블의 크기 x 한 번 갱신하는 데 걸리는 연산
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 방식의 풀이가 더 좋을 수 있다.
•
Bottom-Up
◦
반복문을 이용하여 갱신하므로 초보자 입장에서 코드를 이해하기 쉽다.
◦
DP Table의 값을 갱신하는 과정에서 접근하는 순서에 유의할 필요가 있다.
(즉, 아직 갱신되지 않은 부분의 값을 사용하면 안 된다.)
•
Top-Down
◦
재귀함수 구현이 익숙하지 않다면, 코딩을 하는 데에 어려움이 있을 수 있다.
◦
DP Table의 값은 재귀적인 과정을 거치며 필요한 부분만 접근하기 때문에 순서를 따로 고려할 필요는 없다.
3. DP 문제를 잘 풀려면 어떻게 해야 할까?
•
DP 문제가 어려운 이유
◦
DP를 이용하여 문제를 해결하려면 문제의 재귀적인 구조(관계식)를 찾아야 하기 때문이다.
(= 적절한 형태의 DP Table 구조를 설계하는 과정이 DP를 처음 배울 때는 쉽지 않음)
•
DP 문제를 푸는 실력 키우기
◦
문제를 DP로 해석하는 능력을 키워야 함.
◦
따라서, 다음과 같은 과정을 여러번 연습하는 것이 필요함.
1.
문제에서 적절한 DP Table 구조를 설계
2.
DP 식을 정의하고 타당한지 판단
3.
DP 식의 초기값을 구할 수 있는지 판단
•
DP는 최적해를 구하는 알고리즘이므로 다음과 같은 경우에 많이 사용된다.
◦
~한 경우의 수를 구하시오.
◦
~의 최소값을 구하시오.
◦
~의 최대값을 구하시오.