[BaekJoon/백준] 1149번 / 순열조합은 동적계획법인가? | 복습 1회 완료

이 문제는 혼자 못 풀었다. 다른 분의 코드를 참고한 뒤 풀었다.

 

처음에 내가 구현한 코드는 아래와 같다. 재귀함수를 사용했다.

#include <stdio.h>

int arr[1000][3];
int memo[1001];
int N;

int min = 1000000;

void print_count() {
    int result = 0;
    for(int i = 0; i < N; i++) {
        result += arr[i][memo[i+1]-1];
    }
    if(min > result)
        min = result;
}
void rgb(int count) {
    
    if(count > N) {
        print_count();
        return;
    }
    
    for(int i = 1; i < 4; i++) {
        if(!(memo[count - 1]==i)) {
            memo[count] = i;
            rgb(count + 1);
            memo[count] = 0;
        }
    }
    
}

int main() {
    scanf("%d", &N);
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < 3; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    
    rgb(1);
    printf("%d", min);
     
}

순열/조합 형식처럼 하나씩 뽑아나가는 방식이고, 재귀함수로 구현했다.

정답이 47퍼센트까지 올라갔다가, 시간초과로 실패했다.

 

 

재귀함수로 푸는 방식이 아닌 것 같아서, 포문으로 돌려봤으나 피보나치 같은 경우의 수가 한 가지인 알고리즘은 가능할 것 같은데 이런 뽑기는 재귀가 꼭 필요할 것 같았다.

 

하지만 다른분들의 코드를 참고한 뒤 아래와 같이 코드를 구성할 수 있었다.

#include <stdio.h>
#define MIN(a,b) ((a<b)?a:b)

int d[1001][3];

int main() {
    int N, R, G, B;
    
    scanf("%d", &N);
    
    // d 배열은 1인덱스부터 시작. 각 배열의 요소값은, 'i번째 자리에 R/G/B 값을 칠하는 데의 최솟값'
    // 1인덱스부터이므로 d[1][0] = 가장 첫 줄 R 값.
    for(int i = 0; i < N; i++) {
            
        scanf("%d %d %d", &R, &G, &B);
        
        d[i+1][0] = MIN(d[i][1], d[i][2]) + R;
        d[i+1][1] = MIN(d[i][0], d[i][2]) + G;
        d[i+1][2] = MIN(d[i][0], d[i][1]) + B;
    }
    
    printf("%d", MIN(d[N][0], MIN(d[N][1], d[N][2])));
}

재귀를 사용하지 않고도, 포문으로 구성할 수 있었다.

d 배열은 ' i번째 자리에 R/G/B 값을 칠하는 데의 최솟값'으로, i번째 자리 이전의 자리들의 결과를 참고하여 풀어나간다.

d 배열은 인덱스 1부터 시작하게 했으며, 그러므로 마지막 인덱스인 d[N][0], d[N][1], d[N][2] 에는 각각

마지막 자리가 R/G/B로 칠해졌을 때의 결과값으로 결산이 된다.

 

다른사람들은 너무 쉽다고 하는데 ㅠ 난 너무 어려웠다..

 

 

 

 

문제를 풀어나가면서 궁금증이 하나 생겼었다. 첫번째 코드에서는 memo[count - 1] 방식을 사용하기 때문에, 이전의 함수 결과를 다시 호출하므로 '중복되는 함수의 호출을 방지하기 위해 메모이제이션을 도입'했다고 볼 수 있다. (함수 1에서 함수 2로 갔는데, 함수 2에서 다시 함수 1의 결과를 필요로 하므로)

 

그런데 '일반적인 순열 / 조합 문제에서, 뽑아 나갈 때 마다 체크하는 배열들도 과연 메모이제이션이라고 볼 수 있을까?' 라는 궁금증이 생겼다. -> 해당 코드 예시 hevton.tistory.com/244

 

