[8주차] Segment Tree

본 글은 건국대학교 알고리즘 동아리 AlKon 스터디 5조에서 진행된 발표 내용입니다.

 

2517 달리기

2517번: 달리기

 

시간 제한	입력	범위
1초	N, 기량	3 ≤ N ≤ 500,000 // 1 ≤ 기량 ≤ 1,000,000,000

 

N: 선수의 수

N개의 줄: 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시

 

참가한 선수들의 평소 실력은 모두 다르다.

 

---

접근법

세미나에서 들은 내용은 아래와 같다.

 

기량의 최댓값은 1,000,000,000이므로 이 범위로는 세그먼트 트리를 만들 수 없다.ㅜ

→

참가한 선수의 기량의 모두 다르다는 것에 집중해보자.

 

입력 받은 선수들의 기량을 오름차순으로 정렬하여 1~N으로 매칭시키면 최대 500,000개가 된다.

따라서, 최대 길이 N개로 세그먼트 트리를 만들 수 있다 ! 굿.

 

문제 해결 방법은 예를 들어 생각해보자.!

세그먼트 트리 구성하는 방법

현재 등수에서 1등부터 8등까지의 평소 기량을 다음과 같이 입력 받았다고 하자. 2, 8, 10, 7, 1, 9, 4, 5

 

사실, 선수들의 평소 기량에 대한 정확한 수치는 중요하지 않다.

자신의 평소 기량이 현재 대회에 참가하고 있는 전체 선수 중 몇 번째인 지만 알면 된다.

다른 모든 선수들에 대하여 평소 기량의 상대적인 정보만 있으면 내가 앞설 수 있는 선수인지 아닌지 판단 가능하기 때문이다.

 

즉, 2, 8, 10, 7, 1, 9, 4, 5 의 입력(평소 기량)은 2, 5, 7, 4, 1, 6, 3, 8 로 나타낼 수 있다.

 

최선의 등수(최대 등수) 식 구하기

우리는 1등부터 n등까지 순차적으로 가능한 최고 순위를 결정할 것이다.

왜냐하면, 나보다 앞선 사람의 정보가 중요하기 때문이다. 뒤에 있는 사람은 상관이 없다!

 

내가 3등이라고 하자. 앞선 두 선수 중에서 나보다 기량이 좋은 선수가

• 한 명도 없을 때, 나는 1등을 할 수 있다.
• 한 명일 때, 나는 최대 2등을 할 수 있다.
• 두 명일 때, 나는 최대 3등을 할 수 있다.

이것은 앞선 선수 중 자신보다 기량이 좋은 선수의 수 + 1 이 나의 가능한 최대 등수임을 의미한다.

 

모든 선수에 대하여 최선의 등수(최대 등수) 식 구하기

근데.. 그래서 앞선 선수 중 자신보다 기량이 좋은 선수의 수를 어떻게 구하는데 ?? 🥲

 

여기서 세그먼트 트리를 이용한다. 구간 합 구하는 방법을 그대로 사용하면 된다. 단, 리프 노드의 값이 의미하는 바만 좀 다를 뿐이다.

리프 노드의 값은 0 또는 1이며, 이는 해당 선수의 탐색 여부를 나타낸다.

 

이게 대체 무슨 뚱딴지 같은 말일까??

 

다시,

처음에는 세그먼트 트리의 모든 리프 노드의 값이 0이다. 아직 아무 선수도 탐색하지 않았다는 뜻이다.

 

세그먼트 트리의 리프 노드만 가져와 하나의 배열 arr이라고 생각해보자.

arr 배열(리프 노드)의 인덱스는 각 선수의 평소 기량을, 값은 해당 선수가 나보다 앞선 선수인지를 나타낸다.

선수들의 평소 기량 2, 5, 7, 4, 1, 6, 3, 8 (입력: 2, 8, 10, 7, 1, 9, 4, 5)에 대하여 최초의 리프 노드의 값은 다음과 같다.

1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0

 

이 때, 인덱스인 1~8는 각 선수의 평소 기량을 나타낸다. 즉, 현재 1등인 선수의 기량은 2이기 때문에, 이 선수의 탐색 여부는 arr[2]에 저장된다. 따라서, 1등 선수를 탐색한 후 arr 배열(리프 노드의 값)은 다음과 같다.

1	2	3	4	5	6	7	8
0	1	0	0	0	0	0	0

 

