[C++ 백준 풀이] 14438번 : 수열과 쿼리 17 / 18437번 : 수열과 쿼리 37 (세그먼트 트리)

 

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 14438번 : '수열과 쿼리 17', 18437번 : '수열과 쿼리 37' 문제에 대한 풀이 코드와 해설을 다루고 있습니다.

 

문제의 난이도는 Solved.ac 기준 Gold I에 해당하며, 문제를 풀이하기 위해 세그먼트 트리 응용에 대한 개념을 다룰 것입니다.

 

 

14438번 : 수열과 쿼리 17

 

길이가 N인 수열을 입력 받고, 두 가지 종류의 쿼리를 처리하는 문제입니다.

쿼리 1에 대해서는 특정 인덱스의 값을 바꾸는 처리를 해야 합니다.

쿼리 2에 대해서는 구간에서 가장 작은 값을 출력하면 됩니다.

수열과 쿼리 16 문제와 다른 점은, 쿼리 2에서 구간의 최소 인덱스를 출력하는 것이었는데 여기서는 구간의 최솟값을 출력해야 한다는 것입니다.

 

 

↓ 위의 이미지와 동일한 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <vector>
#include <algorithm>
#define INF 1000000001
using namespace std;

vector<int> Arr, Tree;

int initTree(int Begin, int End, int Node) {
    if(Begin == End) return Tree[Node] = Arr[Begin];
    int Mid = (Begin+End)/2;
    int leftMin = initTree(Begin, Mid, Node*2);
    int rightMin = initTree(Mid+1, End, Node*2+1);
    if(leftMin < rightMin) return Tree[Node] = leftMin;
    else return Tree[Node] = rightMin;
}

int updateTree(int Begin, int End, int Node, int Index) {
    if(Index < Begin || Index > End) return Tree[Node];
    if(Begin == End) return Tree[Node] = Arr[Index];
    int Mid = (Begin+End)/2;
    int leftMin = updateTree(Begin, Mid, Node*2, Index);
    int rightMin = updateTree(Mid+1, End, Node*2+1, Index);
    return Tree[Node] = min(leftMin, rightMin);
}

int findMin(int Begin, int End, int Node, int Left, int Right) {
    if(Left > End || Right < Begin) return INF;
    if(Left <= Begin && Right >= End) return Tree[Node];
    int Mid = (Begin+End)/2;
    int leftMin = findMin(Begin, Mid, Node*2, Left, Right);
    int rightMin = findMin(Mid+1, End, Node*2+1, Left, Right);
    return min(leftMin, rightMin);
}

int main() {
    int N, M, Q, Index, Value, Left, Right;
    scanf("%d", &N);
    Arr.resize(N);
    for(int i=0; i<N; i++) scanf("%d", &Arr[i]);
    Tree.resize(N*4);
    initTree(0, N-1, 1);
    scanf("%d", &M);
    for(int i=0; i<M; i++) {
        scanf("%d", &Q);
        if(Q == 1) {
            scanf("%d %d", &Index, &Value);
            Arr[Index-1] = Value;
            updateTree(0, N-1, 1, Index-1);
        }
        else {
            scanf("%d %d", &Left, &Right);
            printf("%d\n", findMin(0, N-1, 1, Left-1, Right-1));
        }
    }
}

 

이 문제 역시 세그먼트 트리를 이용해서 값의 수정과 구간의 특정 값을 구해줄 수 있습니다.

먼저 배열을 Arr 벡터에 입력받고, 그 값들을 initTree 함수에서 모두 대입해줍니다.

이 트리는 구간의 최솟값을 저장하는 트리이므로, 1개짜리 구간에 대해서는 그냥 Arr의 값을 리턴해주고, 2개 이상의 값에서는 이분하여 두 하위 트리 값 중 최솟값을 리턴하도록 설계합니다.

 

쿼리 1에 대해서는 특정 인덱스에 대해 값을 수정해주어야 하므로 그 둘을 입력받고, updateTree 함수에서 값을 수정해주도록 합니다.

최상위 노드인 1번 노드에서부터 하위 노드로 내려가면서, min 함수를 이용하여 최솟값을 Node에 저장하여 리턴해줍니다.

 

쿼리 2에 대해서는 구간의 최솟값을 찾아주도록 findMin 함수를 설계해줍니다.

만약 구간이 범위를 벗어나면 INF를 리턴하여 절대로 최솟값으로 잘못된 값이 나오지 않게 만들어주고, 구간을 포함하는 범위에 대해서는 그 구간의 최상위 노드 값을 리턴해줍니다.

2개 이상의 노드에 대해서 두 하위 트리의 최솟값 중 더 작은 값을 리턴받도록 하여 최솟값을 구할 수 있도록 합니다.

 

 

