글 읽기 - 히스토그램-분할 정복 코드 분석 도와주세요 ㅠ

dreamian 6년 전 0

https://www.acmicpc.net/blog/v...

문제를 풀다 분할 정복으로 접근하기가 개념이 너무 어려워 백준님이 쓰신 링크에서

아래와 같은 소스 부분을 보았습니다.

query함수는 i~j 범위 내에서 최소의 높이 인덱스를 반환하는 함수인데

제가 궁금한 부분은, 분할의 과정이 아래와 같은 단계로 진행된다고 이해하고 있습니다.

** 전체 범위 중 3번째 인덱스가 최소의 높이임 -> 0~2번째 // 4~n번째 탐색. -> ... -> ...

이런 식으로 진행된다면, 아래 소스코드의 24번째 라인에서 세그먼트 트리로 분할한 노드에서

i~j는 탐색하려는 범위 ( 전 단계에서 높이의 최솟값을 갖는 인덱스를 기준으로 양 옆을 나눈 것 중 하나)이고,

start, end는 tree의 노드가 커버하는 구간일텐데,

만약 i=start-1이라면, 아래 코드에서 tree[node] (start~end의 인덱스 사이의 최솟값을 갖는 인덱스)를 반환할텐데,

start-1은 고려를 안 하게 되는 거 아닌가요?

어떤 점이 잘못 이해하고 있는건지 궁금합니다. 멍하게 모니터만 계속 바라보고 있습니다.. ㅋㅋㅋ

감사합니다

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
void init(vector<int> &a, vector<int> &tree, int node, int start, int end) {
    if (start == end) {
        tree[node] = start;
    } else {
        init(a, tree, node*2, start, (start+end)/2);
        init(a, tree, node*2+1, (start+end)/2+1, end);
        if (a[tree[node*2]] <= a[tree[node*2+1]]) {
            tree[node] = tree[node*2];
        } else {
            tree[node] = tree[node*2+1];
        }
    }
}
///////////////////////////////////
int query(vector<int> &a, vector<int> &tree, int node, int start, int end, int i, int j) {
    if (i > end || j < start) {
        return -1;
    }
    if (i <= start && end <= j) { ///////// 이 부분이 이해가 되지 않습니다.
        return tree[node];
    }
    int m1 = query(a, tree, 2*node, start, (start+end)/2, i, j);
    int m2 = query(a, tree, 2*node+1, (start+end)/2+1, end, i, j);
    if (m1 == -1) {
        return m2;
    } else if (m2 == -1) {
        return m1;
    } else {
        if (a[m1] <= a[m2]) {
            return m1;
        } else {
            return m2;
        }
    }
}
long long largest(vector<int> &a, vector<int> &tree, int start, int end) {
    int n = a.size();
    int m = query(a, tree, 1, 0, n-1, start, end);
    long long area = (long long)(end-start+1)*(long long)a[m];
    if (start <= m-1) {
        long long temp = largest(a, tree, start, m-1);
        if (area < temp) {
            area = temp;
        }
    }
    if (m+1 <= end) {
        long long temp = largest(a, tree, m+1, end);
        if (area < temp) {
            area = temp;
        }
    }
    return area;
}
int main() {
    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;
        vector<int> a(n);
        for (int i=0; i<n; i++) {
            cin >> a[i];
        }
        int h = (int)(ceil(log2(n))+1e-9);
        int tree_size = (1 << (h+1));
        vector<int> tree(tree_size);
        init(a, tree, 1, 0, n-1);
        cout << largest(a, tree, 0, n-1) << '\n';
    }
    return 0;
}

ntopia 6년 전 1

말씀하신 상황이라면

start-1 위치는 다른 query 콜에서 계산되겠죠

맨 처음엔 start, end 가 각각 0, n-1 이고

점점 query 콜이 쪼개지게 되는데

다 하고나면 정확히 i~j 구간을 잘 커버하게 됩니다

dreamian 6년 전 0

답변 감사합니다!

정말 많은 도움이 되었습니다!

댓글을 작성하려면 로그인해야 합니다.