[C++ 백준 풀이] 1306번 : 달려라 홍준 / 1572번, 9426번 : 중앙값 (측정) (슬라이딩 윈도우 알고리즘)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 1306번 : '달려라 홍준', 1572번, 9426번 : '중앙값 (측정)' 문제에 대한 풀이 코드와 해설을 다루고 있습니다.

 

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

 

 

1306번 : 달려라 홍준

 

앞뒤로 M-1칸의 빛의 세기까지 인식이 가능할 때, M번째 칸에서부터 N-M+1번째 칸까지 이동하는 매 칸마다 빛의 세기를 출력하는 문제입니다.

구간의 빛의 세기에 대해 정의가 애매하게 되어 있는데, 문제에서 말하는 빛의 세기란 i번째 칸에 있을 때 i-(M-1) ~ i+(M-1) 구간에서의 빛의 최댓값을 의미합니다.

즉, 세그먼트 트리에 구간 최댓값을 저장하여 구해주기만 하면 되는 쉬운 문제입니다.

 

그리고 이 문제는 슬라이딩 윈도우 알고리즘에도 해당하기 때문에, 같이 알아두고 있으면 유용한 문제입니다.

슬라이딩 윈도우 알고리즘이란 고정 사이즈의 범위가 이동하면서 구간의 특정 값을 반복적으로 구할 때, 중복되는 구간을 최대한 활용하여 연산을 줄이는 알고리즘을 말합니다.

 

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> Tree;
 
void updateTree(int Node, int Begin, int End, int Index, int Intensity) {
    if(Index < Begin || Index > End) return;
    if(Begin == End) {
        Tree[Node] = Intensity;
        return;
    }
    int Mid = (Begin + End)/2;
    updateTree(Node*2, Begin, Mid, Index, Intensity);
    updateTree(Node*2+1, Mid+1, End, Index, Intensity);
    Tree[Node] = max(Tree[Node*2], Tree[Node*2+1]);
}
 
int findMax(int Node, int Begin, int End, int Left, int Right) {
    if(Left > End || Right < Begin) return 0;
    if(Left <= Begin && Right >= End) return Tree[Node];
    int Mid = (Begin + End)/2;
    return max(findMax(Node*2, Begin, Mid, Left, Right), findMax(Node*2+1, Mid+1, End, Left, Right));
}
 
int main() {
    int N, M, Intensity;
    scanf("%d %d", &N, &M);
    Tree.resize(N*4+1);
    for(int i=1; i<=N; i++) {
        scanf("%d", &Intensity);
        updateTree(1, 1, N, i, Intensity);
    }
    for(int i=M; i<=N-M+1; i++) printf("%d ", findMax(1, 1, N, i-(M-1), i+(M-1)));
}

 

풀이를 보면 세그먼트 트리만 구현할 줄 알면 다른 플레티넘 난이도의 문제에 비해서는 굉장히 쉽게 해결할 수 있음을 확인할 수 있습니다.

우선 빛의 세기를 칸마다 입력받으면서 updateTree 함수를 이용하여 세그먼트 트리를 갱신해줍니다.

