[C++ 백준 풀이] 14427번 : 수열과 쿼리 15 / 14428번 : 수열과 쿼리 16 (세그먼트 트리)

 

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

 

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

 

수열과 쿼리 시리즈는 애초에 문제가 40개 가까이 존재하기도 하고, 백준에서 시리즈 문제에 들어가보면 가장 위쪽에 나와있는 시리즈 문제이기 때문에 자주 접했으나 막상 그 난이도가 높아서 접근하지 못하고 있었던 문제입니다.

 

그러나 이번에 세그먼트 트리 관련 문제들을 풀면서 세그먼트 트리로 해결할 수 있는 수열과 쿼리 문제가 몇 개 있어서 이들을 풀이해보도록 하겠습니다.

 

 

14427번 : 수열과 쿼리 15

 

길이가 N인 수열을 입력받고, 두 가지의 쿼리를 처리하는 프로그램을 작성하는 문제입니다.

쿼리 1에 대해서는 특정 번째 숫자를 입력받은 숫자로 변경시키는 처리를 수행해야 합니다.

쿼리 2에 대해서는 수열 전체에서 가장 작은 값의 "주소"를 출력해야 합니다.

최솟값을 출력하는 것이 아니기 때문에 이 부분에서 주의를 하여 풀이를 작성해야 합니다.

 

 

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

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

vector<int> Arr, Tree;

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

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

int main() {
    int N, M, Q, Index, Value;
    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 printf("%d\n", Tree[1]+1);
    }
}

 

이 문제 역시 구간의 특정 값을 출력하는 과정과 특정 값의 수정을 둘 다 수행해야 하므로 세그먼트 트리를 활용해야 합니다.

먼저 Arr에 값들을 모두 입력받은 뒤에 세그먼트 트리를 초기화하는 방법을 이용했습니다.

초기화 과정에서 최솟값을 찾고, 이 최솟값의 Index를 구간 노드마다 저장해주도록 합니다.

트리를 입력받은 이후에는 이제 쿼리를 처리하는데, 쿼리 1에 대해서는 Index의 Value를 바꾸도록 updateTree 함수를 호출해주고, 이 때 Arr 값 역시 바꿔주는 처리를 해야 그 다음 쿼리 1을 처리할 때 오류가 발생하지 않습니다.

어쨌든 updateTree 함수에서는 범위를 벗어나거나 1개짜리 범위에 대해서는 Node의 값을 리턴해서 구간의 최솟값 index를 구할 때 별 다른 일이 없게 만들고, 그렇지 않은 경우에는 구간의 최솟값의 index를 리턴할 수 있도록 해줍니다.

최소 index를 출력하는 쿼리에 대해서는 단순히 최상위 노드의 값을 리턴해주면 됩니다. (최상위 노드의 키 값 자체가 전체 트리에서의 최솟값을 의미하기 때문)

 

 

위의 코드를 제출해보면 76ms의 시간이 소요되며 모든 테스트케이스를 통과함을 확인할 수 있습니다.

 

 

14428번 : 수열과 쿼리 16

 

수열과 쿼리 16 역시 쿼리 1에 대해서는 특정 인덱스의 값을 바꾸고, 쿼리 2에 대해서는 구간에서 가장 작은 값의 인덱스를 출력하는 문제입니다.

수열과 쿼리 15와 달라진 점은 쿼리 2의 구간을 설정해준다는 것입니다.

같은 방법으로 풀되 구간을 잡아주도록 코드를 수정하도록 하겠습니다.

 

 

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

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

vector<int> Arr, Tree;

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

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

int findMinIdx(int Begin, int End, int Node, int Left, int Right) {
    if(Left > End || Right < Begin) return -1;
    if(Left <= Begin && Right >= End) return Tree[Node];
    int Mid = (Begin+End)/2;
    int leftMinIdx = findMinIdx(Begin, Mid, Node*2, Left, Right);
    int rightMinIdx = findMinIdx(Mid+1, End, Node*2+1, Left, Right);
    if(leftMinIdx < 0) return rightMinIdx;
    if(rightMinIdx < 0) return leftMinIdx;
    if(Arr[leftMinIdx] < Arr[rightMinIdx]) return leftMinIdx;
    else if(Arr[leftMinIdx] > Arr[rightMinIdx]) return rightMinIdx;
    else return min(leftMinIdx, rightMinIdx);
}

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", findMinIdx(0, N-1, 1, Left-1, Right-1)+1);
        }
    }
}

 

findMinIdx 함수에서 Left와 Right 변수를 추가해주고, 함수에서는 Left와 Right가 구간을 벗어나면 -1을, 구간을 완전 포함하면 현재 노드에서 더 들어가지 않고 현재 노드의 값을 리턴해주고, 구간을 이분하여 각 트리에서 최솟값을 가진 idx를 받아서 리턴해주면 됩니다.

물론 -1을 리턴 받으면 그 구간은 빼고 나머지 구간에서 최솟값을 가진 idx를 리턴해주면 됩니다.

두 idx 위치의 값이 동일한 경우에는 두 idx 중 더 작은 주소를 리턴해주면 됩니다.

 

 

아직 수열과 쿼리 시리즈에서 세그먼트 트리로 해결할 수 있는 문제가 남아있기 때문에, 관련된 문제를 몇 개만 더 풀이해볼 생각입니다.