4등까지 탐색한 후의 arr 배열은 다음과 같다.

1	2	3	4	5	6	7	8
0	1	0	1	1	0	1	0

 

즉, 4등 선수의 최대 순위를 구하는 순간에 해당 선수보다 앞선 선수는 3명이며 그 선수들의 기량이 2, 5, 7인 것을 알 수 있는 것이다.

 

자. 이제 정말로 1등부터 최선의 순위를 구해보자.

 

1등

1등의 평소 기량은 2이다.

나보다 앞선 선수는 arr 배열의 값이 1인 선수들이므로, 쉽게 알 수 있다. 하지만, 나보다 앞선 모든 선수를 볼 필요는 없다.

 

그렇다면 내가 비교해야 하는 선수는 누구일까?

당연히, 나보다 좋은 기량의 선수만 보면 된다. 현재 나보다 앞선 선수가 나보다 기량이 안 좋으면 나는 충분히 추월할 수 있으므로 그 선수의 수는 중요치 않다.

따라서, 현재 선수의 평소 기량보다 더 좋은 기량을 가진 선수가 현재 선수보다 앞섰는지만 확인하면 된다.

 

arr 배열(리프 노드)의 인덱스는 각 선수의 평소 기량을, 값은 해당 선수가 나보다 앞선 선수인지를 나타낸다.

즉, 현재 선수의 평소 기량이 C라고 했을 때, arr 배열의 [C+1, N]의 값 중 1인 값의 개수를 구하고 1을 더하면 현재 선수의 최대 등수가 된다.

각 선수의 최대 등수(최선의 등수)는앞선 선수 중 자신보다 기량이 좋은 선수의 수 + 1 때문이다.

 

1등의 평소 기량이 2이므로, 구간 [3, 8] (arr[3] ~ arr[8]) 중 나보다 앞서있는 선수의 수를 구하면 되는 것이다. 그 값은 0이다.

따라서, 1등의 최대 등수는 1이다.

1의 최대 등수를 구했으므로, arr[2]=1로 갱신한다.

 

같은 과정을 모든 8등 선수까지 반복하면 된다. 3명만 더 해보자.

 

2등

2등의 평소 기량은 5이므로, 구간[6, 8] 중 배열의 값이 1인 개수는 0이다.

따라서, 2등의 최대 등수는 1이다.

arr[5]=1로 갱신한다.

 

3등

3등의 평소 기량은 7이므로, 구간[8, 8] 중 배열의 값이 1인 개수는 0이다.

따라서, 3등의 최대 등수는 1이다.

arr[7]=1로 갱신한다.

 

4등

4등의 평소 기량은 4이므로, 구간[5, 8] 중 배열의 값이 1인 개수는 2이다.

따라서, 2등의 최대 등수는 3이다.

arr[4]=1로 갱신한다.

 

…

8등까지 계산한다.

 

init, query, update 메서드의 사용

이제 남은 건 init, query, update 메서드를 어떻게 사용하는가? 이다.

 

1. init

모든 리프 노드의 값이 0으로 시작하기 때문에 세그먼트 트리에 대한 initialization은 불필요하다.

문제의 조건에 따라 기량의 최대 범위가 너무 커서 좌표 압축이 필요하므로 이 과정을 init 메서드로 지정해주었다.

 

2. query

query 메서드는 단순하다. 탐색 구간 (현재 선수의 평소 기량+1, 최대 기량)에 대하여 구간 합을 구하면 된다.

이것은 update 메서드를 통하여 미리 구해져 있을 테니 단순히 값을 반환하기만 하면 된다. 설명은 생략하겠다.

 

3. update

한 선수의 최대 등수를 구하고 나면, 해당 선수를 탐색했다고 표시해야 한다.

이 때, 해당 선수의 평소 기량을 구간(s==e==평소기량)으로 가지는 리프 노드의 값을 바꿔야 한다.

리프 노드의 값을 1로 바꾼 후에는, 구간 합에 변동이 생기므로 모든 조상 노드에 대하여 그 값을 갱신해주어야 한다.

 

메서드를 사용하는 방법까지 생각해보았으니 구체적인 알고리즘을 작성하고 구현해보자.

 

---

메서드 별 알고리즘

1. init: 좌표 압축

세그먼트 트리에 대한 작업은 불필요 → 1등부터 탐색하여 자신의 기량을 구간의 시작이자 끝으로 하는 리프 노드 값이 1이 될 것

 

