다이나믹 프로그래밍(DP) 접근법 및 풀이 전략

이번 글의 목적은 피보나치같은 대표적인 예시로 다이나믹 프로그래밍에 대해 뜯어보기 위함이 아닌
저만의 접근(풀이)방식에 대해서 정리한 글입니다. 도움이 되셨다면 좋겠네요.

도입부

알고리즘 문제를 조금 풀어본 사람의 경우, 문제를 풀다보면 “DP로 풀어야하나?” 라는 감이 올 때가 있습니다.

예를 들자면, 완전 탐색을 요구하는 문제인데 입력이 굉장히 클 경우, 일반적인 DFS, BFS로 풀 수가 없다고 느꼈을 때입니다.

 

아마 동전, 배낭문제와 같이 잘 알려진 문제들에 대해서는 곧바로 풀이를 할 수 있겠지만, 이러한 문제들은 코딩테스트에서 잘 나오지 않죠. 심지어 “DP로 풀어야하나?”라는 생각도 들지않게 나올 때도 있습니다.

“DP로 풀어야겠다!”라고 생각을 해도 좀처럼 풀리지 않을텐데, 이유는 문제마다 공식이 제각각이기 때문입니다.

이번 글에서는 이러한 공식을 찾기위한 저만의 접근법에 대해 정리해보려합니다.

 

다음은 다이나믹 프로그래밍(DP)의 이해를 돕기 위한 키워드들에 대해서 정리해봤습니다.

---

 

키워드 정리

• Top-Down
  • 큰 문제를 작은 문제로 쪼개어 나가면서 문제를 해결하는 방식
  • 재귀 활용
• Bottom Up
  • 점화식이라는 전체 알고리즘을 파악하여 작은 문제로 큰 문제를 해결하는 방식
  • 점화식을 가볍게 설명하자면, 이전 해를 통해 현재 해를 구하기 위한 공식
• 메모이제이션
  • 필요할 때 다시 활용할 수 있게 계산된 부분해를 저장하는 방식
  • 주로 중복 계산을 피하기위해 사용

이후 말하는 접근법들은 해당 문제가 다이나믹 프로그래밍 유형이라고 생각했다는 전제가 깔려있습니다.

 

---

접근법

편의를 위해 아래 예제를 통해 설명하겠습니다. (읽기 전 풀이를 한번 해보시면 좋을 것 같습니다.)

https://www.acmicpc.net/problem/2579

 

DP는 최소를 구하던, 최대를 구하던 결국 특정값 X를 구하는 문제입니다.

우리는 여기서 X를 구하기위한 과정을 생각해야합니다.

예제에서의 특정값은 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값 입니다.

---

TIP 1. 주어진 조건을 보고 행동 가능한 경우의 수를 알자.

특정값을 구하기위해 주어진 조건을 먼저 살펴봐야합니다.

1. 한 번에 한계단 or 두계단
2. 3계단을 연속으로 밟으면 안된다.
3. 마지막 도착계단은 반드시 밟아야 한다.

조건에 의하면 저희가 할 수 있는 행동은 다음과 같습니다.

1. 한계단 상승 (이전 연속된 2개의 계단을 밟지 않았다면)
2. 두계단 상승

간단하게 생각하면, DFS와 같은 완전탐색 방식으로 두 가지의 행동을 수행하면서 최대값을 갱신하면 풀릴 것입니다.

그러나 탐색 과정에서 중복되는 경우의 수를 탐색하는 횟수가 굉장히 많이 나오게되어 비효율적인 풀이가 됩니다. (이 부분은 피보나치 수열의 중복계산을 보면 이해가 쉽습니다.)

---

TIP 2. 특정값을 구하기 위해 어떤걸 메모이제이션?

DP의 핵심은 부분해를 메모이제이션을 함으로써 중복계산을 피하는 것이라고 생각합니다.

그러므로 예제에서 중복 경우의수가 나올 수 있는 부분해를 찾아보겠습니다.

예제에서 완전탐색을 하게 될 경우 나오는 부분해는 특정 계단에 도착했을 때 점수합입니다.

예를 들어, 첫번째 계단에서는 10점이라는 한가지 경우의 수가 나오게 됩니다.

두번째 계단에서는 아래처럼 두 가지 경우의 수가 나오게되고, 올라갈수록 경우의 수는 더욱 많아지게 됩니다.

• 두번 연속 오르게 될 경우 30점
• 두계단 상승할 경우 20점

부분해를 찾았다면 다음은 이 부분해를 기록할 메모이제이션 배열을 만드는 것입니다.

각 계단을 배열의 인덱스로, 계단에서 나올 수 있는 점수합을 원소로 1차원 배열로 만들어보겠습니다.

 

이를 1차원 배열로 나타내면 아래와 같습니다.

1계단	2계단	3계단	4계단	5계단	마지막 계단
최대 점수	최대 점수	최대 점수	최대 점수	최대 점수	최대 점수

