robustflame의 블로그

문제링크 - https://www.acmicpc.net/problem/1034문제 분류난이도 - 하태그 - 탐색문제 풀이이 문제는 조금 관찰력이 필요한 문제다. 어떤 열의 램프 상태가 서로 다른 두 행은 동시에 켜져있을 수 없다. 즉, 서로 다른 두 행이 동시에 켜져있으려면 최소한 그 열의 램프 상태는 같아야 한다. 모든 열에 대해서 확장하면 어느 두 행이 동시에 켜져있으려면 그 두 행의 램프 상태는 동일해야 한다. 이러한 사실을 깨닫게되면 스위치를 K번 눌러서 어떤 행이 켜질 수 있는지 확인하고, 이와 램프 상태가 동일한 램프들의 수를 세어서 이 문제를 해결할 수 있다. 소스 코드#include #include #include #include using namespace std; typedef long..

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 나..