[C++] 프로그래머스 - 도둑질 - DP Top-Down 방식에 대한 고찰

평소같이 기계적으로 프로그래머스 코딩테스트를 풀다가.. 벽에 부딪혔다. 나와 같은 실수를 하는 사람들을 위해 글을 남겨보겠다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/42897

프로그래머스

 

풀이

문제는 평범한 DP문제였지만 생각해야 할 점은 집이 원형으로 이루어져 있기 때문에 이를 선형 자료구조인 vector로 다루기 때문에 이 점만 조심하면 된다.

따라서 까다로운 조건인 첫번째 집을 선택했을 때에 마지막 집을 포함하지 않아야 한다는 조건만 생각하면서 이를 두가지로 나누어서 풀어주었다.

• DP1[index] - 첫번째 집을 반드시 선택했을때에 첫번째 집에서 index번째 집까지의 최대값
• DP2[index] - 첫번째 집을 반드시 선택하지 않았을때에 첫번째 집에서 index번째 집까지의 최대값

위와 같이 두가지 경우로 나누고 DP1과 DP2에서 둘 중 큰 값을 정답으로 해주도록 설계하였다.

 

위와같이 DP를 설계하면 점화식은 다음과 같은 방법을 생각해보면 된다.

결국 첫번째 집에서 index번째 집까지의 최대값은

1. index번째 집이 포함이 되고 + 첫번째 집에서 index-2번째 집까지의 최대값(index가 포함되면 index-1이 포함은 포함되면 안되므로) 
2. index번째 집이 포함이 되지 않고 + 첫번째 집에서 index-1번째 집까지의 최대값.

 

즉, 점화식으로 나타내면

DP[index] = max(DP[index-1],  DP[index-2] + money[index]) 

다음과 같이 점화식을 세우고 호기롭게 풀이를 진행했다.

첫 풀이(오답)

#include <string>
#include <vector>

using namespace std;

vector<int> dp1;
vector<int> dp2;
int s = 0;

int DP1(int index, vector<int>& money)
{
    if(index <= 1)
        return money[0];
    
    if(dp1[index] != 0xF0000001)
        return dp1[index];
    
    int result = -1;
    
    result = max(result, DP1(index-1, money));
    result = max(result, DP1(index-2, money) + money[index]);
    
    dp1[index] = result;
    
    return result;
    
}
int DP2(int index, vector<int>& money)
{
    if(index <= 0)
        return 0;
    
    if(dp2[index] != 0xF0000001)
        return dp2[index];
    
    int result = -1;
    
    result = max(result, DP2(index-1, money));
    result = max(result, DP2(index-2, money) + money[index]);
    
    dp2[index] = result;
    
    return result;
    
}

int solution(vector<int> money) {
    int answer = 0;
   
    s = money.size();
    
    dp1 = vector<int>(s,  0xF0000001);
    dp2 = vector<int>(s,  0xF0000001);
    
    answer = max(answer,DP1(s-2, money));
    answer = max(answer,DP2(s-1, money));
   
    
    return answer;
}

 

정확성 테스트는 모두 맞았고.. 효율성 테스트도 가뿐히 넘길 줄 알았으나.. 결과는

이게 무슨일이오..

 

 

알고리즘이나 코드에서 잘못 된 부분이 있는 줄 알고 찾기 위해서 1시간을 삽질했다... 결국에는 잘못된 부분을 모르겠어서 다른 분들의 풀이도 찾아보았지만... 

 

다른 분들과의 차이점은 대부분 Bottom-Up 방식으로 풀이를 하셨지만 나는 Top-Down 방식으로 풀었다는 것이다. 그래서 처음에는 Top-Down 방식 자체가 잘못되었나 하고 나의 DP Top-Down 인생이 부정당하는 기분이었다..

 

그렇게 좌절하던 중.. 혹시나 하는 마음에 DP를 찾는 순서를 바꿔보았다. 위에 풀이에서는 DP[index-1] 부터 찾고 있지만 DP[index-2]부터 찾도록 순서를 바꿔보았다.

 

두번째 풀이(정답)

#include <string>
#include <vector>

using namespace std;

vector<int> dp1;
vector<int> dp2;
int s = 0;