처음에는 둘의 느낌이 너무 다르기 때문에 아예 아니라고 확신했었다. 사실 아직도 헷갈리긴 한다 ㅋ..

 

메모이제이션은, 문제를 부분 문제들로 쪼개는 과정에서 부분문제들이 중복되면 그 각각을 매번 연산하지 않도록, 결과값을 한번 저장해놓았다가 재사용하는 것으로 알고 있는데, 위 링크와 같은 함수에서 check배열 같은것도 메모이제이션이라고 해줘야하나..싶었다.

 

하지만 조금만 더 생각해보면, 둘은 관련이 좀 있었다.

 

예를들면, h(int n) { return h(n - 1) + h(n - 2) } 가 있을 때,

h(4)의 값을 구하려면, h(3) - h(2)의 값을 구해야하고,

h(3)을 구하려면 h(2) - h(1)을 구해야 한다. 벌써부터 중복되는 함수가 보인다.

이 때의 h(2) 같은 연산의 중복을 피하기 위해서 메모이제이션을 사용한다. - 이게 메모이제이션의 확실한 개념, 예시.

 

그리고 순열/조합처럼 뽑아가는 경우는 h(4)가 호출되었을 때 h(3)까지 뽑아놨던 행태를 참조하는 식이다.

 -> 이렇게보면 비록 부분문제의 '중복' 이라고 보기는 애매할 수 있으나, h(1) -> h(2) -> h(3) 으로 올라가면서 한 자리씩 뽑는 과정에서, 각 자리에선 이전의 함수들이 저장해놨던 뽑은 경우를 참조해야한다(함수1에서 함수2로 갔는데, 함수 2에서 다시 함수1의 결과를 필요로 함)

이를 토대로 어떻게 보면 부분문제의 중복이 매 순간 일어나고, 그 결과를 미리 캐싱하여 메모이제이션을 사용하고 있다고 봐도 될 것 같다는 생각이 들었다. ( 느낌은 좀 다른 것 같아서 애매하긴하지만.. 메모이제이션의 측면이라고 봐도 될 것 같다. 하지만 동적계획법에서 설명하는 메모이제이션과의 느낌은 확실히 다르다 ㅠ )

 

함수의 결과와 관련된 값들을 집어넣고, 나중에 필요한 상위함수에서 이를 참조하고 있는 것이다.

 

그리고 위의 두 번째 정답 코드에서는, i번째 를 R로 뽑기위해(d[i][0]), 이전에 이미 실행했던 i - 1 함수의 결과값을 참조하는 것을 볼 수 있고(함수1에서 함수2로 갔다가 함수2에서 함수1의 결과를 필요로함),

이에 더해 결정적으로 [i][0] [i][1] i[2] 가 여러차례 '중복'적으로 호출되기 때문에 메모이제이션이라는 것을 알 수 있다.

 

 

결국, 위 링크도 메모이제이션의 한 측면이라고 볼 수 있을 것 같다.

F(n) = F(1)~F(n-1)의 뽑은 결과를 참조해서 뽑아야함

 

 

 

정말 정말 긴 시간동안 이것이 메모이제이션에 해당되는지 해당되지않는지를 찾아봤다.

인터넷에 올라와있는 메모이제이션의 예는 모두 피보나치 뿐이여서 자료찾기가 힘들었다.

 

아직도 헷갈리긴 하는데, 일단 확실한 건, 문제가 부분문제들로 쪼개지는 과정에서 부분문제들이 중복적으로 존재하여, 같은 문제를 두 번 이상 다시 풀어줘야 할 때 메모이제이션을 사용하는 것이고, 이를 생각했을 때 순열/조합의 check 배열은 A(1) -> A(2) -> A(3) 으로 올라갈수록 한 자리씩 뽑게 되지만 각 뽑는 함수에서 이전에 뽑는 함수들의 결과를 다시 참고해야 한다는 점에서 메모이제이션의 한 측면으로 봐도 될 것 같다.