---

중간점검

1. 문제에 나오는 조건을 통해 할 수 있는 행동을 찾자.
2. 완전탐색하는 방법을 찾고, 중복계산이 될 수 있는 부분해를 찾자.
3. 부분해에 대한 배열을 그리자.

여기까지는 쉽게 할 수 있을거라 생각합니다.

이 다음은 부분해를 구하기위한 점화식을 도출하는 것입니다.

---

TIP3. 각 원소는 어떤값을? 중복경우의 수 중 어떤값을 기록?

예제에서는 최대값을 구하는 것이 목표입니다.

또한 각 부분해(i번째 계단에서의 점수합)는 중복계산 경우의수중에 특정한 값을 기록을 해야합니다.

그리고 구해진 부분해는 이 다음 중복계산을 피하기 위해 재활용됩니다.

 

조금 감이 잡히나요?

 

포인트는 중복계산을 피하기위해 부분해의 최적해를 재활용 해야한다는 것입니다.

최대값을 구하기 위해서 재활용되는 부분해 또한 경우의 수 중 최대값이 되어야 한다는 것을 의미합니다.

피보나치의 경우에는 중복계산 경우의 수들이 모두 같은 값을 가지고 있습니다.
이럴 경우 어떤 경우의수를 활용해야할지 생각할 필요없이, 하나의 결과값을 기록하면 되겠죠.

 

여기까지 왔다면 DP풀이를 위한 첫걸음을 뗐습니다. (시작이 반이라는말이 있죠)

이제는 최적해를 구하기위한 방법에 대해 생각해봐야할테죠.

---

TIP4. i번째 원소의 최적해는 i이전의 값을 통해서

정의부터 내리자면 i번째 원소는 i이전의 행동을 통해서 나오는 값입니다.

i이전에 어떤 경우의수를 거쳐 왔냐에 따라서 i의 값은 달라지게 됩니다.

우리는 i에서의 최대값만을 탐색해왔습니다.

그럼 경우의 수 갈래를 고려하지않고, 그저 그 값을 활용하기만 하면 i번째 값은 정해지게 되겠죠.

 

글로는 이해가 잘 되지않을거라 생각합니다.

“i번째 최적해는 i이전의 최적해를 활용”한다는 점만 머리에 놔두시고 아래 설명을 보면 좋을 것 같습니다.

---

예제 : i번째를 구하기위해 처음부터 따라가보자!

첫번째 계단의 경우 나올 수 있는 경우의 수는 한가지입니다.

시작지점에서 한계단 상승했을 경우 → 그럼 최적해는 10이 되겠죠. 다른 값이 없으니까요.

 

그럼 두번째 계단의 경우 나올 수 있는 경우의 수는 어떻게 될까요?

두계단 상승

한계단씩 상승

위 그림처럼 두가지 경우의 수가 나오게됩니다.

30이라는 부분해를 구하기위해서 1번째 계단에 올랐을 경우를 계산해야합니다.

그러나 저희는 위에서 이미 첫번째 계단에서의 최적해를 구한적이 있죠.

기록했던 메모이제이션값을 활용하여 현재 계단의 값을 더해주기만 하면 해당 경우의 수가 구해질 것입니다.

### 
점화식을 생각하면서
i번째 계단을 통해서 다음 i이후의 값을 고려하는 것이 아닌,
i이전의 값을 통해서 i번째 계단의 최적해를 도출한다는 점을 이해했으면 좋겠습니다.

---

TIP5. 간단한 점화식부터

제가 강조했던 “i번째 최적해는 i이전의 최적해를 활용”한다는 내용이 아직 있으신가요?

 

그럼 여기서 우리는 i번째 원소를 구하기위한 점화식을 써볼 수 있습니다.

편의상 메모이제이션 배열은 dp, 계단 별 점수 입력값은 stairs라고 두겠습니다.

dp[i] = MAX(dp[i-1] + stairs[i], dp[i-2] + stairs[i])

이 점화식을 말로 풀어보자면,

현재 계단의 값은 1계단 전에서 왔을 경우와 2계단 전에서 왔을 경우중 최대값이 됩니다.

각각의 값은 이전에 기록했던 최적해를 재활용하는 것이죠.

 

자 우리는 간단한 점화식을 작성할 수 있었습니다.

그러나 저 점화식으로는 문제가 생기게 되는데요. 한가지 빠트린 조건이 있었죠?

조건 : 3계단을 연속으로 밟으면 안된다.

이 조건을 통해 나올 수 있는 경우의 수는 달라지게 됩니다.

DP문제에서 조건을 잘 이해해야하는 이유이기도 합니다.

 

그럼 저 조건을 어떻게 점화식에 녹여낼 수 있을까요?

---

TIP6. 조건을 점화식에 녹여내기위한 사고방식

저의 방식은 i번째 원소를 기준으로 거꾸로 돌아보며 조건을 어기는 경우가 있는지 보는 것입니다.

