'분류 전체보기' 카테고리의 글 목록

전체

[PS/CP 공부기록] 03. Cartesian Tree, Treap, Implicit Treap 2026.01.13
[PS/CP 공부기록] 02. System of Difference Constraints 2026.01.07
[PS/CP 공부기록] 01. Minimum Steiner Tree in Graph 2026.01.02
[BOJ 27470 // C++] 멋진 부분집합 2025.12.01
[BOJ 34803 // C++] 문자열 로또 2025.11.28
[BOJ 26570 // C++] Semiperfect 2025.11.27

[PS/CP 공부기록] 03. Cartesian Tree, Treap, Implicit Treap

2026. 1. 13. 10:00

※ 이 공부기록은 부정확한 내용이 다수 포함되어있을 수 있다. 또한 이 글은 정보 전달이 주 목적이 아닌 개인적인 기록용이어서 체계적으로 내용이 정리되어 있지 않을 수 있다. 읽는이의 양해를 바란다.

들어가기 전에

지금도 글쓴이는 구현력이 많이 부족하다고 느끼지만, 과거에는 구현력이 매우 부족했었다. (implicit) treap은 그 당시에 익혀보려고 도전했다가 실패했던 자료구조 중 하나이다. 이 때문에 글쓴이는 treap을 막연히 어려운 주제라고 생각하고 있었고, 익히는 도중에도 treap을 제대로 익힐 수 있을지 많은 걱정을 하였었다.

이제 과거의 기억에서 벗어나 treap을 다시 마주할 때가 왔다.

개요

이번 글에서 살펴볼 주제는 Cartesian Tree, Treap, Implicit Treap이다.

Cartesian Tree는 treap과 유사한 점이 많은 자료구조이다. 따라서 이 글에서는 treap을 다루기에 앞서 Cartesian Tree를 먼저 소개할 것이다.

한편, Cartesian Tree는 그 자체만으로도 좋은 성질을 가진 자료구조이기도 하다. PS/CP에서도 이러한 성질을 활용한 문제를 종종 만나볼 수 있다. 따라서 이 글에서는 PS/CP에서 Cartesian Tree가 어떻게 활용되는지 또한 간단히 살펴볼 것이다.

treap은 Randomized Binary Search Tree라고도 불리는 자료구조이다. treap은 (binary search) tree와 heap의 합성어로, BST의 성질과 heap의 성질을 동시에 가지는 특징을 따 이름지어졌다.

PS/CP의 범주에서 treap은 BBST의 역할을 수행하는 자료구조이다. 그런데 PS/CP에서는 정답 코드를 작성하는 시간을 줄이는 것도 중요하므로, BBST를 활용하려는 목적만으로는 그냥 불러와서 사용하면 되는 std::set과 std::map, pbds 등을 제치고 굳이 treap을 직접 구현해 사용할 필요가 없다. 그러면 treap은 공부하지 않아도 되는 자료구조일까?

implicit treap은 key가 추상화된 treap이다. implicit treap은 다양한 쿼리를 처리하기 좋은 자료구조이므로 알아둘 가치가 충분하다. 특히, implicit treap은 많은 경우 implicit splay tree의 기능을 상당수 대체할 수 있다. 그리고 이것이 이번 글의 최종 목표이다.

Cartesian Tree

Cartesian Tree는 서로 다른 수로 구성된 수열에 대하여 다음과 같이 정의되는 binary tree이다.

(1) Cartesian Tree의 각 노드는 주어진 수열의 각 수에 대응된다.

(2) Cartesian Tree에서 inorder traversal(중위순회)을 하면 원래의 수열을 얻는다.

(3) Cartesian Tree는 min-heap property를 갖는다. min-heap property란 부모 노드에 대응되는 수는 (존재하는 모든) 자식 노드에 대응되는 수보다 작아야 한다는 성질을 말한다.

즉, 가볍게 서술하면 Cartesian Tree는 수열에서 가장 작은 수를 root로 하고 그 위치를 기준으로 좌우로 나눠진 두 배열에 대하여 이와 같은 실행을 반복하여 얻게 되는 트리의 각 root를 자식으로 갖는 트리를 말한다.

여기에서 min이라는 것은 (일상적으로 사용하는) 정수의 대소관계만을 뜻하는 것은 아니므로, 대소의 정의를 적절하게 할 수만 있다면 다른 order topology를 대응시켜도 된다. 예를 들어, min-heap property 대신 max-heap property를 적용해도 대소의 정의가 반대로 된 min-heap property를 만족시킨다고 생각할 수 있으므로 정의에 따라 Cartesian Tree라고 볼 수 있다.

Cartesian Tree는 서로 다른 수로 구성된 수열에 대하여 정의되어 있지만, PS/CP 문제풀이에서는 대해서도 등장한 순서에 따라 구분자를 넣는 등의 방법으로 다른 수처럼 취급하여 Cartesian Tree를 활용하기도 한다. 다만 이 경우, 문제 풀이 과정에서 같은 수의 취급에 유의해야 한다.

\(O(n)\) Construction of Cartesian Tree

크기가 \(n\)인 배열의 Cartesian Tree는 몇 가지 방법으로 \(O(n)\)에 구성할 수 있다. 이 글에서는 monotonic stack을 이용한 접근을 알아본다.

수열 \(a_1, a_2,\cdots a_n\)의 Cartesian Tree는 1부터 \(n\)까지의 인덱스 \(i\)에 대하여 다음의 1~4의 과정을 차례대로 진행하는 것으로 구성할 수 있다.

(0) 빈 stack을 준비한다. 이 stack은 monotonic stack이다.

(1) stack이 비거나 끝에 저장된 인덱스의 수열 값이 \(a_i\)보다 작아질 때까지 stack의 원소를 빼낸다.

(2) stack이 비지 않았다면 스택의 끝에 저장된 인덱스의 노드의 오른쪽 자식을 \(i\)로 한다.

(3) (1)에서 stack에서 마지막으로 뺀 원소가 존재한다면 그 원소를 \(i\)의 왼쪽 자식을 그 원소로 한다.

(4) stack에 \(i\)를 넣는다.

랜덤 수열에 대한 Cartesian Tree

수열의 수가 랜덤으로 주어질 때 Cartesian Tree의 높이의 기댓값은 어느 정도일까?

그 답은 quicksort와 비교해 생각해보면 금방 얻을 수 있다. 매번 주어진 배열에서 가장 작은 수를 고르고 그 양 옆의 각 두 부분수열에 대하여 재귀적으로 기대 높이를 구하는 과정에서 배열의 길이가 줄어드는 과정은. quicksort에서 배열의 크기가 줄어드는 과정이랑 완전히 대응된다.

따라서 크기 \(n\)인 랜덤 수열의 Cartesian Tree의 높이의 기댓값은 \(O(\lg n)\)이며, 이 수열의 높이가 \(O(n)\)이 될 확률은 이 수열을 quicksort로 정렬하는 시간복잡도가 \(O(n^2)\)가 될 확률에 가깝다는 것을 알 수 있다. 즉, quicksort의 경우 적절하게 자료의 순서를 먼저 섞어주면 사실상 \(O(n\lg n)\)에 수행할 수 있는 것처럼, 가중치가 임의로 주어진 수열의 Cartesian Tree의 높이는 사실상 \(O(\lg n)\)이 된다.

따라서 랜덤 수열에 대한 Cartesian Tree는 어느 한 쪽으로 노드가 지나치게 치우치지 않은, 어느 정도 균형 잡힌 이진 트리와 같은 모양을 하게 된다는 점을 알 수 있다.

Treap(Randomized Binary Search Tree; Randomized BST)

위와 같은 관찰로부터, key와 랜덤 가중치를 가지는 노드로 구성된, key 순서대로 정렬된 배열의 랜덤 가중치에 대한 Cartesian Tree는 균형 잡힌 이진 트리처럼 다룰 수 있다는 것을 알 수 있다. 이와 같은 구성의 자료구조를 treap이라고 한다.

treap은 tree와 heap이 합쳐져 만들어진 이름이다. treap 자료구조의 key는 BST처럼 정렬되어 있으며, 각 노드의 배치는 랜덤 가중치에 대한 heap 구조를 이루고 있기 때문이다. 다른 이름으로는 랜덤성을 이용해 만든 BST라는 측면에서 Randomized Binary Search Tree라고 부르기도 한다.

treap을 실질적인 BBST처럼 사용하려면 자료의 삽입 및 제거 등 기본 BBST 연산을 수행할 수 있어야 한다. treap에서 이러한 연산은 대부분 split과 merge의 두 가지 기본 연산을 활용해 구현할 수 있다.

split 연산

split은 주어진 treap을 기준이 되는 값 \(val\)을 기준으로 두 개의 treap으로 쪼개는 연산이다.

설명 편의상 \(val\)이 treap의 key 와 distinct하다고 가정하자. 이 때 split은 \(val\)을 기준으로 이 값보다 작은 key가 저장되어 있는 treap과 큰 값이 저장되어 있는 treap으로 쪼갠다. 이를 진행하면서 treap의 min-heap property가 깨지지 않아야 한다는 점에 유의하자.

split하려는 treap의 root와 기준이 되는 값 \(val\)이 주어질 때, split 연산은 (1) root에서부터 시작해서 현재 노드가 어느 쪽 treap에 들어갈지를 기준삼아 leaf까지 내려가는 과정과 (2) 다시 root로 돌아오면서 노드를 적절하게 이어붙여 두 개의 treap으로 split하는 과정으로 이루어져 있다. 이 과정을 자세히 살펴보자.

과정 (1)은 단순하다. 현재 노드의 key와 \(val\)을 비교했을 때 key가 \(val\)보다 작다면 현재 노드는 split 이후 왼쪽 treap에 속하게 될 것이다. 한편, 이 노드의 왼쪽 자식 노드를 root로 갖는 부분 treap의 노드의 모든 key는 현재 노드의 key보다 작은 값을 가지므로, 이 노드들 또한 모두 왼쪽 treap에 속하게 된다. 그러나 이 노드의 오른쪽 자식 노드는 어느 쪽 treap에 속하게 될지 정보가 부족하다. 따라서 오른쪽 노드로 탐색을 진행한다.

key가 \(val\)보다 큰 경우도 위와 거의 같다. 이 경우 현재 노드는 split 이후 오른쪽 treap에 속하게 되며, 이 노드의 오른쪽 자식 노드와 그 밑에 연결된 노드 오른쪽 treap에 속해야 한다는 점을 알 수 있다. 그리고 왼쪽 자식 노드는 아직 어느 쪽 treap에 붙게 될지에 대한 정보가 부족하다. 따라서 왼쪽 노드로 탐색을 진행한다.

이 탐색은 아무런 정보도 담고 있지 않은 null 노드가 나올 때까지 진행한다.

과정 (2)는 정보가 없던 자식 노드쪽의 정보를 재귀적으로 위로 전달하며 왼쪽 treap과 오른쪽 treap을 구성해나가는 과정이다. 정보가 없던 자식 노드에 대하여 왼쪽 treap에 속할 부분treap의 root와 오른쪽 treap에 속할 부분treap의 root를 얻어 현재 노드를 root로 하는 부분treap을 둘로 쪼개어 올라가는 것을 반복하자.

이 때 treap은 Cartesian Tree의 구조를 따르므로, 어떤 노드가 조상 노드의 왼쪽 자식으로 붙어야 하는 상황이라면 부모로 거슬러 올라가는 과정 중 오른쪽으로 올라가는 상황을 처음 만났을 때 그 노드의 왼쪽 자식으로 붙게 되며, 오른쪽 자식으로 붙어야 하는 상황이라면 부모로 거슬러 올라가는 과정 중 왼쪽으로 올라가는 상황을 처음 만났을 때 그 노드의 오른쪽 자식으로 붙게 됨을 확인하자.

한편, 이 과정에서 새로 붙게 되는 부모-자식 관계의 노드쌍은 기존 treap에서도 조상-자손 관계에 있었으므로 이와 같은 수정은 min-heap property를 깨지 않는다는 점을 확인하자.

과정 (2)까지 마치면 split 과정이 종료되며, 분리된 두 treap과 각각의 root 노드를 얻는다.

split 연산의 시간복잡도는 그 과정에서 재귀적으로 들어가는 노드의 깊이에 비례하며, 이 값은 평균적으로 \(O(lg n)\)임을 앞서 살펴보았다. 따라서 각 노드의 가중치를 랜덤으로 부여하면 split의 평균시간복잡도는 \(O(\lg n)\)이 된다.

merge 연산

merge는 주어진 두 개의 treap을 하나의 treap으로 합치는 연산이다. 이 때, 여기에서 주어지는 두 treap의 key의 범위는 서로 겹치지 않아야 한다. 편의상 두 treap을 왼쪽 treap과 오른쪽 treap이라고 부르자.

merge 결과로 얻게 되는 treap의 root는 왼쪽 treap의 root거나 오른쪽 treap의 root일 것이다. 그 외의 노드가 root가 된다면 treap의 min-heap property가 깨지기 때문이다.

먼저 왼쪽 treap의 root의 가중치가 오른쪽 root의 가중치보다 더 작은 경우를 살펴보자. 이 때, 왼쪽 treap의 root는 최종적으로 merge된 treap의 root가 될 것이다. 또한, 왼쪽 treap의 오른쪽 자식을 root로 갖는 부분 treap과 오른쪽 treap을 merge하여 왼쪽 treap의 왼쪽 자식에 붙이면 key의 정렬 순서도 깨지지 않고 min-heap property도 깨지지 않음을 관찰할 수 있다. 따라서 이를 재귀적으로 수행하는 것으로 merge 연산을 수행할 수 있다.

merge 연산의 시간복잡도 또한 split처럼 그 과정에서 재귀적으로 들어가는 노드의 깊이에 비례하며, 이 값은 평균적으로 \(O(\lg n)\)임을 앞서 살펴보았다. 따라서 각 노드의 가중치를 랜덤으로 부여하면 merge의 평균시간복잡도는 \(O(\lg n)\)이 된다.

다른 연산들

split과 merge를 이용하면 BBST가 가져야 하는 모든 연산을 어렵지 않게 구현할 수 있다. 예를 들어 특정 key의 삽입은 key를 기준으로 treap을 split한 뒤 삽입하려는 자료 노드 하나로 구성된 tree를 사이에 넣어 merge를 두 번 하면 된다. 또한 특정 key의 제거는 이 key를 기준으로 각각 왼쪽과 오른쪽 자료로 구성된 treap을 split으로 얻어 이들을 다시 merge하면 된다.

정렬된 자료가 주어졌을 때, Treap을 \(n\)번의 merge를 통해서도 구성할 수 있지만 Cartesian Tree의 \(O(n)\) 구성과 같은 방식으로 \(O(n)\)에 구성할 수도 있다.

Implicit Treap

implicit treap은 treap를 BBST처럼 사용하는 대신 배열에 대응시킨 것과 같이 사용하는 자료구조이다. implicit treap에서 일반 treap의 key에 대응되는 개념은 배열의 인덱스이다. 그러나 implicit treap을 활용하는 과정에서 이러한 인덱스는 쉽게 변경될 수 있고, 실제로 implicit treap은 이러한 변경이 필요할 때 주로 사용하는 자료구조이기도 하다.

implicit treap을 활용하는 대표적인 두 예시를 보자.

(1) 부분배열을 잘라서 다른 위치에 삽입하기

먼저 자르려는 부분배열의 앞뒤와 삽입할 위치를 기준으로 split을 시행한 뒤, 자른 부분배열을 삽입할 위치에 오게끔 적절한 순서로 merge한다.

(2) 부분배열의 자료 순서를 뒤집기(역순으로 바꾸기)

이 작업을 하려면 먼저 뒤집기 연산에 대한 lazy tag를 노드에 기록해둬야 한다.

먼저 뒤집으려는 부분배열의 앞뒤를 기준으로 split을 시행한 뒤, 자른 부분배열 treap의 root에 뒤집기 lazy tag를 toggle한다. 그리고 lazy tag가 켜져 있는 노드에 대한 접근이 필요할 때, lazy tag를 propagate하면서 해당 노드의 두 자식을 swap한다.

어떤 노드와 그 노드의 모든 자손 노드들에 대하여 왼쪽 자식과 오른쪽 자식을 swap하면 그 노드에 대응되는 배열이 뒤집어짐을 확인하자.

implicit treap은 더 이상 BBST가 아니므로 위와 같은 연산으로 key의 정렬이 무너지거나 하는 것은 신경쓸 필요가 없다. 오히려 가상의 key로 생각하고 있는 개념인 배열의 index를 의도대로 바꾸므로 이는 적절한 사용 방법이다. 또한 이 연산을 통해 Cartesian Tree의 min-heap property가 깨지지도 않음을 확인하자.

참고 자료

https://en.wikipedia.org/wiki/Cartesian_tree

https://en.wikipedia.org/wiki/Random_binary_tree

https://en.wikipedia.org/wiki/Treap

https://cp-algorithms.com/data_structures/treap.html

https://usaco.guide/adv/treaps

https://docs.google.com/presentation/d/14xgtdDWnIBwmJRAuIdZ8FvLZcX9uRxnNoGOGAQRDIvc/

728x90

'CP자료모음' 카테고리의 다른 글

[PS/CP 공부기록] 02. System of Difference Constraints (0)	2026.01.07
[PS/CP 공부기록] 01. Minimum Steiner Tree in Graph (0)	2026.01.02

[PS/CP 공부기록] 02. System of Difference Constraints

2026. 1. 7. 10:00

이전 공부기록에 이어서, 그래프에서의 relaxation 개념과 더욱 친숙해지고자 이 주제를 고르게 되었다.

개요

이번 글에서 살펴볼 주제는 System of Difference Constraints이다.

일반적으로 LP(Linear Programming; 선형계획법)은 PS/CP의 범위에서 쉽게 해결하기 어렵다. 그러나 몇몇 형태의 LP 문제는 풀기 쉬운 다른 형태의 문제로 변형할 수 있다.

이 글에서는 해결하기 쉬운 LP 문제의 형태 중 하나인 system of difference constraints를 알아보자.

System of Difference Constraints

System of Difference Constraints는 변수 \(x_1\), \(x_2\), \(\cdots\), \(x_n\)와 상수 \(c_1\), \(c_2\), \(\cdots\), \(c_m\)에 대하여 \(x_j-x_i\le c_k\)꼴의 여러 부등식으로 구성된 연립부등식을 말한다. \(c_k\)는 음수일 수도 있다.

변수와 부등식의 개수가 많아지면 주어진 연립부등식의 해가 존재하는지조차 빠르게 판단하기 어려워진다. 따라서, system of difference constraints를 푼다는 것은 일반적으로 (1)해의 존재성을 판단하고, 해가 존재한다면 (2) 실제로 가능한 해를 하나 구하는 것을 뜻한다.

Constraints Graph

다음과 같이 system of difference constraints에 대응되는 그래프인 Constraints Graph를 만들자. 이 그래프는 weighted directed graph이다.

(1) 각각의 변수 \(x_i\)에 대응되는 정점 \(v_i\)를 생성한다.

(2) 각각의 Difference Constraint \(x_j-x_i\le c_k\)에 대응되는 간선을 생성한다. 이 간선은 정점 \(v_i\)에서 \(v_j\)로 향하는 가중치 \(c_k\)의 간선이다.

두 정점 \(v_p\)와 \(v_q\)에 대하여 \(v_p\)에서 \(v_q\)로 향하는 경로 \(P\)에 대응되는 difference constraints를 나열하고 이들을 모두 합하면 \(\displaystyle x_q-x_p\le \sum c_k\)가 된다. 이 때 \(\displaystyle \sum c_k\)는 경로에 포함된 간선의 가중치의 합을 나타낸다.

위의 관찰에 따라, 서로 다른 두 변수 \(x_i\)와 \(x_j\)에 대하여 \(v_i\)에서 \(v_j\)로 도달 가능한 경로가 존재하는 경우, \(x_j-x_i\)의 값은 항상 \(v_i\)에서 \(v_j\)로의 최단 경로의 길이 이하임을 알 수 있다. 따라서 \(x_i\)들의 값은 constraints graph에서의 최단거리 제약을 만족해야 함을 알 수 있다.

한편, 위 constraints graph에 가상의 정점 \(v'\)을 하나 추가하고, \(v'\)에서 각각의 \(v_i\)로 가중치 0인 간선을 그어보자. 이 때, \(v'\)로부터 \(v_i\)까지의 최단거리는 앞서 살펴본 constraints graph에서의 최단거리 제약을 모두 만족함을 어렵지 않게 알 수 있다. (최단거리의 성질과 relaxation에 대해 잘 생각해보자.)

두 정점 사이에 최단경로가 존재하지 않는 경우는 두 가지가 있는데, 하나는 \(v_i\)에서 \(v_j\)로 도달 가능한 경로가 존재하지 않는 경우이고 다른 하나는 경로 중간에 negative cycle이 존재하는 경우이다. 경로가 존재하지 않는 경우, \(v_j-v_i\)에 대한 \(v_j-v_i\le c_k\)꼴의 제약이 없다는 뜻이므로 그 값은 어떤 값이 되어도 상관없다. 반면 negative cycle이 존재하는 경우, (엄밀한 표현은 아니지만) \(v_j-v_i\le -\infty\)가 성립한다는 뜻이므로 주어진 system of difference constraints는 해가 없음을 알 수 있다.

문제 특성상 가중치가 음수인 간선이 등장하고 negative cycle도 발견해야 하므로, 음수 간선이 있는 경우에도 효과적으로 동작하는 최단거리 알고리즘을 활용해야 한다. 일반적으로 PS/CP에서 system of difference constraints를 풀 때에는 Bellman-Ford를 이용한다.

식 정리 패턴

이 문단에서는 PS/CP에서 볼 수 있는 system of difference constraints 유형의 문제에서 식을 정리할 때 쓰이는 몇 가지 패턴을 소개한다. 각각만 놓고 보면 당연해 보이지만, 처음 보거나 익숙하지 않으면 떠올리기 어려울 수 있으니 유의하자.

(0) \(x_j-x_i\ge k\) 형태

위 부등식은 \(x_i-x_j\le -k\)와 같이 변형이 가능하다.

(1) \(x_j-x_i=c_k\) 형태, \(x_i=x_j\) 형태

종종 연립부등식으로 나타나는 조건과 함께 \(x_j-x_i=c_k\) 형태의 등식을 같이 만족시키는 해를 찾을 것을 요구하는 문제가 출제된다. 이 경우 해당 등식을 \(x_j-x_i\le c_k\)와 \(x_j-x_i\ge c_k\)의 두 부등식으로 나누어 생각해 조건을 difference constraints로 변형할 수 있다.

물론 \(x_i=x_j\) 또한 \(c_k\)가 0인 특수한 경우로 보고 똑같이 변형할 수 있다.

(2) \(x_i\le k\) 형태, \(x_j\ge k\) 형태

0을 나타내는 가상의 정점 \(v\)를 하나 생각하면, \(x_i\le k\)는 \(x_i-0\le k\), \(x_j\ge k\)는 \(x_j-0\ge k\)이므로 \(v\)를 활용한 그래프 모델링을 생각할 수 있다.

(3) 구간합

\(x_i+x_{i+1}+\cdots+x_j\le k\) 꼴의 부등식으로 이루어진 연립부등식은 이 글에서 설명한 system of difference constraints의 형태는 아니다. 그러나 \(x_i\)의 prefix sum인 나타내는 \(p_i\)를 이용하면 위 연립부등식을 \(p_j-p_{i-1}\le k\) 꼴의 \(p_i\)에 대한 system of difference constraints로 변형할 수 있다.

(4) 로그

\(\frac{x_j}{x_i}\le c_k\)꼴의 연립부등식이 주어진다면 양변에 로그를 취해 \(\log x_j-\log x_i \le \log c_k\)의 형태로 변형할 수 있다. 이는 \(\log x_i\)들에 대한 difference constraints로 생각할 수 있다.

예시 문제: [LuoguP4926] 倍杀测量者

참고 자료

CLRS 24.4

728x90

'CP자료모음' 카테고리의 다른 글

[PS/CP 공부기록] 03. Cartesian Tree, Treap, Implicit Treap (0)	2026.01.13
[PS/CP 공부기록] 01. Minimum Steiner Tree in Graph (0)	2026.01.02

[PS/CP 공부기록] 01. Minimum Steiner Tree in Graph

2026. 1. 2. 10:00

공부기록을 남기기 시작하며

처음으로 오프라인 대회(Good Bye, BOJ 2025!)를 나가고 느낀 점이 있다.

그동안 쉬운 문제를 빠르게 해결하는 실력을 갖추기 위해 쉬운 문제를 대량으로 풀어왔다. 그 결실이 있었는지, 글쓴이는 대회에서 상대적으로 쉬운 문제를 빠르게 해결할 수 있게 된 것을 느꼈다. 그러나 구현이 많이 필요하거나 고급 이론을 활용해야 하는 문제에서 글쓴이가 많이 약하다고 느꼈다.

하지만 쉬운 문제도 빠르게 못 풀던 예전과는 다르게, 이제는 단순히 쉬운 문제를 반복해서 푸는 것보다 다양한 이론, 알고리즘, 자료구조를 접하고, 구현 실력이 필요한 문제 또한 시도해 대회 환경에서 더 많은 문제를 푸는 것을 목표로 해도 될 것 같는 생각이 들었다.

이제 한동안 잘 모르거나 얕게만 알던 다양한 주제를 공부하고 그 내용을 기록으로 남기려고 한다.

이번 글에서 살펴볼 주제는 Minimum Steiner Tree in Graph이다.

PS/CP에서 찾아볼 수 있는 Minimum Steiner Tree 문제는 크게 둘로 구분지어 생각할 수 있는 것 같다. 그 중 하나는 그래프에서 정의되어 있고, 다른 하나는 좌표평면 위의 점과 유클리드 거리에 대하여 정의되어 있다. 이 글에서는 전자의 문제를 다룬다.

Minimum Steiner Tree in Graph

먼저 Minimum Steiner Tree가 무엇인지 알아보자.

정점의 집합 \(V\)와 (음이 아닌) 가중치가 있는 간선의 집합 \(E\)로 구성된 연결그래프 \(G\)에 대하여, \(V\)의 (공집합이 아닌) 부분집합을 \(K\)라 하자. 이 때, Steiner Tree는 \(K\)의 모든 정점을 포함하는 \(G\)의 subtree를 말한다. 또한 Minimum Steiner Tree는 모든 Steiner Tree 중 간선의 가중치의 합이 가장 작은 Steiner Tree를 말한다. 또한 \(K\)에 속한 정점들을 Terminal이라고 부른다.

\(K\)의 크기가 1이면 Minimum Steiner Tree는 그 정점만을 포함한 가중치 0의 subtree가 됨은 자명하다. 또한 \(K\)의 크기가 2이면 두 정점을 잇는 최단경로의 형태가 Minimum Steiner Tree가 될 것이며, \(K\)의 크기가 3이면 각 정점에 대하여 세 정점으로부터의 최단거리의 합을 구했을 때 그 합이 가장 작은 정점을 중심으로 \(K\)의 세 정점을 최단거리로 이은 형태가 Minimum Steiner Tree가 될 것이다. 그러나 \(K\)의 크기가 4 이상이면 이와 같은 단순한 접근은 점점 어려워지게 된다.

이 문제는 Minimum Spanning Tree를 구하는 문제의 일반화로 생각할 수 있다. \(K=V\)인 경우 Minimum Spanning Tree와 정확히 같은 문제가 됨을 관찰하자. 그러나 이 문제는 NP-Hard 문제임이 잘 알려져있다. 따라서 P=NP가 아닌 이상에는 Minimum Steiner Tree 문제를 다항시간 내에 해결하기 어려울 것이다.

Minimum Steiner Tree를 구하기 위한 다양한 approximation algorithm이 존재하지만 이러한 알고리즘은 PS/CP에서 나오는 문제들과 잘 맞지 않는다. 일반적으로 PS/CP에서는 정확한 해를 구할 것을 요구하는 문제가 주로 나오기 때문이다. 따라서 이 글에서는 Exact Minimum Steiner Tree를 구하는 내용만을 다룬다.

Dreyfus-Wagner Algorithm

Minimum Steiner Tree를 구하는 알고리즘으로 Dreyfus-Wagner 알고리즘이 잘 알려져 있다. 이 알고리즘은 다음과 같은 DP로 진행된다.

\(K\)의 부분집합 \(K'\)과 \(V\)에 속하는 정점 \(v\)에 대하여 \(dp[K'][v]\)를 \(K'\)에 속한 모든 정점을 포함하면서 \(v\) 또한 포함하는 가장 가중치가 작은 \(G\)의 서브트리의 가중치로 정의하자. 즉, \(dp[K'][v]\)는 \(K'\cup\{v\}\)에 대한 Minimum Steiner Tree의 가중치를 나타낸다.

이 때, \(dp[K'][v]\)의 값은 다음과 같은 두 가지 방식으로 다른 상태로부터 계산할 수 있다.

(1) 이 상태를 나타내는 Minimum Steiner Tree에서 \(v\)의 degree가 2 이상인 경우:

\(K'\)을 두 집합 \(K_1\)과 \(K_2\)로 나누면 \(dp[K'][v]=dp[K_1][v]+dp[K_2][v]\)가 되게끔 할 수 있다.

(2) 이 상태를 나타내는 Minimum Steiner Tree에서 \(v\)의 degree가 1인 경우:

그 Minimum Steiner Tree에서 \(v\)와 연결된 정점을 \(u\)라 하고, 그 연결 간선의 가중치를 \(w\)라 하자. 이 때 \(dp[K'][v]=dp[K'][u]+w\)가 성립한다.

(1)의 경우, \(K'\)의 모든 부분집합에 대하여 문제를 먼저 해결해둔다면 계산을 쉽게 처리할 수 있다. 다만 이 값을 계산하는 시점에는 \(K'\)를 어떻게 쪼개야 최적인지에 대한 정보를 가지고 있지 않으므로, 가능한 모든 방법으로 \(K'\)를 쪼개봐야 한다는 점에 유의하자.

(2)의 경우, 이 과정을 degree가 1이 아닌 정점이 나올 때까지 반복하면 \(K'\)의 Minimum Steiner Tree를 얻게 됨을 관찰하자. 따라서, \(K'\)의 Minimum Steiner Tree의 값에서부터 relaxation을 반복하여 값을 갱신해나가는 것으로 (2)의 계산을 처리할 수 있다. 이해하기 어렵다면 Dijkstra 알고리즘의 relaxation 과정을 생각해보자.

기저 상태를 각 \(K\)의 원소 \(k\)에 대하여 \(dp[\{k\}][k]\)의 값을 0, 나머지 상태의 값을 전부 (가상의) 무한대로 설정하고 위와 같이 \(dp\)의 값을 계산해 문제를 해결하자.

relaxation 과정에 binary heap을 사용한다고 가정하면, Dreyfus-Wagner 알고리즘의 시간복잡도는 \(O(V3^K+(V+E)2^K\log V)\)와 같다. 여기서 \(V3^K\)는 DP에서의 (1)의 처리에 드는 시간복잡도이고, \((V+E)2^K\log V\)는 DP에서의 (2)의 처리에 드는 시간복잡도이다. (1)의 시간복잡도를 이해하기 어렵다면, bitmasking으로 \(K\)까지의 정수가 나타내는 각 집합에 대하여 각각의 부분집합의 개수의 합이 \(O(3^K)\)과 같다는 내용을 찾아보도록 하자.

따라서 Dreyfus-Wagner 알고리즘은 \(V\)와 \(E\)가 어느 정도 크더라도 \(K\)가 충분히 작다면 PS/CP에서 충분히 제한 내에 사용할 수 있다.

Dreyfus-Wagner 알고리즘 구현 팁

bitmask를 활용하여 표현된 어떤 집합을 나타내는 정수\(x\)가 있을 때, \(x\)의 모든 부분집합은 초기값이 \(x\)인 변수 \(x'\)에 대하여 \(x':=(x'-1)\&x\)를 반복하는 것으로 모두 접근할 수 있다.

Dijkstra 알고리즘을 문제 제한에 따라 다양한 방식으로 최적화할 수 있듯이, 위 알고리즘의 중간 과정인 relaxation은 문제 상황에 따라 문제에 따라 다양하게 변형해 복잡도를 낮출 수 있다. 예를 들어 노드가 적지만 dense한 그래프의 경우 우선순위 큐를 사용하지 않고 \(O(N^2)\)으로 relaxation을 처리할 수 있다. 또한 가중치의 크기가 매우 제한적이라면 Dial 알고리즘처럼 버킷을 활용해 relaxation을 처리할 수 있다.

Rectilinear Minimum Steiner Tree

Rectilinear Minimum Steiner Tree 문제는 좌표평면 위에 \(K\)개의 점이 주어졌을 때 이 점들을 축과 평행한 선분만으로 모두 연결하기 위해 그어야 하는 선분의 길이의 최솟값을 구하는 문제이다.

주어진 \(K\)개의 점에 대하여 두 축과 각각 평행한 직선을 그려 얻게 되는 격자형태의 그래프를 Hanan Grid라고 부른다.

\(K\)개의 점에 대한 Rectilinear Minimum Steiner Tree는 이 \(K\)개의 정점으로 생성된 Hanan Grid 위에서 항상 찾을 수 있다. 따라서 \(K\)가 충분히 작을 경우 Dreyfus-Wagner 알고리즘으로 Rectilinear Minimum Steiner Tree 문제 또한 해결할 수 있다.

여담

Dijkstra 알고리즘처럼 relaxation을 진행하는 아이디어는 Dreyfus-Wagner 알고리즘에서만 사용되는 것이 아닌 다른 많은 문제에서도 종종 사용되는 트릭이니 잘 기억해두자.

참고 자료

https://en.wikipedia.org/wiki/Steiner_tree_problem

https://en.wikipedia.org/wiki/Rectilinear_Steiner_tree

https://en.wikipedia.org/wiki/Hanan_grid

https://codeforces.com/blog/entry/91601

https://kopricky.github.io/code/Academic/steiner_tree.html

728x90

'CP자료모음' 카테고리의 다른 글

[PS/CP 공부기록] 03. Cartesian Tree, Treap, Implicit Treap (0)	2026.01.13
[PS/CP 공부기록] 02. System of Difference Constraints (0)	2026.01.07

[BOJ 27470 // C++] 멋진 부분집합

2025. 12. 1. 10:00

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 27470번 문제인 멋진 부분집합이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/27470

주어진 원소 중 절반 이상의 원소가 특정 소인수를 포함하고 있다면, 임의의 원소를 뽑았을 때 그 수가 특정 소인수를 포함하고 있을 확률은 50% 이상이다.

따라서, 위와 같은 원소 뽑기를 충분히 많이 반복하면 답이 되는 소인수를 포함하는 경우가 나오지 않을 확률은 0에 수렴하게 된다.

위의 관찰을 이용하여 충분히 많은 횟수의 원소를 뽑아 해당 수의 소인수들이 특정 소인수가 될 수 있는지 판단해 문제를 해결하자.

이 과정에서 이미 확인한 소인수를 다시 확인할 필요는 없으므로, 중복된 확인을 하지 않기 위한 최적화를 같이 진행해주자. 방법은 다양하지만 글쓴이는 주어진 원소에서 확인한 소인수는 나누어주는 방식으로 구현하였다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <random>
using namespace std;

bool sieve[32768];
vector<int> vec, ans;

void init() {
    sieve[0] = sieve[1] = 1;
    for (int i = 2; i * i < 32768; i++) {
        if (sieve[i]) continue;
        for (int j = i * i; j < 32768; j += i) sieve[j] = 1;
    }
    for (int i = 2; i < 31622; i++) {
        if (!sieve[i]) vec.emplace_back(i);
    }
}

int N;
int A[500000], AA[500000];
random_device rd;
mt19937 mt(rd());

void func(int i) {
    int cnt = 0;
    for (int k = 0; k < N; k++) {
        if (!(AA[k] % i)) {
            cnt++;
            while (!(AA[k] % i)) AA[k] /= i;
        }
    }
    if (cnt >= (N + 1) / 2) {
        cout << "YES\n";
        cnt = (N + 1) / 2;
        for (int k = 0; k < N && cnt; k++) {
            if (!(A[k] % i)) cnt--, cout << A[k] << ' ';
        }
        exit(0);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    init();

    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) AA[i] = A[i];
    for (int _ = 0; _ < 40; _++) {
        int x = AA[mt() % N];
        for (auto &i:vec) {
            if (i * i > x) break;
            if (x % i) continue;
            func(i);
            while (!(x % i)) x /= i;
        }
        if (x > 1) func(x);
    }

    cout << "NO";
}

728x90

'BOJ' 카테고리의 다른 글

[BOJ 34803 // C++] 문자열 로또 (0)	2025.11.28
[BOJ 26570 // C++] Semiperfect (0)	2025.11.27
[BOJ 34679 // C++] 홍수 (0)	2025.11.26
[BOJ 29338 // C++] Склад Оби-Вана Кеноби (0)	2025.04.03
[BOJ 29343 // C++] Шифровка (0)	2025.04.02

[BOJ 34803 // C++] 문자열 로또

2025. 11. 28. 10:00

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 34803번 문제인 문자열 로또이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/34803

주어진 제한조건에서, 각 문자열에서 얻을 수 있는 길이 \(K\)의 부분문자열은 총 \(L-K+1\)개임을 관찰하자.

따라서 주어진 문제는 총 \(N(L-K+1)\)개의 부분문자열 중 가장 많이 등장한 문자열의 등장 횟수를 구하는 문제로 볼 수 있다.

모든 부분문자열의 길이는 100 이하이고 부분문자열의 총 개수는 2000 이하이므로, 정렬이나 map 등을 이용하여 각 각 부분문자열의 등장 횟수를 구해 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <map>
using namespace std;

int L, N, K, ans;
string s[20];
map<string, int> mp;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> L >> N;
    for (int i = 0; i < N; i++) cin >> s[i];
    cin >> K;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k + K <= L; k++) mp[s[i].substr(k, K)]++;
    }

    for (auto &p:mp) ans = max(ans, p.second);
    cout << ans;
}

728x90

'BOJ' 카테고리의 다른 글

[BOJ 27470 // C++] 멋진 부분집합 (0)	2025.12.01
[BOJ 26570 // C++] Semiperfect (0)	2025.11.27
[BOJ 34679 // C++] 홍수 (0)	2025.11.26
[BOJ 29338 // C++] Склад Оби-Вана Кеноби (0)	2025.04.03
[BOJ 29343 // C++] Шифровка (0)	2025.04.02

[BOJ 26570 // C++] Semiperfect

2025. 11. 27. 10:00

※ 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 26570번 문제인 Semiperfect이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/26570

100만 미만의 양의 정수 \(m\)이 주어질 때, \(m\)의 자기 자신을 제외한 약수 중 일부(전체도 가능)의 합으로 \(m\)을 만들 수 있는지를 판별하는 문제이다.

100만 미만의 정수 중 가장 많은 수는 240개의 약수를 가진다(720720 등). 따라서 \(m\)의 모든 약수를 활용하여 \(m\)을 생성할 수 있는지 판단하는 방식으로 문제를 충분히 해결할 수 있다.

이러한 유형의 문제를 해결하는 대표적인 방법으로 knapsack dp가 있다. 특히 이 문제에서는 존재의 여부만을 확인하면 되므로 0과 1로 모든 상태를 표현할 수 있고, 따라서 비트셋을 활용한 knapsack 구현이 가능하다. 글쓴이는 이를 활용하여 문제를 해결하였다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <bitset>
using namespace std;

int T;
bitset<1000000> st;

bool func(int n) {
    st = 0;
    st[0] = 1;
    for (int i = 1; i * i <= n; i++) {
        if (n % i) continue;
        if (i != n) st = (st << i) | st;
        if (n / i != n && n / i != i) st = (st << (n / i)) | st;
    }
    return st[n];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> T;
    while (T--) {
        int x; cin >> x;
        if (func(x)) cout << "Semiperfect\n";
        else cout << "NOT Semiperfect\n";
    }
}

728x90

'BOJ' 카테고리의 다른 글

[BOJ 27470 // C++] 멋진 부분집합 (0)	2025.12.01
[BOJ 34803 // C++] 문자열 로또 (0)	2025.11.28
[BOJ 34679 // C++] 홍수 (0)	2025.11.26
[BOJ 29338 // C++] Склад Оби-Вана Кеноби (0)	2025.04.03
[BOJ 29343 // C++] Шифровка (0)	2025.04.02

PREV 1 2 3 4 ···389 NEXT

전체

들어가기 전에

개요

Cartesian Tree

\(O(n)\) Construction of Cartesian Tree

랜덤 수열에 대한 Cartesian Tree

Treap(Randomized Binary Search Tree; Randomized BST)

split 연산

merge 연산

다른 연산들

Implicit Treap

관련 문제

참고 자료

'CP자료모음' 카테고리의 다른 글

개요

System of Difference Constraints

Constraints Graph

식 정리 패턴

관련 문제

참고 자료

'CP자료모음' 카테고리의 다른 글

공부기록을 남기기 시작하며

Minimum Steiner Tree in Graph

Dreyfus-Wagner Algorithm

Dreyfus-Wagner 알고리즘 구현 팁

Rectilinear Minimum Steiner Tree

여담

관련 문제

참고 자료

'CP자료모음' 카테고리의 다른 글

'BOJ' 카테고리의 다른 글

'BOJ' 카테고리의 다른 글

'BOJ' 카테고리의 다른 글

티스토리툴바