robustflame의 블로그

Modular Arithmetic 정수 \(a, b, m\)에 대하여, \(m \ | \ (a-b)\) 일때, \(a\)는 법 \(m\)에 대하여 \(b\)와 합동이다(\(a\) is congruent to \(b\) modulo \(m\)). 이때, 기호로 \(a\equiv b\pmod m\)이라고 쓴다. 여기서 \(m\)을 합동의 법(modular)이라고 한다. 수학적인 정의는 이렇고, 간단하게 말하면 '\(a\)와 \(b\)를 \(m\)으로 나누었을 때, 그 둘의 나머지가 같다'라고 생각하면 된다. 모듈라 연산에서의 덧셈, 뺄셈, 곱셈은 다음과 같은 성질들이 성립한다. \((a+b) \pmod m \equiv ((a \pmod m) + (b \pmod m)) \pmod m\) \((a-b) \pmo..

n개의 원소들이 저장된 배열에서 특정 원소 x를 찾는다고 할때, 여러 가지 탐색(Search) 방법이 존재한다. Linear Search 배열의 첫 번째 원소부터 차례대로 하나씩 x와 같은지 비교하는 방식으로 가장 간단한다. 시간복잡도는 \(O(n)\) 이다. 구현int search(int arr[], int n, int x) { for (int i = 0; i < n; i++) { if (arr[i] == x) return i; } return -1; } Binary Search 일단 배열의 원소들을 정렬한다. 그 후 반복적으로 배열을 반으로 나누어 x가 위치한 곳을 좁혀나가는 방식이다. 상당히 유용하게 사용되는 탐색 방법이다. 정렬하는데 \(O(nlog_2n)\)의 시간이 걸리지만, 탐색하는데에는 \..

Counting Sort 계수 정렬(Counting Sort)은 총 \(n\)개의 원소가 1에서 \(k\)의 범위에 있을 때, 선형 시간복잡도 \(O(n+k)\)를 가지는 빠른 정렬 방법이다. \(O(nlog_2n)\)의 시간복잡도를 가지는 Merge Sort, Heap Sort, Quick-Sort 같은 정렬법보다도 빠르게 동작한다. 단, 원소의 범위가 1에서 \(n^2\)이라면 \(O(n^2)\)의 시간복잡도를 가지게 되는 제약이 있다. 구현#include using namespace std; void countSort(char arr[], int range) { char newArr[strlen(arr)]; int cnt[range + 1] = { 0 }; for (int i = 0; arr[i];..

Suffix Array 접미사 배열(suffix array)는 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해둔 것으로, 보통 각 접미사의 시작 위치를 저장하는 정수 배열로 구현된다. 길이가 \(n\)인 문자열의 접미사 배열을 만드는 가장 빠른 알고리즘은 \(O(N)\)만에 접미사 배열을 만든다고 한다. 하지만 프로그래밍 대회에서는 이 복잡한 알고리즘을 직접 구현하여 사용하기에는 어려워 보통 그 대안으로 적당히 구현하기 쉽고, 적당히 빠른 알고리즘을 대신 사용한다. 접미사 배열을 만드는 \(O(N{log_2}^2N)\) 알고리즘은 각 접미사를 첫 한 글자로 정렬하고, 그 다음에 두 글자, 네 글자.. 로 \(log_2N\) 번 정렬하는 것이다. 각 접미사들이 서로 완전히 다른 문자열들이 아니라 두 접미..

트리의 지름 (Diameter of Tree) 트리에서 가장 멀리 떨어진 두 노드 사이의 길이를 트리의 지름이라고 한다. 이 트리의 지름을 가장 간단하게 구하는 방법은 다음과 같다. 트리의 임의의 한 노드 \(u\)에서 가장 멀리 있는 노드 \(v\)를 찾는다.\(v\)에서 가장 멀리 있는 노드 \(w\)를 찾는다.\(v\) ~ \(w\)가 트리의 지름이 된다. 위의 방법에서 특정 노드에서 가장 멀리 있는 노드는 DFS나 BFS를 사용하면 쉽게 찾을 수 있다. 증명은 귀류법을 이용하여 \(v\) ~ \(w\)가 아닌 다른 두 노드 \(a\) ~ \(b\)를 트리의 지름이라고 가정한 후, 이것이 모순이 됨을 보이면 된다. (자세한 내용은 여기를 참고하자) 예제BOJ 1967 트리의 지름 BOJ 2132 나..

Knuth-Morris-Pratt Pattern Searching 긴 문자열 \(A\)(길이 \(M\))에서 특정 패턴 문자열 \(B\)(길이 \(N\))가 나타나는 모든 위치를 \(O(M + N)\) 시간에 찾아내는 알고리즘이다. 구현#include using namespace std; // 문자열 A에서 문자열 B와 일치하는 위치를 모두 찾는다. vector KMPSearch(const string& A, const string& B) { int AN = A.length(), BN = B.length(); // 부분 일치 테이블 생성 vector pi(BN, 0); int matched = 0; for (int i = 1; i 0 && B[i] !..