오랜만에 돌아온 알고리즘 공부 시간!
세그먼트 트리의 필요성
A1, A2, … AN 의 수열이 있을 떄, L, R을 입력 받아서 AL 부터 AR 까지의 수열의 합을 구하라.
→ 이런 쿼리가 있다면, 누적합을 이용해서 sum[R] - sum[L-1]을 통해서 쉽게 구할 수 있을 것이다.
→ 하지만, 이렇게 누적합을 구하는 과정에서 중간에 수열의 값이 변한다면, 각각의 누적합에 대해 연산을 실시해야하므로 O(N) 의 시간복잡도가 걸린다.
→ 이러한 연산을 효율적으로 실행할 수 있게 해주는 기법이 세그먼트 트리 기법이다.
세그먼트 트리란
- 각 노드는 특정 구간을 대표한다.
- 노드들은 이진트리 구조를 이룬다. (부모 노드가 대표하는 구간은 자식 노드가 대표하는 구간의 합집합이다. )
- 총 길이는 2^k 꼴일 때, 비 재귀 방식에도 유용하고 이해에도 도움이 되기 떄문에 N이상의 2^k 꼴의 수를 사용한다.
세그먼트 트리의 특징
- 임의의 인덱스에 대해 그 인덱스를 포함하는 노드들이 O(logN) 개 존재한다.
- 임의의 구간에 대해 최대 O(logN) 개의 서로 겹치지 않는 구간들의 합으로 표현할 수 있다.
- 세그먼트 트리의 각 노드는 자신이 담당하는 구간에 공통적으로 더해진 수를 저장한다.
- 점의 값 업데이트: 해당 점을 포함하는 모든 구간에 점의 값을 더하거나 빼서 업데이트한다.
- 구간의 값 업데이트: 해당 구간을 포함하는, 갈라진 구간들에 대해 값을 더하거나 빼서 업데이트 한다.
세그먼트 트리의 사용
- 점 갱신/ 구간 최대, 최소 값 구하기
- 구간에 값 더하기 / 점의 값 구하기
- 구간에 Ai = max(Ai, X) 연산 취하기 / 한점에 적힌 값 구하기
- 구간에 값 더하기/ 구간의 합 구하기/ 구간의 최댓값 구하기
- etc
세그먼트 트리 구현하기
- 재귀 방식: 구현은 좀 더 시간이 걸리고 실제로도 시간이 더 걸리는 반면, 복잡한 연산을 취하기 좋은 확장성을 갖고 있다.
- 비 재귀 방식 : 복잡하지 않은 간단한 걸 구현할 때 구현이 빠르고 실행도 빠르다.
- 재귀 방식의 update
#v 위치의 노드의 값을 x 로 변경 시, 구간의 합에 대한 노드들도 변경
#update(v ,x, 1, 1, SIZE
def update(v, x, node, s, e):
if(s == e) :
tree[node] = x
return
mid = (s + e)/ 2
if(v <= mid):
update(v, x, 2 * node, s, mid)
else:
update(v, x, 2 * node + 1, mid + 1, e)- 재귀 방식의 query
# L ~ R 구간 사이의 합을 구하는 쿼리
# (L부터 R까지의 값을 찾고자 한다.) (node, node가 포함하는 범위의 왼쪽, 오른쪽 끝)
# query(L, R, 1, 1, SIZE)
def query (L ,R, node, S, E):
if(S > R || E < L): # 구하고자 하는 구간을 벗어난 경우
return 0
elif(L <= S && E <= R): #구하고자 하는 구간을 S, E가 포함할 때
return tree[node]
else:
mid = (S + E)/2
return query(L, R, node * 2, S, mid+1, size) + query(L ,R, node * 2 + 1, mid + 1, E, size)- 비 재귀 방식의 update
//update(v,x) : v위치의 노드를 x로 변경. (그 에 따른 구간합도 변경되게.)
void update(v, x){
v += size - 1;
tree[v] = x;
for(int v/2; v >= 1; v /=2)
tree[v] = tree[v * 2] + tree[v* 2 + 1];
}
- 비 재귀 방식의 query
int query(L, R){
L += SIZE -1;
R += SIZE -1; //내가 구하고자하는 인덱스는 트리에서는 size -1 자리의 노드.
int ret = 0;
for(; L <= R; L /=2 , R /= 2){
if(L % 2 == 1) ret += tree[L++];
if(R % 2 == 0) ret += tree[R--];
}
return ret;
}
응용 문제 : 백준 12015 https://www.acmicpc.net/problem/12015
12015번: 가장 긴 증가하는 부분 수열 2
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)
www.acmicpc.net
푼 코드 :
입력받은 수열의 최댓값을 K라고 할 떄, 1 부터 K를 모두 노드로 보고 푼 세그먼트 트리의 방식이다.
각 세그먼트 트리는 가리키는 구간 내 최대 길이라고 할 수 있다.
n에 대해 0부터 n-1까지의 구간에서의 LIS 값을 구한다음, + 1 값으로 update 해주는 방식으로 진행한다.
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <stack>
#include <cstring>
#include <sstream>
#define FAST cin.tie(NULL); ios::sync_with_stdio(false);
using namespace std;
#define NONE -1
#define INF 19876543
// #define SIZE (1 << 17)
long long SIZE;
vector<int> tree;
// int nums[1001];
// long long ans[91];
int N,T;
long long max(long long a, long long b){
return a > b ? a: b;
}
void update(unsigned long v, unsigned long x){//v의 자리를 x로 업데이트
v += SIZE -1;
tree[v]= x;
for(v /= 2; v >= 1; v /= 2)
tree[v] = max(tree[v * 2] , tree[v * 2 + 1]);
}
long long query(unsigned long L, unsigned long R){
L += SIZE -1;
R += SIZE -1; //내가 구하고자하는 인덱스는 트리에서는 size -1 자리의 노드.
long long ret = 0;
for(; L <= R; L /=2 , R /= 2){
if(L % 2 == 1) ret = max(ret, tree[L++]);
if(R % 2 == 0) ret = max(ret, tree[R--]);
}
return ret;
}
bool cmp(pair<int, int> a, pair<int ,int >b){
return a.first < b.first;
}
int main(){
FAST
cin >> N;
SIZE = ( 1 << ((int)log2(N) + 3));
tree.assign(SIZE, 0);
int n;
long long ans = -INF;
for(unsigned long i = 0; i < N ; i++){
cin >> n;
long long best = query(0, n-1);
// cout << "n , best : " << n << " " << best << "\n";
update(n, best + 1);
if (ans < best + 1)
ans = best + 1;
}
cout << ans;
}
세그먼트 트리의 공부는 서울대학교 학생분의 알고리즘 강의 영상을 참고했다.
https://www.youtube.com/watch?v=Afr0yvd-8bA
'알고리즘 > 이론정리' 카테고리의 다른 글
| LIS - lower_bound 로 푸는 이유?(다이나믹 프로그래밍) (2) | 2023.02.21 |
|---|---|
| c++ 프로모션(연산 시 정수형, unsigned 변환) (0) | 2023.02.03 |
| 그래프 - 최단경로에서 이동 경로 찾기 (1) | 2023.01.25 |
| 크루스칼 알고리즘 (1) | 2023.01.23 |
| 플로이드 워셜 알고리즘이란? - 원리를 바탕으로 (0) | 2023.01.22 |