https://www.acmicpc.net/problem/10775
10775번: 공항
예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불
www.acmicpc.net
숫자가 1부터 G까지 하나씩 있는 집합 A가 있을 때 주어진 숫자 x에 대해 아래의 연산을 수행한다.
- 집합 A에서 x보다 작거나 같은 원소 중 가장 큰 숫자를 찾는다.
- 위에서 찾은 원소를 A에서 제거한다.
- 위에서 찾은 원소를 반환한다.
일감은 구간 트리(segment tree)를 이용하여 해결하는 것이다.
- 구간 트리에 대해서 i번째 원소를 i로 초기화 한다.
- x에 대해 구간 트리의 [1, x] 구간에 대해 가장 큰 숫자를 질의한다.
- 위에서 찾은 숫자에 해당하는 원소를 0으로 업데이트한다.
구간 트리를 이용한 해법의 연산당 시간 복잡도는 O(log G)이다. P개의 연산에 대해 전체 시간 복잡도는 O(P log G)이다.
문제를 풀고 나서 알고리즘 분류를 보니 분리 집합(disjoint set, union-find) 이 눈에 보였다. 분리 집합을 이용한 해법은 아래와 같다.
- 크기가 G 인 분리 집합을 준비한다.
- x에 대해 x번째 원소의 대표 원소를 찾는다. (find(x))
- x의 대표 집합을 바로 앞의 원소가 속한 집합에 병합한다. 이때 바로 앞 집합이 대표 집합이 되어야 한다. (rank 최적화를 사용하면 안 된다.) (union(find(x)-1, find(x)))
분리 집합을 이용한 해법의 연산당 시간 복잡도는 O(log* G)이다.
https://en.wikipedia.org/wiki/Disjoint-set_data_structure#:~:text=Time%20complexity%5Bedit%5D
Disjoint-set data structure - Wikipedia
MakeSet creates 8 singletons. After some operations of Union, some sets are grouped together. In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of
en.wikipedia.org
비슷한 문제를 5달 전에 푼 적이 있는데 완전히 까먹고 있었다. 반복 학습의 중요성을 깨닫는다.
https://www.acmicpc.net/problem/16566
16566번: 카드 게임
첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로
www.acmicpc.net
'problem solving' 카테고리의 다른 글
| c++ stl vector 원소를 참조할 때 주의할 점 (0) | 2022.04.15 |
|---|---|
| BOJ 1019 책 페이지 (0) | 2022.04.12 |
| BOJ 12858 Range GCD (0) | 2022.02.27 |
| BOJ 1031 스타대결 (0) | 2022.02.26 |
| BOJ 24231 해석 (0) | 2022.02.20 |