int DP1(int index, vector<int>& money)
{
    if(index <= 1)
        return money[0];
    
    if(dp1[index] != 0)
        return dp1[index];
    
    int result = -1;
    
  
    result = max(result, DP1(index-2, money) + money[index]);
    result = max(result, DP1(index-1, money));
    
    dp1[index] = result;
    
    return result;
    
}
int DP2(int index, vector<int>& money)
{
    if(index <= 0)
        return 0;
    
    if(dp2[index] != 0)
        return dp2[index];
    
    int result = -1;
    
    result = max(result, DP2(index-2, money) + money[index]);
    result = max(result, DP2(index-1, money));
    
    dp2[index] = result;
    
    return result;
    
}

int solution(vector<int> money) {
    int answer = 0;
   
    s = money.size();
    
    dp1 = vector<int>(s,  0);
    dp2 = vector<int>(s,  0);
    
    answer = max(answer,DP1(s-2, money));
    answer = max(answer,DP2(s-1, money));
   
    
    return answer;
}

혼란스럽다.. 혼란스러워..

 

놀랍게도 DP를 찾는 순서만 바꿨을 뿐인데 오답이 정답이 되었다.

 

문제점

문제는 다음과 같은데

만약 index-1 부터 재귀적으로 DP를 탐색할 경우 그림과 같이 값을 DP의 값을 찾게된다.

빨간선은 miss, 파란선은 저장된 DP를 찾는 흐름

 

만약 N번째 에서 시작하면 빨간선부터 먼저 탐색을 하게 되므로 매번 DP 값이 저장되어 있지 않아(이를 miss라고 부르겠다) miss가 나게 되고 DP를 탐색해야 된다. 즉, N부터 1까지 모든 값을 탐색하기 때문에 사실상.. DP가 의미 없어진다.

결국 index-1을 다 찾고 index-2를 찾는 파란선 부터는 miss가 나지 않고 DP의 효과를 볼 수 있게 된다.

 

만약 index-2부터 탐색을 한다면 어떻게 될까?

빨간선은 miss, 파란선은 정상적으로 DP에 접근

 

물론 엄밀하게 위의 그림처럼 작동하지는 않겠지만 대략적으로 그림과 같이 처음 index-2를 탐색할 때에는 miss가 나게 된다. 하지만 후에 index-1에 대한 값을 찾을 때 같은 miss가 나더라도 후에 계산을 할 때는 이미 앞에서 계산한 dp에 접근하는 횟수가 많아지기 때문에 훨씬 효율적으로 DP를 탐색할 수 있다.

 

이를 더 자세히 알아보기 위해 직접 코드를 실행해보았다. 

이미 계산된 DP에 접근한 횟수(이하 findCount)를 알아보기 위해 코드를 그대로 가지고 와서 실행해보았다.

이런식으로 DP를 찾았을 때 findCount를 늘려줌

size는 3000으로 해주었고 결과는

(좌) index-1부터 계산, (우) index-2부터 계산

결과에서 알 수 있듯이 index-2부터 계산했을 때 이미 계산된 DP에 더 많이 접근한다는 의미이고, 훨씬 효율적인 방법임을 알 수 있다.

 

결론

즉, DP란 결국 한번 계산한 것은 다시 계산하지 않는 다는 것이 큰 장점인데.. 어떻게 보면 cache와 같은 역할을 한다고 보면 된다.

그렇다면 cache를 이용할 때 locality를 고려하는 것처럼 DP(Top-Down 방식)를 이용할 때에도 범위가 더 작은 부분의 DP를 계산하고 나서, 그 후에 범위가 큰 부분을 계산하게 되면, 범위가 큰 부분은 결국 범위가 작은 부분을 포함하게 되므로 훨씬 효과적으로 DP를 계산할 수 있게 된다.

 

사실 이게 싫다면 Bottom-Up으로 푸는 게 좋다.. Bottom-Up은 애초에 재귀적인 방식을 이용하지 않으므로 스택 메모리에 대한 부담도 없다..

 

뭔가 요즘 너무 기계적으로 코딩테스트 문제를 푸는 느낌이었는데.. 매너리즘을 깨주는 좋은 문제였던것 같다. 한 문제를 풀더라도 생각하면서 풀어야 겠다고 느끼는 계기가 된 것 같다!