[10강] DP 알고리즘

---

안녕하세요 Gliver 입니다.

이번 글에서는 DP 알고리즘에 대해 알아보겠습니다.

 

목차

1. DP 알고리즘
2. 실제 문제에서 DP 알고리즘

 

 

접근 방식과 알고리즘

접근 방식과 알고리즘 내용은 브루트 포스 알고리즘, 그리디 알고리즘, DP 알고리즘 글에 동일하게 존재합니다.

 

접근 방식은 문제의 핵심 아이디어를 찾는 것을 도와주는 방법론이고

알고리즘은 문제를 해결하는 과정을 일련의 순차적인 절차로 만들어놓은 방법론입니다.

 

구체적인 예를 들어 설명해보겠습니다.

 

에라토스테네스의 체 알고리즘은 소수(prime number)를 판별하는 알고리즘이고

그리디 알고리즘은 매 순간에서 가장 최선의 선택을 하여 답을 구해내는 알고리즘입니다.

 

에라토스테네스의 체 알고리즘은 언제 쓰면 될까요?

→ 소수(prime number)를 판별할 때 쓰면 됩니다.

 

그리디 알고리즘은 언제 쓰면 될까요?

→ 매 순간에서 가장 최선의 선택을 하여 답이 나올 때 쓰면 됩니다.

 

어떠신가요?

에라토스테네스의 체 알고리즘 같은 경우는 소수(prime number)를 판별할 때 쓰면 되는 반면

그리디 알고리즘의 경우는 "매 순간에서 가장 최선의 선택을 하여 답이 나올 때가 언제인데?" 라는 의문이 들 것입니다.

 

따라서,

에라토스테네스의 체 알고리즘과 같이 쓰이는 상황이 구체적인 알고리즘을 알고리즘이라 생각하고

그리디 알고리즘과 같이 쓰이는 상황이 구체적이지 않은 알고리즘을 접근 방식이라 생각하시면 됩니다.

 

접근 방식에 가까운 알고리즘은 대표적으로

브루트 포스 알고리즘, 그리디 알고리즘, DP 알고리즘 등이 있습니다.

 

이러한 접근 방식에 가까운 알고리즘 문제는

알고리즘을 쓸 수 있도록 상황을 해석하는 능력(문제해결능력)이 중요하게 작용합니다.

 

 

 

1. DP 알고리즘

DP는 Dynamic Programming의 약자로
번역하면 동적 프로그래밍이라는 의미입니다.

동적 프로그래밍(Dynamic Programming)이란 단어와 실제 의미는 상관관계가 없습니다.
동적 프로그래밍을 만든 사람이 단지 Dynamic이란 단어가 멋있어서 지은 이름임.

[DP 알고리즘]

DP 알고리즘은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 기법을 의미한다.

DP 알고리즘은 메모이제이션 기법을 활용하여 중복된 계산을 줄임으로써 답을 구해나간다.
메모이제이션 기법은 동일한 계산을 반복해야 하는 경우에
한 번 계산한 결과를 저장해 두었다가 다시 씀으로써 중복 계산을 방지하는 기법입니다.

 

DP 알고리즘의 핵심은 문제의 재귀적인 구조(관계식)를 찾는 데에 있습니다.
왜냐하면, 문제의 재귀적인 구조를 찾아 중복된 계산을 줄일 수 있기 때문입니다.

저는 DP 알고리즘을 다음과 같이 3단계로 나누어 사용합니다.
1. 문제의 재귀적인 구조 파악
2. 수식으로 표현
3. 초기값 처리

DP 알고리즘은 백문이 불여일견이므로
구체적인 예를 들어 설명하겠습니다.

 

DP 알고리즘 사용 예시

[문제]
동전 1원, 3원, 4원을 가지고 N원을 만들어야 한다.
최소한의 동전의 개수로 N원을 만드는 경우를 출력하는 프로그램을 적성하시오. 답이 여러 가지인 경우 아무 경우나 출력하시오.
(단, N은 1,000,000 이하의 자연수이고, 시간 제한은 1초이다.)
시간 제한이 1초이므로, 약 1억 번의 연산을 넘기면 안 됨.

이 문제는 그리디 알고리즘 글의 "Case2) 그리디 알고리즘 사용 불가능" 에서 다룬 문제입니다.

그리디 알고리즘 글에서 이 문제는 그리디 알고리즘을 사용할 수 없어서
브루트 포스 알고리즘을 이용하여 풀었습니다.

이번 글에서는 DP 알고리즘을 이용해서 풀어보겠습니다.

 

