ABOUT ME

구르미의 개발 블로그입니다. 개발, Devops 관련 포스팅을 주로 다루고 있습니다.

Today
Yesterday
Total
  • 알고스팟 문제 풀이 FENCE
    24년 11월 이전/레거시-알고리즘 2019. 10. 25. 11:55
    반응형

    책 "알고리즘 문제 해결 전략"에 나오는 algospot 문제 "FENCE"에 대한 풀이입니다.

    목차

    1. 문제 해결 전략 - 무작정 풀기
    2. 코드 전문 - 무작정 풀기
    3. 문제 해결 전략 - 분할 정복
    4. 코드 전문 - 분할 정복

    FENCE 문제 URL은 다음과 같습니다.

    문제 해결 전략 - 무작정 풀기

    먼저, 이 문제를 풀기 위해서 "무작정 풀기" 전략을 선택해 봅시다. 제일 쉬운 방법은 모든 인덱스를 돌면서, 그 높이를 가진 울타리 영역의 최대치를 구하면 됩니다. 무슨 소리냐면, 첫 번째 입력을 예로 살펴봅시다.

    이런 울타리에서 첫 번째 판자의 높이로 울타리를 잘라낸다고 하면, 오른쪽 판자의 높이가 자신보다 낮습니다.따라서 다음 영역의 울타리를 잘라낼 수 있습니다. 영역의 너비는 7(7 * 1)이 됩니다.

    두 번째 판자의 높이로 울타리를 잘라낸다면, 높이가 제일 낮기 때문에, 해당 높이로 처음부터 끝까지 울타리를 잘라낼 수 있습니다. 영역의 너비는 7(1 * 7)입니다.

    이제 세 번째 판자의 높이로 잘라내봅시다. 먼저 바로 왼쪽의 높이가 자신보다 낮습니다. 또한 오른쪽으로 +4 에 위치한 판자가 자신의 높이보다 작기 때문에, 다음 영역을 잘라낼 수 있습니다. 영역의 너비는 20(5 * 4)입니다.

    이런 식으로 인덱스를 돌면서, 구할 수 있는 최대 영역을 구하면 됩니다. 이를 코드로 표현하면 다음과 같습니다.

     

    int solution(const int N, const vector<int>& heights) {
        
        int result = 0;
    
        for (int i=0; i<N; i++) {
            int height = heights[i];
            int right = i + 1, left = i - 1;
    
            while (right < N && heights[right] >= height) {
                right += 1;
            }
    
            while (left >= 0 && heights[left] >= height){
                left -= 1;
            }
            
            int width = right - left - 1;
            result = max(result, height * width);
        }
    
        return result;
    }

     

    코드 전문 - 무작정 풀기

    다음은 무작정 풀기를 적용한 알고리즘 풀이 코드 전문입니다. 위에서 설명하지 않은 main 함수에서 문제의 입력을 다루고 있으니 유의해서 봐주세요!

     

    int solution(const int N, const vector<int>& heights) {
        
        int result = 0;
    
        for (int i=0; i<N; i++) {
            int height = heights[i];
            int right = i + 1, left = i - 1;
    
            while (right < N && heights[right] >= height) {
                right += 1;
            }
    
            while (left >= 0 && heights[left] >= height){
                left -= 1;
            }
            
            int width = right - left - 1;
            result = max(result, height * width);
        }
    
        return result;
    } 
    
    int main() {
        int C;
        cin >> C;
    
        if ( !(0 < C && C <= 50) ) {
            cout << "fail: C must be between 1 and 50" << endl;
            return 0;
        }
    
        for (int i=0; i<C; i++) {
            int N;
            cin >> N;
    
            if ( !(1 <= N && N <= 20000) ) {
                cout << "fail: N must be between 1 and 20000" << endl;
                return 0;
            }   
    
            vector<int> heights = vector<int>(N, 0);
    
            for (int j=0; j<N; j++) {
                int h;
                cin >> h;
    
                if ( !(0 <= h && h <= 10000) ) {
                    cout << "fail: h must be between 1 and 10000" << endl;
                    return 0;
                }   
    
                heights[j] = h;
            }
    
            int result = solution(N, heights);
            cout << result << endl;
        }
    
        return 0;
    }

     

    알고리즘을 제출하면 800ms로 통과하고 있습니다. 그러나, 우리 문제의 최대 입력은 20,000이고, 시간 제한은 3000ms입니다. 이 알고리즘의 시간 복잡도는 O(N ^ 2)이기 때문에, 최대 입력을 넣었을 때는 통과하지 못할 것입니다. (400,000,000 > 3,000,000)

    문제 해결 전략 - 분할 정복

    저는 이 알고리즘을 최적화하기 위해서 "분할 정복" 패러다임을 적용할 것입니다. 이 문제는 다음의 3가지로 분할 할 수 있습니다.

     

    첫 번째, 가장 큰 직사각형이 왼쪽 부분에 존재할 때

    두 번째, 가장 큰 직사각형이 오른쪽 부분에 존재할 때

    세 번째, 가장 큰 직상각형은 왼쪽과 오른쪽 부분에 걸쳐 있을 때

    1, 2의 경우 반으로 나누어 부분 문제를 재귀 호출하여 해결할 수 있습니다.

     

    int solve(const vector<int>& heights, int left, int right) {
        //...
    
        // 반으로 나누고,
        int mid = (left + right) / 2;
        // 부분 문제 해결
        int ret = max(solve(heights, left, mid), solve(heights, mid + 1 ,right));
    
        //...
    }

     

    이제 문제는 양쪽에 걸쳐 있을 때를 해결하는 것입니다. 양쪽에 있을 때는 어떻게 해결할 수 있을까요? 먼저 가운데 mid를 기준으로 잘라낼 영역을 선택합니다. (mid, mid+1)

    이 때, mid+1의 높이가 적기 때문에, 영역의 너비는 다음과 같아집니다.

     

    2 * mid+1의 높이 = 2 * 6 = 12

     

    그렇게 시작해서, 왼쪽 오른쪽으로 서서히 영역을 넓혀나가면 됩니다. 다음과 같이 동작하게 되지요. 먼저, 오른쪽으로 영역이 넓혀집니다. 너비는 12에서 18로 변합니다.

    이제 왼쪽으로 영역을 한칸 더 넓힙니다. 이때 최소 높이는 6에서 5로 갱신되고 최대 너비도 20으로 갱신됩니다.

    또 오른쪽으로 한 칸 더 영역을 넓힙니다. 이 때 최소 높이는 3으로 변하지만, 최대 너비는 갱신되지 않습니다. (20 > 15)

    이제 왼쪽으로 한 칸 더 영역을 넓힙니다. 이 때 최소 높이는 1로 변하지만, 최대 너비는 갱신되지 않습니다. (20 > 6)

    이제 왼쪽으로 한 칸 더 영역을 넓힙니다. 이 때 최소 높이는 1로 유지되고, 최대 너비 역시 갱신되지 않습니다. (20 > 7)

    어떻게 동작하는지 아시겠나요? 아래 과정을 반복해서 가운데에 영역에 최대치를 구하면 됩니다. 이것은 다음과 같이 표현할 수 있습니다.

     

    1. lo = mid, hi = mid+1 부터 시작합니다.
    2. 영역 중 최소 높이를 구합니다. (height = min(heights[lo], heights[hi]))
    3. 영역을 구합니다. (area = 2 * height)
    4. left < lo || hi < right를 만족할 때까지 다음을 반복합니다.
      1. hi < right && (lo == left || heights[lo - 1] < heights[hi + 1]) 을 만족한다면 다음을 실행합니다.
        1. hi를 오른쪽으로 한 칸 옮깁니다.
        2. 최소 높이를 갱신합니다. (height = min(height, heights[hi]))
      2. 아니라면 다음을 실행합니다.
        1. lo를 왼쪽으로 한 칸 옮깁니다.
        2. 최소 높이를 갱신합니다. (height = min(height, heights[lo]))
      3. 영역을 구해서, 최대치를 갱신합니다.

    이제, 여기서 구한 최대 영역과, 왼쪽에서 최대와 오른쪽에서 최대를 비교한 것과 비교해서 최댓값을 구하면 됩니다. 코드는 다음과 같습니다.

     

    int solve(const vector<int>& heights, int left, int right) {
        //...
        //중간에 결쳐있을 때,
        int lo = mid, hi = mid + 1;
        int height = min(heights[lo], heights[hi]);
        int area = height * 2;
    
        while (left < lo || hi < right) {
    
            if (hi < right && (lo == left || heights[lo - 1] < heights[hi + 1])) {
                hi += 1;
                height = min(height, heights[hi]);
            } else {
                lo -= 1;
                height = min(height, heights[lo]);
            }   
            
            area = max(area, height * (hi - lo + 1));
        }
    
        return max(ret, area);
    }

     

    그리고 이렇게 했을 때, 예외 상황을 적용해주어야 합니다. 그래야 재귀 호출에서 벗어날 수 있을테니까요. 이 문제에서 예외 상황은 left, right가 같을 때, 즉 한 판자만을 가리킬 때입니다. 이 때는 판자의 높이를 그대로 반환하면 됩니다. 왜냐하면, 다음 그림처럼 너비는 1이니까요.

    코드는 다음과 같습니다.

     

    int solve(const vector<int>& heights, int left, int right) {
        if (left == right) {
            return heights[left];
        }
    
        //...
    }

     

    그래서 이 문제를 해결하기 위한 전체 코드는 다음과 같습니다.

     

    int solve(const vector<int>& heights, int left, int right) {
        if (left == right) {
            return heights[left];
        }
    
        int mid = (left + right) / 2;
        int ret = max(solve(heights, left, mid), solve(heights, mid + 1 ,right));
    
        int lo = mid, hi = mid + 1;
        int height = min(heights[lo], heights[hi]);
        int area = height * 2;
    
        while (left < lo || hi < right) {
    
            if (hi < right && (lo == left || heights[lo - 1] < heights[hi + 1])) {
                hi += 1;
                height = min(height, heights[hi]);
            } else {
                lo -= 1;
                height = min(height, heights[lo]);
            }   
            
            area = max(area, height * (hi - lo + 1));
        }
    
        return max(ret, area);
    }
    
    int solution(const int N, const vector<int>& heights) {
        return solve(heights, 0, N-1);    
    } 

     

    solution 함수에서 분할 정복이 적용된 solve 함수를 부르고 있습니다. 이는 "무작정 풀기"때 만든 입력, 즉 main 함수 변경 없이 그대로 사용하기 위해서 만들어진 패턴입니다. 유의깊게 살펴봐주세요.

    코드 전문 - 분할 정복

    "분할 정복" 패러다임을 적용한 코드 전문입니다. main은 이전과 같습니다.

     

    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    int solve(const vector<int>& heights, int left, int right) {
        if (left == right) {
            return heights[left];
        }
    
        int mid = (left + right) / 2;
        int ret = max(solve(heights, left, mid), solve(heights, mid + 1 ,right));
    
        int lo = mid, hi = mid + 1;
        int height = min(heights[lo], heights[hi]);
        int area = height * 2;
    
        while (left < lo || hi < right) {
    
            if (hi < right && (lo == left || heights[lo - 1] < heights[hi + 1])) {
                hi += 1;
                height = min(height, heights[hi]);
            } else {
                lo -= 1;
                height = min(height, heights[lo]);
            }   
            
            area = max(area, height * (hi - lo + 1));
        }
    
        return max(ret, area);
    }
    
    int solution(const int N, const vector<int>& heights) {
        return solve(heights, 0, N-1);    
    } 
    
    int main() {
        // 무작정 풀기와 동일
    }

     

    이 알고리즘을 제출하면 300ms 이내로 문제를 해결하는 것을 알 수 있습니다. 분할정복을 적용해서 알고리즘 복잡도를 O(N * log(N))으로 낮췄기 때문에, 최대 입력을 넣어도 약 290,000 (= 290ms < 3,000ms) 정도로 문제를 해결할 수 있기 때문입니다.

    728x90

    '레거시 > 레거시-알고리즘' 카테고리의 다른 글

    알고스팟 문제 풀이 QUADTREE  (0) 2019.10.17
    목차  (0) 2019.10.15
    무식하게 풀기(Brute Force)  (0) 2019.10.15
Designed by Tistory.