반복 호출되는 함수 변수로 const를 넣을 때 주의점.

https://algospot.com/judge/problem/read/FENCE

 

울타리 잘라내기 문제는 분할 정복을 풀어본 사람들에게 유명한 문제이다. 대표적인 문제라고 봐도 과언이 아니다. PS 자료가 잘 정리되있기로 유명한 kks277(http://kks227.blog.me/)님의 블로그에서도 해당 문제의 백준 버전을 추천해주고 있기도 하고.

암튼, 간만에 문제를 풀다가 아무 생각 없이 한 실수이다.

#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;

#define INF 987654321
#define ull unsigned long long
#define pa <int, int>

vector<int> fence;

int maxSize(int left, int right) {
    if (left == right)return fence[left];

    int mid = (left + right) / 2;

    int res = max(maxSize( left, mid), maxSize( mid + 1, right));

    int lo = mid, hi = mid + 1;
    int height = min(fence[lo], fence[hi]);
    res = max(res, height * 2);
    while (lo>left || hi<right) {
        if (hi < right && (lo==left || fence[lo-1]<=fence[hi+1])) {
            ++hi;
            height = min(height, fence[hi]);
        }
        else {
            --lo;
            height = min(height, fence[lo]);
        }
        res = max(res, height * (hi - lo + 1));

    }
    return res;

}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int T; cin >> T;
    for (int testCase = 0; testCase < T; testCase++) {
        int n; cin >> n;
        fence = vector<int>(n);
        for (int i = 0; i < n; i++) {
            cin >> fence[i];
        }
        cout << maxSize( 0, n-1) << endl;
    }

    return 0;
}

위의 코드는 나중에 작성했던, 시간 초과를 해결한 코드이고

int maxSize(const vector<int> fence, int left, int right) {
    if (left == right)return fence[left];

    int mid = (left + right) / 2;

    int res = max(maxSize(fence, left, mid), maxSize(fence, mid + 1, right));

    int lo = mid, hi = mid + 1;
    int height = min(fence[lo], fence[hi]);
    res = max(res, height * 2);
    while (lo>left || hi<right) {
        if (hi < right && (lo==left || fence[lo-1]<=fence[hi+1])) {
            ++hi;
            height = min(height, fence[hi]);
        }
        else {
            --lo;
            height = min(height, fence[lo]);
        }
        res = max(res, height * (hi - lo + 1));

    }
    return res;

}

요 코드는 처음 작성했던, 시간 초과가 나온 코드.

두 코드의 차이점은 함수가 호출되는 타이밍에 const로 vector 컨테이너를 넘겨주었느냐, 아니면 전역변수로 있는 벡터를 사용했느냐 차이가 있는데, 이게 큰 차이가 있을까 싶어 테스트를 진행했다.

vector<int> fence;

void insertVectConst(const vector<int> inp) {
    int n=0;
    for (int i = 0; i < inp.size(); i++) {
        n++;
    }
}
void notInsertVectConst() {
    int n = 0;
    for (int i = 0; i < fence.size(); i++) {
        n++;
    }
}




int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    clock_t start1, start2, end1, end2;
    vector<int> tmp;
    for (int i = 0; i < 100000; i++) {
        tmp.push_back(i);
        fence.push_back(i);
    }
    start1 = clock();

    for (int i = 0; i < 10000; i++) {
        insertVectConst(tmp);
    }

    end1 = clock();
    cout << (double)(end1 - start1) << endl;

    start2 = clock();
    for (int i = 0; i < 10000; i++) {
        notInsertVectConst();
    }
    end2 = clock();
    cout << (double)(end2 - start2) << endl;




    return 0;
}

결과는

VectConst를 집어넣은 경우는 23339

아닌 경우는 23305

단순 선형 시간에는 얼마 차이 나지 않는 것을 볼 수 있다.

이렇게 되면 결론이 찝찝하기 때문에, 본래 코드로 테스트를 진행해보도록 합니다.

문제에서 조건은 최대 input갯수 2000개, 최대 높이 10000이므로, 갯수는 20000개 고정, 높이는 rand 이용하여 재보았습니다.

시간 초과 나지 않은 코드

#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include <random>
#include<time.h>

using namespace std;

#define INF 987654321
#define ull unsigned long long
#define pa <int, int>

vector<int> fence;

int maxSize(int left, int right) {
    if (left == right)return fence[left];

    int mid = (left + right) / 2;

    int res = max(maxSize(left, mid), maxSize(mid + 1, right));

    int lo = mid, hi = mid + 1;
    int height = min(fence[lo], fence[hi]);
    res = max(res, height * 2);
    while (lo > left || hi < right) {
        if (hi < right && (lo == left || fence[lo - 1] <= fence[hi + 1])) {
            ++hi;
            height = min(height, fence[hi]);
        }
        else {
            --lo;
            height = min(height, fence[lo]);
        }
        res = max(res, height * (hi - lo + 1));

    }
    return res;

}





int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    clock_t start, end;

    int n=20000;
    fence = vector<int>(n);
    for (int i = 0; i < n; i++) {
        fence[i] = rand()%10000;
    }
    start = clock();
    cout << maxSize(0, n - 1) << endl;
    end = clock();

    cout << (double)(end - start) << endl;

    return 0;
}

결과는 29

시간초과 난 코드

#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include <random>
#include<time.h>

using namespace std;

#define INF 987654321
#define ull unsigned long long
#define pa <int, int>

vector<int> fence;

int maxSize(const vector<int> fence, int left, int right) {
    if (left == right)return fence[left];

    int mid = (left + right) / 2;

    int res = max(maxSize(fence, left, mid), maxSize(fence, mid + 1, right));

    int lo = mid, hi = mid + 1;
    int height = min(fence[lo], fence[hi]);
    res = max(res, height * 2);
    while (lo > left || hi < right) {
        if (hi < right && (lo == left || fence[lo - 1] <= fence[hi + 1])) {
            ++hi;
            height = min(height, fence[hi]);
        }
        else {
            --lo;
            height = min(height, fence[lo]);
        }
        res = max(res, height * (hi - lo + 1));

    }
    return res;

}





int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    clock_t start, end;

    int n=20000;
    fence = vector<int>(n);
    for (int i = 0; i < n; i++) {
        fence[i] = rand()%10000;
    }
    start = clock();
    cout << maxSize(fence, 0, n - 1) << endl;
    end = clock();

    cout << (double)(end - start) << endl;

    return 0;
}

결과는 `505`

1 clock이 0.001초이므로, 전자는 0.03, 후자는 0.5의 차이.
O(nlogn)의 알고리즘에서 16배의 차이가 나기 때문에, 계산하는 컴퓨터의 사양에 따라 충분히 시간초과를 만들 수 있는 차이일 수 있다고 생각한다.
다만, 아무래도 해당하는 부분은 이번 경우처럼 직접 edge case를 겪어보지 않으면 알 수 없는 부분이므로, 이런 일을 실제상황에서 겪지 않으려면 많은 삽질이 동반되어야 함이 틀림 없다.