좌표 압축

1. 입력 받을 때, 기량과 입력 순서(인덱스)를 함께 저장함

2. 기량에 대하여 오른차순 정렬

3. 정렬된 순서 인덱스로로 기량 정보를 덮어씀 = 좌표 압축

4. 입력 순서로 정렬

 

아래 '더 보기'에는 구현 코드가 있습니다. 코드를 보기 전에 스스로 구현해 보는 것을 권장합니다.

void init() { // 좌표 압축
 sort(arr.begin(), arr.end());
 for(int i=1; i<=n; i++) arr[i].first = i;
 sort(arr.begin(), arr.end(), compare);
}

 

ex. 입력: 2 8 10 7 1 → 좌표 압축: 2 4 5 3 1

 

2. query(now): 현재 등수에 해당하는 선수의 평소 기량이 now일 때, 앞선 선수 중 자신보다 기량이 좋은 선수의 수

-> query(1, 1, n, now+1, n) 호출

 

아래 '더 보기'에는 구현 코드가 있습니다. 코드를 보기 전에 스스로 구현해 보는 것을 권장합니다.

ll query(int node, int s, int e, int l, int r) {
    if(r<s || e<l) return 0;
    if(l<=s && e<=r) return tree[node];

    int mid=(s+e)/2;
    return query(node<<1, s, mid, l, r) + query(node<<1|1, mid+1, e, l, r);
}

 

3. update(): 선수의 탐색 여부 표시

탐색 완료한 선수의 평소 기량을 의미하는 리프 노드의 값을 1로 갱신

 

아래 '더 보기'에는 구현 코드가 있습니다. 코드를 보기 전에 스스로 구현해 보는 것을 권장합니다.

void update(int node, int s, int e, int idx){
    if(idx<s || e<idx) return;
    if(s==e && s==idx) {tree[node]=1; return;}

    int mid=(s+e)/2;
    update(node<<1, s, mid, idx);
    update(node<<1|1, mid+1, e, idx);
    tree[node] = tree[node<<1] + tree[node<<1|1];
}

 

---

전체 알고리즘

1. 선수의 수 n과 현재 1~n등 선수의 기량을 입력 받는다.
   • {기량, 현재 등수}로 저장한다.
2. 좌표 압축을 수행한다.
   • init()
3. 1등부터 n등까지 순차적으로 최대 순위를 구한다.
   • now = 현재 선수의 평소 기량
   • 최대 순위 = query(now) + 1
   • update(now): 현재 순위 선수 탐색 여부 표시

 

---

시간복잡도

init - O(N)

query, update - O(logN)

 

→ O(NlonN)

 

---

제출

 

---

Code - C++

코드를 보기 전에 스스로 구현해 보는 것을 권장합니다.

#include <iostream>
#include <algorithm>
#define endl "\n"
typedef long long ll;
using namespace std;

int n;
vector<pair<ll, ll>> arr;
ll tree[2000001]={0,};

bool compare(pair<ll, ll> a, pair<ll, ll> b){
    return a.second < b.second;
}

void init() { // 좌표 압축
    sort(arr.begin(), arr.end());
    for(int i=1; i<=n; i++) arr[i].first = i;
    sort(arr.begin(), arr.end(), compare);
}

ll query(int node, int s, int e, int l, int r) {
    if(r<s || e<l) return 0;
    if(l<=s && e<=r) return tree[node];

    int mid=(s+e)/2;
    return query(node<<1, s, mid, l, r) + query(node<<1|1, mid+1, e, l, r);
}
ll query(int now) {return query(1, 1, n, now+1, n);}

void update(int node, int s, int e, int idx){
    if(idx<s || e<idx) return;
    if(s==e && s==idx) {tree[node]=1; return;}

    int mid=(s+e)/2;
    update(node<<1, s, mid, idx);
    update(node<<1|1, mid+1, e, idx);
    tree[node] = tree[node<<1] + tree[node<<1|1];
}
void update(int idx) {update(1, 1, n, idx);}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n; arr.resize(n+1);

    int temp;
    for(int i=1; i<=n; i++) {
        cin >> temp;
        arr[i] = {temp, i};
    }

    init();
    int now;
    for(int i=1; i<=n; i++) {
        now = arr[i].first;
        cout << query(now)+1 << endl;
        update(now);
    }

    return 0;
}