A L I D A
NOMENCLATURE
- $V$ : 노드(Node, Vertex)의 개수
- $E$ : 간선(Edge)의 개수
- $n$ : 원소의 개수 (또는 $N$)
- $\log n$ : 밑이 2인 $\log_2 n$을 간략하게 표기
- 노드 = 정점
- 간선 = 엣지
Algorithm & Data structure
Linear data structure
Array
배열(Array)는 메모리 상에 원소를 연속하게 배치한 자료구조를 말한다. C++에서는 배열의 원소가 한 번 정해지면 ( int A[10] ) 이후 크기를 변경하는 것이 일반적으로 불가능하다.
- 시간복잡도
- 접근, 맨 뒤 삽입/제거 $O(1)$
- 탐색, 임의 위치 삽입/제거 $O(n)$
- 공간복잡도: $O(n)$
- C++ (Pure) #1
더보기
#include <cstdio>
int A[10] = {10, 20, 30};
int len = 3;
void insert(int idx, int num) {
for(int i=len; i>idx; i--) A[i] = A[i-1];
A[idx] = num;
len++;
}
void erase(int idx) {
len--;
for(int i=idx; i<len; i++) A[i] = A[i+1];
}
void Print() {
for(int i=0; i<len; i++) printf("%d ", A[i]);
puts("");
}
int main() {
printf("insert test\n");
insert(3, 40); Print(); // 10 20 30 40
insert(1, 50); Print(); // 10 50 20 30 40
insert(0, 15); Print(); // 15 10 50 20 30 40
printf("erase test\n");
erase(4); Print(); // 15 10 50 20 40
erase(1); Print(); // 15 50 20 40
erase(3); Print(); // 15 50 20
}- C++ (Pure) #2
더보기
#include <bits/stdc++.h>
using namespace std;
int* A;
int len = 0; // 실제 데이터가 들어있는 크기
int capacity = 0; // 삽입 가능한 최대 크기
void init(){
A = new int[1];
capacity = 1;
}
void expand(){
int* tmp = new int[2*capacity];
for(int i=0;i<len;i++)
tmp[i] = A[i];
delete[] A;
A = tmp;
capacity = 2*capacity;
}
void insert(int idx, int num) {
if(len == capacity) expand();
for(int i=len; i>idx; i--) A[i] = A[i-1];
A[idx] = num;
len++;
}
void erase(int idx) {
len--;
for(int i=idx; i<len; i++) A[i] = A[i+1];
}
void Print() {
for(int i=0; i<len; i++) printf("%d ", A[i]);
puts("");
}
int main() {
init();
printf("insert test\n");
insert(0, 10); Print(); // 10, len = 1, capacity = 1
insert(0, 30); Print(); // 30 10, len = 2, capacity = 2
insert(1, 20); Print(); // 30 20 10, len = 3, capacity = 4
insert(3, 40); Print(); // 30 20 10 40, len = 4, capacity = 4
insert(1, 50); Print(); // 30 50 20 10 40, len = 5, capacity = 8
insert(0, 15); Print(); // 15 30 50 20 10 40, len = 6, capacity = 8
}
std::vector
STL의 벡터(vector) 컨테이너를 사용하면 배열과 유사하지만 크기를 가변적으로 사용할 수 있다. 벡터는 가변적인 배열의 역할을 수행하기 때문에 C++에서 광범위하게 사용된다.
- 시간복잡도
- push_back : 원소를 끝에 추가 $\text{Amortized } O(1)$
- pop_back : 마지막 원소 제거 $O(1)$
- [], at : 임의의 위치에 원소 확인/변경 $O(1)$
- insert, erase : 임의의 위치에 원소 추가/제거 $O(n)$
- 공간복잡도: $O(n)$
- 동적 배열이 필요한 경우 매 번 길이가 capacity에 도달할 때마다 배열의 길이를 2배씩 증가시켜주면 삽입 연산의 시간복잡도가 Amortized $O(1)$이 된다. (사실 상 $O(1)$과 동일한 시간복잡도)
- operator= : 깊은 복사(deep copy)가 발생한다.
- C++ (w/ STL)
더보기
#include <cstdio>
#include <vector>
using namespace std;
vector<int> A;
void Print() {
for(int i=0; i<A.size(); i++) printf("%d ", A[i]);
puts("");
}
int main() {
A.push_back(10), A.push_back(20), A.push_back(30);
printf("insert test\n");
A.insert(A.begin()+3, 40); Print(); // 10 20 30 40
A.insert(A.begin()+1, 50); Print(); // 10 50 20 30 40
A.insert(A.begin()+0, 15); Print(); // 15 10 50 20 30 40
printf("erase test\n");
A.erase(A.begin()+4); Print(); // 15 10 50 20 40
A.erase(A.begin()+1); Print(); // 15 50 20 40
A.erase(A.begin()+3); Print(); // 15 50 20
}
Linked list
연결 리스트(Linked List)는 노드들이 포인터로 연결되어 있는 선형 자료구조이다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있으며, 데이터의 동적 추가 및 삭제가 용이하다. 연결하는 방법 및 개수에 따라 단일 연결 리스트(single linked list), 이중 연결 리스트(double linked list), 원형 연결 리스트(circular linked list)로 구분할 수 있다.
- 시간복잡도
- 접근, 탐색 $O(n)$
- 앞/중간/뒤 삽입, 삭제 $O(1)$ (노드 위치를 알고 있는 경우)
- 공간복잡도: $O(n)$
- 배열과 달리 임의의 원소로 가기 위해서는 첫번째 원소부터 순서대로 방문해야 한다.
- 배열과 달리 메모리 상의 배치가 불연속적이다.
- 다음 원소의 주소값을 가지고 있어야 하므로 64비트(=8바이트) 컴퓨터 기준 $8N$ 바이트만큼 추가적인 메모리가 필요하다. (배열 대비 오버헤드가 있음)
- C++ (Pure)
더보기
#include <bits/stdc++.h>
using namespace std;
const int LM = 1000005;
int dat[LM], pre[LM], nxt[LM];
int unused = 1;
void insert(int addr, int num) {
dat[unused] = num;
pre[unused] = addr;
nxt[unused] = nxt[addr];
if(nxt[addr] != -1) pre[nxt[addr]] = unused;
nxt[addr] = unused;
unused++;
}
void erase(int addr){
nxt[pre[addr]] = nxt[addr];
if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}
void traverse(){
int cur = nxt[0];
while(cur != -1){
printf("%d ", dat[cur]);
cur = nxt[cur];
}
puts("");
}
int main(int argc, char **argv){
fill(pre, pre+LM, -1);
fill(nxt, nxt+LM, -1);
printf("****** insert_test *****\n");
insert(0, 10); // 10(address=1)
traverse();
insert(0, 30); // 30(address=2) 10
traverse();
insert(2, 40); // 30 40(address=3) 10
traverse();
insert(1, 20); // 30 40 10 20(address=4)
traverse();
insert(4, 70); // 30 40 10 20 70(address=5)
traverse();
printf("****** erase_test *****\n");
erase(1); // 30 40 20 70
traverse();
erase(2); // 40 20 70
traverse();
erase(4); // 40 70
traverse();
erase(5); // 40
traverse();
}
std::list
STL의 list 컨테이너는 이중 연결 리스트(double linked list)이다.
- 시간복잡도
- $k$번째 원소를 확인/변경 $O(k)$
- 임의의 위치에 원소를 추가/제거 $O(1)$
- 공간복잡도: $O(n)$
- C++ (w/ STL)
더보기
#include <cstdio>
#include <list>
using namespace std;
list<int> L;
void traverse() {
for(auto l : L) printf("%d ", l);
puts("");
}
int main() {
L = {1, 2}; // 1 2
auto t = L.begin(); // t는 1을 가리킴
L.push_front(10); traverse(); // 10 1 2
L.push_back(5); traverse(); // 10 1 2 5
L.insert(t, 6); traverse(); // 10 6 1 2 5
t = L.erase(t); // 1 제거, t가 가리키는 값은 2
printf("%d", *t); // 2
}
Stack
스택(Stack)은 마지막에 삽입된 요소가 가장 먼저 삭제되는 LIFO(Last In, First Out) 방식의 선형 자료구조이다. 이는 함수의 호출 스택 처리, 수식의 괄호 검사 등에 활용된다. 스택은 제일 상단이 아닌 나머지 원소들의 확인과 변경이 원칙적으로 불가능한 특징이 있다.
- 시간복잡도
- 원소 추가/제거: $O(1)$
- 제일 상단의 원소 확인: $O(1)$
- 공간복잡도: $O(n)$
- C++ (Pure)
더보기
#include <cstdio>
constexpr int LM = 1000005;
struct Stack{
int stack[LM];
int pos=0;
void push(int x) { stack[pos++] = x; }
void pop() { pos--; }
bool empty() { return (pos==0); }
int top() { return stack[pos-1]; }
} S;
int main() {
S.push(5); S.push(4); S.push(3);
printf("%d\n", S.top()); // 3
S.pop(); S.pop();
printf("%d\n", S.top()); // 5
S.push(10); S.push(12);
printf("%d\n", S.top()); // 12
S.pop();
printf("%d\n", S.top()); // 10
}- C++ (w/ STL)
더보기
#include <cstdio>
#include <stack>
using namespace std;
stack<int> S;
int main() {
S.push(5); S.push(4); S.push(3);
printf("%d\n", S.top()); // 3
S.pop(); S.pop();
printf("%d\n", S.top()); // 5
S.push(10); S.push(12);
printf("%d\n", S.top()); // 12
S.pop();
printf("%d\n", S.top()); // 10
}
Queue
큐(Queue)는 처음 삽입된 요소가 가장 먼저 삭제되는 FIFO(First In, First Out) 방식의 선형 자료구조이다. 운영체제의 작업 스케줄링, 네트워크 요청 처리 등에 사용된다. 큐는 제일 앞/뒤가 아닌 나머지 원소들의 확인과 변경이 원칙적으로 불가능한 특징이 있다.
- 시간복잡도
- 원소 추가/제거: $O(1)$
- 제일 앞/뒤의 원소 확인: $O(1)$
- 공간복잡도: $O(n)$
- C++ (Pure) #1
더보기
#include <cstdio>
constexpr int LM = 1000005;
struct Queue{
int fr=0, re=0;
int que[LM];
void push(int x) { que[re++] = x; }
void pop() { fr++; }
int front() { return que[fr]; }
int back() { return que[re-1]; }
} Q;
int main() {
Q.push(10); Q.push(20); Q.push(30);
printf("%d %d\n", Q.front(), Q.back()); // 10 30
Q.pop(); Q.pop();
Q.push(15); Q.push(25);
printf("%d %d\n", Q.front(), Q.back()); // 30 25
}- C++ (Pure) #2
더보기
// JUNGOL 5436 연결요소 개수세기
// https://jungol.co.kr/problem/5436
#include <bits/stdc++.h>
using namespace std;
constexpr int LM = 1005;
int N,M;
vector<int> adj[LM];
int visited[LM];
int que[LM*LM];
int fr,re;
bool bfs(int node){
if(visited[node]) return false;
que[re++] = node;
visited[node] = 1;
while(fr < re) {
int cur = que[fr++];
for(int next : adj[cur]){
if(visited[next]) continue;
que[re++] = next;
visited[next] = 1;
}
}
return true;
}
int main(int argc, char **argv){
scanf("%d%d", &N, &M);
for(int i=0; i<M; i++){
int a,b; scanf("%d%d", &a, &b);
adj[a].push_back(b);
adj[b].push_back(a);
}
int ans = 0;
for(int i=1; i<=N; i++){
if(bfs(i)){
ans++;
}
}
printf("%d\n", ans);
}- C++ (w/ STL)
더보기
#include <cstdio>
#include <queue>
using namespace std;
queue<int> Q;
int main() {
Q.push(10); Q.push(20); Q.push(30);
printf("%d %d\n", Q.front(), Q.back()); // 10 30
Q.pop(); Q.pop();
Q.push(15); Q.push(25);
printf("%d %d\n", Q.front(), Q.back()); // 30 25
}
Deque
덱(Deque)은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조로, 스택과 큐의 특성을 모두 갖는다. 더 유연한 데이터 처리가 가능해 다양한 알고리즘 구현에 유용하다.
- 시간복잡도
- 원소 추가/제거: $O(1)$
- 제일 앞/뒤의 원소 확인: $O(1)$
- 공간복잡도: $O(n)$
- 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능 (하지만 STL deque는 가능)
- C++ (Pure)
더보기
#include <cstdio>
constexpr int LM = 1000005;
int deque[2*LM+1];
int fr=LM, re=LM;
void push_front(int x){ deque[--fr] = x; }
void push_back(int x){ deque[re++] = x; }
void pop_front(){ fr++; }
void pop_back(){ re--; }
int front(){ return deque[fr]; }
int back(){ return deque[re-1]; }
int main() {
push_back(30); // [30]
printf("%d ", front()); printf("%d\n", back()); // 30 30
push_front(25); // [25 30]
push_back(12); printf("%d\n", back()); // 12
push_back(62); // [25 30 12 62]
pop_front(); // [30 12 62]
printf("%d\n", front()); // 30
pop_front(); // [12 62]
printf("%d\n", back()); // 62
}- C++ (w/ STL)
더보기
#include <cstdio>
#include <deque>
using namespace std;
deque<int> DQ;
int main() {
DQ.push_back(30); // [30]
printf("%d ", DQ.front()); printf("%d\n", DQ.back()); // 30 30
DQ.push_front(25); // [25 30]
DQ.push_back(12); printf("%d\n", DQ.back()); // 12
DQ.push_back(62); // [25 30 12 62]
DQ.pop_front(); // [30 12 62]
printf("%d\n", DQ.front()); // 30
DQ.pop_front(); // [12 62]
printf("%d\n", DQ.back()); // 62
}
Tree & hierarchy
트리(Tree)는 계층적 관계를 표현하기 위한 비선형 자료구조로, 노드(node)와 노드를 연결하는 엣지(edge)로 구성된다. 상위 개념과 하위 개념이 명확히 나뉘는 구조를 표현하는 데 적합하며, 파일 시스템, 조직도, 수식 구조, 게임 상태 트리 등 다양한 곳에서 사용된다.
트리는 기본적으로 사이클이 존재하지 않으며, 하나의 루트(root)를 기준으로 부모–자식 관계가 정의된다. 이러한 성질 때문에 그래프의 특수한 형태로 볼 수 있지만, 일반적인 그래프와는 다른 알고리즘과 성질을 가진다. 이진 트리, 이진 탐색 트리, 균형 트리(AVL, Red-Black Tree) 등은 트리 구조를 기반으로 한 대표적인 자료구조들이다.
Tree
그래프 이론에서 트리는 무방향이면서 사이클이 없는 연결 그래프(undirected, acyclic, connected graph)으로 정의된다. 동치인 성질로는 다음을 들 수 있다.
- 정점이 $V$개일 때 간선의 수는 항상 $V-1$개이다
- 임의의 간선 하나를 제거하면 그래프는 더 이상 연결 그래프가 아니다
- 임의의 두 정점 사이의 경로는 항상 유일하다
이러한 성질 때문에 트리에서는 DFS, BFS를 사용할 때 방문 관리가 단순해지고, 구조 자체가 문제의 조건으로 주어지는 경우가 많다.
Binary tree
이진 트리(binary tree)는 각 노드가 가질 수 있는 자식의 수가 최대 2개인 트리를 말한다. 왼쪽 자식(left child)과 오른쪽 자식(right child)이라는 개념이 명확히 구분된다. 이진 트리는 구조적 제약만 있을 뿐, 값의 크기나 정렬 규칙은 포함하지 않는다. 이진 트리는 이후 등장하는 이진 탐색 트리, 힙, 세그먼트 트리 등의 기반이 되는 구조다.
이진 트리에는 대표적으로 다음과 같은 순회(traversal)가 정의된다.
- 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder), 레벨 순회(Level-order)
- 전위/중위/후위 순회를 하는 예제 C++
더보기
#include <bits/stdc++.h>
using namespace std;
struct Node{
char left;
char right;
};
int N;
map<char, Node> tree;
// 전위순회
void preOrder(char node){
if(node=='.') return;
printf("%c", node);
preOrder(tree[node].left);
preOrder(tree[node].right);
}
// 중위순회
void inOrder(char node){
if(node=='.') return;
inOrder(tree[node].left);
printf("%c", node);
inOrder(tree[node].right);
}
// 후위순회
void postOrder(char node){
if(node=='.') return;
postOrder(tree[node].left);
postOrder(tree[node].right);
printf("%c", node);
}
int main(int argc, char **argv){
scanf("%d", &N);
for(int i=0;i<N;i++){
char node, left, right;
cin >> node >> left >> right;
tree[node].left = left;
tree[node].right = right;
}
preOrder('A'); printf("\n");
inOrder('A'); printf("\n");
postOrder('A'); printf("\n");
}
Binary search tree
이진 탐색 트리(binary search tree, BST)는 이진 트리에 값의 대소 관계 규칙을 추가한 자료구조다. 각 노드에 대해 다음 조건을 만족한다.
- 왼쪽 서브트리의 모든 값 < 현재 노드의 값
- 오른쪽 서브트리의 모든 값 > 현재 노드의 값
이 규칙 덕분에 탐색, 삽입, 삭제를 트리의 높이에 비례하는 시간에 수행할 수 있고, 중위 순회를 하면 항상 정렬된 순서로 값이 나온다. 시간 복잡도는 다음과 같다.
- 시간복잡도
- 삽입, 삭제, 탐색 평균 $O(\log n)$, 최악 $O(n)$
- 공간복잡도: $O(n)$
Balanced tree
이진 탐색 트리(BST)는 왼쪽 < 루트 < 오른쪽 규칙만 지키면 되기 때문에, 입력 순서가 나쁘면 트리가 한쪽으로 길게 늘어져서(편향) 사실상 연결 리스트처럼 되어버릴 수 있다. 이렇게 되면 탐색/삽입/삭제가 평균적으로는 빠르더라도, 최악의 경우 높이가 $N$까지 커져서 연산이 $O(N)$으로 무너진다.
균형 트리(balanced tree)는 이런 최악 상황을 막기 위해, 삽입/삭제가 일어날 때마다 트리의 높이가 너무 커지지 않도록 스스로 형태를 조정하는 BST 계열 자료구조다. 핵심 목표는 항상 트리의 높이를 $O(\log N)$ 수준으로 유지해서 탐색, 삽입, 삭제를 최악 시간복잡도까지 $O(\log N)$ 으로 보장하는 것이다.
균형 트리의 핵심 목표는 다음과 같다.
- 트리의 높이를 항상 $O(\log N)$ 수준으로 유지
- 탐색, 삽입, 삭제 연산을 최악의 경우에도 $O(\log N)$ 으로 보장
대표적인 균형 트리로는 AVL Tree와 Red-Black Tree가 있다. PS에서 자주 사용하는 set, map은 내부적으로 이러한 균형 트리(Red-Black Tree 계열) 기반으로 구현되어 있어, 원소가 항상 정렬된 상태를 유지하면서도 연산이 $O(\log N)$에 수행된다.
std::set
STL에서 제공하는 set은 자가 균형 이진 검색 트리(self-balancing binary search tree)의 일종인 Red Black 트리 자료구조로 구현되어 있으며 '키' 만을 사용한다. 이는 요소의 중복을 허용하지 않는 모든 경우에 유용하게 사용된다.
- 시간복잡도
- 삽입, 삭제, 탐색, lower_bound, next, prev 모두 $O(\log n)$
- 공간복잡도: $O(n)$
- C++ (w/ STL)
더보기
// Set : https://blog.encrypted.gg/1013
#include <bits/stdc++.h>
using namespace std;
int main(){
set<int> s;
s.insert(-10); s.insert(100); s.insert(15); // {-10, 15, 100}
s.insert(-10); // {-10, 15, 100}
cout << s.erase(100) << '\n'; // {-10, 15}, 1
cout << s.erase(20) << '\n'; // {-10, 15}, 0
if(s.find(15) != s.end()) cout << "15 in s\n";
else cout << "15 not in s\n";
cout << s.size() << '\n'; // 2
cout << s.count(50) << '\n'; // 0
for(auto e : s) cout << e << ' ';
cout << '\n';
s.insert(-40); // {-40, -10, 15}
set<int>::iterator it1 = s.begin(); // {-40(<-it1), -10, 15}
it1++; // {-40, -10(<-it1), 15}
auto it2 = prev(it1); // {-40(<-it2), -10, 15}
it2 = next(it1); // {-40, -10, 15(<-it2)}
advance(it2, -2); // {-40(<-it2), -10, 15}
auto it3 = s.lower_bound(-20); // {-40, -10(<-it3), 15}
auto it4 = s.find(15); // {-40, -10, 15(<-it4)}
cout << *it1 << '\n'; // -10
cout << *it2 << '\n'; // -40
cout << *it3 << '\n'; // -10
cout << *it4 << '\n'; // 15
}
std::map
STL에서 제공하는 map은 자가 균형 이진 검색 트리(self-balancing binary search tree)의 일종인 Red Black 트리 자료구조로 구현되어 있으며 '키-값' 쌍을 사용한다. 각 키는 유일하며 이를 통해 값을 조회할 수 있다. 데이터의 효율적인 저장과 검색에 쓰인다.
- 시간복잡도
- 삽입, 삭제, 탐색, lower_bound, next, prev 모두 $O(\log n)$
- 공간복잡도: $O(n)$
- C++ (w/ STL)
더보기
// Map : https://blog.encrypted.gg/1013
#include <bits/stdc++.h>
using namespace std;
int main(){
map<string, int> m;
m["hi"] = 123;
m["bkd"] = 1000;
m["gogo"] = 165; // ("bkd", 1000), ("gogo", 165), ("hi", 123)
cout << m.size() << '\n'; // 3
m["hi"] = -7; // ("bkd", 1000), ("gogo", 165), ("hi", -7)
if(m.find("hi") != m.end()) cout << "hi in m\n";
else cout << "hi not in m\n";
m.erase("bkd"); // ("gogo", 165), ("hi", 123)
for(auto e : m)
cout << e.first << ' ' << e.second << '\n';
auto it1 = m.find("gogo");
cout << it1->first << ' ' << it1->second << '\n'; // gogo 165
}
Trie
Trie(트라이)는 문자열을 효율적으로 저장하고 검색하는 트리형 자료구조로, 각 노드는 문자열의 접두사를 공유하며 계층적으로 구성된다. "삽입(insert)" 연산을 통해 문자를 추가하고, "탐색(search)" 연산을 통해 특정 문자열이 존재하는지 빠르게 확인할 수 있다. 노드에 값을 저장하거나 마킹하는 방식으로 단어의 끝을 나타내며, 해시맵 기반 구현 또는 배열을 활용한 최적화 기법을 적용하면 $O(|L|)$의 시간 복잡도로 동작한다. Trie는 자동완성, 사전(dictionary), 문자열 검색 등 다양한 문제에서 활용된다.
- 시간복잡도
- 삽입, 삭제, 탐색 $O(|L|)$
- $|L|$ : 문자열 $L$의 길이
- 공간복잡도: $O(n \times A)$ ($A$는 문자(알파벳) 집합의 크기)
- 문자열을 그냥 배열에 저장하는 것보다 최대 '4 x 글자의 종류' 배만큼 메모리를 더 사용한다 (e.g., 각 단어가 알파벳 대문자로만 구성되어 있을 경우 104배)
- 이론적인 시간복잡도와는 별개로 실제로는 트라이가 해시, 이진검색트리에 비해 훨씬 느리며 공간복잡도도 훨씬 크다. 일반적인 문자열 문제는 해시, 이진검색트리를 사용하면 되지만 자동완성 같은 특수한 활용에서는 트라이가 필요하다
- C++ (Pure)
더보기
// 문자열 집합 boj.kr/14425
#include <bits/stdc++.h>
using namespace std;
const int LM = 500 * 10000 + 5; // 최대 등장 가능한 글자의 수 (길이 500인 문자열 10000개)
const int ROOT = 1;
int N, M;
int unused = 2;
bool chk[LM]; // 해당 정점이 문자열의 끝인지 여부 저장
int nxt[LM][26]; // 각 정점에서 자식의 정점 번호
// 배열에 문자열 저장 : char 1칸 (1바이트)
// Trie에 문자열 저장 : int 26칸 (4x26바이트)
int c2i(char c) { return c-'a'; }
// Trie
void insert( string& s ) {
int cur = ROOT;
for ( auto c : s ) {
int i = c2i( c );
if ( nxt[cur][i] == -1 )
nxt[cur][i] = unused++;
cur = nxt[cur][i];
}
chk[cur] = true;
}
bool find( string& s ) {
int cur = ROOT;
for ( auto c : s ) {
int i = c2i( c );
if ( nxt[cur][i] == -1 ) return false;
cur = nxt[cur][i];
}
return chk[cur];
}
void erase( string& s ) {
int cur = ROOT;
for ( auto c : s ) {
int i = c2i( c );
if ( nxt[cur][i] == -1 ) return;
cur = nxt[cur][i];
}
chk[cur] = false;
}
int main( int argc, char** argv ) {
for ( int i = 0; i < LM; i++ ) {
fill( nxt[i], nxt[i] + 26, -1 );
}
scanf( "%d%d", &N, &M );
while ( N-- ) {
string s;
cin >> s;
insert( s );
}
int ans = 0;
while ( M-- ) {
string s;
cin >> s;
ans += find( s );
}
printf( "%d\n", ans );
}- C++(Pure, 구조체 버전)
더보기
// 문자열 집합 boj.kr/14425
#include <bits/stdc++.h>
using namespace std;
const int LM = 500*10000+5;
int N,M;
int c2i(char c) { return c-'a'; }
struct TrieNode {
TrieNode* child[26];
bool terminal;
TrieNode() :terminal(false){
memset(child, 0, sizeof(child));
}
~TrieNode(){
for(int i=0; i<26; i++){
if(child[i]) delete child[i];
}
}
void insert(const char* key){
if(*key==0) terminal = true;
else {
int next = c2i(*key);
if(child[next] == NULL) child[next] = new TrieNode();
child[next]->insert(key+1);
}
}
TrieNode* find(const char* key){
if(*key==0) return this;
int next = c2i(*key);
if(child[next] == NULL) return NULL;
return child[next]->find(key+1);
}
};
int main(int argc, char **argv){
//freopen("s_in_1345.txt", "r", stdin);
scanf("%d%d",&N,&M);
TrieNode trie;
while(N--){
string s; cin >> s;
trie.insert(s.c_str());
}
int ans = 0;
while(M--) {
string s; cin >> s;
TrieNode* t = trie.find(s.c_str());
if(t != nullptr && t->terminal) ans++;
}
printf("%d\n", ans);
}
Heap
힙(heap)은 완전 이진 트리를 기반으로 하는 자료구조로, 각 노드의 값이 자식 노드보다 크거나 같은(최대 힙) 또는 작거나 같은(최소 힙)을 만족한다. 우선순위 큐의 구현에 주로 사용된다.
- 시간복잡도
- 삽입, 삭제 $O(\log n)$
- 최대/최소 확인 $O(1)$
- $n$개 요소로 힙 만들기 : $O(n)$
- 공간복잡도: $O(n)$
- C++ (Pure) (Max heap)
더보기
#include <cstdio>
constexpr int NUM = 10;
constexpr int LM = 105;
int A[] = { 5,2,7,1,3,8,4,6,10,9 };
int heap[LM];
int hn = 0;
void swap(int &a, int &b) {
int t = a;
a = b;
b = t;
}
void push(int nd) {
heap[++hn] = nd;
for (int c = hn; c > 1; c /= 2) {
if (heap[c] > heap[c / 2]) {
swap(heap[c], heap[c / 2]);
}
else {
break;
}
}
}
void pop() {
swap(heap[1], heap[hn--]);
for (int c = 2; c <= hn; c *= 2) {
if (c < hn && heap[c + 1] > heap[c]) {
c++;
}
if (heap[c] > heap[c / 2]) {
swap(heap[c], heap[c / 2]);
}
else {
break;
}
}
}
int main() {
for(int i = 0; i < NUM; i++) printf("%d ", A[i]); // 5 2 7 1 3 8 4 6 10 9
printf("\n");
// max heap push
for(int i = 0; i < NUM; i++) { push(A[i]); }
for(int i = 1; i <= hn; i++) { printf("%d ", heap[i]); } // 10 9 7 6 8 5 4 1 3 2
printf("\n");
// max heap pop
while (hn > 1) { pop(); }
for(int i = 1; i <= NUM; i++) printf("%d ", heap[i]); // 1 2 3 4 5 6 7 8 9 10
printf("\n");
}- C++ (Pure) (Min heap)
더보기
#include <cstdio>
constexpr int NUM = 10;
constexpr int LM = 105;
int A[] = { 5,2,7,1,3,8,4,6,10,9 };
int heap[LM];
int hn = 0;
void swap(int &a, int &b) {
int t = a;
a = b;
b = t;
}
void push(int nd) {
heap[++hn] = nd;
for (int c = hn; c > 1; c /= 2) {
if (heap[c] < heap[c / 2]) { // 변경: 최소 힙 조건
swap(heap[c], heap[c / 2]);
}
else {
break;
}
}
}
void pop() {
swap(heap[1], heap[hn--]);
for (int c = 2; c <= hn; c *= 2) {
if (c < hn && heap[c + 1] < heap[c]) { // 변경: 최소 힙 조건
c++;
}
if (heap[c] < heap[c / 2]) { // 변경: 최소 힙 조건
swap(heap[c], heap[c / 2]);
}
else {
break;
}
}
}
int main() {
for(int i = 0; i < NUM; i++) printf("%d ", A[i]); // 5 2 7 1 3 8 4 6 10 9
printf("\n");
// min heap push
for(int i = 0; i < NUM; i++) { push(A[i]); }
for(int i = 1; i <= hn; i++) { printf("%d ", heap[i]); } // 최소 힙 구조 확인
printf("\n");
// min heap pop
while (hn > 1) { pop(); }
for(int i = 1; i <= NUM; i++) printf("%d ", heap[i]); // 10 9 8 7 6 5 4 3 2 1
printf("\n");
}
Priority queue
우선순위 큐(priority queue)는 원소들이 우선순위에 따라 정렬되며, 우선순위가 가장 높은 원소가 가장 먼저 삭제된다. 힙(heap)을 사용하여 구현할 수 있으며, 다익스트라 같은 그래프 알고리즘에서 중요하게 사용된다.
- 시간복잡도 (heap과 동일)
- 삽입, 삭제 $O(\log n)$
최대/최소 확인 $O(1)$
$n$개 요소로 힙 만들기 : $O(n)$
- 삽입, 삭제 $O(\log n)$
- 공간복잡도: $O(n)$
- C++ (Pure) (Max heap)
더보기
#include <cstdio>
#define LM 1000
class PriorityQueue {
private:
int heap[LM];
int hn;
void swap(int &a, int &b) {
int t = a; a = b; b = t;
}
public:
PriorityQueue() : hn(0) {}
void push(int nd) {
heap[++hn] = nd;
for (int c = hn; c > 1; c /= 2) {
if (heap[c] > heap[c / 2]) {
swap(heap[c], heap[c / 2]);
} else {
break;
}
}
}
void pop() {
if (hn == 0) return;
swap(heap[1], heap[hn--]);
for (int c = 2; c <= hn; c *= 2) {
if (c < hn && heap[c + 1] > heap[c]) {
c++;
}
if (heap[c] > heap[c / 2]) {
swap(heap[c], heap[c / 2]);
} else {
break;
}
}
}
int top() {
return hn > 0 ? heap[1] : -1;
}
bool empty() {
return hn == 0;
}
};
int main() {
// Max heap
PriorityQueue pq;
pq.push(5); pq.push(2); pq.push(7); pq.push(1); pq.push(3);
pq.push(8); pq.push(4); pq.push(6); pq.push(10); pq.push(9); // 5 2 7 1 3 8 4 6 10 9
printf("%d ", pq.top()); // 10
pq.pop(); printf("%d ", pq.top()); // 9
pq.pop(); printf("%d ", pq.top()); // 8
pq.pop(); printf("%d ", pq.top()); // 7
pq.pop(); printf("%d ", pq.top()); // 6
pq.pop(); printf("%d ", pq.top()); // 5
pq.pop(); printf("%d ", pq.top()); // 4
pq.pop(); printf("%d ", pq.top()); // 3
pq.pop(); printf("%d ", pq.top()); // 2
pq.pop(); printf("%d ", pq.top()); // 1
printf("\n");
}- C++ (w/ STL) (Max heap)
더보기
#include <cstdio>
#include <queue>
#define LM 1000
int main() {
// Max heap
std::priority_queue<int> pq;
pq.push(5); pq.push(2); pq.push(7); pq.push(1); pq.push(3);
pq.push(8); pq.push(4); pq.push(6); pq.push(10); pq.push(9); // 5 2 7 1 3 8 4 6 10 9
printf("%d ", pq.top()); // 10
pq.pop(); printf("%d ", pq.top()); // 9
pq.pop(); printf("%d ", pq.top()); // 8
pq.pop(); printf("%d ", pq.top()); // 7
pq.pop(); printf("%d ", pq.top()); // 6
pq.pop(); printf("%d ", pq.top()); // 5
pq.pop(); printf("%d ", pq.top()); // 4
pq.pop(); printf("%d ", pq.top()); // 3
pq.pop(); printf("%d ", pq.top()); // 2
pq.pop(); printf("%d ", pq.top()); // 1
printf("\n");
}- C++ (w/ STL) (Min heap)
더보기
#include <cstdio>
#include <vector>
#include <queue>
#define LM 1000
int main() {
// Min heap
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
pq.push(5); pq.push(2); pq.push(7); pq.push(1); pq.push(3);
pq.push(8); pq.push(4); pq.push(6); pq.push(10); pq.push(9); // 5 2 7 1 3 8 4 6 10 9
printf("%d ", pq.top()); // 1
pq.pop(); printf("%d ", pq.top()); // 2
pq.pop(); printf("%d ", pq.top()); // 3
pq.pop(); printf("%d ", pq.top()); // 4
pq.pop(); printf("%d ", pq.top()); // 5
pq.pop(); printf("%d ", pq.top()); // 6
pq.pop(); printf("%d ", pq.top()); // 7
pq.pop(); printf("%d ", pq.top()); // 8
pq.pop(); printf("%d ", pq.top()); // 9
pq.pop(); printf("%d ", pq.top()); // 10
printf("\n");
}
Hash
해시(hash)는 키-값 쌍을 저장하는데 사용되며, 해시 함수를 통해 키를 해시 테이블의 주소로 변환하여 데이터를 효율적으로 조회, 삽입, 삭제할 수 있다. 빠른 데이터 검색에 유리하다.
- 시간복잡도
- 탐색, 삽입, 삭제 평균 $O(1)$, 최악 $O(n)$
- 공간복잡도: $O(n)$
- C++ (Pure) (Chaining)
더보기
// Hash using chaining : https://blog.encrypted.gg/1009
#include <bits/stdc++.h>
using namespace std;
const int M = 1'000'003;
const int a = 1'000;
const int MX = 500'005; // 최대 삽입 횟수
int head[M];
int pre[MX], nxt[MX];
string key[MX];
int val[MX];
int unused = 0;
int myHash(string& s){
int h=0;
for(auto x : s)
h = (h*a + x) % M;
return h;
}
int find(string k) {
int h = myHash(k);
int idx = head[h];
while(idx != -1) {
if(key[idx] == k) return idx;
idx = nxt[idx];
}
return -1;
}
void insert(string k, int v) {
int idx = find(k);
if(idx != -1) {
val[idx] = v;
return;
}
int h = myHash(k);
key[unused] = k;
val[unused] = v;
if(head[h] != -1) {
nxt[unused] = head[h];
pre[head[h]] = unused;
}
head[h] = unused;
unused++;
}
void erase(string k) {
int idx = find(k);
if(idx == -1) return;
if(pre[idx] != -1) nxt[pre[idx]] = nxt[idx];
if(nxt[idx] != -1) pre[nxt[idx]] = pre[idx];
int h = myHash(k);
if(head[h] == idx) head[h] = nxt[idx];
}
int main(int argc, char **argv){
fill(head, head+M, -1);
fill(pre, pre+MX, -1);
fill(nxt, nxt+MX, -1);
cout << "start!\n";
insert("orange", 724); // ("orange", 724)
insert("melon", 20); // ("orange", 724), ("melon", 20)
assert(val[find("melon")] == 20);
insert("banana", 52); // ("orange", 724), ("melon", 20), ("banana", 52)
insert("cherry", 27); // ("orange", 724), ("melon", 20), ("banana", 52), ("cherry", 27)
insert("orange", 100); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
assert(val[find("banana")] == 52);
assert(val[find("orange")] == 100);
erase("wrong_fruit"); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
assert(find("orange") == -1);
erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
insert("orange", 15); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15)
assert(val[find("orange")] == 15);
insert("apple", 36); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36)
insert("lemon", 6); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36), ("lemon", 6)
insert("orange", 701); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 701), ("apple", 36), ("lemon", 6)
assert(val[find("cherry")] == 27);
erase("xxxxxxx");
assert(find("xxxxxxx") == -1);
assert(val[find("apple")] == 36);
assert(val[find("melon")] == 20);
assert(val[find("banana")] == 52);
assert(val[find("cherry")] == 27);
assert(val[find("orange")] == 701);
assert(val[find("lemon")] == 6);
cout << "good!\n";
}- C++ (Pure) (Open addressing)
더보기
// Hash using open addressing : https://blog.encrypted.gg/1009
#include <bits/stdc++.h>
using namespace std;
const int M = 1'000'003;
const int a = 1'000;
const int EMPTY = -1;
const int OCCUPY = 0;
const int DUMMY = 1;
int status[M]; // EMPTY, OCCUPY, DUMMY
string key[M];
int val[M];
int myHash(string& s){
int h=0;
for(auto x : s)
h = (h*a + x) % M;
return h;
}
int find(string k) {
int idx = myHash(k);
while(status[idx] != EMPTY) {
if(status[idx] == OCCUPY && key[idx] == k) return idx;
idx = (idx+1) % M;
}
return -1;
}
void insert(string k, int v) {
int idx = find(k);
if(idx != -1) {
val[idx] = v;
return ;
}
idx = myHash(k);
while(status[idx] == OCCUPY)
idx = (idx+1) % M;
key[idx] = k;
val[idx] = v;
status[idx] = OCCUPY;
}
void erase(string k) {
int idx = find(k);
if(idx != -1) status[idx] = DUMMY;
}
int main(int argc, char **argv){
fill(status, status+M, -1);
cout << "start!\n";
insert("orange", 724); // ("orange", 724)
insert("melon", 20); // ("orange", 724), ("melon", 20)
assert(val[find("melon")] == 20);
insert("banana", 52); // ("orange", 724), ("melon", 20), ("banana", 52)
insert("cherry", 27); // ("orange", 724), ("melon", 20), ("banana", 52), ("cherry", 27)
insert("orange", 100); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
assert(val[find("banana")] == 52);
assert(val[find("orange")] == 100);
erase("wrong_fruit"); // ("orange", 100), ("melon", 20), ("banana", 52), ("cherry", 27)
erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
assert(find("orange") == -1);
erase("orange"); // ("melon", 20), ("banana", 52), ("cherry", 27)
insert("orange", 15); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15)
assert(val[find("orange")] == 15);
insert("apple", 36); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36)
insert("lemon", 6); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 15), ("apple", 36), ("lemon", 6)
insert("orange", 701); // ("melon", 20), ("banana", 52), ("cherry", 27), ("orange", 701), ("apple", 36), ("lemon", 6)
assert(val[find("cherry")] == 27);
erase("xxxxxxx");
assert(find("xxxxxxx") == -1);
assert(val[find("apple")] == 36);
assert(val[find("melon")] == 20);
assert(val[find("banana")] == 52);
assert(val[find("cherry")] == 27);
assert(val[find("orange")] == 701);
assert(val[find("lemon")] == 6);
cout << "good!\n";
}- C++ (w/ STL)
더보기
// Hash using stl : https://blog.encrypted.gg/1009
#include <bits/stdc++.h>
using namespace std;
unordered_set<int> s;
int main(int argc, char **argv){
cout << "start!\n";
s.insert(-10); s.insert(100); s.insert(15); // {-10, 100, 15}
s.insert(-10); // {-10, 100, 15}
cout << s.erase(100) << '\n'; // 1
cout << s.erase(20) << '\n'; // 0
if(s.find(15) != s.end()) cout << "15 in s\n"; // 15 in s
else cout << "15 not in s\n";
cout << s.size() << '\n'; // 2
cout << s.count(50) << '\n'; // 0
for(auto e : s) cout << e << ' '; // 15 -10
cout << '\n';
cout << "good!\n";
}std::unordered_set
STL에서 제공하는 unordered_set은 Hash로 구현되어 있으며 '키' 만을 사용한다. 이는 요소의 중복을 허용하지 않는 모든 경우에 유용하게 사용된다.
- 시간복잡도
- 탐색, 삽입, 삭제 평균 $O(1)$, 최악 $O(n)$
- 공간복잡도: $O(n)$
std::unordered_map
STL에서 제공하는 unordered_map은 Hash로 구현되어 있으며 '키-값' 쌍을 사용한다. 각 키는 유일하며 이를 통해 값을 조회할 수 있다. 데이터의 효율적인 저장과 검색에 쓰인다.
- 시간복잡도
- 탐색, 삽입, 삭제 평균 $O(1)$, 최악 $O(n)$
- 공간복잡도: $O(n)$
Hash table
해시 테이블(hash table)은 키(key)를 해시 함수(hash function)에 넣어 배열 인덱스(=버킷)로 바꾼 뒤, 그 위치에 값을 저장하는 자료구조다. 목표는 탐색/삽입/삭제를 평균적으로 매우 빠르게 처리하는 것이다. 다만 서로 다른 키가 같은 인덱스로 매핑되는 충돌(collision)은 반드시 발생할 수밖에 없고, 해시 테이블 구현은 결국 충돌을 어떻게 처리하느냐로 나뉜다.
Chaining
체이닝(chaining) 각 버킷에 연결 리스트(또는 동적 배열)를 두고, 같은 버킷으로 들어온 원소들을 그 안에 모아두는 방식이다. 구현이 직관적이고, 삭제가 비교적 깔끔하다. 버킷 수 M이 충분하고 해시 함수가 괜찮으면 평균적으로 각 버킷의 길이는 짧게 유지된다. 반대로 특정 버킷으로 몰리면 그 버킷 내부에서 선형 탐색이 일어나 최악 성능이 무너진다.
Open addressing
개방주소법(open addressing)은 버킷 자체에는 원소 하나만 두고, 충돌이 나면 다른 빈 칸을 찾아 '다음 위치로 밀어 넣는' 방식이다. 대표적으로 linear probing(한 칸씩), quadratic probing(제곱 간격), double hashing(해시를 한 번 더) 등이 있다. 포인터 구조가 없어 캐시 친화적이라 빠를 수 있지만, 삭제 처리가 까다롭고(보통 tombstone 마킹), 로드 팩터(load factor, 채워진 비율)가 높아지면 성능이 급격히 떨어질 수 있다(클러스터링 문제).
PS에서 std::unordered_map / std::unordered_set은 평균 $O(1)$을 기대하고 쓰지만, 최악 $O(n)$도 가능하다. 특히 해시 충돌이 의도적으로 유발되는 입력이나, 로드 팩터가 높은 상태에서는 성능이 크게 흔들릴 수 있다. 시간 제한으로 해시가 계속 터지는 상황이면 set/map(균형 트리, $O(\log n)$)로 바꾸는 게 더 안정적인 선택이 되기도 한다.
Graph
그래프(graph)는 노드들과 이를 연결하는 엣지들로 구성된 자료구조이다. 방향성, 가중치 유무에 따라 다양한 종류가 있으며, 네트워크 구조, 경로 찾기 등에 사용된다.
- 공간복잡도
- 인접 행렬 $O(V^2)$
- 인접 리스트 $O(V+E)$
- 인접 행렬 구현은 두 점의 연결여부를 자주 확인하거나 $E$가 $V^2$와 가까울 때 사용하면 효율적
- 인접 리스트 구현은 특정 정점에 연결된 모든 정점을 자주 확인하거나 $E$가 $V^2$보다 훨씬 작을 때 효율적이다 (일반적으로 인접 리스트가 필요한 상황이 PS에서 자주 나옴)
- 차수(degree) : 각 노드에 대해 엣지로 연결된 이웃한 노드의 개수
- 무방향 그래프(undirected graph) : 엣지의 방향이 없는 그래프 (degree 존재)
- 방향 그래프(directed graph): 엣지의 방향이 있는 그래프 (indegree, outdegree 존재)
- 사이클 : 임의의 한 점에서 출발해 자기 자신으로 돌아올 수 있는 경로
- 순환 그래프(cyclic graph) : 사이클이 하나라도 있는 그래프
- 비순환 그래프(acyclic graph) : 사이클이 하나도 없는 그래프
- 완전 그래프(complete graph) : 모든 서로 다른 두 노드 쌍이 엣지로 연결된 그래프
- 연결 그래프(connected graph) : 임의의 두 노드 사이에 경로가 항상 존재하는 그래프
- 루프 : 한 노드에서 시작해 같은 노드로 들어오는 엣지
- C++ (Pure) (인접 행렬)
더보기
#include <bits/stdc++.h>
using namespace std;
int adj[10][10] = {};
int main(int argc, char **argv){
int v,e;
scanf("%d %d", &v, &e);
for(int i=0; i<e; i++){
int u,v;
scanf("%d %d", &u, &v);
adj[u][v] = 1;
adj[v][u] = 1; // 무방향 그래프 (방향 그래프이면 12번 라인만 사용)
}
}- C++ (w/ STL) (인접 리스트)
더보기
#include <bits/stdc++.h>
using namespace std;
int edge[10][2];
int deg[10]; // 각 정점의 outdegree
int* adj[10];
int idx[10]; // adj[i]에서 새로운 정점을 추가할 때의 위치
int main(int argc, char **argv){
int v,e;
scanf("%d %d", &v, &e);
for(int i=0; i<e; i++){
scanf("%d %d", &edge[i][0], &edge[i][1]);
deg[edge[i][0]]++;
deg[edge[i][1]]++; // 무방향 그래프 (방향 그래프인 경우 14번 라인만 사용)
}
for(int i=1; i<=v; i++)
adj[i] = new int[deg[i]];
for(int i=0; i<e; i++){
int u = edge[i][0], v = edge[i][1];
adj[u][idx[u]] = v;
idx[u]++;
}
}- C++ (w/ STL) (인접 리스트)
더보기
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[10];
int main(int argc, char **argv){
int v,e;
scanf("%d %d", &v, &e);
for(int i=0; i<e; i++){
int u,v;
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u); // 무방향 그래프 (방향 그래프이면 12번 라인만 사용)
}
}
Search
DFS
깊이 우선 탐색(depth first search, DFS)은 그래프의 깊은 부분을 우선적으로 탐색하는 방식이다.
- 시간복잡도: $O(V+E)$
- 공간복잡도: $O(V)$
- C++ (w/ STL)
더보기
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
constexpr int LM = 1005;
vector<vector<int>> A;
int visited[LM];
void DFS(int start) {
stack<int> st;
st.push(start);
visited[start] = 1;
while (!st.empty()) {
int current = st.top();
st.pop();
printf("%d ", current);
// 현재 노드에 인접한 노드를 스택에 추가
// 인접한 노드를 거꾸로 탐색하여 스택에 넣어줌으로써, 재귀 버전의 탐색 순서를 유지
for (int i = A[current].size() - 1; i >= 0; i--) {
int next = A[current][i];
if (visited[next]) continue;
visited[next] = 1;
st.push(next);
}
}
}
int main() {
A = { // 그래프 표현 (인접 리스트)
{1, 2}, // 정점 0에 인접한 정점: 1, 2
{0, 3, 4}, // 정점 1에 인접한 정점: 0, 3, 4
{0, 4}, // 정점 2에 인접한 정점: 0, 4
{1, 5}, // 정점 3에 인접한 정점: 1, 5
{1, 2}, // 정점 4에 인접한 정점: 1, 2
{3} // 정점 5에 인접한 정점: 3
};
memset(visited, 0, sizeof(visited));
DFS(0); // 시작 정점을 스택에 넣고 DFS 시작
return 0;
}- C++ (Pure)
더보기
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
constexpr int LM = 1005;
vector<vector<int>> A;
int visited[LM];
void DFS(int s) {
if(visited[s]) return; // base condition
visited[s] = 1;
printf("%d ", s);
for(int i = 0; i < A[s].size(); i++) {
int next = A[s][i];
if(!visited[next]) DFS(next);
}
}
int main() {
A = { // 그래프 표현 (인접 리스트)
{1, 2}, // 정점 0에 인접한 정점: 1, 2
{0, 3, 4}, // 정점 1에 인접한 정점: 0, 3, 4
{0, 4}, // 정점 2에 인접한 정점: 0, 4
{1, 5}, // 정점 3에 인접한 정점: 1, 5
{1, 2}, // 정점 4에 인접한 정점: 1, 2
{3} // 정점 5에 인접한 정점: 3
};
memset(visited, 0, sizeof(visited));
DFS(0); // 0 1 3 5 4 2
return 0;
}BFS
너비 우선 탐색(breadth first search, BFS)은 가까운 노드를 먼저 탐색하며, 레벨 별로 탐색하는 방식이다.
- 시간복잡도: $O(V+E)$
- 공간복잡도: $O(V)$
- C++ (w/ STL)
더보기
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
constexpr int LM = 1005;
vector<vector<int>> A;
queue<int> q;
int visited[LM];
void BFS(int s) {
q.push(s);
visited[s] = 1; // 시작 정점을 큐에 넣고 방문 처리
while (!q.empty()) {
int cur = q.front();
q.pop();
printf("%d ", cur);
for (int i = 0; i < A[cur].size(); i++) { // 현재 정점에 인접한 모든 정점을 탐색
int next = A[cur][i];
if (visited[next]) continue; // 이미 방문한 정점은 스킵
q.push(next); // 아직 방문하지 않은 정점이라면 큐에 넣고
visited[next] = 1; // 방문 처리
}
}
puts("");
}
int main() {
A = { // 그래프 표현 (인접 리스트)
{1, 2}, // 정점 0에 인접한 정점: 1, 2
{0, 3, 4}, // 정점 1에 인접한 정점: 0, 3, 4
{0, 4}, // 정점 2에 인접한 정점: 0, 4
{1, 5}, // 정점 3에 인접한 정점: 1, 5
{1, 2}, // 정점 4에 인접한 정점: 1, 2
{3} // 정점 5에 인접한 정점: 3
};
memset(visited,0, sizeof(visited));
BFS(0); // 0 1 2 3 4 5
return 0;
}- C++ (Pure)
더보기
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
constexpr int LM = 1005;
vector<vector<int>> A;
int que[LM*LM];
int visited[LM];
int fr, re;
void BFS(int s) {
fr = re = 0;
que[re++] = s;
visited[s] = 1; // 시작 정점을 큐에 넣고 방문 처리
while (fr < re) {
int cur = que[fr++];
printf("%d ", cur);
for (int i = 0; i < A[cur].size(); i++) { // 현재 정점에 인접한 모든 정점을 탐색
int next = A[cur][i];
if (visited[next]) continue; // 이미 방문한 정점은 스킵
que[re++] = next; // 아직 방문하지 않은 정점이라면 큐에 넣고
visited[next] = 1; // 방문 처리
}
}
puts("");
}
int main() {
A = { // 그래프 표현 (인접 리스트)
{1, 2}, // 정점 0에 인접한 정점: 1, 2
{0, 3, 4}, // 정점 1에 인접한 정점: 0, 3, 4
{0, 4}, // 정점 2에 인접한 정점: 0, 4
{1, 5}, // 정점 3에 인접한 정점: 1, 5
{1, 2}, // 정점 4에 인접한 정점: 1, 2
{3} // 정점 5에 인접한 정점: 3
};
memset(visited,0, sizeof(visited));
BFS(0); // 0 1 2 3 4 5
return 0;
}
Shortest path
Dijkstra
다익스트라(Dijkstra) 알고리즘은 가중치가 있는 그래프에서 두 정점 사이의 최단 경로를 찾는 알고리즘이다. 음수 가중치를 가진 간선이 없을 때 사용할 수 있다. 알고리즘은 출발점에서 각 정점까지의 최단 거리를 저장하면서, 가장 가까운 정점을 선택하고, 이 정점을 통해 다른 정점으로 가는 거리를 업데이트하는 과정을 반복한다.
- 시간복잡도: $O(E\log V)$ (우선순위큐 사용 시) (엄밀히 말하면 $O((E+V)\log V)$이지만 $E$가 $V$보다 일반적으로 크므로 $V$ 생략 가능)
- C++ (Pure)
- 시간복잡도: $O(V^2 + E)$ : $V$가 20,000개가 넘으면 PS 알고리즘에서 보통 TLE 발생
더보기
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
constexpr int LM = 20005;
constexpr int INF = 0x3f3f3f3f;
vector<pii> adj[LM];
int fix[LM];
int d[LM];
int V, E, K;
void dijkstraNaive(int u) {
fill(d, d + V + 1, INF); // 최단거리 테이블 초기화
d[u] = 0;
while (1) {
int idx = -1;
for (int i = 1; i <= V; i++) {
if (fix[i]) continue;
if (idx == -1) idx = i;
else if (d[i] < d[idx]) idx = i;
}
if (idx == -1 || d[idx] == INF) break; // 더 이상 선택할 정점이 없으면
fix[idx] = 1; // 정점 idx 고정
for(auto next : adj[idx]) {
int &w = next.X;
int &v = next.Y;
d[v] = min(d[v], d[idx] + w);
}
}
}
int main() {
V = 5; // 노드
E = 6; // 엣지
K = 1; // 시작 정점 번호
// u, v, w
vector<tuple<int, int, int>> edges = {
{5, 1, 1},
{1, 2, 2},
{1, 3, 3},
{2, 3, 4},
{2, 4, 5},
{3, 4, 6}
};
for (auto [u, v, w] : edges) {
adj[u].push_back({ w, v });
}
dijkstraNaive(K);
for (int i = 1; i <= V; i++) {
if (d[i] == INF) printf("INF\n");
else printf("%d\n", d[i]);
}
// 0
// 2
// 3
// 7
// INF
}- C++ (w/ STL)
- 시간복잡도: $O(E\log V)$ : 일반적으로 PS에서 자주 사용되는 방식
더보기
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
constexpr int LM = 20005;
constexpr int INF = 0x3f3f3f3f;
vector<pii> adj[LM];
priority_queue<pii, vector<pii>, greater<pii>> pq;
int d[LM];
int V, E, K;
void dijkstra(int u) {
fill(d, d + V + 1, INF);
d[u] = 0;
pq.push({ d[u], u });
while (!pq.empty()) {
auto cur = pq.top(); pq.pop();
int &w = cur.X;
int &v = cur.Y;
if (d[v] != w) continue;
for (auto next : adj[v]) {
int &nw = next.X;
int &nv = next.Y;
if (d[nv] <= d[v] + nw) continue;
d[nv] = d[v] + nw;
pq.push({ d[nv], nv });
}
}
}
int main() {
V = 5; // 노드
E = 6; // 엣지
K = 1; // 시작 정점 번호
// u, v, w
vector<tuple<int, int, int>> edges = {
{5, 1, 1},
{1, 2, 2},
{1, 3, 3},
{2, 3, 4},
{2, 4, 5},
{3, 4, 6}
};
for (auto [u, v, w] : edges) {
adj[u].push_back({ w, v });
}
dijkstra(K);
for (int i = 1; i <= V; i++) {
if (d[i] == INF) printf("INF\n");
else printf("%d\n", d[i]);
}
// 0
// 2
// 3
// 7
// INF
}- C++ (w/ STL) (+ 경로 복원)
- 시간복잡도: $O(E \log V)$ : 위와 동일
더보기
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
const int LM = 1005;
const int INF = 0x3f3f3f3f;
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<pii> adj[LM];
int V, E, st, en;
int d[LM];
int pre[LM];
void dijkstra(int u){
d[u] = 0;
pq.push({ d[u], u });
while (!pq.empty()) {
auto cur = pq.top(); pq.pop();
int &w = cur.X;
int &v = cur.Y;
if (d[v] != w) continue;
for (auto next : adj[v]) {
int &nw = next.X;
int &nv = next.Y;
if (d[nv] <= d[v] + nw) continue;
d[nv] = d[v] + nw;
pq.push( { d[nv], nv } );
pre[nv] = v; // 경로 복원
}
}
}
int main() {
V = 5; // 노드
E = 6; // 엣지
// u,v,w (u,v : node) (w : cost)
vector<tuple<int, int, int>> edges = {
{5, 1, 1},
{1, 2, 2},
{1, 3, 3},
{2, 3, 4},
{2, 4, 5},
{3, 4, 6}
};
st = 1; // start
en = 4; // end
fill(d, d + V + 1, INF);
for (auto [u, v, w] : edges) {
adj[u].push_back({w, v});
}
dijkstra(st);
// 도착 도시까지 최소 비용
printf("%d\n", d[en]);
// 경로 복원
vector<int> path;
int cur = en;
while (cur != st) {
path.push_back(cur);
cur = pre[cur];
}
path.push_back(cur);
reverse(path.begin(), path.end());
printf("%d\n", (int)path.size()); // 도시 개수
for (auto x : path) printf("%d ", x); // 최소 비용을 갖는 경로
// 7
// 3
// 1 2 4
}
Floyd-Warshall
플로이드-워셜(Floyd-Warshall) 알고리즘은 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 동적 프로그래밍을 기반으로 하며, 그래프의 모든 정점을 거쳐 가는 경로를 고려하여 최단 거리를 계산한다. 이는 각 정점을 거쳐 가는 모든 경로의 최단 거리를 행렬로 저장하고 업데이트하는 방식으로 작동한다.
- 시간복잡도: $O(V^3)$
- 공간복잡도: $O(V^2)$
- C++ (Pure)
더보기
#include <bits/stdc++.h>
using namespace std;
const int LM = 105;
const int INF = 0x3f3f3f3f;
int d[LM][LM];
int n, m;
// Floyd-Warshall
void floyd() {
for (int i = 1; i <= n; i++)
d[i][i] = 0;
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
int main() {
n = 5; // node
m = 14; // edge
// a,b,c (a,b : node) (c : cost)
vector<tuple<int, int, int>> edges = {
{1, 2, 2}, {1, 3, 3}, {1, 4, 1}, {1, 5, 10},
{2, 4, 2}, {3, 4, 1}, {3, 5, 1}, {4, 5, 3},
{3, 5, 10}, {3, 1, 8}, {1, 4, 2}, {5, 1, 7},
{3, 4, 2}, {5, 2, 4}
};
for (int i = 1; i <= n; i++) {
fill(d[i], d[i] + n + 1, INF);
}
for (auto [a, b, c] : edges) {
d[a][b] = min(d[a][b], c);
}
floyd();
// 최단 거리 테이블
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (d[i][j] == INF) printf("0 ");
else printf("%d ", d[i][j]);
}
puts("");
}
}- C++ (Pure) (using dp) (+경로 복원)
더보기
#include <bits/stdc++.h>
using namespace std;
const int LM = 105;
const int INF = 0x3f3f3f3f;
int d[LM][LM];
int nxt[LM][LM];
int n, m;
// Floyd-Warshall
void floyd(){
for (int i = 1; i <= n; i++)
d[i][i] = 0;
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (d[i][k] + d[k][j] < d[i][j]) {
d[i][j] = d[i][k] + d[k][j];
nxt[i][j] = nxt[i][k];
}
}
}
}
}
// 경로 복원
void restorePath() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (d[i][j] == 0 || d[i][j] == INF) {
printf("0\n");
continue;
}
vector<int> path;
int st = i;
while (st != j) {
path.push_back(st);
st = nxt[st][j];
}
path.push_back(j);
printf("%d ", (int)path.size());
for (auto x : path) printf("%d ", x);
puts("");
}
}
}
int main() {
n = 5; // node
m = 14; // edge
// a,b,c (a,b : node) (c : cost)
vector<tuple<int, int, int>> edges = {
{1, 2, 2}, {1, 3, 3}, {1, 4, 1}, {1, 5, 10},
{2, 4, 2}, {3, 4, 1}, {3, 5, 1}, {4, 5, 3},
{3, 5, 10}, {3, 1, 8}, {1, 4, 2}, {5, 1, 7},
{3, 4, 2}, {5, 2, 4}
};
for (int i = 1; i <= n; i++) {
fill(d[i], d[i] + n + 1, INF);
}
for (auto [a, b, c] : edges) {
d[a][b] = min(d[a][b], c);
nxt[a][b] = b;
}
floyd();
// 최단 거리 테이블
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (d[i][j] == INF) printf("0 ");
else printf("%d ", d[i][j]);
}
puts("");
}
restorePath();
}
Minimum spanning tree (MST)
최소 비용 신장트리(minimum spanning tree, MST)는 그래프의 모든 노드를 최소의 연결 비용으로 연결하는 부분 그래프(트리)이다. 프림(Prim) 알고리즘과 크루스칼(Kruskal) 알고리즘은 MST를 찾는 데 널리 사용되는 알고리즘이다. 이들은 각각 탐욕적 방법을 사용하여 전체 그래프에서 최소 비용의 에지들을 선택하여 MST를 구성한다.
- C++ (Kruskal algorithm) #1
- 시간복잡도: $O(E\log V)$ (using Union-find)
더보기
#include <bits/stdc++.h>
using namespace std;
using tiii = tuple<int,int,int>;
vector<int> p(10005,-1);
int find(int x){
if(p[x] < 0) return x;
return p[x] = find(p[x]);
}
bool isDiffGroup(int a, int b){
a = find(a); b = find(b);
if(a == b) return 0;
if(p[a] == p[b]) p[a]--;
if(p[a] < p[b]) p[b] = a;
else p[a] = b;
return 1;
}
int main(void) {
int v = 3, e = 3;
// a,b,c (a,b : node) (c : cost)
tiii edge[] = {
{1, 2, 1},
{2, 3, 2},
{1, 3, 3}
};
sort(edge, edge + e);
int cnt = 0;
int ans = 0;
// Kruskal algorithm (using Union-find)
for(int i = 0; i < e; i++){
int a, b, cost;
tie(cost, a, b) = edge[i];
if(!isDiffGroup(a, b)) continue;
ans += cost; // MST 가중치의 합
cnt++;
if(cnt == v-1) break;
}
printf("%d\n", ans); // 3
}- C++ (Kruskal algorithm) #2
더보기
// JUNGOL 1060 최소비용 신장트리
// https://jungol.co.kr/problem/1060
#include <bits/stdc++.h>
using namespace std;
const int LM = 105;
int N;
int p[LM];
int rk[LM];
struct Data{
int s,e,w;
bool operator<(const Data& r) const {
return w < r.w;
}
} E[LM*LM];
int ecnt;
void input(){
scanf("%d", &N);
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
int w;
scanf("%d", &w);
if(i<j) E[ecnt++] = {i,j,w};
}
}
sort(E, E+ecnt);
}
int find(int x){
if(p[x]==x) return x;
return p[x] = find(p[x]);
}
void swap(int& a, int& b){ int c=a; a=b; b=c;}
bool Union(int a, int b){
a=find(a), b=find(b);
if(a==b) return 0;
if(rk[a] < rk[b]) swap(a,b);
p[b] = a;
if(rk[a] == rk[b]) rk[a]++;
return 1;
}
int kruskal(){
int ret=0;
for(int i=0;i<=N;i++) { p[i] = i; rk[i] = 0; }
int cnt=0;
for(int i=0; i<ecnt; i++){
if(Union(E[i].s, E[i].e) == 0) continue;
ret += E[i].w;
cnt++;
if(cnt == N-1) break;
}
return ret;
}
int main(int argc, char **argv){
//freopen("data/s_in_3333.txt", "r", stdin);
input();
int ans = kruskal();
printf("%d\n", ans);
}- C++ (Prim algorithm)
- 시간복잡도: $O(E \log V)$ (using pq)
더보기
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
constexpr int LM = 10005;
vector<pii> adj[LM]; // adj[i] = { cost , vertex_id }
bool chk[LM]; // chk[i] : i번째 정점이 MST에 속해있는가?
int cnt = 0; // 현재 선택된 간선의 수
int main() {
int v = 3, e = 3;
// a,b,c (a,b : node) (c : cost)
vector<tuple<int, int, int>> edges = {
{1, 2, 1},
{2, 3, 2},
{1, 3, 3}
};
for (auto [a, b, cost] : edges) {
adj[a].push_back({ cost, b });
adj[b].push_back({ cost, a });
}
// Prim algorithm
priority_queue<tiii, vector<tiii>, greater<tiii>> pq; // pq[i] = { cost, vertex_id1, vertex_id2 }
chk[1] = 1;
for (auto nxt : adj[1]) {
pq.push({ nxt.X, 1, nxt.Y });
}
int ans = 0;
while (cnt < v - 1) {
int cost, a, b;
tie(cost, a, b) = pq.top(); pq.pop();
if (chk[b]) continue;
ans += cost; // MST의 가중치 합
chk[b] = 1;
cnt++;
for (auto nxt : adj[b]) {
if (!chk[nxt.Y])
pq.push({ nxt.X, b, nxt.Y });
}
}
printf("%d\n", ans); // 3
}
Topological sort
위상 정렬(topological sorting)은 방향 비순환 그래프(DAG, Directed Acyclic Graph)의 모든 노드를 방향성에 위배되지 않도록 순서대로 나열하는 정렬 방법이다. 이는 주로 의존성이 있는 여러 작업을 수행해야 할 때 그 순서를 결정하는 데 사용된다.
- 시간복잡도: $O(V+E)$
- 공간복잡도: $O(V)$
- C++ (Pure)
더보기
#include <bits/stdc++.h>
using namespace std;
const int LM = 32005;
vector<int> adj[LM];
int deg[LM];
int N;
int main() {
// Nodes
N = 4;
// Edges
adj[4].push_back(2);
deg[2]++;
adj[3].push_back(1);
deg[1]++;
// Topological sort
queue<int> q;
vector<int> result;
for (int i = 1; i <= N; i++)
if (deg[i] == 0) q.push(i);
while (!q.empty()) {
int cur = q.front(); q.pop();
result.push_back(cur);
for (int nxt : adj[cur]) {
deg[nxt]--;
if (deg[nxt] == 0) q.push(nxt);
}
}
for (auto x : result) printf("%d ", x); // 3 4 1 2
}
Strong connected component (SCC)
강한 연결 요소(SCC)는 방향 그래프에서 서로 도달 가능한 정점들의 최대 집합을 말한다. 즉 같은 SCC 안의 두 정점 $u, v$는 $u \rightarrow v$도 가능하고 $v \rightarrow u$도 가능하다. SCC로 그래프를 압축하면 DAG(사이클 없는 방향 그래프)가 되기 때문에, 원래 그래프에서 복잡했던 순환 구조를 정리해서 다루기 쉬워진다. 2-SAT, 도미노, 순환 의존성 분해 등에서 자주 등장한다.
Kosaraju
정방향 그래프에서 DFS 종료 순서를 쌓고, 역방향 그래프에서 그 순서대로 DFS를 돌리며 SCC를 뽑는다.
- 시간복잡도: $O(V+E)$
- 공간복잡도: $O(V+E)$
Tarjan
한 번의 DFS로 low-link 개념을 이용해 SCC를 찾아낸다. 스택을 유지하며 현재 DFS 스택에서 SCC 루트가 되는 지점을 판별한다.
- 시간복잡도: $O(V+E)$
- 공간복잡도: $O(V+E)$
Articulation point & bridge
단절점(articulation point)은 그 정점을 제거했을 때 그래프의 연결 요소 개수가 증가하는 정점이고, 단절선(bridge)은 그 간선을 제거했을 때 연결 요소 개수가 증가하는 간선이다. 단절선은 cut edge라고도 부른다. 네트워크가 특정 노드/간선 하나에 의존하는 취약 지점을 찾는 문제로 생각하면 직관적이다. PS에서는 그래프를 끊는 핵심 지점, 최소한의 제거로 분리 같은 문제에서 자주 등장한다.
주의할 점이 하나 있다. cut edge(= bridge)와 edge cut은 다른 개념이다. cut edge는 '간선 하나'를 제거했을 때 끊어지는 경우를 말하고, edge cut은 '간선들의 집합'을 제거해서 그래프를 분리하는 개념이다. 여기서 다루는 것은 cut edge(bridge)와 articulation point이다.
일반적으로 DFS 트리와 low-link(또는 low 배열) 개념으로 푼다.
- low[x] = x에서 시작해 DFS 트리 간선과 역방향 간선을 이용해 도달 가능한 정점들 중 가장 작은 방문 순서
- 단절선 판정: (x - child) 간선에서 low[child] > tin[x] 이면 그 간선은 bridge
- 단절점 판정: 루트가 아닌 정점 x에 대해 어떤 child가 low[child] >= tin[x] 를 만족하면 x는 articulation point (루트는 자식이 2개 이상이면 단절점)
- 시간복잡도: $O(V+E)$
- 공간복잡도: $O(V+E)$ (인접 리스트 + DFS 배열)
Matching & cover
매칭(matching)은 그래프에서 서로 정점을 공유하지 않는 간선들의 집합을 의미한다. 즉, 하나의 정점은 매칭에 최대 한 번만 사용될 수 있다. 매칭의 크기는 포함된 간선의 개수로 정의된다.
이론적으로 매칭은 일반 그래프에서도 정의되지만, PS에서 '매칭'이라고 하면 거의 항상 이분 그래프(bipartite graph)에서의 매칭, 즉 이분 매칭을 의미한다. 이유는 일반 그래프 매칭(Blossom 알고리즘)이 구현 난이도와 상수 측면에서 매우 무겁고 출제 빈도도 낮기 때문이다.
Bipartite matching
이분 매칭(bipartite matching) 문제는 이분 그래프에서 서로 다른 두 부분 집합의 노드를 매칭하는 최대 집합을 찾는 문제이다. 이는 예를 들어, 일자리 할당, 자원 분배 등 다양한 최적화 문제에서 중요한 역할을 한다. 홉크로프트-카프(Hopcroft-Karp) 알고리즘은 이분 매칭 문제를 효율적으로 해결하는 알고리즘 중 하나이다.
Vertex cover
정점 커버(vertex cover)는 그래프에서 모든 간선을 덮도록 선택한 정점들의 집합을 의미한다. 어떤 간선이든, 그 양 끝 정점 중 최소 하나는 선택된 집합에 포함되어야 한다. 일반 그래프에서의 최소 정점 커버(minimum vertex cover)는 NP-hard 문제다. 하지만 PS에서 다루는 대부분의 정점 커버 문제는 이분 그래프에 한정되며, 이 경우에는 다항 시간에 해결할 수 있다.
이분 그래프에서의 정점 커버는 다음과 같은 형태로 자주 등장한다.
- 모든 관계(간선)를 끊기 위해 최소 몇 개를 선택해야 하는가
- 충돌을 제거하기 위해 최소한으로 제거해야 하는 대상의 수
- 모든 조건을 만족시키기 위한 최소 선택 문제
이분 그래프라는 조건이 주어지면, 정점 커버는 매칭 문제로 자연스럽게 연결된다. 이 연결을 가능하게 해주는 핵심 이론이 바로 케닉의 정리(König’s theorem)다.
König's theorem
케닉의 정리는 이분 그래프에서 최대 매칭과 최소 정점 커버 사이의 관계를 설명하는 정리다. 정리의 내용은 다음과 같다.
"이분 그래프에서 최대 매칭의 크기 = 최소 정점 커버의 크기"
이 정리는 PS에서 매우 중요하다. 이유는 정점 커버를 직접 구하지 않아도, 최대 이분 매칭만 구하면 답의 크기가 자동으로 결정되기 때문이다. 그래서 문제에서 '최소 정점 커버', '최소 제거', '최소 선택' 같은 표현이 나오더라도, 그래프가 이분 구조라면 실제 풀이는 다음 흐름을 따른다.
- 문제를 이분 그래프로 모델링
- 최대 이분 매칭을 구함
- 케닉의 정리를 이용해 답 도출
PS에서 vertex cover와 matching은 사실상 같은 문제군으로 묶어 생각하는 게 자연스럽다.
Independent set
독립 집합(independent set)은 그래프에서 서로 인접한 정점이 하나도 없는 정점들의 집합을 의미한다. 즉, 선택된 정점들 사이에는 간선이 존재하지 않는다. 독립 집합은 정점 커버(vertex cover)와 항상 보완 관계에 있다. 어떤 그래프에서든, 정점 커버 $C$가 주어지면 전체 정점 집합 $V$에서 $C$를 제외한 $V - C$는 독립 집합이 된다. 반대로, 독립 집합의 여집합은 항상 정점 커버가 된다. 따라서 다음 관계는 그래프의 종류와 상관없이 항상 성립한다.
"최소 정점 커버의 크기 + 최대 독립 집합의 크기 = 전체 정점의 개수"
일반 그래프에서 최대 독립 집합 문제는 NP-hard이기 때문에, PS에서 직접적으로 독립 집합을 구하라고 나오는 경우는 거의 없다. 하지만 그래프가 이분 그래프인 경우에는 케닉의 정리(König’s theorem)에 의해,
"이분 그래프에서 최대 매칭의 크기 = 최소 정점 커버의 크기"
가 성립한다. 이로부터 이분 그래프에서는 최대 매칭, 최소 정점 커버, 최대 독립 집합이 서로 직접적으로 연결된다.
Hungarian algorithm
헝가리안 알고리즘은 가중치가 있는 이분 매칭 문제, 특히 배정 문제(assignment problem)를 해결하기 위한 알고리즘이다. 완전 이분 그래프에서 각 간선에 비용(cost)이 주어졌을 때, 전체 비용의 합이 최소(또는 최대)가 되도록 매칭을 찾는 것이 목표다.
이 알고리즘은 일반적인 이분 매칭과 달리,
- 모든 왼쪽 정점이 정확히 하나의 오른쪽 정점과 매칭되어야 하며
- “매칭의 개수”가 아니라 “매칭의 총 비용”을 최적화한다.
PS에서 헝가리안 알고리즘은 출제 빈도가 높지는 않지만,
- 문제 크기가 명확히 N ≤ 300~400 정도로 주어지고
- 비용 행렬이 주어지는 배정 문제 형태라면 사실상 대안이 거의 없는 정석 알고리즘이다.
네트워크 플로우(min-cost max-flow)로도 풀 수 있지만 구현이 훨씬 복잡하고 상수도 크기 때문에 헝가리안 알고리즘이 더 적합한 경우가 많다.
- 시간복잡도: $O(N^3)$
- 공간복잡도: $O(N^2)$
Network flow
Maximum flow
최대 유량(maximum flow) 문제는 네트워크 플로우 이론에서 주어진 네트워크의 두 노드 사이(일반적으로 소스와 싱크라고 함)를 통해 흐를 수 있는 최대의 유량을 찾는 문제이다. 간선에는 용량(capacity)이 존재하며 각 간선을 흐르는 유량은 용량을 초과할 수 없고, 중간 정점에서는 들어오는 유량과 나가는 유량이 같아야 한다(flow conservation).
대표적인 최대 유량 알고리즘으로는 Ford-Fulkerson, Edmonds-Karp, Dinic 알고리즘이 있으며 PS에서는 시간복잡도와 구현 안정성 때문에 Dinic 알고리즘이 사실상 표준으로 사용된다.
이분 매칭 문제는 최대 유량 문제로 변환할 수 있지만 PS에서는 대부분 전용 이분 매칭 알고리즘을 사용하며 네트워크 플로우는 보다 일반적인 유량/비용 문제에서 사용된다.
Minimum cut
최소 컷(minimum cut)은 네트워크 플로우에서 그래프의 정점 집합을 두 부분으로 나눴을 때, 그 둘을 연결하는 간선들의 용량 합이 최소가 되도록 하는 컷(cut)을 말한다. 보통 소스(source)와 싱크(sink)가 서로 다른 쪽에 속하도록 정점을 분할하며, 이때 소스 쪽 집합을 $S$, 싱크 쪽 집합을 $T$라고 한다.
$S$에서 $T$로 향하는 모든 간선들의 용량 합을 컷의 용량이라고 하고, 이 값이 최소가 되는 분할이 최소 컷이다. 직관적으로는 '소스에서 싱크로 가는 흐름을 완전히 막기 위해 제거해야 하는 최소 비용의 간선 집합'이라고 생각하면 된다.
PS에서 최소 컷은 보통
- 그래프를 최소 비용으로 분리하라
- 두 그룹 사이의 연결을 최소로 끊어라
같은 형태로 등장한다. 하지만 실제로 최소 컷을 직접 구하는 알고리즘을 따로 구현하는 경우는 거의 없고, 대부분 최대 유량을 구하는 과정에서 자연스럽게 함께 해결된다
Max-flow min-cut theorem
최대 유량–최소 컷 정리는 네트워크 플로우 이론에서 가장 중요한 정리 중 하나다. 이 정리는 다음을 보장한다.
"어떤 네트워크에서든 소스에서 싱크로 보낼 수 있는 최대 유량의 값은 소스와 싱크를 분리하는 최소 컷의 용량과 같다."
이 정리의 의미는 매우 강력하다. 최대 유량을 구하면, 그 값이 동시에 최소 컷의 값이 된다는 뜻이기 때문이다. 즉, 최소 컷을 따로 계산할 필요 없이, 최대 유량 알고리즘을 한 번만 실행하면 두 문제를 동시에 해결할 수 있다. 구현 관점에서 보면, 최대 유량 알고리즘을 종료한 뒤의 잔여 그래프(residual graph)를 이용해 최소 컷을 실제로 구할 수도 있다. 최종 잔여 그래프에서 소스에서 도달 가능한 정점들의 집합을 $S$, 도달 불가능한 나머지를 $T$로 나누면, $S$에서 $T$로 향하는 모든 간선들이 하나의 최소 컷을 이룬다.
문제에서 '최소 컷, 최소 제거, 최소 비용으로 분리' 같은 표현이 보이면 실제 풀이는 '최대 유량을 구한다'로 바로 연결된다
Min-cost max-flow
최소 비용 최대 유량(min-cost max-flow)은 '유량을 가능한 많이 흘리되(최대 유량), 그 최대 유량을 달성하는 방법들 중에서 총 비용이 최소가 되도록' 만드는 문제다. 각 간선에는 용량(capacity)과 비용(cost)이 함께 주어진다. 비용은 보통 “그 간선으로 유량 1을 보낼 때 드는 비용”으로 해석한다. 즉 목표는 두 단계로 생각하면 편하다.
- 소스에서 싱크로 보낼 수 있는 유량을 최대화한다.
- 그 최대 유량을 보내는 과정에서 발생하는 총 비용(유량 * 비용)의 합을 최소화한다.
PS에서 자주 등장하는 형태는 다음과 같다.
- 사람–일 배정에서 비용이 있을 때
- 시간/거리/패널티 같은 비용이 붙은 최적 배정
- 최대로 처리하면서 비용 최소 형태의 최적화
대표 풀이 방식은 잔여 그래프(residual graph)에서 최단 경로를 반복적으로 찾으며 augment(유량 증가)하는 방식이다. 비용이 있는 상황에서는 단순 BFS/DFS로는 안 되고, 비용 기준으로 최단 경로를 찾아야 한다. 구현에서 많이 쓰는 조합은 다음과 같다.
- SPFA(Shortest Path Faster Algorithm)로 최단 경로를 찾고 augment 반복
- 또는 잠재치(potential)를 써서 음수 간선을 제거한 뒤 Dijkstra로 최단 경로를 찾고 augment 반복
시간복잡도는 구현 방식과 그래프 형태에 따라 표현이 달라진다. 보통 'augment 횟수(흘리는 총 유량) * 최단 경로 계산 비용'으로 생각하면 된다. 예를 들어 Dijkstra를 쓰면 대략 $F$번 최단 경로를 구한다는 형태가 된다($F$는 흘린 총 유량).
- 시간복잡도: $O(F * E log V)$ Dijkstra-based
- 공간복잡도: $O(V+E)$
Disjoint set
Union-find
유니온 파인드(union find) 또는 서로소 집합(disjoint set union, DSU)는 여러 개의 원소를 효율적으로 그룹화하고 관리하는 자료구조로, "find" 연산을 통해 특정 원소가 속한 집합의 대표를 찾고, 'union' 연산을 통해 두 집합을 합칠 수 있다. 경로 압축(path compression)과 랭크 기반 합치기(union by rank) 같은 최적화 기법을 적용하면 평균적으로 매우 빠르게 동작하며, 그래프의 연결 요소 찾기, 최소 스패닝 트리(MST) 등 다양한 문제에서 활용된다.
- 시간복잡도
- 초기화 $O(n)$
- (최적화 적용 시) union, find 모두 $O(\alpha(n))$
- $\alpha(n)$ : 아커만 함수, $\alpha(10^{80})=5$ 수준이므로 사실 상 상수 시간복잡도라고 보면 된다
- C++ (Pure) #1
더보기
// 종교 jungol.co.kr/problem/1863
#include <bits/stdc++.h>
using namespace std;
constexpr int LM = 50005;
int N, M, ret;
int p[LM], rk[LM];
int find(int x) {
if (p[x] == x) return x;
return p[x] = find(p[x]); // 최적화1 : 경로 압축 적용
}
void swap(int& a, int& b) { int c=a; a=b; b=c;}
void Union( int a, int b ) {
a = find( a ), b = find( b );
if ( a == b ) return;
ret--;
// 최적화2 : 랭크 기반 합치기
if ( rk[a] < rk[b] ) swap( a, b );
p[b] = a;
if ( rk[a] == rk[b] ) rk[a]++;
}
int main() {
scanf( "%d %d", &N, &M );
ret = N;
for(int i=0; i<N; i++){
p[i] = i;
rk[i] = 0; // 랭크 초기화
}
for ( int i = 0; i < M; i++ ) {
int a, b;
scanf( "%d %d", &a, &b );
Union( a, b );
}
printf( "%d", ret );
}- C++ (Pure) #2
더보기
// 종교 jungol.co.kr/problem/1863
#include <bits/stdc++.h>
using namespace std;
constexpr int LM = 50005;
int N, M, ret;
vector<int> p(LM, -1);
int find(int x) {
if (p[x] < 0) return x;
return p[x] = find(p[x]); // 최적화1 : 경로 압축 적용
}
void swap(int& a, int& b) { int c=a; a=b; b=c;}
void Union( int a, int b ) {
a = find( a ), b = find( b );
if ( a == b ) return;
ret--;
// 최적화2 : 랭크 기반 합치기, rank, parent를 하나의 변수에서 처리하는 버전
if ( p[a] < p[b] ) swap( a, b );
if ( p[a] == p[b] ) p[a]--;
p[b] = a;
}
int main() {
scanf( "%d %d", &N, &M );
ret = N;
for ( int i = 0; i < M; i++ ) {
int a, b;
scanf( "%d %d", &a, &b );
Union( a, b );
}
printf( "%d", ret );
}
Advanced Tree
Lowest common ancestor (LCA)
최소 공통 조상(LCA)는 두 정점 $u, v$의 최소 공통 조상을 찾는 문제다. 트리에서 $u$와 $v$ 사이의 경로를 다루는 문제가 나오면 거의 필수로 등장한다. 예를 들어 두 노드 사이 거리, 경로 위의 최소(최대), $k$번째 정점같은 문제는 LCA를 기반으로 풀리는 경우가 많다.
Heavy-light decomposition (HLD)
HLD는 트리를 여러 개의 체인(chain)으로 분해해서, 트리 경로 쿼리를 세그먼트 트리/펜윅 트리 같은 1차원 자료구조로 처리하게 만드는 기법이다. 트리에서 $u \sim v$ 경로를 그대로 처리하기 어렵지만, HLD를 쓰면 $u \sim v$ 경로가 $O(\log N)$개의 구간으로 쪼개지고, 각 구간은 1차원 인덱스 배열 위의 연속 구간이 된다. 그래서 경로 합/최대/최소, 경로 업데이트 같은 문제를 빠르게 처리할 수 있다.
- 시간복잡도:
- 전처리 $O(N)$
- 쿼리/업데이트 $O(\log^2 N)$ (세그먼트 트리 사용 시) (최적화에 따라 log를 줄이는 변형도 있음)
- 공간복잡도: $O(N)$ + (세그먼트 트리 공간)
String
문자열 문제는 겉보기에는 단순해 보여도, 길이가 커지면 $O(N^2)$ 비교는 바로 시간 초과가 난다. 그래서 PS에서 문자열 파트는 패턴 매칭과 문자열 전처리를 이용해 선형 또는 준선형으로 푸는 알고리즘들이 핵심이다. KMP 같은 고전 알고리즘 외에도, Z algorithm처럼 구현이 단순하면서도 강력한 도구가 자주 쓰인다.
Z algorithm
Z 알고리즘은 문자열 S에 대해 $Z[i]$ = $S[0..]$와 $S[i..]$의 가장 긴 공통 접두사 길이를 모든 $i$에 대해 구하는 알고리즘이다. 한 번 Z 배열을 만들면, 패턴 매칭을 포함해 다양한 문제를 선형 시간에 해결할 수 있다. 대표 활용은 다음과 같다
- 패턴 $P$를 텍스트 $T$에서 찾기: $S = P + \alpha + T$ 를 만들고, $Z$ 값이 $|P|$인 위치가 있으면 매칭이 존재한다.
- 문자열의 주기성(period) 판단, 접두사/접미사 관련 문제
- 가장 긴 반복, 특정 접두사와 일치하는 구간 찾기 등
핵심 아이디어는 현재까지 알고 있는 가장 오른쪽 매칭 구간 $[L, R]$을 유지하면서, 그 구간 안의 $i$에 대해서는 이미 계산된 Z 값을 재활용하는 것이다. 이 덕분에 전체 비교 횟수가 선형으로 제한된다.
- 시간복잡도
- Z 배열 계산: $O(|N|)$ ($|N|$ = 문자열 길이)
- 공간복잡도: $O(N)$
KMP
KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 검색을 효율적으로 수행하는 알고리즘으로, 패턴 내에서 접두사와 접미사의 일치 정보를 활용하여 불필요한 비교를 줄인다. 전처리 연산을 통해 패턴의 "접두사 배열(longest prefix suffix, LPS 배열 또는 실패 함수)"을 생성하고, "탐색(search)" 연산을 수행할 때 이를 활용하여 중복된 비교 없이 빠르게 문자열 내에서 패턴을 찾는다. 일반적인 브루트포스 검색보다 빠르며, 대량의 텍스트 검색에서 효과적이다. KMP는 문자열 검색, DNA 서열 분석, 편집 거리 계산 등의 문제에서 활용된다.
- 시간복잡도: $O(|N|+|M|)$ (브루트포스 기반 문자열 매칭 : $O(|N| \times |M|)$)
- $|N|$: 전체 문자열 $N$의 길이
- $|M|$: 검색할 패턴 $M$의 길이
- C++ (Pure)
더보기
// 부분 문자열 boj.kr/16916
#include <bits/stdc++.h>
using namespace std;
string s, p;
// longest prefix suffix, LPS 배열(실패 함수) 구하기
vector<int> failure( string& s ) {
vector<int> f( s.size() );
int j = 0;
for ( int i = 1; i < s.size(); i++ ) {
while ( j > 0 && s[i] != s[j] ) j = f[j - 1];
if ( s[i] == s[j] ) f[i] = ++j;
}
return f;
}
void kmpSearch(){
vector<int> f = failure( p );
int j = 0;
for ( int i = 0; i < s.size(); i++ ) {
while ( j > 0 && s[i] != p[j] ) j = f[j - 1];
if ( s[i] == p[j] ) j++;
if ( j == p.size() ) {
printf( "1\n" );
return;
}
}
printf( "0\n" );
}
int main( int argc, char** argv ) {
cin >> s >> p;
// s : baekjoon
// p : aek
kmpSearch(); // 1
}Aho-Corasick
아호-코라식(Aho-Corasick) 알고리즘은 여러 패턴 문자열을 한 번에 효율적으로 찾을 수 있게 해주는 대표적인 다중 문자열 탐색 알고리즘이다. 이 알고리즘은 먼저 트라이(Trie)를 만들어 패턴들을 저장하고, 각 노드에 실패 링크(failure link)를 추가하는데, 이 실패 링크의 원리는 KMP 알고리즘의 실패 함수와 유사하다. 이를 통해 패턴이 불일치할 때 빠르게 다음 후보로 이동할 수 있다. 탐색 과정에서는 텍스트의 각 문자를 한 번씩만 읽으면서도, 동시에 모든 패턴의 일치 여부를 판별할 수 있다.
- 시간 복잡도
- 패턴 입력 및 실패 링크 구성 $O(\sum |P_i|)$
- 텍스트 탐색 $O(|T|+k)$
- $\sum |P_i|$ : 모든 패턴의 총 길이, $|T|$: 텍스트 길이, $k$: 패턴의 총 등장 횟수
- 아호-코라식 알고리즘은 KMP의 실패 함수 아이디어를 트라이 구조로 확장해 여러 패턴을 동시에 처리할 수 있게 했다는 점에서 의의가 있다.
- 악성코드 탐지, 금칙어 필터, 유전체 분석 등 대용량 텍스트 내 다중 패턴 검색에 널리 활용된다.
- C++ (Pure)
더보기
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int ALPHABET = 26;
int c2i(char c) { return c - 'a'; }
// Aho-Corasick
struct TrieNode {
TrieNode* child[ALPHABET];
TrieNode* fail;
vector<int> output;
TrieNode() : fail(0) {
memset(child, 0, sizeof(child));
}
~TrieNode() {
for (int i = 0; i < ALPHABET; ++i)
if (child[i] && child[i] != this)
delete child[i];
}
void insert(const string& word, int idx) {
TrieNode* cur = this;
for (char c : word) {
int nxt = c2i(c);
if (!cur->child[nxt]) cur->child[nxt] = new TrieNode();
cur = cur->child[nxt];
}
cur->output.push_back(idx);
}
};
void computeFailFunc(TrieNode* root) {
queue<TrieNode*> q;
root->fail = root;
for (int i = 0; i < ALPHABET; ++i) {
if (root->child[i]) {
root->child[i]->fail = root;
q.push(root->child[i]);
} else {
root->child[i] = root; // 없는 간선은 루트로 연결
}
}
while (!q.empty()) {
TrieNode* cur = q.front(); q.pop();
for (int i = 0; i < ALPHABET; ++i) {
TrieNode* nxt = cur->child[i];
if (!nxt || nxt == root) continue;
TrieNode* f = cur->fail;
while (!f->child[i] && f != root)
f = f->fail;
nxt->fail = f->child[i] ? f->child[i] : root;
nxt->output.insert(nxt->output.end(),
nxt->fail->output.begin(),
nxt->fail->output.end());
q.push(nxt);
}
}
}
// (마지막 위치, 패턴 번호) 쌍을 리턴
vector<pii> search(const string& text, TrieNode* root) {
vector<pii> res;
TrieNode* cur = root;
for (int i = 0; i < (int)text.size(); ++i) {
int idx = c2i(text[i]);
while (!cur->child[idx] && cur != root)
cur = cur->fail;
cur = cur->child[idx];
if (!cur) cur = root;
for (int pat : cur->output)
res.emplace_back(i, pat);
}
return res;
}
int main() {
vector<string> patterns = {"he", "she", "his", "hers"};
string text = "ushers";
TrieNode* root = new TrieNode();
for (int i = 0; i < patterns.size(); ++i)
root->insert(patterns[i], i);
computeFailFunc(root);
auto result = search(text, root);
cout << "Text: " << text << '\n';
for (auto [pos, pat] : result) {
int start = pos - (int)patterns[pat].size() + 1;
cout << "Pattern [" << patterns[pat] << "] found at: " << start << '\n';
}
// Pattern [she] at: 1
// Pattern [he] at: 2
// Pattern [hers] at: 2
}Suffix array (Manber-Myers)
맨버-마이어스(Manber-Myers) 알고리즘은 문자열의 접미사 배열(Suffix array)을 효율적으로 구성하는 대표적인 방법이다. 이 알고리즘은 처음에 각 접미사를 한 글자씩 비교하여 정렬한 뒤, 비교 길이를 두 배씩 늘려가며 정렬을 반복한다. 이전 단계의 순위를 활용해 빠르게 다음 정렬 기준을 계산할 수 있기 때문에 매우 효율적인 알고리즘이다. 구현이 비교적 간단한 편이며, 문자열 검색, 중복 문자열 처리, 최장 공통 접두사(LCP) 계산 등 다양한 문자열 알고리즘의 기반이 되는 자료구조로 널리 사용된다.
- 시간복잡도: $O(|N|\log |N|)$
- $|N|$: 문자열 $N$의 길이
- C++ (Pure)
더보기
#include <bits/stdc++.h>
using namespace std;
// Manber-Myers
vector<int> buildSuffixArray(const string& s) {
int n = s.size();
vector<int> perm(n), group(n), ngroup(n);
// 초기 정렬: 문자 기준
for (int i = 0; i < n; ++i) {
perm[i] = i;
group[i] = s[i];
}
for (int t = 1;; t *= 2) {
auto cmp = [&](int i, int j) -> bool {
if (group[i] != group[j]) return group[i] < group[j];
int ri = (i+t < n) ? group[i+t] : -1;
int rj = (j+t < n) ? group[j+t] : -1;
return ri < rj;
};
sort(perm.begin(), perm.end(), cmp);
ngroup[perm[0]] = 0;
for (int i = 1; i < n; ++i)
ngroup[perm[i]] = ngroup[perm[i-1]] + cmp(perm[i-1], perm[i]);
group = ngroup;
if (group[perm[n-1]] == n-1) break; // 모든 순위가 유일하면 종료
}
return perm;
}
int main() {
string s = "banana";
vector<int> perm = buildSuffixArray(s);
cout << "Suffix array:\n";
for (int i : perm)
cout << i << ' ' << s.substr(i) << '\n'; // 5 3 1 0 4 2
}
Math & Number theory
Prime number
소수(prime number)는 1과 자기 자신으로만 나누어지는 수를 말한다. 즉, 임의의 수를 약분했을 때 약수가 2개이면 해당 수를 소수라고 한다.
- 현재 숫자 n이 1 이외에 다른 수로 나눠지는지 확인함으로써 소수 판별
- 시간복잡도: $O(\sqrt{n})$
더보기
bool isPrime(int n) {
if(n==1) return 0;
for(int i=2; i*i<=n; i++){ // search until sqrt(n)
if(n % i == 0) return 0;
}
return 1;
}- 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하여 소수가 아닌 값들을 마킹함으로써 소수 판별
- 시간복잡도: $O(n \log (\log n))$
더보기
#include<bits/stdc++.h>
constexpr int N = 1005;
bool is_prime[N];
// Pure
void sieve() {
memset(is_prime, 1, sizeof(is_prime));
is_prime[1] = false;
for(int i=2; i*i<=N; i++){
if(is_prime[i] == false) continue;
for(int j=i*i; j<=N; j+=i) {
is_prime[j] = false;
}
}
}
int main() {
sieve();
for(int i=2; i<=N; i++){
if(is_prime[i]) { // check if 'i' is prime number
printf("%d ", i);
}
}puts("");
}더보기
#include<bits/stdc++.h>
using namespace std;
int N = 1005;
vector<int> primes;
// STL
void sieve() {
vector<bool> state(N+1, true);
state[1] = false;
for(int i=2; i*i<=N; i++){
if(!state[i]) continue;
for(int j=i*i; j<=N; j+=i)
state[j] = false;
}
for(int i=2; i<=N; i++) {
if(state[i]) primes.push_back(i);
}
}
int main() {
sieve();
for(int i=2; i<=N; i++){
// check if 'i' is prime number
if(find(primes.begin(), primes.end(), i) != primes.end()) {
printf("%d ", i);
}
} puts("");
}
Prime factorization
소인수분해(prime factorization)은 정수를 소수의 곱으로 나타내는 것을 의미한다. 모든 자연수는 소인수분해하는 방법이 딱 한가지만 존재하므로 유일한 소인수분해 값을 얻을 수 있다.
- C++ (Pure)
- 시간복잡도: $O(\sqrt{n})$
더보기
#include <bits/stdc++.h>
using namespace std;
// O(sqrt(n))
void primeFactorization(int n) {
for(int i=2; i*i<=n; i++){
while(n%i == 0) {
printf("%d ", i);
n /= i;
}
}
if(n != 1) printf("%d ", n);
puts("");
}
int main(int argc, char **argv){
int N;
scanf("%d",&N); // 1100
primeFactorization(N); // 2 2 5 5 11
}- 에라토스테네스의 체를 활용한 빠른 소인수분해
- 시간복잡도: $O(\log n)$
더보기
#include <bits/stdc++.h>
using namespace std;
const int LM = 1000005;
int minFactor[LM]; // minFactor[i] : i의 가장 작은 소인수(i가 소수인 경우는 자기 자신)
// 시간복잡도: O(nloglogn)
void eratosthenes2(int n) {
// 초기화
minFactor[0] = minFactor[1] = -1;
for ( int i = 2; i <= n; i++ ) {
minFactor[i] = i;
}
// 에라토스테네스의 체
for ( int i = 2; i*i <= n; i++ )
if ( minFactor[i] == i )
for ( int j = i * i; j <= n; j += i )
if ( minFactor[j] == j ) // 아직 약수를 본 적 없는 숫자인 경우 i를 써둔다
minFactor[j] = i;
}
// 시간복잡도: O(logn)
vector<int> factor( int n ) {
vector<int> ret;
// n이 1이 될 때까지 가장 작은 소인수로 나누기를 반복한다
while ( n > 1 ) {
ret.push_back( minFactor[n] );
n /= minFactor[n];
}
return ret;
}
int main( int argc, char **argv ) {
int N;
scanf("%d", &N); // 1100
eratosthenes2(N);
vector<int> ret = factor(N);
for(auto& e : ret) {
printf("%d ", e); // 2 2 5 5 11
}
puts("");
}
Divisor
약수(divisor)는 어떤 수를 나누어떨어지게 하는 수를 말한다. 예를 들어 $24$의 약수는 $[1, 2, 3, 4, 6, 8, 12, 24]$이다.
- C++ (w/ STL)
- 시간복잡도 $O(\sqrt{n})$
더보기
#include <bits/stdc++.h>
using namespace std;
// O(sqrt(n))
vector<int> divisor(int n){
vector<int> div;
for(int i=1; i*i <= n; i++){
if(n % i == 0) div.push_back(i);
}
for(int j=(int)div.size()-1; j>=0; j--) {
if(div[j]*div[j] == n) continue;
div.push_back(n/div[j]);
}
return div;
}
int main(int argc, char **argv){
int N;
scanf("%d",&N); // 24
vector<int> divs = divisor(N);
for(auto x : divs) printf("%d ", x); // 1 2 3 4 6 8 12 24
puts("");
}
GCD
최대공약수(greatest common divisor)는 두 자연수의 공통된 약수 중 가장 큰 약수를 말한다. 유클리드 호제법을 사용하면 GCD를 빠르게 구할 수 있다.
- 유클리드 호제법(Euclidean algorithm): 두 수 $a$, $b$에 대하여 $a$를 $b$로 나눈 나머지를 $r$이라고 하면 GCD($a,b$)=GCD($b,r$)이 성립한다
- C++ (Pure)
- 시간복잡도: $O(\log(\min(a,b))$
더보기
#include <bits/stdc++.h>
using namespace std;
// recursion
int gcd(int a, int b){
if(a==0) return b;
return gcd(b%a, a);
}
// while
int gcd2(int a, int b) {
while(b){ int t = a % b; a = b; b = t; }
return a;
}
int main(int argc, char **argv){
int A,B;
scanf("%d %d",&A, &B); // 32, 6
printf("%d\n", gcd(A, B)); // GCD(32,6) = 2
//printf("%d\n", gcd2(A, B)); // GCD(32,6) = 2
}
LCM
최소공배수(least common multiple)는 두 자연수의 공통된 배수 중 가장 작은 배수를 말한다.
- LCM($a,b$) = $(a\times b) / $ GCD($a,b$)가 성립한다 (원래 식은 $a\times b$ = GCD($a,b$) $\cdot$ LCM($a,b$))
- C++ (Pure)
- 시간복잡도: $O(\log(\min(a,b))$
더보기
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
if(a==0) return b;
return gcd(b%a, a);
}
int gcd2(int a, int b) {
while(b){ int t = a % b; a = b; b = t; }
return a;
}
int lcm(int a, int b){
return a / gcd(a,b)*b;
// return a / gcd2(a,b)*b;
}
int main(int argc, char **argv){
int A,B;
scanf("%d %d",&A, &B); // 32, 6
printf("%d\n", lcm(A, B)); // LCM(32,6) = 96
}
Permutation
순열(permutation)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다.
- 시간복잡도: $O(n! \times n)$
- C++ (w/ STL)
더보기
#include <algorithm>
#include <cstdio>
using namespace std;
constexpr int LM=10005;
int num[LM] = {0};
int main(int argc, char **argv){
num[0]=1;
num[1]=2;
num[2]=3;
do{
for(int i=0;i<3;i++)
printf("%d ", num[i]);
printf("\n");
}while(next_permutation(num, num+3));
return 0;
}- C++ (Pure)
더보기
#include <algorithm>
#include <cstdio>
using namespace std;
int num[3]={0};
int N=3;
int main(int argc, char **argv){
num[0]=1, num[1]=2, num[2]=3;
while(1) {
for(int i=0;i<N;i++)
printf("%d ", num[i]);
printf("\n");
bool last_perm=true; // 마지막 순열인지 체크
for(int i=N-1;i>0;i--){ // 입력된 순열의 마지막 원소부터 검사
if(num[i-1] < num[i]){ // 왼쪽 원소(기준) < 오른쪽 원소
int idx=i; // 교환할 원소의 인덱스
for(int j=N-1; j>=i; j--)
if(num[i-1] < num[j] && num[j] < num[idx]) // 기준 원소보다 크면서 제일 작은 원소
idx=j;
int tmp = num[idx]; // 교환
num[idx] = num[i-1];
num[i-1] = tmp;
sort(num+i, num+N); // 기준 원소 우측 오름차순 정렬
last_perm=false;
break;
}
}
if(last_perm) break;
}
}- 순열 $_nP_r$ 경우의 수를 구하는 예제 C++
더보기
#include <bits/stdc++.h>
// nPr = n! / (n-r)!
// 시간복잡도 O(r)
long long permutation(int n, int r) {
if (r > n) return 0;
unsigned long long res = 1;
for (int i = 0; i < r; ++i) {
res *= (n - i);
}
return res;
}
int main() {
int n = 10, r = 5;
printf("%lld\n", permutation(n,r)); // 30240
}
Combination
조합(combination)은 집합에서 일부 원소를 취해 부분 집합을 만드는 연산이다.
- 시간복잡도: $O( \ _nC_k \times n \ ) = O( (n! / (k!(n-k)!) ) \times n )$
- C++ (w/ STL)
더보기
#include <bits/stdc++.h>
using namespace std;
int num[5] = {1,2,3,4,5};
int main(int argc, char **argv) {
int n = 5;
int k = 3;
// Initialize mask with k 1's followed by n-k 0's
int mask[5];
memset(mask, 0, sizeof(mask));
for(int i=0; i<k; i++){
mask[i] = 1;
}
do {
for (int i = 0; i < n; ++i) {
if (mask[i])
printf("%d ", num[i]);
}
printf("\n");
} while (prev_permutation(mask, mask + n));
// 1 2 3
// 1 2 4
// 1 2 5
// 1 3 4
// 1 3 5
// 1 4 5
// 2 3 4
// 2 3 5
// 2 4 5
// 3 4 5
}- C++ (Pure) #1
더보기
#include <cstdio>
using namespace std;
int arr[5] = {1, 2, 3, 4, 5};
int n = 5, k = 3;
int main(int argc, char **argv) {
int indices[3] = {0,1,2}; // Initialize indices for the first combination
do {
for (int i = 0; i < k; ++i)
printf("%d ", arr[indices[i]]);
printf("\n");
int i = k - 1;
while (i >= 0 && indices[i] == n - k + i)
--i;
if (i < 0) break; // All combinations generated
++indices[i];
for (int j = i + 1; j < k; ++j)
indices[j] = indices[j - 1] + 1;
} while (1);
}- C++ (Pure) #2
더보기
#include <cstdio>
using namespace std;
int arr[5] = {1, 2, 3, 4, 5};
int sel[5];
int n = 5, k = 3;
void comb(int idx, int start) {
if(idx == k) {
for(int i = 0; i < k; i++) {
printf("%d ", sel[i]);
}
puts("");
return;
}
for(int i = start; i < n; i++) {
sel[idx] = arr[i];
comb(idx + 1, i + 1);
}
}
int main(){
comb(0, 0);
return 0;
}- 조합 $_nC_r$ 경우의 수를 구하는 예제 C++
더보기
#include <bits/stdc++.h>
using ll = long long;
const int LM=1005;
const int MOD=10007;
ll comb[LM][LM];
// O(nr)
void computeCombination() {
// compute Comb 1 ~ LM in advance
for(int i=1; i<LM; i++){
comb[i][0] = comb[i][i] = 1;
for(int j=1; j<i; j++){
comb[i][j] = comb[i-1][j] + comb[i-1][j-1]; // DP, nCr = n-1Cr-1 + n-1Cr
}
}
}
int main(int argc, char **argv){
int n=10,r=5;
computeCombination();
printf("%lld\n", comb[n][r]); // 252
}
Transform
Transform은 주로 다항식/컨볼루션(convolution)처럼, 단순 $O(N^2)$로 하면 느린 계산을 더 빠르게 처리하는 알고리즘이다. 특히 FFT, NTT는 PS에서 고급 영역이지만, 한 번 필요해지면 대체가 잘 안 되는 무기다.
FFT
고속 푸리에 변환(Fast Fourier transform)는 다항식 곱셈(컨볼루션)을 빠르게 하기 위한 알고리즘이다. 길이 N의 두 수열 A, B에 대해 컨볼루션 $C[k] = \sum A[i]B[k-i]$ 를 구하면, 직접 계산은 $O(N^2)$지만 FFT를 쓰면 $O(N \log N)$으로 줄일 수 있다. 실수/복소수 기반으로 동작하며, 반올림 오차 관리가 중요하다. PS에서는 큰 정수 곱셈, 문자열 매칭(특정 패턴의 점수 계산), 거리/상관관계 계산 등에서 나온다.
- 시간복잡도: $O(N \log N)$
- 공간복잡도: $O(N)$
NTT
NTT(Number theoretic transform)는 FFT의 모듈러 정수 버전이다. 복소수가 아니라 mod prime에서 원시근(primitive root)을 이용해 변환하므로, 오차 없이 정수 컨볼루션을 계산할 수 있다. 단 사용 가능한 모듈러가 제한되고(대표적으로 998244353 같은 형태), 길이 N이 2의 거듭제곱이어야 하며, 구현 난이도가 FFT보다 조금 더 높다. 정확한 계수가 중요한 다항식 문제에서 NTT가 더 안정적이다.
- 시간복잡도: $O(N \log N)$
- 공간복잡도: $O(N)$
Sort
Bubble sort
버블 정렬(bubble sort)는 인접한 두 원소를 비교하여 정렬하는 방식이다. 시간 복잡도가 높아 실제 PS에서는 잘 사용되지 않는다.
- 시간복잡도
- 평균/최악 $O(n^2)$, 최적(거의 정렬된 경우) $O(n)$
- 공간복잡도: $O(1)$
- C++ (Pure)
더보기
#include <cstdio>
constexpr int LM = 10;
int A[LM] = { 5,2,7,1,3,8,4,6,10,9 };
void BubbleSort(int *arr, int s, int e) {
for(int i = s; i < e; i++) {
for(int j = s; j < e - (i - s); j++) {
if(arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
for(int i=0; i<LM; i++) printf("%d ", A[i]); // 5 2 7 1 3 8 4 6 10 9
puts("");
BubbleSort(A, 0, LM - 1);
for(int i=0; i<LM; i++) printf("%d ", A[i]); // 1 2 3 4 5 6 7 8 9 10
puts("");
return 0;
}
Insertion sort
삽입 정렬(insertion sort)는 각 원소를 이미 정렬된 배열의 적절한 위치에 삽입하는 방식으로 구현된다. 작은 데이터 집합에 효율적이다.
- 시간복잡도
- 평균/최악 $O(n^2)$, 최적(거의 정렬된 경우) $O(n)$
- 공간복잡도: $O(1)$
- C++ (Pure)
더보기
#include <cstdio>
constexpr int LM = 10;
int A[LM] = { 5,2,7,1,3,8,4,6,10,9 };
void InsertionSort(int *arr, int s, int e) {
for(int i = s + 1; i <= e; i++) {
int key = arr[i];
int j = i - 1;
while(j >= s && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
for(int i=0; i<LM; i++) printf("%d ", A[i]); // 5 2 7 1 3 8 4 6 10 9
puts("");
InsertionSort(A, 0, LM - 1);
for(int i=0; i<LM; i++) printf("%d ", A[i]); // 1 2 3 4 5 6 7 8 9 10
puts("");
return 0;
}
Heap sort
힙(heap) 자료 구조를 사용하여 정렬하는 방식으로 최대 힙(max heap)을 구성한 후 힙의 루트부터 모든 원소를 꺼내서 재구성하면 오름차순으로 정렬된다.
- 시간복잡도
- 최악 $O(n \log n)$, 추가 메모리 사용이 적은 편 (힙 구성 $O(n)$, $n$번에 걸쳐서 힙 재정렬 $O(\log n)$ 씩)
- 공간복잡도: $O(1)$ (배열 내에서 힙을 구성하므로 추가 공간이 거의 필요 없음)
- C++ (Pure)
더보기
#include <cstdio>
constexpr int NUM = 10;
constexpr int LM = 105;
int A[] = { 5,2,7,1,3,8,4,6,10,9 };
int heap[LM];
int hn = 0;
void swap(int &a, int &b) { int t = a; a = b; b = t; }
void push(int nd) {
heap[++hn] = nd;
for (int c = hn; c > 1; c /= 2) {
if (heap[c] > heap[c / 2]) {
swap(heap[c], heap[c / 2]);
}
else {
break;
}
}
}
void pop() {
swap(heap[1], heap[hn--]);
for (int c = 2; c <= hn; c *= 2) {
if (c < hn && heap[c + 1] > heap[c]) {
c++;
}
if (heap[c] > heap[c / 2]) {
swap(heap[c], heap[c / 2]);
}
else {
break;
}
}
}
int main() {
for(int i = 0; i < NUM; i++) printf("%d ", A[i]); // 5 2 7 1 3 8 4 6 10 9
printf("\n");
for(int i = 0; i < NUM; i++) { push(A[i]); }
while (hn > 1) { pop(); }
for(int i = 1; i <= NUM; i++) printf("%d ", heap[i]); // 1 2 3 4 5 6 7 8 9 10
printf("\n");
}
Quick sort
퀵 정렬(quick sort)은 분할 정복 기법을 사용하여 빠른 평균 시간 복잡도를 가지나, 최악의 경우 시간 복잡도가 높아질 수 있다.
- 시간복잡도
- 평균 $O(n \log n)$, 최악 $O(n^2)$
- 공간복잡도
- 평균 $O(\log n)$ (재귀 호출 스택), 최악 $O(n)$ (심하게 편향된 분할의 경우)
- C++ (w/ STL)
더보기
#include <cstdio>
#include <algorithm>
using namespace std;
constexpr int LM = 10;
int A[LM] = { 5,2,7,1,3,8,4,6,10,9 };
int main() {
for(int i=0; i<LM; i++) printf("%d ", A[i]); // 5 2 7 1 3 8 4 6 10 9
puts("");
sort(A, A+LM);
for(int i=0; i<LM; i++) printf("%d ", A[i]); // 1 2 3 4 5 6 7 8 9 10
puts("");
return 0;
}
- C++ (Pure)
더보기
// 실제 PS에서 STL 없이 정렬을 구현해야 한다면 퀵소트보다는 머지소트를 구현하는 것이 좋다
// 손구현은 피봇이나 여러 최적화 기법이 들어가있지 않기 때문에 최악의 경우 O(N^2)이 나올 수 있다
// 손구현은 참고용으로만 보는 것이 좋다
#include <bits/stdc++.h>
using namespace std;
const int LM = 100005;
int N = 10;
int A[LM] = {5,2,7,1,3,8,4,6,10,9};
void quickSort(int st, int en) {
if(en <= st+1) return; // base case : 수열의 길이가 1 이하이면 함수 종료
int pivot = A[st]; // 제일 앞의 것을 pivot으로 잡는다
int l = st+1;
int r = en-1;
while(1){
while(l <= r && A[l] <= pivot) l++;
while(l <= r && A[r] >= pivot) r--;
if(l > r) break;
swap(A[l], A[r]);
}
swap(A[st], A[r]);
quickSort(st, r);
quickSort(r+1, en);
}
int main() {
quickSort(0, N);
for(int i = 0; i < N; i++)
printf("%d ", A[i]); // 1 2 3 4 5 6 7 8 9
puts("");
}
Merge sort
병합 정렬(merge sort)는 분할 정복 방식을 통해 구현되며, 안정적인 정렬 방식으로 다양한 상황에서 효율적이다.
- 시간복잡도
- 평균/최악 동일하게 $O(n \log n)$
- 공간복잡도: $O(n)$ (병합 과정에서 보조 배열 사용)
- C++ (w/ STL)
더보기
#include <cstdio>
#include <algorithm>
using namespace std;
constexpr int LM = 10;
int A[LM] = { 5,2,7,1,3,8,4,6,10,9 };
int main() {
for(int i=0; i<LM; i++) printf("%d ", A[i]); // 5 2 7 1 3 8 4 6 10 9
puts("");
stable_sort(A, A+LM);
for(int i=0; i<LM; i++) printf("%d ", A[i]); // 1 2 3 4 5 6 7 8 9 10
puts("");
return 0;
}- C++ (Pure)
더보기
#include <cstdio>
constexpr int LM = 10;
int A[LM] = { 5,2,7,1,3,8,4,6,10,9 };
int trr[LM];
void mergeSort(int *arr, int s, int e) {
if(s>=e) return;
int m=(s+e)/2, i=s, j=m+1, k=s;
mergeSort(arr,s,m), mergeSort(arr,m+1,e);
while(i<=m && j<=e) {
if(arr[j] < arr[i]) trr[k++] = arr[j++];
else trr[k++] = arr[i++];
}
while(i<=m) trr[k++] = arr[i++];
while(j<=e) trr[k++] = arr[j++];
for(i=s; i<=e; i++) arr[i] = trr[i];
}
int main() {
for(int i=0; i<LM; i++) printf("%d ", A[i]); // 5 2 7 1 3 8 4 6 10 9
puts("");
mergeSort(A, 0, LM-1);
for(int i=0; i<LM; i++) printf("%d ", A[i]); // 1 2 3 4 5 6 7 8 9 10
puts("");
return 0;
}
Counting sort
계수 정렬(counting sort)는 각 항목의 발생 횟수를 계산하여 정렬하는 방식으로, 작은 정수를 정렬할 때 유용하다. 비교 정렬 알고리즘의 하한은 $O(n \log n)$으로 알려져 있으나 입력된 자료의 원소가 제한적인 성질(원소의 최대값 k가 $-O(n) \sim O(n)$ 범위 내 존재해야 함)을 만족하는 경우 계수 정렬은 $O(n)$ 정렬이 가능하다. 계수 정렬은 개수를 셀 배열과 정렬된 결과가 저장될 배열이 추가로 필요한 단점이 존재한다.
- 시간복잡도: ($n$이 작은 경우) $O(n)$
- C++ (Pure)
더보기
#include <cstdio>
constexpr int N = 10;
int A[N] = { 1,4,3,2,2,4,3,5,3,1 };
int sortedA[N];
int cnt[N];
int K = 6; // 정렬할 값의 상한
void CountingSort(int A[], int n){
int i;
for(i=0; i<K; i++) cnt[i]=0; // 카운팅 배열 초기화
for(i=0; i<n; i++) cnt[A[i]]++; // 숫자들 카운팅
for(i=1; i<K; i++) cnt[i] += cnt[i-1]; // 누적합 구하기
for(i=n-1; i>=0; i--)
sortedA[--cnt[A[i]]] = A[i];
}
int main() {
for(int i=0; i<N; i++) printf("%d ", A[i]); // 1 4 3 2 2 4 3 5 3 1
puts("");
CountingSort(A, N);
for(int i=0; i<N; i++) printf("%d ", sortedA[i]); // 1 1 2 2 3 3 3 4 4 5
puts("");
return 0;
}
Radix sort
기수 정렬(radix sort)는 자릿수별로 데이터를 분류하여 정렬하는 방식으로, 숫자나 문자열 정렬에 효과적이다. 기수 정렬 역시 계수 정렬과 유사하게 입력된 자료의 원소가 제한적인 성질을 만족하는 경우 더 빠른 정렬이 가능하다. 기수 정렬은 원소의 자리수가 $d$ 자리 이하인 경우 $O(d n)$의 시간복잡도를 가진다. 또한 음수를 포함한 정수를 정렬할 수 있다.
낮은 자리부터 정렬하고 정렬된 순서를 유지하면서 보다 높은 자리를 정렬하는 과정에서 계수 정렬(counting sort)가 사용된다. 자리수 별로 정렬할 때 몫과 나머지 연산을 사용하는데 이 때 10진수 기법을 사용하면 효율성이 떨어지므로 2의 제곱수 진법을 사용한다. 일반적으로 $256(=2^8)$ 진법을 사용하며 자리수 $d=4$가 된다.
- 시간복잡도 : ($d$ 자리수 이하인 경우) $O(dn)$
- C++ (Pure)
더보기
#include <cstdio>
constexpr int N = 10;
constexpr int EXP = 8;
constexpr int MOD = (1<<EXP); // 256진법
constexpr int MASK = MOD-1;
int A[N] = { 1,4,3,2,2,4,3,5,3,1 };
int B[N];
int cnt[MOD];
void RadixSort() {
int i, j;
int *ap=A, *bp=B, *tp;
for(i=0; i<32; i+=EXP) { // 32비트에 대하여 8비트씩 연산
for(j=0; j<MOD; j++) cnt[j]=0;
for(j=0; j<N; j++) cnt[(ap[j]>>i)&MASK]++; // ap[j]를 2^i로 나눈 몫을 256으로 나눈
for(j=1; j<MOD; j++) cnt[j] += cnt[j-1]; // 나머지이므로 (0~255) 값이 나옴
for(j=N-1; j>=0; j--)
bp[--cnt[(ap[j]>>i)&MASK]] = ap[j];
tp=ap, ap=bp, bp=tp; // 배열 swap
}
}
int main() {
for(int i=0; i<N; i++) printf("%d ", A[i]); // 1 4 3 2 2 4 3 5 3 1
puts("");
RadixSort();
for(int i=0; i<N; i++) printf("%d ", A[i]); // 1 1 2 2 3 3 3 4 4 5
puts("");
return 0;
}
Search
Binary search
이진 탐색(binary search)는 정렬된 리스트에서 중간값을 기준으로 탐색 범위를 반으로 줄여가며 원하는 값을 찾는 방법이다. 이진 탐색을 수행하기 전 데이터는 오름차순으로 정렬되어 있어야 한다.
- 시간복잡도: $O(\log n)$
- C++ (w/ STL)
더보기
#include <cstdio>
#include <algorithm>
constexpr int LM = 1005;
int A[LM];
int N;
int main() {
N = 10;
A[0] = 5; A[1] = 2; A[2] = 7; A[3] = 1; A[4] = 3;
A[5] = 9; A[6] = 4; A[7] = 6; A[8] = 10; A[9] = 9; // 5 2 7 1 3 9 4 6 10 9
std::sort(A, A + N); // 1 2 3 4 5 6 7 8 9 10
int ret = std::binary_search(A, A+N, 7);
if(ret == 1) printf("found\n");
else printf("not found\n");
}- C++ (Pure)
더보기
#include <cstdio>
#include <algorithm>
constexpr int LM = 1005;
int A[LM];
int N;
int binarySearch(int target) {
int l = 0;
int r = N-1;
while (l <= r) {
int m = (l+r) / 2;
if (A[m] == target) return 1; // 찾은 경우
if (A[m] < target) l = m + 1;
else r = m - 1;
}
return 0; // 찾지 못한 경우
}
int main() {
N = 10;
A[0] = 5; A[1] = 2; A[2] = 7; A[3] = 1; A[4] = 3;
A[5] = 9; A[6] = 4; A[7] = 6; A[8] = 10; A[9] = 9; // 5 2 7 1 3 9 4 6 10 9
std::sort(A, A + N); // 1 2 3 4 5 6 7 8 9 10
int ret = binarySearch(7);
if(ret == 1) printf("found\n");
else printf("not found\n");
}
Parametric search
매개변수 탐색(parametric search)는 조건을 만족하는 최소/최대값을 구하는 최적화 문제를 결정 문제로 변환하여 이분 탐색을 수행하는 방법을 말한다.
- BOJ 1654 랜선 자르기
- (최적화 문제) N개를 만들 수 있는 랜선의 최대 길이 X는? (Maximize X, subject to N)
- (결정 문제) 랜선의 길이가 X일 때 랜선이 N개 이상인가? (Yes or No)
더보기
// 랜선 자르기 boj.kr/1654
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int LM = 10005;
int N,K;
int A[LM];
// Parametric search
bool solve(ll x){
ll cur = 0;
for(int i=0;i<K;i++)
cur += A[i]/x;
return cur >= N;
}
int main(int argc, char **argv){
scanf("%d %d",&K,&N);
for(int i=0;i<K;i++)
scanf("%d", &A[i]);
ll st = 1;
ll en = 0x7fffffff; // 2^31 - 1
while(st < en) {
ll m = (st+en+1)/2;
if(solve(m)) st = m;
else en = m-1;
}
printf("%lld\n", st);
}
Range query
Segment tree
구간 트리(segment tree)는 배열 같은 선형 자료구조에 대해 구간 합이나 구간 최댓값·최솟값 등의 쿼리를 빠르게 처리하기 위해 트리 형태로 분할·구성하는 자료구조이다. 배열을 여러 구간으로 나누어 각 구간의 대표 정보를 저장하며, 쿼리가 들어오면 관련된 구간들만 빠르게 확인하여 결과를 합산하거나 갱신한다. 이를 통해 원소를 일일이 확인하지 않고도 구간 정보를 효율적으로 처리할 수 있으며, 쿼리와 업데이트 모두 일반적으로 $O(\log n)$에 처리할 수 있다.
- 시간복잡도
- 초기화 $O(n)$
- 구간 쿼리, 업데이트 $O(\log n)$
- 공간복잡도: $O(n) \sim O(4n)$
- 최대값 Segment Tree C++ (Pure)
더보기
// JUNGOL 1726 구간의 최대값1
// jungol.co.kr/problem/1726
// 세그먼트 트리 : 최대값 업데이트 및 쿼리
#include <bits/stdc++.h>
using namespace std;
const int LM = 50005;
const int TLM = 1 << 17; // 131072
int N, Q;
int tree[TLM];
void update(int idx, int val, int node, int l, int r){
if (l == r) {
tree[node] = val;
return;
}
int m = (l + r) / 2;
if (idx <= m) update(idx, val, node*2, l,m);
else update(idx, val, node*2+1, m+1, r);
tree[node] = max(tree[node*2], tree[node*2+1]);
}
int query(int ql, int qr, int node, int l, int r){
if(qr <l || r < ql) return INT_MIN;
if(ql <= l && r <= qr) return tree[node];
int m = (l+r)/2;
return max(query(ql, qr, node*2,l,m), query(ql,qr,node*2+1,m+1,r));
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data/1111.txt", "r", stdin);
#endif
scanf("%d %d", &N, &Q);
int i, s, e, val;
for (i = 1; i <= N; ++i) {
scanf("%d", &val);
update(i, val, 1, 1, N);
}
for (i = 0; i < Q; ++i) {
scanf("%d %d", &s, &e);
printf("%d\n", query(s, e, 1, 1, N));
}
}- 최대값 Segment Tree C++ (Pure, 구조체 버전)
더보기
// JUNGOL 1726 구간의 최대값1
// jungol.co.kr/problem/1726
#include <bits/stdc++.h>
#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
using namespace std;
int N, Q;
struct SegTree{
int n;
vector<int> tree;
SegTree(const vector<int>& arr) {
n = arr.size();
tree.resize(n*4);
build(arr, 1, 0, n-1);
}
void build(const vector<int>& arr, int node, int l, int r){
if (l == r) { tree[node] = arr[l]; return; }
int m = (l + r) / 2;
build(arr, node*2, l, m);
build(arr, node*2+1, m+1, r);
tree[node] = max(tree[node*2], tree[node*2+1]);
}
void update(int idx, int val, int node, int l, int r){
if (l == r) { tree[node] = val; return; }
int m = (l + r) / 2;
if (idx <= m) update(idx, val, node*2, l,m);
else update(idx, val, node*2+1, m+1, r);
tree[node] = max(tree[node*2], tree[node*2+1]);
}
int query(int ql, int qr, int node, int l, int r){
if(qr < l || r < ql) return INT_MIN;
if(ql <= l && r <= qr) return tree[node];
int m = (l+r)/2;
return max(query(ql, qr, node*2,l,m), query(ql,qr,node*2+1,m+1,r));
}
void update(int idx, int val) { update(idx, val, 1, 0, n-1); }
int query(int l, int r) { return query(l, r, 1, 0, n-1); }
};
int main(int argc, char **argv){
#ifndef ONLINE_JUDGE
freopen("data/1111.txt", "r", stdin);
#endif
scanf("%d%d", &N,&Q);
vector<int> arr(N);
for(int i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}
SegTree seg(arr);
while (Q--) {
int l,r; scanf("%d%d", &l, &r);
int ans = seg.query(l-1, r-1);
printf("%d\n", ans);
}
}
Fenwick tree (BIT)
펜윅 트리(Fenwick tree), 또는 바이너리 인덱스 트리(Binary Indexed Tree)는 선형적인 배열 구조에서 특정 위치의 값 갱신과 구간의 누적 합(prefix sum) 등의 쿼리를 효율적으로 처리하기 위한 자료구조이다. 배열을 인덱스의 비트 단위로 적절히 나누어, 각 구간에 대한 부분적인 합 정보를 트리 형태로 압축하여 저장한다. 쿼리가 발생하면 이 비트 연산을 이용해 필요한 구간들만 효율적으로 탐색하고 결과를 빠르게 누적하거나 갱신한다. 이를 통해 단순 배열 탐색 없이도 빠르게 구간 정보를 처리할 수 있으며, 각 원소 업데이트와 누적합 쿼리를 모두 일반적으로 $O(\log N)$ 시간에 처리할 수 있다.
- 시간복잡도
- 초기화 (최적화 시) $O(n)$
- 쿼리, 업데이트 $O(\log n)$
- 공간복잡도: $O(n)$ (세그먼트 트리보다 작음)
- 세그먼트 트리(Segment tree)보다 구현이 훨씬 간단하고 메모리 사용량도 적으며 상수 시간이 작아 더 빠르게 동작하는 경우가 많다.
- 하지만 세그먼트 트리가 다양한 연산(구간 합, 최대/최소, GCD 등)에 쉽게 확장 가능한 반면, 펜윅 트리는 주로 구간 합과 빈도수 관리 등 비교적 단순한 연산에 특화되어 있다. 펜윅 트리는 기본적으로 누적합 구조(prefix sum)를 기반으로 하므로 임의의 복잡한 연산을 처리하려면 추가적인 변형이나 테크닉이 필요하다.
- C++ (Pure, 구조체 버전)
더보기
#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
vector<int> tree;
Fenwick(int n) : tree(n+1) {}
int query(int pos){
++pos;
int ret=0;
while(pos>0){
ret += tree[pos];
pos -= pos & -pos; // or pos &= pos-1;
}
return ret;
}
void update(int pos, int val){
++pos;
while(pos < tree.size()){
tree[pos] += val;
pos += pos & -pos;
}
}
int query(int s, int e) {
return query(e) - query(s-1);
}
};
int main() {
int N = 8; // 원소 8개
vector<int> A = {0, 3, 2, 4, 1, 6, 5, 7, 2}; // 1-based dummy 0 포함
// idx: 1 2 3 4 5 6 7 8
Fenwick ft(N);
// build
for(int i=1; i<=N; i++) ft.update(i, A[i]);
printf("%d\n", ft.query(2,5)); // 2~5 합 = 2+4+1+6 = 13
ft.update(4,3); // A[4] += 3 (4→7)
printf("%d\n", ft.query(2,5)); // 2~5 합 = 16
}
Computational geometry
Convex hull
컨벡스 헐(convex hull)은 평면 위에 주어진 점 집합을 모두 포함하는 가장 작은 볼록 다각형을 구하는 문제다. 직관적으로는 점들을 고무줄로 감쌌을 때, 고무줄이 닿는 바깥쪽 점들의 집합이라고 생각하면 된다. 컨벡스 헐에 포함된 점들은 내부에 다른 점을 두지 않고, 어떤 두 점을 잇는 선분도 항상 다각형 내부에 존재한다. 이 성질 때문에 계산기하 문제에서 경계(boundary)를 구하는 기본 도구로 자주 등장한다.
PS에서 컨벡스 헐은 다음과 같은 문제 유형의 전처리로 많이 쓰인다.
- 가장 바깥 점들만 남겨서 이후 연산을 단순화해야 하는 경우
- 점 집합의 외곽선 길이, 면적을 구하는 문제
- 회전하는 캘리퍼스(rotating calipers)와 결합되는 문제
대표적인 알고리즘으로는 Graham Scan, Monotone Chain(Andrew 알고리즘)이 있다. PS에서는 구현이 간단하고 안정적인 Monotone Chain 방식이 가장 많이 쓰인다.
핵심 아이디어는 다음과 같다.
- 점들을 x좌표, x가 같으면 y좌표 기준으로 정렬한다.
- 정렬된 순서대로 아래쪽 헐(lower hull)을 만들면서, 최근 두 변과 새 점이 이루는 방향이 시계 방향 또는 일직선이 되면 중간 점을 제거한다.
- 같은 방식으로 위쪽 헐(upper hull)을 만든다.
- 아래쪽 헐과 위쪽 헐을 합치면 컨벡스 헐이 된다.
- 이때 방향 판정은 CCW(counter-clockwise, 반시계) 판별을 사용한다.
- 시간복잡도: $O(N \log N)$
- 공간복잡도: $O(N)$
Shoelace algorithm
신발끈 알고리즘(Shoelace formula)은 단순 다각형의 면적을 좌표만으로 계산하는 공식이다. 다각형의 꼭짓점들이 시계 방향 또는 반시계 방향으로 주어졌을 때, 각 변을 따라 좌표를 교차 곱해 더하고 빼는 방식으로 면적을 구한다. 이름이 '신발끈'인 이유는 좌표를 세로로 적어 놓고 대각선으로 곱해 더하는 과정이 신발끈을 엮는 모습과 비슷하기 때문이다.
다각형의 꼭짓점이 $(x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n)$ 순서로 주어졌을 때 면적은 다음과 같이 계산된다
$$A = | (x_1 y_2 + x_2 y_3 + \cdots + x_n y_1) - (y_1 x_2 + y_2 x_3 + \cdots + y_n x_1) | / 2$$
이 공식은 다각형이 볼록이든 오목이든 상관없이, 단순 다각형이면 항상 적용 가능하다. 단, 꼭짓점 순서가 뒤섞여 있으면 안 되고 반드시 경계를 따라 순서대로 주어져야 한다. PS에서 신발끈 알고리즘은 다음 상황에서 자주 쓰인다.
- 컨벡스 헐을 구한 뒤, 그 면적을 계산하는 문제
- 좌표로 주어진 다각형의 넓이를 직접 구하는 문제
- 영역 비교(어느 쪽 면적이 더 큰지) 문제
- 시간복잡도: $O(N)$
- 공간복잡도: $O(1)$
Rotating calipers
회전하는 캘리퍼스(Rotating Calipers)는 컨벡스 헐 위에서 두 점(또는 두 변)을 효율적으로 탐색하는 기법이다. 핵심은 hull 위의 포인터들을 한 방향으로만 움직이면서 최적값을 찾는다는 점이다. 이 기법은 반드시 컨벡스 헐이 전제 조건이다. 원본 점 집합에 바로 쓰지 않고, 먼저 컨벡스 헐을 구한 뒤 그 결과에 적용한다. 회전하는 캘리퍼스는 다음과 같은 문제에서 대표적으로 사용된다.
- 컨벡스 헐에서 가장 먼 두 점의 거리(지름, diameter)
- 최소 넓이의 외접 직사각형
- 최대 면적 삼각형
- 헐 위에서의 최대 거리/최대 면적 문제
이름은 실제 측정 도구인 캘리퍼스를 다각형의 양쪽에 대고, 다각형의 모서리를 따라 함께 회전시키는 개념에서 왔다. 중요한 점은 포인터가 뒤로 돌아가지 않고 한 방향으로만 이동한다는 것이다. 예를 들어 '컨벡스 헐에서 가장 먼 두 점' 문제에서는,
- 한 포인터는 헐의 한 꼭짓점을 따라 이동
- 다른 포인터는 해당 변에서 가장 먼 점을 가리키도록 이동
- 면적(또는 거리)이 증가하는 동안만 포인터를 전진
- 이 과정을 반복하면 전체를 선형 시간에 처리할 수 있다.
컨벡스 헐의 꼭짓점 개수를 H라고 하면, 두 포인터는 각각 최대 H번만 움직이므로 전체 시간은 선형이다.
- 시간복잡도: $O(H)$, $H$는 컨벡스 헐에 포함된 점의 개수, $H \le N$
- 공간복잡도: $O(1)$ (헐 저장 공간 제외)
Sweeping
라인 스위핑(Line sweeping) 또는 플레인 스위핑(plane sweeping) 알고리즘은 기하학적 문제, 특히 여러 개의 객체(예: 직사각형, 선분 등)가 주어졌을 때 이들 사이의 관계(예: 교차, 면적 계산 등)를 효율적으로 찾는 데 사용된다. 스위핑 라인(sweep line)을 가상으로 그려가며, 이 라인이 객체들을 스캔하면서 필요한 계산을 수행한다.
- C++
더보기
// JUNGOL 3336 직각다각형
// https://jungol.co.kr/problem/3336
#include <bits/stdc++.h>
#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define X first
#define Y second
using pii = std::pair<int,int>;
using ll = long long;
using namespace std;
int N;
vector<pii> points;
struct Event{
int pos, delta;
bool operator<(const Event& r)const{
if(pos != r.pos) return pos < r.pos;
return delta < r.delta;
}
};
int solve(){
vector<Event> events;
// Horizontal
for(int i=0;i<N;i++){
int j=(i+1)%N;
if(points[i].X == points[j].X){
int y1 = points[i].Y;
int y2 = points[j].Y;
int ymin = min(y1,y2);
int ymax = max(y1,y2);
if(ymin < ymax){
events.push_back({ymin, +1});
events.push_back({ymax, -1});
}
}
}
sort(events.begin(), events.end());
int active = 0, maxh = 0;
for(auto &e : events){
active += e.delta;
maxh = max(maxh, active);
}
// Vertical
events.clear();
for(int i=0;i<N;i++){
int j=(i+1)%N;
if(points[i].Y == points[j].Y){
int x1 = points[i].X;
int x2 = points[j].X;
int xmin = min(x1,x2);
int xmax = max(x1,x2);
if(xmin < xmax){
events.push_back({xmin, +1});
events.push_back({xmax, -1});
}
}
}
sort(events.begin(), events.end());
active = 0;
int maxv = 0;
for(auto &e : events){
active += e.delta;
maxv = max(maxv, active);
}
return max(maxh, maxv);
}
int main(int argc, char **argv){
#ifndef ONLINE_JUDGE
freopen("data/d3336.txt", "r", stdin);
#endif
scanf("%d", &N);
points.resize(N);
for(int i=0; i<N; i++) {
scanf("%d%d", &points[i].X, &points[i].Y);
}
// printf("%d %d\n", h, v);
printf("%d\n", solve());
}
Offline queries
Mo's algorithm
Mo’s algorithm은 구간 쿼리(range query)가 매우 많고, 쿼리의 순서를 마음대로 바꿔도 되는 문제에서 자주 쓰는 오프라인(offline) 기법이다. 핵심은 쿼리를 적절한 순서로 정렬해서, 현재 보고 있는 구간 $[L, R]$을 조금씩만 움직이면서 답을 업데이트하는 것이다.
보통 배열 A에 대해 각 쿼리 $[l, r]$에 대한 어떤 값(예: 서로 다른 값의 개수, 최빈값 관련 통계, xor/빈도 기반 값 등)을 물어볼 때 사용한다. 쿼리를 정렬할 때 블록 크기 B(보통 $\sqrt{N}$)로 L을 묶고, 같은 블록 내에서는 R을 증가/감소 순으로 정렬한다. 그러면 전체적으로 L과 R이 움직이는 총량이 줄어들고, 구간의 양 끝에 원소를 하나 추가/삭제할 때 $O(1)$ 또는 작은 비용으로 상태를 갱신할 수 있으면 전체가 빨라진다.
- 구간의 양 끝에 원소를 1개 넣고/빼는 연산(add/remove)이 빠르게 구현 가능해야 한다.
- 온라인(쿼리 순서 고정)에는 그대로 쓰기 어렵고, 쿼리를 모아 정렬해서 푸는 오프라인 문제에 적합하다.
- 값 범위가 크면 좌표압축을 같이 쓰는 경우가 많다.
- 시간복잡도: $O((N + Q) \cdot \sqrt{N}$ (정렬 포함 세부 상수는 구현에 따라 달라짐)
- 공간복잡도: $O(N + Q)$ + (상태를 위한 추가 배열)
Ad-hoc
PS에서 ad-hoc 문제는 특정 알고리즘이나 자료구조를 바로 적용할 수 없는 문제를 의미한다. 문제를 보고 다익스트라, 세그먼트 트리처럼 분류가 바로 떠오르지 않고 조건을 관찰해서 규칙을 직접 구성해야 하는 유형이다. 구현 자체는 단순할 수 있지만 조건이 많고 예외 처리가 중요해 실수하기 쉽다. PS에서 ad-hoc은 독립된 알고리즘이라기보다는 정형화된 알고리즘으로 깔끔하게 분류되지 않는 문제들을 호칭하는 것으로 이해하면 쉽다.
Algorithm techniques
Recursion
재귀(recursion)는 함수가 자기 자신을 호출하여 문제를 해결하는 방식이다. 재귀로 문제를 푼다는 것은 귀납적인 방식으로 문제를 해결하겠다는 것과 동일하다. 올바른 재귀 함수는 반드시 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 하는데 이를 보통 base condition이라고 한다. 또한 모든 입력은 base condition으로 수렴해야 한다. 재귀는 반복문으로 구현했을 때와 비교하여 코드는 간결하지만 메모리와 시간 측면에서는 일반적으로 손해를 본다. 재귀는 분할 정복 알고리즘, 트리 탐색 등에 널리 사용된다.
- 피보나치 수열을 재귀로 구하는 예제 C++
- 시간복잡도: $O(\phi^n) \approx O(1.618^n)$
더보기
#include <cstdio>
// recursive: O(1.618^n)
int fibonacci(int n) {
if (n == 0 || n == 1) return 1; // base case
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n = 20;
for (int i = 0; i <= n; i++) {
printf("%d ", fibonacci(i)); // 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
}
puts("");
}
- 하노이 탑을 재귀로 구하는 예제 C++
- 시간복잡도: $O(2^n)$
더보기
#include <bits/stdc++.h>
using namespace std;
void hanoi(int from, int to, int n){
if(n==1) { printf("%d %d\n",from,to); return; }
int by = 6-from-to;
hanoi(from, by, n-1);
printf("%d %d\n", from,to);
hanoi(by, to, n-1);
}
void hanoi2(int from, int by, int to, int n){
if(n==1) { printf("%d %d\n", from, to); return; }
hanoi2(from, to, by, n-1); // n-1개의 원반을 보조 기둥(by)로 이동
printf("%d %d\n", from, to); // 가장 큰 원반을 목표 기둥(to)로 이동
hanoi2(by, from, to, n-1); // n-1개의 원반을 목표 기둥(to)로 이동
}
int main(int argc, char **argv){
int K; scanf("%d",&K);
printf("%d\n", (1<<K)-1);
hanoi(1, 3, K);
// hanoi2(1, 2, 3, K);
}
Divide and conquer
분할정복(divide and conquer)은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고 각 부분 문제의 답으로 전체 문제의 답을 계산하는 알고리즘을 말한다. 분할 정복이 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다. 분할정복은 많은 경우 같은 작업을 더 빠르게 처리할 수 있다.
- 아래 알고리즘들이 모두 분할정복 패턴을 사용한다
- merge sort
- quick sort
- binary search
- segment tree
- karatsuba multiplication
- closest pair of points
- convolution (FFT)
- counting inversions via merge
- 1+2+...+n까지의 합을 분할정복으로 푸는 예제 C++
더보기
#include <bits/stdc++.h>
using ll = long long;
// 시간복잡도 O(log n)
ll fastSum(int n){
if(n==1) return 1;
if(n%2 == 1) return fastSum(n-1) + n;
else return 2*fastSum(n/2) + (n/2)*(n/2);
}
int main(int argc, char **argv){
printf("%lld\n", fastSum(9651)); // 46575726
}- 정방행렬의 거듭제곱을 분할정복으로 푸는 예제 C++
더보기
#include <bits/stdc++.h>
using namespace std;
class SquareMatrix {
public:
vector<vector<long long>> mat;
int n;
SquareMatrix(int n) : n(n), mat(n, vector<long long>(n, 0)) {}
SquareMatrix(const vector<vector<long long>>& arr)
: n((int)arr.size()), mat(arr) {}
int size() const { return n; } // 행렬 크기 반환
SquareMatrix operator*(const SquareMatrix &r) const {
SquareMatrix ret(n);
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
long long sum = 0;
for(int k=0; k<n; k++){
sum += mat[i][k] * r.mat[k][j];
}
ret.mat[i][j] = sum;
}
}
return ret;
}
};
SquareMatrix identity(int n){
SquareMatrix I(n);
for(int i=0; i<n; i++){
I.mat[i][i] = 1;
}
return I;
}
// 분할정복으로 행렬 거듭제곱
// 시간복잡도: O(n^3 log m), n: 행렬 크기, m: 거듭제곱 횟수
// 분할정복 안 쓴 경우 O(n^3 m)
SquareMatrix pow(const SquareMatrix& A, int m) {
if(m == 0) return identity(A.size());
if(m % 2 > 0) return pow(A, m - 1) * A;
SquareMatrix half = pow(A, m / 2);
return half * half;
}
int main(){
SquareMatrix M({{1,2},{3,4}}); // 2x2 행렬 예시
int exponent = 5;
SquareMatrix result = pow(M, exponent);
for(int i=0; i<result.size(); i++){
for(int j=0; j<result.size(); j++){
cout << result.mat[i][j] << " ";
}
cout << "\n";
}
}- 두 큰 정수의 곱셈을 분할정복으로 푸는 예제 C++ (a.k.a 카라츠바 알고리즘)
더보기
#include <bits/stdc++.h>
using namespace std;
// 카라츠바 시간복잡도: O(n^log3) ~= O(n^1.585)
// 단순히 두 큰 수를 곱하는 O(n^2)보다 훨씬 적은 곱셈을 필요로 한다
// num[]의 자리수 올림을 처리한다
void normalize(vector<int>& num){
num.push_back(0);
// 자리수 올림 처리
for(int i=0; i<num.size()-1; i++){
if(num[i] < 0) {
int borrow = (abs(num[i]) + 9) / 10;
num[i+1] -= borrow;
num[i] += borrow * 10;
}
else {
num[i+1] += num[i] / 10;
num[i] %= 10;
}
}
while(num.size() > 1 && num.back() == 0)
num.pop_back();
}
// 두 긴 자연수의 곱을 반환한다
// 각 배열에는 각 수의 자리수가 1의 자리에서부터 시작해 저장되어있다
vector<int> multiply(const vector<int>& a, const vector<int>& b) {
vector<int> c(a.size() + b.size() + 1, 0);
for(int i=0; i<a.size(); i++){
for(int j=0; j<b.size(); j++){
c[i+j] += a[i] * b[j];
}
}
normalize(c);
return c;
}
// a += b * (10^k)
void addTo(vector<int>& a, const vector<int>& b, int k) {
// Ensure a has enough size to accommodate b shifted by k
int sizeNeeded = max((int)a.size(), (int)(b.size() + k));
if(a.size() < sizeNeeded) {
a.resize(sizeNeeded, 0);
}
// Digit-wise addition
for(int i=0; i<b.size(); i++){
a[i + k] += b[i];
}
normalize(a);
}
// a -= b
void subFrom(vector<int>& a, const vector<int>& b) {
// Subtract b from a
for(int i=0; i<b.size(); i++){
a[i] -= b[i];
}
normalize(a);
}
vector<int> karatsuba(const vector<int>& a, const vector<int>& b) {
int an = a.size(), bn = b.size();
// a가 b보다 작으면 swap
if(an < bn) return karatsuba(b,a);
if(an == 0 || bn == 0)
return vector<int>();
// 작은 크기에서는 일반 곱으로 계산
if(an <= 50)
return multiply(a,b);
int half = an / 2;
// a, b를 절반으로 분할
vector<int> a0(a.begin(), a.begin() + half);
vector<int> a1(a.begin() + half, a.end());
vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));
vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());
// 재귀적으로 계산
vector<int> z2 = karatsuba(a1, b1);
vector<int> z0 = karatsuba(a0, b0);
// (a0 + a1)*(b0 + b1)를 계산
addTo(a0, a1, 0); // a0 = a0 + a1
addTo(b0, b1, 0); // b0 = b0 + b1
vector<int> z1 = karatsuba(a0, b0);
// z1 = z1 - z0 - z2
subFrom(z1, z0);
subFrom(z1, z2);
// 결과를 ret에 합치기
vector<int> ret;
// 시작은 0으로 아무것도 없는 상태
addTo(ret, z0, 0);
addTo(ret, z1, half);
addTo(ret, z2, half + half);
return ret;
}
int main(){
string s1, s2;
s1 = "1234";
s2 = "5678";
vector<int> a, b;
for(int i = s1.size()-1; i >= 0; i--){
a.push_back(s1[i] - '0');
}
for(int i = s2.size()-1; i >= 0; i--){
b.push_back(s2[i] - '0');
}
// Karatsuba로 곱셈
vector<int> result = karatsuba(a, b);
// Leading zero 제거 (최소 한 자리는 남겨둠)
while(result.size() > 1 && result.back() == 0) {
result.pop_back();
}
// 정상적인(가장 큰 자리부터) 순서로 출력
for(int i = result.size()-1; i >= 0; i--){
printf("%d", result[i]);
}
puts("");
}
Dynamic programming
동적계획법(dynamic programming)은 복잡한 문제를 작은 하위 문제로 나누어 해결하고, 이 결과를 저장하여 재사용함으로써 전체 문제의 효율적인 해결을 가능하게 한다. 최적 부분 구조와 중복되는 하위 문제를 가진 경우에 유용하다. DP에는 다양한 유형들이 있기 때문에 유형별로 정리하였다.
최대 증가 부분수열(LIS, Longest Increasing Subsequence)
수열이 주어졌을 때 순서를 유지하면서 증가하는 부분수열 중 길이가 최대인 부분수열
- 최대 증가 부분수열을 dp로 푸는 예제 C++ #1
더보기
#include <bits/stdc++.h>
using namespace std;
int N;
int dp[100]; // dp[i] = i에서 시작하는 LIS 길이
vector<int> A;
// 시간복잡도: O(n^2) 재귀형 (top-down)
int lis(int start) {
int &ret = dp[start];
if(ret != -1) return ret;
ret = 1;
for(int next = start+1; next<N; next++){
if(A[start] < A[next])
ret = max(ret, lis(next)+1);
}
return ret;
}
// 시간복잡도: O(n^2) 반복형 (bottom-up)
int lis2() {
for(int i = 0; i < N; i++)
dp[i] = 1;
for(int i = 0; i < N; i++){
for(int j = 0; j < i; j++){
if(A[j] < A[i]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
int ret = 0;
for(int i = 0; i < N; i++)
ret = max(ret, dp[i]);
return ret;
}
int main(int argc, char **argv){
N = 8;
A = {5,3,6,2,7,1,4,8};
memset(dp, -1, sizeof(dp));
int ans=0;
for(int i=0; i<N; i++)
ans = max(ans, lis(i));
printf("%d\n", ans); // 4 (5,6,7,8)
// printf("%d\n", lis2());
}- 최대 증가 부분수열을 dp로 푸는 예제 C++ #2
더보기
// JUNGOL 1257 전깃줄(중)
// jungol.co.kr/!1257
#include <bits/stdc++.h>
#define X first
#define Y second
using pii = std::pair<int,int>;
using namespace std;
const int LM = 105;
vector<pii> arr;
int dp[LM];
int N;
// 시간복잡도: O(NlogN) 이분탐색
vector<int> lisopt(){
vector<int> tails;
for(int i=0;i<N;i++){
auto it = lower_bound(tails.begin(), tails.end(), arr[i].Y);
if(it == tails.end()) tails.push_back(arr[i].Y);
else *it = arr[i].Y;
}
return tails;
}
// 시간복잡도: O(NlogN) 이분탐색, 경로 복원
pair<int, vector<int>> lisopt2() {
vector<int> tails_idx;
vector<int> prev(N, -1);
for(int i = 0; i < N; i++) {
auto it = lower_bound(tails_idx.begin(), tails_idx.end(), arr[i].Y,
[&](int idx, int val) { return arr[idx].Y < val; });
int p = it - tails_idx.begin();
prev[i] = (p > 0) ? tails_idx[p-1] : -1;
if(it == tails_idx.end()) tails_idx.push_back(i);
else *it = i;
}
vector<int> lis_indices;
if(!tails_idx.empty()) {
for(int i = tails_idx.back(); i != -1; i = prev[i]) {
lis_indices.push_back(i);
}
reverse(lis_indices.begin(), lis_indices.end());
}
return {tails_idx.size(), lis_indices};
}
int main(int argc, char **argv){
#ifndef ONLINE_JUDGE
freopen("data/1257.txt", "r", stdin);
#endif
scanf("%d", &N);
for(int i=0; i<N; i++){
int a,b; scanf("%d%d", &a,&b);
arr.push_back({a,b});
}
sort(arr.begin(), arr.end());
auto [len, ret] = lisopt2();
int ans = N - len;
printf("%d\n", ans);
vector<bool> inlis(N, false);
for(int idx : ret){
inlis[idx] = true;
}
for(int i=0; i<N; i++){
if(!inlis[i])
printf("%d\n", arr[i].X);
}
}
배낭 문제(Knapsack problem)
물건 n개가 있고 각 물건은 무게 w, 가치 v를 지닐 때 배낭 용량 w를 넘지 않게 담아서 가치 합을 최대화하는 문제. 각 물건은 한 번만 사용 가능하면 0/1 knapsack, 여러번 사용 가능하면 unbounded knapsack 문제로 불린다.
- 배낭 문제를 dp로 푸는 예제 C++ #1
더보기
// JUNGOL 2616 앱(APP)
// jungol.co.kr/problem/2616
#include <bits/stdc++.h>
using namespace std;
const int LM = 105;
const int MAX_COST = 10005;
int N,M;
int mem[LM], cost[LM];
int dp[MAX_COST + 1]; // dp[j] : j 비용으로 확보할 수 있는 최대 메모리
int main(int argc, char **argv){
#ifndef ONLINE_JUDGE
freopen("data/d2616.txt", "r", stdin);
#endif
scanf("%d%d", &N,&M);
for(int i=0; i<N; i++){
scanf("%d", &mem[i]);
}
for(int i=0; i<N; i++){
scanf("%d", &cost[i]);
}
memset(dp, 0, sizeof(dp));
for(int i=0; i<N; i++){
for(int j=MAX_COST; j>=cost[i]; j--){
dp[j] = max(dp[j], dp[j-cost[i]] + mem[i]);
}
}
int ans = MAX_COST + 1;
for(int j=0; j<=MAX_COST;j++){
if(dp[j] >= M){
ans = j;
break;
}
}
printf("%d\n", ans);
}- 배낭 문제를 dp로 푸는 예제 C++ #2
더보기
// BOJ 2629 양팔저울
// boj.kr/2629
#include <bits/stdc++.h>
#define rnt register int
#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define X first
#define Y second
using pii = std::pair<int,int>;
using ll = long long;
using namespace std;
const int LM = 35;
int N, M;
int dp[LM][15005]; // dp[i][d] : 앞의 i개 추로 무게 차이 d를 만들 수 있는지
int A[LM];
int total;
int main(int argc, char **argv){
#ifndef ONLINE_JUDGE
freopen("data/d1352.txt", "r", stdin);
#endif
scanf("%d", &N);
for(int i=1; i<=N; i++){
scanf("%d", &A[i]);
total += A[i];
}
dp[0][0] = true;
for(int i=1; i<=N; i++){
int w = A[i];
for(int j=0; j<total; j++){
if(dp[i-1][j]){
dp[i][j] = true;
if(j+w <= total)
dp[i][j+w] = true;
dp[i][abs(j-w)] = true;
}
}
}
scanf("%d", &M);
for(int i=0;i<M;i++){
int x; scanf("%d", &x);
if(x > total) { printf("N "); continue; }
if(dp[N][x]) printf("Y ");
else printf("N ");
}
puts("");
}
서열 정렬(Sequence alignment)
DNA/RNA/단백질처럼 문자열(서열) 두 개를 비슷한 부분이 최대한 잘 맞도록 갭을 넣어 정렬하는 문제
- Needleman-Wunsch (전역 정렬)
- Smith-Waterman (국소 정렬)를 dp로 푼 예제 C++
더보기
// JUNGOL 1858 DNA유사도
// jungol.co.kr/!1858
#include <bits/stdc++.h>
#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define X first
#define Y second
using pii = std::pair<int,int>;
using ll = long long;
using namespace std;
const int LM = 1005;
int dp[LM][LM];
int main(int argc, char **argv){
#ifndef ONLINE_JUDGE
freopen("data/1858.txt", "r", stdin);
#endif
int n,m;
string s1,s2;
cin >> n >> s1;
cin >> m >> s2;
int best = 0, bi=0, bj=0;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
int match = (s1[i-1] == s2[j-1]) ? 3 : -2;
int diag = dp[i-1][j-1] + match;
int up = dp[i-1][j] - 2;
int left = dp[i][j-1] - 2;
dp[i][j] = max({0, diag, up, left});
if(dp[i][j] > best){
best = dp[i][j];
bi = i; bj = j;
}
}
}
string sub1, sub2;
int i=bi, j=bj;
while(i>0 && j>0 && dp[i][j]>0){
int cur = dp[i][j];
int match = (s1[i-1]==s2[j-1]) ? 3 : -2;
if(cur == dp[i-1][j-1] + match){
sub1.push_back(s1[i-1]);
sub2.push_back(s2[j-1]);
i--; j--;
}
else if(cur == dp[i-1][j] - 2){
sub1.push_back(s1[i-1]);
i--;
}
else{
sub2.push_back(s2[j-1]);
j--;
}
}
reverse(sub1.begin(), sub1.end());
reverse(sub2.begin(), sub2.end());
printf("%d\n%s\n%s\n", best, sub1.c_str(), sub2.c_str());
}
Others
- 피보나치 수열을 DP로 구하는 예제 C++
더보기
#include <cstdio>
// recursive : O(1.618^n)
// dp : O(n)
int fibonacci(int n){
int f[50];
f[0] = f[1] = 1;
for(int i=2; i<=n; i++)
f[i] = f[i-1] + f[i-2];
return f[n];
}
int main() {
printf("%d\n", fibonacci(20)); // 10946
}
Greedy
탐욕(greedy) 알고리즘은 매 선택에서 지역적으로 최적인 선택을 함으로써 최종적인 해답의 최적성을 보장하는 알고리즘이다. 문제에 따라 최적해를 보장하지 않을 수도 있다.
- C++
더보기
// BOJ 11047 동전0
// boj.kr/11047
#include <bits/stdc++.h>
#define rnt register int
#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define WATCH(x) cout << #x << " : " << x << '\n';
#define PRINT(x) cout << x << '\n';
#define X first
#define Y second
using namespace std;
using pii = pair<int,int>;
using ll = long long;
int n,k;
int a[15];
int main(int argc, char **argv){
int ans =0;
scanf("%d%d",&n,&k);
for(int i=0; i<n; i++) scanf("%d", &a[i]);
// Greedy (a[i]가 배수이므로 그리디 사용 가능)
for(int i=n-1; i>=0; i--) {
ans += k / a[i];
k %= a[i];
}
printf("%d\n", ans);
}
Two pointers
투 포인터(two pointers) 알고리즘은 배열에서 원래 이중 for문으로 $O(n^2)$에 처리되는 작업을 2개의 포인터의 움직임으로 $O(n)$에 해결하는 알고리즘을 말한다.
- 시간복잡도: $O(n)$
- C++ (Pure)
더보기
// 수 고르기 boj.kr/2230
#include <bits/stdc++.h>
using namespace std;
constexpr int LM = 100'005;
constexpr int INF = 0x7fffffff;
int N,M;
int A[LM];
int main(int argc, char **argv){
scanf("%d%d",&N, &M);
for(int i=0; i<N; i++){
scanf("%d", &A[i]);
}
sort(A, A+N);
int ans = INF;
// Two pointers
int en = 0;
for(int st=0; st<N; st++){
while(en < N && A[en] - A[st] < M) en++;
if(en == N) break; // en이 범위를 벗어날 시 종료
ans = min(ans, A[en] - A[st]);
}
printf("%d\n", ans);
}
Sqrt decomposition
제곱근 분할(sqrt decomposition)은 데이터를 $\sqrt{n}$ 크기의 블록으로 나누어, 구간 합이나 구간 최솟값·최댓값 등의 쿼리를 빠르게 처리하기 위한 알고리즘 기법이다. 각 블록에 대한 요약 정보를 미리 계산해 두고, 쿼리가 들어오면 필요한 블록만 참조하여 결과를 합산하거나 갱신한다. 이를 통해, 개별 원소를 전부 확인하지 않고도 효율적으로 쿼리에 응답할 수 있다. 일반적으로 쿼리와 업데이트가 모두 $O(\sqrt{n})$에 처리되어, 단순한 방법에 비해 성능을 크게 향상시킬 수 있다.
- 시간복잡도
- 초기화 $O(n)$
- 구간 쿼리, 업데이트 $O(\sqrt{n})$
- 공간복잡도: $O(\sqrt{n})$
- C++ (Pure) #1
더보기
// JUNGOL 1726 구간의 최대값1
// jungol.co.kr/problem/1726
// sqrt decomposition : [s, e) , update() 함수 구현
#include <cstdio>
const int LM = 50005;
const int MOD = 256; // sqrt(50000) = 223.606
int N, Q;
int A[LM]; // 입력 데이터
int B[MOD + 1]; // 각 블록별 최대값
inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }
void update(int idx, int newVal) {
int bn = idx / MOD; // idx가 속한 블록 번호
int sn = bn * MOD, en = min(sn + MOD, N); // idx가 속한 블록의 시작과 끝 인덱스
A[idx] = B[bn] = newVal;
for (int i = sn; i < en; ++i) // 블록 내 최대값 갱신
B[bn] = max(B[bn], A[i]);
}
int query(int s, int e) { // 구간 [s, e)에서 최대값 찾기
int maxValue = A[s];
// 1. 왼쪽 끝부분에서 블록 경계를 맞추기 위해 개별 비교
while (s < e && s % MOD) maxValue = max(maxValue, A[s++]);
// 2. 오른쪽 끝부분에서 블록 경계를 맞추기 위해 개별 비교
while (s < e && e % MOD) maxValue = max(maxValue, A[--e]);
// 3. 블록 단위로 최대값 비교
for (s /= MOD, e /= MOD; s < e; s++) maxValue = max(maxValue, B[s]);
return maxValue;
}
int main() {
int s, e;
scanf("%d %d", &N, &Q);
for (int i = 0; i < N; ++i) {
scanf("%d", A + i);
update(i, A[i]);
}
for (int i = 0; i < Q; ++i) {
scanf("%d %d", &s, &e);
printf("%d\n", query(s - 1, e));
}
}- C++ (Pure) #2
더보기
// JUNGOL 7035 등수조작
// http://jungol.co.kr/problem/7035
#include <bits/stdc++.h>
using namespace std;
constexpr int LM = 100005;
constexpr int MOD = 320;
int N, Q;
int S[LM];
int A[LM]; // A[score] = cnt
int B[MOD];
void update(int sid, int val) {
A[S[sid]]--;
B[S[sid] / MOD]--;
S[sid] = val;
A[S[sid]]++;
B[S[sid] / MOD]++;
}
void query(int l, int r) {
int sum = 0;
while (l < r && l%MOD) sum += A[l++]; // l
while (l < r && (r+1)%MOD) sum += A[r--]; // r
for (; l < r; l+=MOD) sum += B[l/MOD]; // group
printf("%d\n", N - sum + 1);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data/d7979.txt", "r", stdin);
#endif
scanf("%d%d", &N, &Q);
for (int i = 1; i <= N; i++) {
scanf("%d", S + i);
A[S[i]]++;
B[S[i] / MOD]++;
}
while (Q--) {
int cmd, a, b;
scanf("%d%d", &cmd, &a);
if (cmd == 1) {
query(0, S[a]);
}
else {
scanf("%d", &b);
update(a, b);
}
}
}
Solving tips
Tip
- 문제는 다음 링크를 통해 확인할 수 있다.
- 백준: boj.kr/{문제 번호}
- 정올: jungol.co.kr/problem/{문제 번호}
- 알고스팟: algospot.com/judge/problem/read/{문제 이름}
- 채점용 서버는 일반적으로 1초에 1~5억번의 연산을 수행한다.
- 따라서 데이터가 $n=10000\sim20000$개 일 때 $O(n^2)$ 알고리즘은 제한시간 1초 내 통과하기 어렵다.
- #include <bits/stdc++.h>는 Mac이나 Windows에서 기본적으로 지원하지 않으므로 해당 링크에서 다운로드 받은 후 아래 경로에 넣어준다.
- Mac: /Library/Developer/CommandLineTools/usr/include/bits/stdc++.h
- Windows: C:\Program Files (x86)\Microsoft Visual Studio\{Version}\Community\VC\Tools\MSVC\{Version}\include\bits\stdc++.h
- Ubuntu: /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h (기본적으로 파일이 존재한다)
- 전역변수와 static 변수는 자동으로 0으로 초기화되는 반면 지역변수는 자동으로 초기화되지 않고 쓰레기 값(garbage value)으로 채워지게 된다.
int A; // 자동으로 0으로 초기화
int B[50]; // 자동으로 0으로 초기화
static int C; // 자동으로 0으로 초기화
int main() {
int D; // 쓰레기 값(garbage value)으로 채워짐
int E[50]; // 쓰레기 값(garbage value)으로 채워짐
}- $\pi = 3.14159\cdots$는 다음과 같이 여러 방법으로 사용할 수 있다
#include <cmath>
#include <cstdio>
const double pi = acos(-1);
const double pi_ = 2.0 * acos(0);
const double pi__ = 4.0 * atan(1);
int main() {
// 모두 <cmath> 헤더 필요
printf("%lf\n", M_PI); // #1(GNU ok, MSVC는 #define _USE_MATH_DEFINES 선언 후 사용)
printf("%lf\n", pi); // #2
printf("%lf\n", pi_); // #3
printf("%lf\n", pi__); // #4
}
Time complexity
시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간의 양을 나타내는 척도이다. 이는 주로 입력 크기의 함수로 표현되며, 알고리즘이 실행될 때 필요한 기본 연산의 횟수로 측정된다. 시간 복잡도를 평가할 때는 최악의 경우, 평균 경우, 최선의 경우를 고려할 수 있으나, 대부분의 경우 최악의 시간 복잡도가 중요한 지표로 사용된다. 시간 복잡도는 Big O 표기법을 사용하여 표현한다. $\log n$은 밑이 2인 $\log_2 n$을 의미한다.
- $O(1)$: 상수 시간. 입력 크기와 상관없이 알고리즘의 실행 시간이 일정하다.
- $O(\log n)$: 로그 시간. 데이터 양이 증가해도 실행 시간이 비교적 적게 증가한다. e.g., 이진 탐색
- $O(n)$: 선형 시간. 알고리즘의 실행 시간이 입력 크기에 직접 비례한다. 예를 들어, e.g., 배열 순회
- $O(n \log n)$: 선형 로그 시간. 많은 효율적인 정렬 알고리즘들이 이 시간 복잡도를 갖는다.
- $O(n^2)$: 제곱 시간. 입력 크기의 제곱에 비례하는 실행 시간을 가지며, 이중 반복문을 사용하는 알고리즘에서 흔히 발생한다.
- $O(2^n)$: 지수 시간. 알고리즘의 실행 시간이 입력 크기의 지수 함수로 증가한다. 일부 재귀 알고리즘에서 발생할 수 있다.
- $O(n!)$: 팩토리얼 시간. 알고리즘의 실행 시간이 입력 크기의 팩토리얼에 비례하여 증가한다. 순열을 생성하는 알고리즘 등에서 나타날 수 있다.
Space complexity
공간 복잡도는 알고리즘의 실행 과정에서 필요한 저장 공간의 양을 나타내는 척도이다. 이는 알고리즘이 작동하기 위해 필요한 메모리 양을 의미하며, 입력 크기와 알고리즘의 구현 방식에 따라 달라진다. 공간 복잡도 역시 Big O 표기법을 사용하여 표현되며, 주로 입력 데이터, 추가적으로 필요한 변수, 재귀 호출 시 스택 공간 등을 고려하여 계산한다.
알고리즘 설계 시, 시간 복잡도와 공간 복잡도 사이에는 종종 trade-off 관계가 있다. 예를 들어, 더 많은 메모리를 사용하여 실행 시간을 단축시키는 경우(공간을 시간으로 바꾸는 경우)가 있을 수 있다. 효율적인 알고리즘을 설계하기 위해서는 문제의 요구 사항에 따라 시간과 공간 복잡도 사이의 최적의 균형을 찾는 것이 중요하다.
Snippet code
아래 코드는 필자가 PS를 시작할 때 사용하는 C++ 스니펫 코드이다. 항상 사용하는 것은 아니며 필요한 경우 수정하여 사용한다.
#include <bits/stdc++.h>
#define rnt register int
#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define X first
#define Y second
using pii = std::pair<int,int>;
using ll = long long;
using namespace std;
int main(int argc, char **argv){
}
vscode용 스니펫 코드는 다음과 같다. (Ctrl+Shift+P --> Snippets: Configure Snippets --> cpp.json)
"ps": {
"prefix": "ps",
"body": [
"#include <bits/stdc++.h>",
"#define rnt register int",
"#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);",
"#define X first",
"#define Y second",
"using pii = std::pair<int,int>;",
"using ll = long long;",
"using namespace std;",
"",
"int main(int argc, char **argv){",
" $1",
"}"
],
"description": ""
}
Macro
- C++11부터 #define 대신 constexpr을 사용할 수 있다.
- #define LM 10005
- constexpr int LM = 10005;
- register int는 int 자료형보다 미세하게 실행 속도가 빠르다. 이는 constexpr 로는 선언이 안되므로 항상 #define 으로 선언해줘야 한다.
- #define rnt register int
- #define POWER(x) x*x 과 같이 선언하면 안된다. POWER(2+3) = 2+3*2+3 = 11이 되므로 #define POWER(x) ((x)*(x))와 같이 항상 괄호로 감싸줘야 한다.
- #define POWER(x) ((x)*(x))
- #define ABS(x) ((x)>0 ? (x):-(x))
- #define MIN(x,y) ((x)<(y) ? (x) : (y))
- #define MAX(x,y) ((x)<(y) ? (y) : (x))
- #define ALL(x) begin(x), end(x)
- #define SIZE(x) int(size(x))
- #define REP(i,a,b) for(int i=(a); i<=(b); i++)
- 디버깅용 매크로
- #define WATCH(x) cout << #x << " : " << x << '\n'
- #define DEBUG(x) cout << "DB - " << x << '\n'
- #define PRINT(x) cout << x << '\n'
- #define NWATCH(x)
- #define NDEBUG(x)
- #define NPRINT(x)
- DEBUG, WATCH, PRINT 앞에 N만 입력해주면 출력 구문을 비활성화할 수 있다.
Value initialization
memset() 함수는 배열을 $0$ 또는 $-1$ 값으로 초기화할 때만 사용한다. 이외의 값은 memset 함수로 세팅할 수 없다. 배열을 특정 값으로 세팅하고 싶다면 단순하게 for 문을 돌리거나 algorithm 헤더의 std::fill() 함수를 사용하면 된다.
- memset(A, 0, sizeof(A));
- for(int i=0; i<N; i++) A[i] = k; : k는 임의의 수
- std::fill(A, A+N, k);
예외적으로 다익스트라, 플로이드 와샬 알고리즘 등 그래프 최단거리 문제 등에서 무한대 값을 나타낼 때 memset()이 종종 사용되기도 한다
- memset(A, 0x3f, sizeof(A));
이는 A의 값을 0x3f3f3f3f (=1,061,109,567)으로 변경하여 해당 배열이 무한대(INF)로 초기화되었음을 의미한다. 0x3f3f3f3f은 2배를 해도 int 범위 내에 있기 때문에 오버플로우로부터 안전하여 무한대 값으로 자주 사용된다
constexpr int INF = 0x3f3f3f3f; // 무한대 값으로 자주 사용됨
I/O stream
1. cin/cout을 사용할 경우 다음 명령을 실행시켜야 시간 초과가 발생하지 않는다
- ios_base::sync_with_stdio(0); : C stream과 C++ stream의 동기화를 비활성화하여 C++ stream만 사용. 속도 측면에서 이득이지만 이후부터는 printf와 cout을 섞어쓰면 안된다.
- cin.tie(0), cout.tie(0) : cin, cout 명령 수행 전 flush 버퍼를 비우는 과정을 비활성화함으로써 속도 측면에서 이득을 봄 (하지만 입출력의 순서를 보장받을 수 없기 때문에 PS 이외에는 권장하는 방법은 아님)
- cin.tie(0)->sync_with_stdio(0); : 둘을 한 줄로 작성 가능
2. std::endl은 개행 문자 '\n'를 입력 후 버퍼를 비우는 과정을 자동으로 수행하기 때문에 느리므로 사용하지 않는다. endl 대신 '\n'을 사용한다.
3. getline(cin, s) : 공백까지 통째로 한 줄 입력을 받을 때 사용
4. cout << fixed << setprecision(n) : 소수점 아래 n자리까지 반올림하여 출력할 때 사용
Range-based for loop
1. C++11부터 추가된 기능
- for(int v : V) : 벡터 V의 모든 원소의 복사본 v대해 루프를 돈다
- for(int &v : V) : 벡터 V의 모든 원소의 원본 v에 대해 루프를 돈다
Bit-wise operation
유용하게 사용되는 비트연산자
- a를 k로 나눈 나머지 값 (k가 2의 거듭제곱인 경우만)
- result = a & (k-1); // same as 'a % k' (k = 2, 4, 8, 16, ... 2^n)
- a가 홀수인지 판단하는 법
- if(a & 1) { printf("odd"); }
- a가 짝수인지 판단하는 법
- if(~a & 1) { printf("even"); }
- a와 $2^k$을 곱한 결과
- result = a << k;
- a를 $2^k$로 나눈 몫 p와 나머지 q
- p = a >> k;
- q = a & ((1 << k) - 1);
- a와 b의 값을 서로 바꾸는 코드
- a = a^b, b = a^b, a = a^b;
- a = a^b, b = a^b, a = a^b;
- a가 2의 제곱수인지 판별
- result = a & (a-1); // a!=0 이면서 result==0이면 2의 제곱수
- k개의 집합 원소가 주어졌을 때
- a = (1 << k) - 1; // 꽉 찬 집합 구하기
- a = 0; // 공집합 구하기
- a |= (1 << k); // k번째 원소의 추가
- a &= ~(1 << k); // k번째 원소의 삭제
- a ^= (1 << k); // k번째 원소의 토글 (0이면 1, 1이면 0으로 변경)
- result = a & (1 << k); // k번째 원소의 포함 여부 확인
- result = (a | b); // a,b의 합집합
- result = (a & b); // a,b의 교집합
- result = (a & ~b); // a에서 b를 뺀 차집합
- result = (a ^ b); // a와 b 중 하나에만 포함된 원소들의 집합
- 최소 원소 지우기 (a가 2의 제곱수인지 판별하는 코드와 동일)
더보기
int main(){
int a = 40; // 40 (0b101000)
// 39 (0b100111)
a &= a-1;
printf("%d\n", a); // 32 (0b100000)
}- 집합의 크기 구하기
더보기
int bitCount(int x){
if(x==0) return 0;
return x%2 + bitCount(x/2);
}
int main() {
int a = 72; // 0b01001000
printf("%d\n", bitCount(a)); // 2, Naive method
printf("%d\n", __builtin_popcount(a)); // 2, Optimized method(gcc/g++ only)
}- 모든 부분 집합 순회하기 (공집합 제외)
더보기
int main(){
int a = 40; // 0b101000
for(int s=a; s; s=((s-1) & a)) {
printf("%d ", s); // 40(0b101000) 32(0b100000) 8(0b001000)
}
}- a의 Least Significant 1 Bit (LSB1 : $2^0$부터 시작하여 처음 만나는 1인 비트의 가중치 값)을 구하는 법
더보기
int main() {
int a = 72; // 0b01001000
int lsb = (a & -a);
printf("a's LSB magnitude %d\n", lsb); // 8, 2^3
printf("a's LSB order %d\n", __builtin_ctz(a)); // 3 (gcc/g++ only)
}- pos에서 가장 낮은 1비트(LSB1)만 남긴 값을 구한 후 이를 추가/제거하는 법 (펜윅 트리(Fenwick tree)에서 사용)
더보기
int main(){
int pos = 0b10111; // 23
pos -= pos & -pos; // #1 LSB1 제거: 0b10111 -> 0b10110
pos &= pos-1; // #2 LSB1 제거: 0b10110 -> 0b10100
pos += pos & -pos; // #3 LSB1를 기존값에 더함: 0b10100 + 0b00100 -> 0b11000
}- a의 Most Signimifacnt 1 BiT (MSB1: 왼쪽에서 가장 처음 만나는 1인 비트의 가중치 값)을 구하는 법
더보기
#include <bits/stdc++.h>
using namespace std;
int main() {
int a = 72; // 0b01001000
int msb_order = 31 - __builtin_clz(a); // MSB1 index
int msb = 1 << msb_order; // MSB1 magnitude
printf("a's MSB magnitude %d\n", msb); // 64, 2^6
printf("a's MSB order %d\n", msb_order); // 6
}
Prime number
- 현재 숫자 n이 1 이외에 다른 수로 나눠지는지 확인함으로써 소수 판별
- 시간복잡도: $O(\sqrt{n})$
더보기
bool isPrime(int n) {
if(n==1) return 0;
for(int i=2; i*i<=n; i++){ // search until sqrt(n)
if(n % i == 0) return 0;
}
return 1;
}
- 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하여 소수가 아닌 값들을 마킹함으로써 소수 판별
- 시간복잡도: $O(n \log (\log n))$
- C++ (Pure)
더보기
#include<bits/stdc++.h>
constexpr int N = 1005;
bool prime[N];
// Pure
void sieve() {
memset( prime, 1, sizeof( prime ) );
prime[1] = false;
for ( int i = 2; i * i <= N; i++ ) {
if ( prime[i] == false ) continue;
for ( int j = i * i; j <= N; j += i ) {
prime[j] = false;
}
}
}
int main() {
sieve();
for ( int i = 2; i <= N; i++ ) {
if ( prime[i] ) { // check if 'i' is prime number
printf( "%d ", i );
}
}
puts( "" );
}- C++ (w/ STL)
더보기
#include <bits/stdc++.h>
using namespace std;
int N = 1005;
vector<int> primes;
// STL
void sieve() {
vector<bool> state( N + 1, true );
state[1] = false;
for ( int i = 2; i * i <= N; i++ ) {
if ( !state[i] ) continue;
for ( int j = i * i; j <= N; j += i )
state[j] = false;
}
for ( int i = 2; i <= N; i++ ) {
if ( state[i] ) primes.push_back( i );
}
}
int main() {
sieve();
for ( int i = 2; i <= N; i++ ) {
if ( find( primes.begin(), primes.end(), i ) != primes.end() ) {
printf( "%d ", i );
}
}
puts( "" );
}- 최적화된 에라토스테네스의 체 #1 (비트마스킹으로 1/8 메모리 사용)
더보기
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int LM = numeric_limits<int>::max(); // 2'147'483'647
const int SIZE = ( LM >> 3 ) + 1; // 1/8 메모리 사용
unsigned char sieve[SIZE];
inline bool isPrime( int k ) {
return sieve[k >> 3] & ( 1 << ( k & 7 ) );
}
inline void setComposite( int k ) {
sieve[k >> 3] &= ~( 1 << ( k & 7 ) );
}
void eratosthenes() {
memset( sieve, 255, sizeof( sieve ) );
setComposite( 0 );
setComposite( 1 );
for ( int i = 2; (ll)i * i <= LM; i++ ) {
if ( isPrime( i ) )
for ( ll j = (ll)i * i; j <= LM; j += i )
setComposite( j );
}
}
int main( int argc, char **argv ) {
eratosthenes();
// 첫 20개의 소수 출력
int cnt = 1;
for ( int i = 2; cnt < 20; i++ ) {
if ( isPrime( i ) ) {
printf( "%d ", i ); // 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67
cnt++;
}
}
puts( "" );
}- 최적화된 에라토스테네스의 체 #2 (비트마스킹 + 홀수만 탐색으로 1/16 메모리 사용)
더보기
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int LM = numeric_limits<int>::max(); // 2'147'483'647
const int SIZE = ( LM >> 4 ) + 1; // 1/16 메모리 사용, 홀수만 탐색
unsigned char sieve[SIZE];
inline bool isPrime( int k ) {
return sieve[k >> 4] & ( 1 << ( ( k >> 1 ) & 7 ) );
}
inline void setComposite( int k ) {
sieve[k >> 4] &= ~( 1 << ( ( k >> 1 ) & 7 ) );
}
void eratosthenes() {
memset( sieve, 255, sizeof( sieve ) );
setComposite( 1 );
for ( int i = 3; (ll)i * i <= LM; i += 2 ) {
if ( isPrime( i ) )
for ( ll j = (ll)i * i; j <= LM; j += i * 2 )
setComposite( j );
}
}
int main( int argc, char **argv ) {
eratosthenes();
// 첫 20개의 소수 출력
printf( "2 " ); // 2는 먼저 출력
int cnt = 2;
for ( int i = 3; cnt < 20; i += 2 ) {
if ( isPrime( i ) ) {
printf( "%d ", i ); // 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67
cnt++;
}
}
puts( "" );
}
Partial sum
- 1D 부분합을 구하는 코드
- $P[i] = \sum_{j=0}^{i} A[j]$
- $\text{sum}(a,b) = P[b] - P[a-1]$
더보기
#include <bits/stdc++.h>
using namespace std;
vector<int> partialSum( const vector<int>& A ) {
vector<int> ret( A.size() );
ret[0] = A[0];
for ( int i = 1; i < A.size(); i++ ) {
ret[i] = ret[i - 1] + A[i];
}
return ret;
}
int rangeSum( const vector<int>& psum, int a, int b ) {
if ( a == 0 ) return psum[b];
return psum[b] - psum[a - 1];
}
int main( int argc, char **argv ) {
vector<int> A;
A.push_back(10); // 0
A.push_back(9); // 1
A.push_back(6); // 2 <--
A.push_back(7); // 3
A.push_back(6); // 4
A.push_back(2); // 5 <--
A.push_back(4); // 6
A.push_back(5); // 7
A.push_back(1); // 8
A.push_back(8); // 9
vector<int> psum = partialSum( A );
int ret = rangeSum( psum, 2, 5 ); // (6+7+6+2) = 21
printf( "%d\n", ret );
}- 2D 부분합을 구하는 코드
- $P[y,x] = \sum_{i=0}^{y}\sum_{j=0}^{x} A[i,j]$
- $\text{sum}(y_1,x_1,y_2,x_2) = P[y_2,x_2] - P[y_2,x_1-1]-P[y_1-1,x_2] + P[y_1-1, x_1-1]$
더보기
#include <bits/stdc++.h>
using namespace std;
int gridSum( const vector<vector<int>>& psum, int y1, int x1, int y2, int x2 ) {
return psum[y2][x2] - psum[y1 - 1][x2] - psum[y2][x1 - 1] + psum[y1 - 1][x1 - 1];
}
int main() {
int n = 8;
vector<vector<int>> A(n, vector<int>(n));
vector<vector<int>> psum(n, vector<int>(n));
for (int i = 0, value = 1; i < n; i++) {
for (int j = 0; j < n; j++, value++) {
A[i][j] = value;
psum[i][j] = A[i][j]
+ (i > 0 ? psum[i - 1][j] : 0)
+ (j > 0 ? psum[i][j - 1] : 0)
- (i > 0 && j > 0 ? psum[i - 1][j - 1] : 0);
}
}
// (1,1)부터 (4,4)까지의 부분합 출력
printf("%d\n", gridSum(psum, 1, 1, 4, 4)); // 376
}- 부분합을 사용하여 분산을 구하는 코드
- $var = \frac{1}{b-a+1} \cdot \sum_{i=a}^{b} (A[i] - m)^2$
- $\quad \ \ = \frac{1}{b-a+1} \cdot \sum_{i=a}^{b}(A[i]^2 - 2A[i]\cdot m + m^2)$
- $\quad \ \ = \frac{1}{b-a+1} \cdot \Big( \sum_{i=a}^{b}A[i]^2 - 2m\cdot \sum_{i=a}^{b}A[i] + (b-a+1)m^2 \Big)$
더보기
#include <bits/stdc++.h>
using namespace std;
vector<int> partialSum( const vector<int>& A ) {
vector<int> ret( A.size() );
ret[0] = A[0];
for ( int i = 1; i < A.size(); i++ ) {
ret[i] = ret[i - 1] + A[i];
}
return ret;
}
int rangeSum( const vector<int>& psum, int a, int b ) {
if ( a == 0 ) return psum[b];
return psum[b] - psum[a - 1];
}
double variance( const vector<int>& sqpsum,
const vector<int>& psum, int a, int b ) {
double tot = b - a + 1;
double mean = rangeSum( psum, a, b ) / tot;
double ret = rangeSum( sqpsum, a, b ) - 2 * mean * rangeSum( psum, a, b ) + tot * mean * mean;
return ret / tot;
}
int main() {
vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> psum = partialSum(data);
vector<int> sqdata(data.size());
for (int i = 0; i < data.size(); i++) {
sqdata[i] = data[i] * data[i];
}
vector<int> sqpsum = partialSum(sqdata);
// 구간 [a, b]의 분산 계산
int a = 4, b = 6;
printf("%lf\n", variance(sqpsum, psum, a, b)); // 0.6666
}
Modulo operation
- Mod 연산(%)은 나머지를 구하는 연산으로 다음과 같은 동치 관계가 성립한다
- (a + b) % MOD = ((a % MOD) + (b % MOD)) % MOD
- (a + b + c) % MOD = ((a % MOD) + (b % MOD) + (c % MOD)) % MOD
Base conversion
- A진법을 10진법으로 변환하는 코드 (Horner's method 사용)
- result = (((0*A + digit1) * A + digit2) * A + digit3) * A + ...
- A: base
더보기
int main() {
int A;
char S[100];
scanf("%d %s", &A, S);
int ret = 0;
for(int i=0; S[i]; i++) {
if(S[i] < 'A') ret = ret * A + (S[i] - '0');
else ret = ret * A + (S[i] - 'A' + 10);
}
printf("%d", ret);
}- 10진법을 B진법으로 변환하는 코드 (재귀 함수 사용) (한 글자씩 바로 출력)
더보기
char chr[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
void Get(int ret, int to) {
if(ret < to) {
printf("%c", chr[ret]);
return;
}
Get(ret/to, to);
printf("%c", chr[ret%to]);
}
int main() {
int ret, B;
scanf("%d %d", &ret, &B);
Get(ret, B);
}
std::string
- 문자열을 반복 연산할 때 흔히하는 실수 ($L$은 문자열, $|L|$은 문자열 길이)
- for ( int i = 0; i < 1000000; i++ ) { s = s + 'a'; } : 시간복잡도 $O(|L|^2)$
- for ( int i = 0; i < 1000000; i++ ) { s += 'a'; } : 시간복잡도 $O(|L|)$
더보기
#include <bits/stdc++.h>
using namespace std;
int main( int argc, char **argv ) {
string s;
// 시간복잡도: O(N^2)
// s+'a'라는 객체를 새로 만든 후 이를 s에 대입
for ( int i = 0; i < 1'000'000; i++ ) {
s = s + 'a';
}
// 시간복잡도: O(N)
// += 연산자를 이용하면 시간복잡도가 더해지는 길이에만 영향 받음
for ( int i = 0; i < 1'000'000; i++ ) {
s += 'a';
}
}- 문자열을 특정 구분자(seperator, delimeter) 단위로 나눈 결과를 반환하는 split 함수
더보기
#include <bits/stdc++.h>
using namespace std;
vector<string> split( string& s, string& sep ) {
vector<string> ret;
int pos = 0;
while ( pos < s.size() ) {
int nxt_pos = s.find( sep, pos );
if ( nxt_pos == -1 ) nxt_pos = s.size();
if ( nxt_pos - pos > 0 )
ret.push_back( s.substr( pos, nxt_pos - pos ) );
pos = nxt_pos + sep.size();
}
return ret;
}
int main( int argc, char **argv ) {
string s = "aaaaa,bbbbb ccccc,ddddd.eeeee";
string sep1 = " ";
string sep2 = ",";
string sep3 = ".";
vector<string> sp = split( s, sep2 );
for ( auto s : sp )
cout << s << endl;
}
Problems
Array, vector
Level1 - 개념 문제
- [ JUNGOL 4851 수열, Solution ], [ JUNGOL 2497 수열, Solution1, Solution2 ], [ JUNGOL 3123 키로거, Solution ]
- [ ALGOSPOT 조세푸스 문제(JOSEPHUS), Solution ]
Linked list
Level1 - 개념 문제
- [ BOJ 1406 에디터, Solution1, Solution2 ], [ BOJ 5397 키로거, Solution ]
Stack
Level1 - 개념 문제
- [ BOJ 10828 스택, Solution ], [ BOJ 9093 단어 뒤집기, Solution ], [ BOJ 17298 오큰수, Solution ], [ BOJ 4949 균형 잡힌 세상, Solution1, Solution2 ]
- [ ALGOSPOT 짝이 맞지 않는 괄호(BRAKETS2), Solution ]
Queue
Level1 - 개념 문제
- [ BOJ 10845 큐, Solution ]
- [ ALGOSPOT 외계 신호 분석(ITES), Solution ]
Deque
Level1 - 개념 문제
- [ BOJ 10866 덱, Solution ]
Priority queue
Level1 - 개념 문제
- [ BOJ 11286 절대값 힙, Solution ], [ BOJ 1715 카드 정렬하기, Solution ]
- [ JUNGOL 4697 질의1, Solution ], [ JUNGOL 4876 질의+, Solution ], [ JUNGOL 3240 회원 참여도 분석1, Solution ], [ JUNGOL 4892 우선순위큐가 3개, Solution ], [ JUNGOL 4944 두부장수2, Solution ]
- [ ALGOSPOT 변화하는 중간값 (RUNNINGMEDIAN), Solution ]
Tree
Level1 - 개념 문제
- [ BOJ 1991 트리순회, Solution ], [ BOJ 11725 트리의 부모 찾기, Solution ]
- [ ALGOSPOT 트리 순회 순서 변경(TRAVERSAL), Solution ]
Level2 - 발전 문제
Binary search tree (set, map)
Level1 - 개념 문제
- [ BOJ 7662 이중 우선순위 큐, Solution ], [ BOJ 1202 보석 도둑, Solution ]
- [ JUNGOL 4918 두부장수1, Solution ]
- [ ALGOSPOT 삽입 정렬 뒤집기(INSERTION), Solution ]
Level2 - 발전 문제
Hash
Level1 - 개념 문제
- [ BOJ 7785 회사에 있는 사람, Solution ], [ BOJ 1620 나는야 포켓몬 마스터 이다솜, Solution ]
- [ JUNGOL 4853 문자열 별칭, Solution ],[ JUNGOL 4854 땅 점령 게임, Solution ], [ JUNGOL 5393 도시와주, Solution ]
Level2 - 발전 문제
Union-find
Level1 - 개념 문제
- [ BOJ 1717 집합의 표현, Solution ], [ BOJ 7511 소셜 네트워킹 어플리케이션, Solution ]
- [ JUNGOL 1863 종교, Solution1, Solution2 ], [ JUNGOL 4779 친구 네트워크, Solution ]
- [ ALGOSPOT 에디터 전쟁(EDITORWARS), Solution ]
Level2 - 발전 문제
- [ BOJ 13306 트리, Solution ], [ BOJ 2463 비용, Solution ]
Trie
Level1 - 개념 문제
Level2 - 발전 문제
Basic I/O & Simulation
Level1 - 개념 문제
- [ BOJ 2557 Hello World, Solution ], [ BOJ 11718 그대로 출력하기, Solution1, Solution2 ], [ BOJ 1000 A+B, Solution ], [ BOJ 11720 숫자의 합, Solution ], [ BOJ 10953 A+B-6, Solution ], [ BOJ 2741 N찍기, Solution ], [ BOJ 2739 구구단, Solution ], [ BOJ 1924 2007년, Solution ], [ BOJ 10818 최소, 최대, Solution ], [ BOJ 4101 크냐?, Solution ], [ BOJ 10871 X보다 작은 수, Solution ], [ BOJ 10808 알파벳 개수, Solution ], [ BOJ 11723 집합, Solution1, Solution2 ], [ BOJ 17413 단어 뒤집기2, Solution ], [ BOJ 17413 단어 뒤집기2, Solution ], [ BOJ 10824 네 수, Solution ],
- [ JUNGOL 3574 수식계산기1, Solution ], [ JUNGOL 1105 수식계산기2, Solution ], [ JUNGOL 4710 문자열 넘버링, Solution ]
Level2 - 발전 문제
- [ BOJ 2658 직각이등변삼각형찾기, Solution ]
- [ JUNGOL 1374 긴 자리 덧셈 뺄셈, Solution1, Solution2, Solution3, Solution4]
String
Level1 - 개념 문제
- [ BOJ 1543 문서 검색, Solution ], [ BOJ 2941 크로아티아 알파벳, Solution ],
- [ JUNGOL 4913 문자열 검색, Solution ]
Bit-wise operation
Level1 - 개념 문제
- [ BOJ 14391 종이조각, Solution ],[ BOJ 11576 Base Conversion, Solution ], [ BOJ 11723 집합, Solution3 ], [ BOJ 1497 기타콘서트, Solution ]
- [ JUNGOL 1419 엔디안, Solution ], [ JUNGOL 3293 비트연산 1, Solution ], [ JUNGOL 1239 비밀편지, Solution ], [ JUNGOL 3112 보안시스템, Solution ]
Level2 - 발전 문제
Brute force
Level1 - 개념 문제
- [ BOJ 18111 마인크래프트, Solution ],[ BOJ 2309 일곱난쟁이, Solution ], [ BOJ 3085 사탕게임, Solution ], [ BOJ 14889 스타트와 링크, Solution ], [ BOJ 15661 링크와 스타트, Solution ]
- [ JUNGOL 1733 오목, Solution ]
- [ ALGOSPOT 게임판 덮기(BOARDCOVER), Solution ]
Level2 - 발전 문제
Math
Level1 - 개념 문제
- [ BOJ 7571 점 모으기, Solution ], [ BOJ 10158 개미, Solution ], [ BOJ 2477 참외밭, Solution ], [ BOJ 2527 직사각형, Solution ], [ BOJ 2503 숫자야구, Solution ], [ BOJ 10430 나머지, Solution ], [ BOJ 10972 다음순열, Solution1, Solution2 ], [ BOJ 10973 이전순열, Solution ], [ BOJ 10974 모든순열, Solution ], [ BOJ 10819 차이를최대로, Solution ], [ BOJ 10971 외판원순회2, Solution ], [ BOJ 11005 진법변환2, Solution ], [ BOJ 2745 진법변환, Solution ], [ BOJ 1373 2진수8진수, Solution ], [ BOJ 1212 8진수2진수, Solution ], [ BOJ 10872 팩토리얼, Solution ], [ BOJ 1978 소수 찾기, Solution ], [ BOJ 1929 소수구하기, Solution ], [ BOJ 2609 최대공약수와 최소공배수, Solution ], [ BOJ 9613 GCD합, Solution ], [ BOJ 6603 로또, Solution ], [ BOJ 11653 소인수분해, Solution ], [ BOJ 11050 이항계수1, Solution ], [ BOJ 11051 이항계수2, Solution ], [ BOJ 1550 16진수, Solution ]
- [ JUNGOL 3106 진법변환, Solution ], [ JUNGOL 3135 const 구간의 합 구하기 1D, Solution ], [ JUNGOL 3136 const 구간의 합 구하기 2D, Solution ], [ JUNGOL 1274 2진수를 10진수로, Solution ], [ JUNGOL 2568 직사각형, Solution ]
Level2 - 발전 문제
- [ BOJ 6064 카잉 달력, Solution ],[ BOJ 10827 a^b, Solution ]
- [ JUNGOL 4692 눈 내리는 겨울밤, Solution ], [ JUNGOL 3109 숫자야구2, Solution ]
- [ ALGOSPOT 비밀번호 486(PASS486), Solution1, Solution2 ], [ ALGOSPOT 마법의 약(POTION), Solution1, Solution2 ], [ ALGOSPOT 크리스마스 인형(CHRISTMAS), Solution ]
Recursion
Level1 - 개념 문제
- [ BOJ 1629 곱셈, Solution ], [ BOJ 11729 하노이 탑 이동 순서, Solution ]
- [ JUNGOL 1459 숫자고르기, Solution ]
Backtracking
Level1 - 개념 문제
- [ BOJ 1182 부분수열의 합, Solution ], [ BOJ 13023 ABCDE, Solution ], [ BOJ 15649 N과M (1), Solution ], [ BOJ 9663 N-Queen, Solution ]
- [ JUNGOL 1169 주사위 던저기1, Solution ], [ JUNGOL 1127 맛있는 음식(PERKET), Solution ], [ JUNGOL 1027 좋은수열, Solution ], [ JUNGOL 1175 주사위던지기2, Solution ], [ JUNGOL 1824 스도쿠, Solution ]
- [ ALGOSPOT 피크닉(PICNIC), Solution ]
Two pointers
Level1 - 개념 문제
- [ BOJ 2467 용액, Solution ], [ BOJ 2230 수 고르기, Solution ] , [ BOJ 1806 부분 합, Solution ]
DFS
Level 1 - 개념 문제
- [ BOJ 11724 연결요소의 개수, Solution ], [ BOJ 1707 이분그래프 , Solution ]
- [ JUNGOL 5436 연결요소 개수세기 , Solution ]
- [ ALGOSPOT 단어 제한 끝말잇기(WORDCHAIN), Solution ], [ ALGOSPOT 고대어 사전(DICTIONARY), Solution ], [ ALGOSPOT 감시 카메라 설치(GALLERY), Solution ]
Level2 - 발전 문제
BFS
Level 1 - 개념 문제
- [ BOJ 2178 미로탐색, Solution1, Solution2 ], [ BOJ 4963 섬의개수, Solution ], [ BOJ 1260 DFS와 BFS, Solution ], [ BOJ 14501 퇴사, Solution1, Solution2] , [ BOJ 7576 토마토, Solution ], [ BOJ 1926 그림, Solution ], [ BOJ 12906 새로운 하노이탑, Solution ], [ BOJ 14502 연구소, Solution ]
- [ JUNGOL 1078 저글링방사능오염, Solution ], [ JUNGOL 1462 보물섬, Solution ], [ JUNGOL 2606 토마토(초), Solution ], [ JUNGOL 3640 잡기 놀이(catch the cow), Solution ], [ JUNGOL 2261 경로 찾기, Solution ], [ JUNGOL 1082 화염에서탈출, Solution ], [ JUNGOL 1111 등산로 찾기, Solution ], [ JUNGOL 2578 버스 갈아타기, Solution ], [ JUNGOL 4189 장기2, Solution ], [ JUNGOL 1131 위성사진, Solution ]
- [ ALGOSPOT Sorting Game (SORTGAME), Solution ],[ ALGOSPOT 하노이의 네 탑 (HANOI4), Solution ]
Level2 - 발전 문제
- [ BOJ 2452 그리드 게임, Solution ], [ BOJ 4179 불!, Solution ], [ BOJ 1697 숨바꼭질, Solution ]
- [ JUNGOL 2058 고돌이 고소미, Solution ], [ JUNGOL 1006 로봇, Solution1 ]
- [ ALGOSPOT 어린이날(CHILDRENDAY), Solution ]
Binary search
Level1 - 개념 문제
- [ BOJ 1920 수 찾기, Solution ], [ BOJ 2110 공유기 설치, Solution ]
- [ JUNGOL 3517 이진탐색, Solution ], [ JUNGOL 1240 제곱근, Solution ]
- [ ALGOSPOT 승률 올리기(RATIO), Solution ]
Level2 - 발전 문제
- [ BOJ 10816 숫자 카드2, Solution1, Solution2 ], [ BOJ 18870 좌표 압축, Solution1, Solution2 ], [ BOJ 2295 세 수의 합, Solution ]
Ternary search
Level2 - 발전 문제
Parametric search
Level1 - 개념 문제
- [ BOJ 1654 랜선 자르기, Solution ]
- [ ALGOSPOT 남극 기지(ARCTIC), Solution ],[ ALGOSPOT DARPA Grand Challenge(DARPA), Solution ], [ ALGOSPOT 캐나다 여행(CANADATRIP), Solution ]
Level2 - 발전 문제
Sort
Level1 - 개념 문제
- [ BOJ 2751 수 정렬하기 2, Solution ], [ BOJ 15688 수 정렬하기 5, Solution ]
- [ JUNGOL 3339 계수정렬(Counting Sort), Solution ], [ JUNGOL 2082 힙정렬2, Solution ], [ JUNGOL 3519 병합정렬, Solution ]
Level2 - 발전 문제
- [ BOJ 7452 합이 0인 네 정수, Solution ], [ BOJ 11652 카드, Solution ]
- [ JUNGOL 3120 기수정렬(Radix Sort), Solution ]
Topological sort
Level1 - 개념 문제
- [ BOJ 2252 줄 세우기, Solution ]
Dynamic programming
Level1 - 개념 문제
- [ BOJ 2193 이친수, Solution ],[ BOJ 9095 123더하기, Solution ], [ BOJ 1463 1로 만들기, Solution ], [ BOJ 12852 1로 만들기 2, Solution ], [ BOJ 2579 계단 오르기, Solution ], [ BOJ 1149 RGB거리, Solution ], [ BOJ 11726 2xN 타일링, Solution ], [ BOJ 11659 구간 합 구하기 4, Solution ],[ BOJ 11053 가장 긴 증가하는 부분수열, Solution ], [ BOJ 11054 가장 긴 바이토닉 부분수열, Solution ], [ BOJ 11055 가장 큰 증가하는 부분수열, Solution ], [ BOJ 2225 합분해, Solution ],
- [ JUNGOL 1411 두 줄로 타일깔기, Solution ],[ JUNGOL 1520 계단 오르기, Solution ], [ JUNGOL 2000 동전 교환, Solution ], [ JUNGOL 3112 보안시스템, Solution ]
- [ ALGOSPOT 외발 뛰기(JUMPGAME), Solution ], [ ALGOSPOT 삼각형 위의 최대 경로(TRIANGLEPATH), Solution ], [ ALGOSPOT 최대 부분 증가 수열(LIS), Solution ], [ ALGOSPOT 합친 LIS(JLIS), Solution ], [ ALGOSPOT 원주율 외우기(PI), Solution ], [ ALGOSPOT 타일링(TILING2), Solution ], [ ALGOSPOT 달팽이(SNAIL), Solution ], [ ALGOSPOT 비대칭 타일링(ASYMTILING), Solution1, Solution2 ]
Level2 - 발전 문제
- [ BOJ 15990 123더하기 5, Solution ]
- [ JUNGOL 2063 택배, Solution ]
- [ ALGOSPOT 와일드카드(WILDCARD), Solution ], [ ALGOSPOT 양자화(QUANTIZE), Solution ], [ ALGOSPOT 삼각형 위의 최대 경로 개수 세기(TRIPATHCNT), Solution ], [ ALGOSPOT 폴로오미노(POLY), Solution ], [ ALGOSPOT 두니발 박사의 탈옥(NUMB3R), Solution1, Solution2 ]
Greedy
Level1 - 개념 문제
- [ BOJ 11047 동전0, Solution ], [ BOJ 1931 회의실 배정, Solution ], [ BOJ 2217 로프, Solution ], [ BOJ 1026 보물, Solution ]
- [ JUNGOL 1816 외양간, Solution ],[ JUNGOL 1828 냉장고, Solution ], [ JUNGOL 1183 동전자판기(하), Solution1, Solution2, Solution3 ]
- [ ALGOSPOT 출전 순서 정하기(MATCHORDER), Solution ], [ ALGOSPOT 도시락 데우기(LUNCHBOX), Solution ]
Level2 - 발전 문제
Divide and conquer
Level1 - 개념 문제
Level2 - 발전 문제
Sqrt decomposition
Level1 - 개념 문제
- [ JUNGOL 1726 구간의 최대값1, Solution1 ], [ JUNGOL 2469 줄세우기, Solution1 ], [ JUNGOL 7035 등수 조작, Solution ], [ JUNGOL 3238 구간의 최대값2, Solution ]
Segment tree
Level1 - 개념 문제
- [ JUNGOL 1726 구간의 최대값1, Solution2, Solution3 ], [ JUNGOL 2469 줄세우기, Solution2 ], [ JUNGOL 3297 구간의합1, Solution ]
- [ ALGOSPOT 등산로(MORDOR), Solution ], [ ALGOSPOT 삽입 정렬 시간 재기(MEASURETIME), Solution ]
Level2 - 발전 문제
Minimum spanning tree (Prim, Kruskal)
Level1 - 개념 문제
- [ BOJ 1197 최소 스패닝 트리, Solution1(Prim), Solution2(Kruskal) ]
- [ JUNGOL 1060 최소비용신장트리, Solution ]
- [ ALGOSPOT 근거리 네트워크(LAN), Solution ]
Level2 - 발전 문제
Floyd-Warshall
Level1 - 개념 문제
- [ BOJ 11404 플로이드, Solution ], [ BOJ 11780 플로이드2, Solution ], [ BOJ 13168 내일로 여행, Solution ]
- [ ALGOSPOT 음주 운전 단속(DRUNKEN), Solution ], [ ALGOSPOT 선거 공약(PROMISES), Solution ]
Dijkstra
Level1 - 개념 문제
- [ BOJ 1753 최단경로, Solution ], [ BOJ 11779 최소비용 구하기2, Solution ]
- [ JUNGOL 2097 지하철, Solution ], [ JUNGOL 2109 꿀꿀이축제, Solution ], [ JUNGOL 3118 최단경로2, Solution ],
- [ ALGOSPOT 신호 라우팅(ROUTING), Solution ],[ ALGOSPOT 소방차(FIRETRUCKS), Solution ]
Level2 - 발전 문제
- [ JUNGOL 8339 길 정비하기, Solution ], [ JUNGOL 1006 로봇, Solution2 ]
- [ ALGOSPOT 철인 N종 경기(NTHLON), Solution ]
Line sweeping
Bellman-Ford
Level1 - 개념 문제
KMP
Level1 - 개념 문제
- [ BOJ 16916 부분 문자열, Solution ]
- [ ALGOSPOT 작명하기(NAMING), Solution ], [ ALGOSPOT 재하의 금고(JAEHASAFE), Solution ]
Level2 - 발전 문제
Suffix array (Manber-Myers)
Level1 - 개념 문제
Network flow (Ford-Fulkerson)
Level1 - 개념 문제
Bipartite matching
Level1 - 개념 문제
Level2 - 발전 문제
Computational geometry
Level1 - 개념 문제
Level2 - 발전 문제
References
Tips
[1] (Blog) 알고리즘 문제풀이(PS) 시작하기 - plzrun
[2] (Blog) 내가 문제풀이를 연습하는 방법 - koosaga
[3] (Blog) 코드포스 블루, 퍼플 달성 후기 및 일지 & 공부법 - Rebro
[4] (Blog) PS를 공부하는 방법 (How to study Problem Solving?) - subinium
[5] (Blog) 개인이 생각하는 알고리즘(PS/CP) 공부 유형 및 보완법 - subinium
[6] (Blog) 코드포스 오렌지 찍었습니다 - Sendipity__
[7] (Site) C++ 유용한 기능들 - dohoon
[9] (Site) Algorithm in A..Z - Minimum Vertex Cover - 개발일지
Sites
[1] (Site) Baejoon Online Judge
[5] (Book) 알고리즘 문제 해결 전략 - 구종만 저
Lectures
[1] (Blog) BaaaaaaaarkingDog의 강좌/실전 알고리즘
[2] (Youtube) BaaaaaaaarkingDog의 강좌/실전 알고리즘
'Coding' 카테고리의 다른 글
| Modern C++ 개념 정리 (STL, Design Pattern, Concurrent, Template Programming) (0) | 2024.06.27 |
|---|---|
| [PS] 알고리즘 문제 풀이 - 유용한 팁 및 문제 리스트 정리 (0) | 2024.03.08 |
| [PS] 자료구조와 알고리즘 개념 정리 (Algorithm) Part 2 (1) | 2024.03.08 |
| [PS] 자료구조와 알고리즘 개념 정리 (Data Structure) Part 1 (1) | 2024.03.07 |
| VPython 예제10 - 2자유도 반한정계 스프링-질량 애니메이션 (0) | 2022.01.11 |