1. 문제의 재귀적인 구조 파악

먼저, 문제의 재귀적인 구조를 찾아봅시다.

어떤 자연수 i를 1, 3, 4의 합을 통해 만들어야 하는 상황입니다.
1, 3, 4의 합을 통해 i가 만들어지기 직전의 상황을 생각해보면
1을 더해서 i가 되는 숫자 (i-1)

3을 더해서 i가 되는 숫자 (i-3)

4를 더해서 i가 되는 숫자 (i-4) 

등의 후보가 존재합니다.

따라서 i를 만들 때
i-1, i-3, i-4의 경우에 대해서만 살펴보면 됩니다.

 

2. 수식으로 표현

이제, 이를 수식으로 나타내 봅시다.

f(i)를 다음과 같이 정의해봅시다.

f(i) : 1, 3, 4의 합으로 i를 만들 때 드는 동전의 최소 개수

위 과정에서 얻은 재귀적인 구조를 수식으로 나타내면 다음과 같이 나타낼 수 있습니다.

f(i) = min(f(i-1), f(i-3), f(i-4)) + 1

즉, i를 만드는 최소 동전 개수는 
i-1을 만드는 최소 동전의 개수
i-3을 만드는 최소 동전의 개수
i-4를 만드는 최소 동전의 개수
중에서 가장 작은 값을 고른 후에 1을 더한다는 뜻입니다.

 

3. 초기값 처리

마지막으로, 초기값을 처리해줍시다.

f(i) = min(f(i-1), f(i-3), f(i-4)) + 1 식에서 i-1, i-3, i-4 가 음수가 될 수 있으니
1 ≤ i ≤ 4 인 경우를 예외처리를 해줘야 합니다.

 

결론적으로

1 ≤ i ≤ 4 인 경우는 일일이 예외처리를 해주고

5 ≤ i ≤ N 인 경우는 도출해낸 수식과 반복문을 이용해서 문제를 해결하면 됩니다.

 

위 풀이를 코드로 구현하면 다음과 같습니다.

 

 

 

이 풀이는 시간 복잡도가 O(N)이므로 시간 초과가 나지 않는 풀이입니다.

 

위 코드를 보면 재귀적인 과정을 거치며 f라는 배열에 값을 저장했습니다.

여기서 f처럼 메모이제이션 기법을 활용하기 위해

값을 저장하는 공간을 DP table이라고 합니다.

 

이 문제의 DP table은 1차원 배열이었지만

문제의 재귀적인 구조가 어떠냐에 따라서 1차원 배열, 2차원 배열 또는 그래프, 트리 등 다양한 형태가 될 수 있습니다.

 

 

 

2. 실제 문제에서 DP 알고리즘

실제 문제에서 DP 알고리즘은
문제를 보고 DP 알고리즘을 쓸 수 있는지 판단하는 게 관건입니다.

DP 알고리즘을 쓸 수 있는지 판단할 때 중요한 것은
문제의 재귀적인 구조(관계식)를 파악하는 것입니다.
문제의 재귀적인 구조를 파악하지 못하면 DP 알고리즘을 사용할 수 없음.

논리에 오류가 없는 재귀적인 구조를 파악했다면
위에서 했듯이 수식으로 표현, 초기값 처리 등을 진행하면 됩니다.

아무리 해도 문제의 재귀적인 구조를 파악할 수 없다면
그 문제는 DP 알고리즘 문제가 아니거나
문제를 재해석해서 재귀적인 구조를 찾아야 하는 문제일 것입니다.

정리하자면, 문제의 상황을 다양하게 재해석해보고
그 재해석한 상황에서 재귀적인 구조를 찾아봅시다.
만약, 재해석을 해봐도 재귀적인 구조를 찾을 수 없다면 다른 풀이를 떠올려야 합니다.

DP 알고리즘은 쓰이는 상황이 구체적이지 않고 (접근 방식에 가까운 알고리즘)
재귀적인 구조를 파악해야 하므로 문제해결능력이 필요합니다.

따라서 이론 학습보단 DP 알고리즘 관련 문제를 풀어보며
재귀적인 구조를 찾는 연습을 많이 해보는 것을 추천드립니다.

 

[관련 문제]

백준 : 계단 오르기 (2579번)

백준 : 2×n 타일링 (11726번)

백준 : 내리막 길 (1520번)

 

 

 

 

---

궁금한 점이나 코멘트는 댓글로 남겨주세요!

 

• 알고리즘 공부법 : https://gliver.tistory.com/6
• 알고리즘 목차 : https://gliver.tistory.com/7