[문제해결기법] 3. 자료구조1

1. RMQ : Range Minimum Query (범위 최소 쿼리)

배열의 부분배열에서 최솟값을 찾기

 

< 방법 >

(1) O(n^3) 전처리, O(1) 질의 : brute force 방식으로 가능한 RMQ(a,b)에 대한 답을 모두 저장해놓는다. n^2칸을 채워야하고, 한 칸을 채울 때 최대 O(n)시간이 걸린다.

(2) O(n^2) 전처리, O(1) 질의 : 가능한 RMQ(a,b)에 대한 답을 모두 저장하는데, RMQ(a,b+1) = min(RMQ(a,b) , A[b+1])을 사용하여 n^2칸을 각각 O(1)의 시간으로 채울 수 있다.

(3) O(n) 전처리, O(sqrt(n)) 질의 : 배열을 sqrt(n) 묶음으로 나눈 후 각 묶음의 최솟값을 구하는데에 O(n)이 걸리며, RMQ(a,b)를 구하는 과정에서 이미 답을 구해놓은 구간에서는 더이상 비교를 할 필요가 없다.

(4) O(n log n) 전처리, O(1) 질의 : 각 A[i] 마다 RMQ(i,i+1), RMQ(i,i+2), RMQ(i,i+4), ... 의 정답을 미리 구해놓는다.

구해야 할 정답 수는 최대 n*log n개이다.

 

 

2. 부분합 문제

Sum(a, b) = A[a] + ... + A[b]

 

(1) O(n) 전처리, O(sqrt(n)) 질의

- 배열을 sqrt(n) 묶음으로 나눈다. 각 묶음의 합을 구한다.

- Sum(a,b) 질의 가 주어지면 양 끝부분의 합은 직접 구하고, 중간에 이미 구한 값들은 추가 계산없이 더해준다

- 질의 처리를 위해서는 가장 오른쪽, 왼쪽 그룹 제외 시 최대 sqrt(n)-2 개의 수, 가장자리에 최대 2*sqrt(n)개의 수

    -> 총 O(sqrt(n)) 시간

- update는 i가 속한 그룹만 다시 계산하면 되므로 O(sqrt(n)) 시간

 

(2) O(n) 전처리, O(1) 질의

- O(n) 시간에 PrefixSum[i] = A[1] + ... + A[i] 계산 (1부터 본인까지 합 계산)

- Sum(a,b) = PrefixSum[b] - PrefixSum[a-1]

- update : PrefixSum 다시 계산해야하므로 O(n) 시간

 

 

3. BIT : binary indexed tree (= Fenwick tree)

L[i] = i를 이진수로 나타냈을 때 마지막 1에 해당하는 값

Tree[i] = A[i]부터 앞으로 L[i]개 값의 합

 

L[i] = i & -i

(-i = ~i + 1)

 

4. PrefixSum[i]

 

아래에서 PrefixSum[13] = Tree[13] + PrefixSum[12] = Tree[13] + Tree[12] + PrefixSum[8]

= Tree[13] + Tree[12] + Tree[8]

 

// Fenwick Tree
int sum(int i){
	int a = 0;
    while(i>0){
    	a += tree[i];
        i -= (i&-i);
    }
    return a;
}

// tree update
void update(int i, int num){
	while(i<=n){
    	tree[i] += num;
        i += (i&-i);
    }
}

 

- 트리 생성 시 모든 값이 0으로 초기화

- 모든 PrefixSum 0으로 초기화

- A[i]=x가 될때마다 update(i,x) 호출 = 최대 log n번 호출됨

총 O(n log n) 시간, 질의는 O(log n) 시간

 

 

5. 연습문제 : 달리기

n명의 사람이 달리기를 하고 있다. 각 사람들의 원래 달리기 등수대로 이 사람들을 1~n으로 이름을 붙이자. 달리기 도중에 사람들의 순서를 보면 1~n 사이의 permutation일 것이다. 달리기가 끝나기 전까지, 이 사람들은 자기보다 앞에있는 사람 중 자신보다 등수가 낮거나 같은 사람들은 앞지를 수 있다.
레이스가 끝났을 때 각 사람들이 얻을 수 있는 최고 등수를 구하는 프로그램을 작성하시오.
예를 들어, 6명이 달리기를 하고 있고 중간 등수가 3, 1, 5, 2, 4, 3라고 하자.
첫번째 3번은 1등 (최소한 본인 등수는 유지 가능하므로)
1번은 1등 (자기 앞의 3은 앞지를 수 있으므로)
5번은 3등 (3, 1을 앞지를 수 없으므로)
2번은 2등
4번은 4등
두번째 3번은 3등

풀이

수학적 귀납법.

맨 앞의 사람은 1등이 최고 등수인 것이 자명하다.

앞에 i명이 있을 때 i+1번째 사람의 등수는 앞의 i명 중 본인보다 달리기를 잘하는 사람 수 + 1 이다.

따라서, 다음과 같이 접근한다.

배열 A[i]의 값은 달리기 실력이 i인 사람이 몇명인지를 나타낸다. 현재 x등인 사람의 달리기 실력이 i 일때, 1등에서 x-1등인 사람들 중 달리기 실력이 1 ~ i-1인 사람이 몇명인지 알아내면 된다.