(1~4 번쨰 값을 뽑고, 마지막 5번째 값을 뽑는다고 볼 때, 5번째를 뽑기 위해서 1~4번째 함수에서 뽑은 값들을 다시 확인해줘야 함)

 

이렇게 정리했지만, 사실 아직도 이게 메모이제이션이 맞는지..(메모이제이션보다는 뭔가 그저 최적부분구조 기반 동작일 뿐인 것 같기도 하고) 싶다. 사람들마다 설명도 다 달라서 해결되지가 않는다 ㅜ.ㅜ 일단 이 글에서 확실한건, 문제가 부분문제들로 쪼개지는 과정에서 부분문제들이 중복적으로 존재하여 같은 문제를 두 번 이상 다시 풀어줘야 할 때 메모이제이션을 사용하는 것이고, 피보나치 수열 같은 게 부분문제들이 중복적으로 분포되어 있는 대표적인 예시인 것ㅜ  (kimdohyeon.tistory.com/43 )

 

 

틀린 부분이 있다면 제발 지적부탁드립니다 ㅜ.ㅜ

 

 

 

---

2021.02.23 복습

다시 풀었다. 음 풀이 전에, 위에서 내가 이전에 풀었던 순열조합 코드가 동적계획법인지에 대해 의문했던 내용이 있는데 이제는 조금 더 정확하게 말할 수 있을 것 같다. 동적계획법이라고 말하기 어렵다. 동적계획법은 중복되는 부분문제에 대한 점화식 느낌이 있다.

둘을 다른 것으로 바로볼 필요가 있다. ( 참고 : www.acmicpc.net/board/view/61375#comment-106705)

 

다시돌아와서, 1149번을 다시 푸는 데 있어 "틀렸습니다"가 반복되었다.. 내 딴에는 아무리봐도 맞는코드인데 자꾸 틀렸다고 해서 어이가 너무 없었다.. 문제점은, arr 배열에 값들이 다 정확히 들어가 있는데, 이 세 값중 최솟값을 구해야 하는 MIN(MIN(a,b),c) 과정이 올바르게 진행되지 않았다. 즉 딴건 다 문제없는데 MIN이 중첩되어 세 가지 수 중 최솟값을 구하려 할 때 올바른 최솟값이 도출되지가 않았다. 이거 때메 한참 헤맸는데,, 결국 매크로 함수를 정의할 때 코드 전체를 괄호로 한번 더 감싸주니 해결되었다..

#define MIN(a,b) (a<=b)?a:b
->
#define MIN(a,b) ((a<=b)?a:b)

크게 괄호로 안감싸준게, MIN을 중첩하여 사용함에 있어서 문제가 되었다..
MIN을 중첩하지 않을 때에는 결과에 문제가 없었기에 몰랐다.

이렇게 바꿔주니 해결되었다...ㅜㅜ 매크로 함수가 중복하여 사용될 때를 대비해서 이렇게 전체 코드를 한번 더 감싸주는게 안전하겠다..

// 풀이 : N - 1 번째의 최솟값 + 자기자신값 = arr[N][0~2]. 그리고 그렇게 얻은 0~2중에 최솟값이 진정 최솟값. (단, 색 안겹치게 지정)
#include <stdio.h>
#define MIN(a,b) ((a<=b)?a:b)

int N;
int arr[1001][3];

int main() {
    
    scanf("%d", &N);
    
    for(int i = 1; i <= N; i++) {
        scanf("%d %d %d", &arr[i][0], &arr[i][1], &arr[i][2]);
        
        arr[i][0] += MIN(arr[i - 1][1], arr[i - 1][2]);
        arr[i][1] += MIN(arr[i - 1][0], arr[i - 1][2]);
        arr[i][2] += MIN(arr[i - 1][0], arr[i - 1][1]);
    }
    
    printf("%d", MIN(MIN(arr[N][0], arr[N][1]), arr[N][2]));
}