Tree의 각 노드에는 구간의 최댓값을 저장하도록 설계해줍니다. (Tree[Node] = max(Tree[Node*2], Tree[Node*2+1])

findMax 함수 역시 구간에서의 최댓값을 리턴해야 하므로, max(왼쪽 트리의 값, 오른쪽 트리의 값)을 반환해줍니다.

특징적인 부분은 findMax를 호출하는 부분인데, Left 좌표를 i-(M-1)로, Right 좌표를 i+(M-1)로 잡아서 호출해주는 과정을 M부터 N-M+1까지 반복해주면 됩니다. (O(N log N) 알고리즘)

 

 

 

풀이를 제출해보면 위와 같이 700ms라는 오랜 시간이 걸리고 나서 모든 테스트케이스를 통과함을 확인할 수 있습니다.

 

 

 

1572번 : 중앙값, 9426번 : 중앙값 측정

 

이 두 문제는 완전히 동일한 문제인데, 문제를 가져오는 과정에서 두 사람이 동시에 가져왔나봅니다. (문제 첨부는 1572번 문제만 하였습니다.)

크기가 N인 수열이 입력되었을 때, 길이가 K인 모든 구간의 중앙값의 합을 출력하는 문제입니다.

특정 구간의 값을 반복해서 얻어야 하기 때문에 이 문제 역시 세그먼트 트리를 이용해서 풀 수 있습니다.

 

 

#include <cstdio>
#include <vector>
#include <queue>
#define MAX 65536
using namespace std;
 
vector<int> Tree;
queue<int> Queue;
 
void updateTree(int Node, int Begin, int End, int Value, int Var) {
    if(Value < Begin || Value > End) return;
    Tree[Node] += Var;
    if(Begin < End) {
        int Mid = (Begin + End)/2;
        updateTree(Node*2, Begin, Mid, Value, Var);
        updateTree(Node*2+1, Mid+1, End, Value, Var);
    }
}
 
int findMid(int Node, int Begin, int End, int Ranking) {
    if(Begin == End) return Begin;
    int Mid = (Begin + End)/2;
    if(Tree[Node*2] >= Ranking) return findMid(Node*2, Begin, Mid, Ranking);
    else return findMid(Node*2+1, Mid+1, End, Ranking-Tree[Node*2]);
}
 
int main() {
    int N, K, Value;
    long long Sum = 0;
    scanf("%d %d", &N, &K);
    Tree.resize(MAX*4+1);
    for(int i=1; i<=K; i++) {
        scanf("%d", &Value);
        updateTree(1, 0, MAX-1, Value, 1);
        Queue.push(Value);
    }
    Sum += (long long)findMid(1, 0, MAX-1, (K+1)/2);
    for(int i=K+1; i<=N; i++) {
        updateTree(1, 0, MAX-1, Queue.front(), -1);
        Queue.pop();
        scanf("%d", &Value);
        updateTree(1, 0, MAX-1, Value, 1);
        Queue.push(Value);
        Sum += (long long)findMid(1, 0, MAX-1, (K+1)/2);
    }
    printf("%lld", Sum);
}

 

우선 트리의 설계는, 노드의 번호가 온도의 값이 되고, 노드의 값은 해당 값이 몇 개인지 count해주는 용도로 만들어주어야 합니다.

왜냐하면 문제에서 주어진 온도의 범위가 0에서 65536 사이의 정수이기 때문에 충분히 배열로 선언할 수 있고 이의 4배 크기 트리 역시 구현이 가능합니다.

그리고 중앙값은 크기 순으로 정렬해서 그 중에서 (K+1)/2번째에 있는 수를 선택해야 하기 때문에, 값에 해당하는 노드 번호에 저장을 하면 중앙값을 쉽게 찾을 수 있습니다.

 

그리고 K개의 범위를 어떻게 잡을지가 어려울 수 있는데, 모든 트리에 값을 다 넣고나서 범위를 잡지 말고 그냥 트리 자체에 K개의 데이터만을 삽입한 상태에서 중앙값을 구해주는 방식으로 문제를 해결할 수 있습니다.

이를 구현하기 위해 큐를 선언하고 큐에 K개의 값을 먼저 삽입해주고, 1개씩 Pop, Push를 반복해주면서 중간마다 (K+1)/2번째 원소를 찾아주면 됩니다.

 

 

 

같은 풀이 코드를 두 문제에 제출해보면, 똑같이 정답을 인정받을 수 있음을 확인할 수 있습니다.

백준에는 가끔씩 같은 문제가 두 개씩 있는 경우가 있으니 잘 확인해보시길 바랍니다. (이름이 달라도 같은 문제인 경우가 있음)