FENCE 문제 실행 시간 질문드립니다.

  • kwonmha
    kwonmha

    종만북을 보면서 FENCE 문제를 풀고 있습니다.
    분할 정복 알고리즘을 적용하는 연습을 하고 있습니다.
    그런데 제가 푼 방식이 책에 있는 코드와 거의 비슷한데
    실행시간이 엄청 차이납니다.
    제 코드 : https://algospot.com/judge/submission/detail/372649
    2000ms

    책의 코드 : https://algospot.com/judge/submission/detail/372680
    60ms

    아무리 들여다 봐도 모르겠어서 질문드립니다.
    왜그런지 알겠는 분은 답변 주시면 감사하겠습니다.

    핵심 코드는 아래와 같습니다.
    양쪽 부분에 걸쳐 있는 넓이를 찾아가는 과정입니다.
    저는 오른쪽으로 확장했을 때의 최소 높이와
    왼쪽으로 확장했을 때의 최소 높이를 비교해 방향을 선택했습니다.
    그리고 한 쪽의 끝에 도달했을 때 배열 이탈을 막기 위해 rightMin 또는 leftMin에 0을 넣어줬습니다.
    이러면 자동적으로 반대편 높이가 크게 되어 그 쪽으로 확장합니다.

    제 코드

    while (start < left || right < last){
        width++;
        int rightMin = right == last ? 0 : min(minHeight, fence[right + 1]);
        int leftMin = left == start ? 0 : min(minHeight, fence[left - 1]);
        if (rightMin >= leftMin){
            right++;
            minHeight = rightMin;
        }
        else{
            left--;
            minHeight = leftMin;
        }

        ret = max(ret, minHeight * width);
    }

    책의 코드

    while (start < left || right < last){
        width++;        
        if (right != last && (left == start || fence[right + 1] >= fence[left - 1])){
            right++;
            minHeight = min(minHeight, fence[right]);           
        }
        else{
            left--;
            minHeight = min(minHeight, fence[left]);
        }

        ret = max(ret, minHeight * width);
    }

    전체 코드 내용

    #include <cstdio>

#pragma warning(disable:4996)

#define MAX 20000

using namespace std;

int getMin(int fence[MAX], int from, int until){
    int min = 20000;
    for (int i = from; i <= until; i++){
        if (fence[i] < min) min = fence[i];
    }
    return min;
}

int max(int a, int b){
    return a >= b ? a : b;
}
int min(int a, int b){
    return a >= b ? b : a;
}

void initFence(int fence[MAX]){
    for (int i = 0; i < MAX; i++){
        fence[i] = 0;
    }
}

int cutFence2(int fence[MAX], int start, int last){ // last 포함
    if (last == start) return fence[start]; 
    int ret;
    int half = (start + last) / 2;
    ret = max(cutFence2(fence, start, half), cutFence2(fence, half + 1, last));

    int left = half, right = half + 1;
    int minHeight = min(fence[left], fence[right]);
    int width = 2;
    ret = max(minHeight * width, ret);
    /* 다른 부분*/
    while (start < left || right < last){
        width++;
        int rightMin = right == last ? 0 : min(minHeight, fence[right + 1]);
        int leftMin = left == start ? 0 : min(minHeight, fence[left - 1]);
        if (rightMin >= leftMin){
            right++;
            minHeight = rightMin;
        }
        else{
            left--;
            minHeight = leftMin;
        }

        ret = max(ret, minHeight * width);
    }
    /* 다른 부분*/

    return ret;
}

int main(void){

    int fence[MAX]; 
    int tc;
    scanf("%d", &tc);

    for (int i = 0; i < tc; i++){
        int fences;
        initFence(fence);
        scanf("%d", &fences);
        for (int j = 0; j < fences; j++){
            scanf("%d", &fence[j]);
        }
        printf("%d\n", cutFence2(fence, 0, fences - 1));
    }
    return 0;
}

    8년 전
2개의 댓글이 있습니다.
  • arubirate
    arubirate

    음...제 생각인데, 핵심코드 상에서 kwonmha 님의 코드는 비교를 적어도 3번하는데다가 무조건 대소비교를 한 번 합니다.

    하지만 책의 코드는 동치비교를 하고 나서, 만족(1) 또는 만족하지 못 할경우(2)에만 대소비교를 합니다.

    그 부분에서 속도차가 좀 나는게 아닌가 싶습니다.

    https://en.wikipedia.org/wiki/Short-circuit_evaluation

    여기를 한 번 읽어보시면 도움이 될 거 같습니다.


    8년 전 link
  • kwonmha
    kwonmha

    답변 감사합니다.
    그런데 short circuit evaluation과 관련해서 제가 책의 비교 코드를

    (fence[right + 1] >= fence[left - 1] || left == start ) && right != last

    (right != last && ( fence[right + 1] >= fence[left - 1]) || left == start)

    이런 식으로 바꿔도 실행 시간이 비슷한 거 보면

    제 코드 상의
    int rightMin = right == last ? 0 : min(minHeight, fence[right + 1]);
    int leftMin = left == start ? 0 : min(minHeight, fence[left - 1]);

    부분이 문제인가 싶시고 하네요...

    그래서 분석을 해봤는데
    제 코드 상에서는
    min() X 2, 비교 연산 3번이 들어가고

    책의 코드는
    min() X 1, 비교 연산이 최소 2번, 최고 3번인데,

    제 코드 상에
    leftMin = left == start ? 0 : min(minHeight, fence[left - 1]);
    를 중복으로 넣어서
    비교 4번, min() X 3을 해봤는데 기존의 제 코드 실행시간과 비슷하더라고요...


    8년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.