위의 코드를 제출하면 88ms의 시간에 모든 테스트케이스를 통과함을 확인할 수 있습니다.

 

 

18437번 : 수열과 쿼리 37

 

다른 수열과 쿼리들은 세그먼트 트리만으로는 풀 수 없고 다른 알고리즘을 활용해야 하기에 세그먼트 트리로만 해결할 수 있는 문제를 가지고 왔습니다.

수열과 쿼리 37 역시 세그먼트 트리만으로 해결이 가능한데, 이는 구간의 짝수의 개수와 구간의 홀수의 개수를 구하는 것이므로, 역시 구간의 특정 값을 구하는 세그먼트 트리를 구현하면 때문입니다.

 

 

코드가 길어서 이미지를 조금 잘랐는데, 잘 안 보이시면 이미지를 클릭하면 확대됩니다.

↓ 위의 이미지와 동일한 풀이 코드는 아래의 접은 글에 정리되어 있습니다.

#include <cstdio>
#include <vector>
using namespace std;

vector<int> Odd, Even;

int updateOdd(int Node, int Begin, int End, int Index, int Value) {
    if(Index < Begin || Index > End) return Odd[Node];
    if(Begin == End) {
        if(Value%2) return Odd[Node] = 1;
        else return Odd[Node] = 0;
    }
    int Mid = (Begin+End)/2;
    int leftCnt = updateOdd(Node*2, Begin, Mid, Index, Value);
    int rightCnt = updateOdd(Node*2+1, Mid+1, End, Index, Value);
    return Odd[Node] = leftCnt+rightCnt;
}

int updateEven(int Node, int Begin, int End, int Index, int Value) {
    if(Index < Begin || Index > End) return Even[Node];
    if(Begin == End) {
        if(Value%2) return Even[Node] = 0;
        else return Even[Node] = 1;
    }
    int Mid = (Begin+End)/2;
    int leftCnt = updateEven(Node*2, Begin, Mid, Index, Value);
    int rightCnt = updateEven(Node*2+1, Mid+1, End, Index, Value);
    return Even[Node] = leftCnt+rightCnt;
}

int cntNum(int Node, int Begin, int End, int Left, int Right, bool isOdd) {
    if(Left > End || Right < Begin) return 0;
    if(Left <= Begin && Right >= End) {
        if(isOdd) return Odd[Node];
        else return Even[Node];
    }
    int Mid = (Begin+End)/2;
    int leftCnt = cntNum(Node*2, Begin, Mid, Left, Right, isOdd);
    int rightCnt = cntNum(Node*2+1, Mid+1, End, Left, Right, isOdd);
    return leftCnt+rightCnt;
}

int main() {
    int N, M, Val, Q, Index, Left, Right;
    scanf("%d", &N);
    Odd.resize(N*4+1), Even.resize(N*4+1);
    for(int i=1; i<=N; i++) {
        scanf("%d", &Val);
        updateOdd(1, 1, N, i, Val);
        updateEven(1, 1, N, i, Val);
    }
    scanf("%d", &M);
    for(int i=0; i<M; i++) {
        scanf("%d", &Q);
        if(Q == 1) {
            scanf("%d %d", &Index, &Val);
            updateOdd(1, 1, N, Index, Val);
            updateEven(1, 1, N, Index, Val);
        }
        else if(Q == 2 || Q == 3) {
            scanf("%d %d", &Left, &Right);
            if(Q == 2) printf("%d\n", cntNum(1, 1, N, Left, Right, 0));
            else if(Q == 3) printf("%d\n", cntNum(1, 1, N, Left, Right, 1));
        }
    }
}

 

이 문제의 경우에는 OddTree와 EvenTree로, 특정 구간에 있는 홀수의 개수와 짝수의 개수를 다른 트리에 저장해주면 됩니다.

즉, 트리를 2개 만들어서 따로 관리해주면 해결이 가능한 문제입니다.

다만 쿼리를 처리하는 부분을 길게 만들었는데 이것은 예제를 대입해볼 때 쿼리를 모두 입력받았다가 한 번에 출력해야 안 끊기고 출력을 알아볼 수 있기 때문에 조금 귀찮지만 길게 코드를 작성했습니다.

쿼리를 모두 저장했다가 하나씩 처리하도록 구현하지 않아도 정답 처리는 받을 수 있습니다.

 

 

위의 풀이 코드를 제출해보면 140ms라는 시간에 모든 테스트케이스를 통과함을 확인할 수 있습니다.

다음 포스트에서는 수열과 쿼리가 아닌 다른 문제들 중에서 세그먼트 트리를 사용할 수 있는 문제들을 가지고 오겠습니다.