구체적으로 “이전해를 재활용했을 때 문제가 생길수 있는가?”를 생각하는 것입니다.

 

이해가 잘 되지 않을텐데요.

예제를 통해서 설명을 해보겠습니다.

---

예제 : 4번째 계단에서 거꾸로 돌아보자.

4번째 계단의 값을 구하기 위해서 한번 생각해볼까요?

4번째 계단

저희는 4번째 계단의 최적해를 구하기위해 2번째와 3번째 계단의 값을 재활용 한다는걸 알고 있습니다.

2번째 부분해부터 생각해보겠습니다.

두번째 계단에서 4번째 계단으로 왔다는 것은 두 계단 상승의 경우를 의미합니다.

이 경우 위 조건을 못지킬 경우는 없으므로 그대로 활용해도 될 것 같네요.

 

그럼 3번째 부분해를 생각해볼까요.

세번째 계단에서 4번째 계단으로 왔다는 것은 한 계단 상승의 경우를 의미합니다.

이 경우 아래와 같이 두가지 경우가 나올 수 있는데요. 파란색의 경우 조건을 어기게 되는 경우가 발생하는걸 볼 수 있습니다.

이러한 조건을 어길 수 있는 부분해가 나오지 않게 점화식을 작성해야 올바른 답이 도출되겠죠.

그럼 어떻게 점화식을 바꿔볼 수 있을까요?

 

이 부분이 DP문제를 풀 때 굉장히 힘든 점이라고 생각합니다.

날마다 반짝하고 떠오를때도 있고, 아무리 붙잡고 있어도 안될 때가 있는데요.

---

TIP7. 이렇게하면 되지 않을까? (무한 생각)

저는 일단 i번째가 위 파란색과 같은 경우가 나오지 않도록 할 수 있는 방법에 대해 생각합니다.

저의 당시 생각을 주절주절 풀어보겠습니다.

“3번째 계단의 최적해는 2번째 계단에서 왔을 수도, 첫번째 계단에서 왔을 수도 있는데….”
“두번째 계단에서 왔을 경우 조건을 어기는거잖아..”
“그럼 두번째 계단에서 왔을 경우를 없애는 방법이 있을까?”
“그럼 애초에 2번째 계단의 최적해를 사용하지 않고, 1번째 계단의 최적해를 사용해서 구해볼까?”
“1번째 계단에서 두계단 상승한 경우만을 사용해야하니까….”
“1번째 계단의 최적해와 3번째, 4번째 계단의 값을 더하면 위와같은 경우의 수만 나올수도?”

네. 그냥 무한생각 하는것이 저의 방식입니다. (저의 블로그 도메인도 infinitecode입니다 :/)

이 부분만큼은 많은 DP문제를 경험해보는 것이 실력이 늘 수 있다고 생각해요.

 

돌아와서, 위처럼 조건을 어기는 경우가 나오지 않게 점화식을 생각해보았다면 검증을 해야합니다.

---

검증은 어떻게?

제일 좋았던 방법은 특정 i번째까지 점화식을 통해 값을 구하는 과정을 그려보는것입니다.

값을 구하는 과정에서 중복계산만 제거가되고, 가능한 모든 경우의 수의 비교가 이루어진다면 검증은 자동으로 되겠죠.

 

이제 검증까지 거쳤다면 점화식을 코드로 작성할 시간입니다.

기존코드 : dp[i] = MAX(dp[i-1] + stairs[i], dp[i-2] + stairs[i])

기존에 점화식에서 i-2의 부분해를 사용하지 않는 저의 점화식을 녹여봅시다.

수정된 코드 : dp[i] = MAX(dp[i-1] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i])

---

TIP10. 전처리 가능한 부분은 하고 시작하자.

DP특성 상 이전해를 재활용해야하기 때문에 i-1 또는 i-2라는 원소에 접근해야할 때가 있는데요.

for문을 0부터 시작한다면 ArrayIndexOutOfBoundsException 를 마주치게 됩니다.

 

저는 때에 따라서 전처리를 두가지 해주는데요.

1. 1번째 원소의 값을 바로 활용해야하는 경우

: 이 경우에는 특정값을 초기화 후 반복문을 수행합니다.

 

2. 최소값을 구하는 경우

: 이 경우에는 문제마다 조금 다르긴 하지만, 최소값 비교를 위해서 DP배열을 최대값으로 초기화 후 반복문을 수행하는 편입니다.

 

이외에는 편의를 위해 DP배열 길이를 조절하는 경우가 있습니다.

인덱스 에러를 피하기위해 DP배열을 늘리고, 1 또는 2에서부터 시작하는 경우가 되겠네요.

 

---

추천문제

"아래로 내려갈수록 어려우니 순서대로 시도하는 것을 추천드립니다."

https://www.acmicpc.net/problem/11048

https://www.acmicpc.net/problem/1446

https://www.acmicpc.net/problem/13398

https://www.acmicpc.net/problem/1520