아무 말

https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 들어가며.. 오른쪽은 이 문제의 태그다. 풀고 나서 보니 신기한게 많지만.. 그냥 백트래킹 문제이다. 풀이 우리가 표현해야 하는 공간은 고작 5×5 사이즈이다. 따라서 경우의 수는 고작 \(2^{25} = 33554432\)이므로, 충분히 통과할 수 있다. 그리고 사실 저 만큼의 경우의 수를 탐색하지도 않는다. 탐색을 진행할 때 현재 선택한 칸에서 인접한 칸으로만 방문할 것이며, 임도연 파에 속한 학..

https://www.acmicpc.net/problem/16367 16367번: TV Show Game Your program is to read from standard input. The input starts with a line containing two integers, k and n (3 < k ≤ 5,000, 1 ≤ n ≤ 10,000), where k is the number of lamps and n the number of game participants. Each of the following n lines contains t www.acmicpc.net 관찰 해당 문제에서는 사람들의 추론 결과를 이용하여 모두가 3개 중 2개 이상의 색을 맞출 수 있는지 확인하라고 하고 있다. 이는..

2008년 Google code jam round A에 나왔던 문제이다. 이 문제에서는 매우 정밀한 수의 연산을 요구하기 때문에 double이나 float, Decimal 등을 이용한 연산이 옳은 결과를 내지 못하도록 설계되어 있다. Solution 먼저, \( (3 + \sqrt{5})^{n} \)에 대해서 생각해 보자. \(\sqrt{5}\)가 살짝 거슬린다. 이를 해결하기 위해 \( (3 - \sqrt{5})^{n}\)을 더해준다. 그러면 \(\sqrt{5}\)가 존재하는 모든 항을 없앨 수 있다. 조금 더 자세히 설명하자면, \( (3+\sqrt{5})^{n}+(3-\sqrt{5})^{n}=\sum_{i=0}^{n} (3)^{n-i}(\sqrt{5})^{i}+\sum_{i=0}^{n} (3)^{n..

https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicp..

들어가며.. 다익스트라 알고리즘(Dijkstra's algorithm)을 이용하면 \(O(|E|+|V| \log(|V|))\)에 단일 출발지 최단 경로를 구할 수 있습니다. 만약, 간선의 가중치가 0 혹인 1 뿐이라면 더 빠르게 작동시킬 수 있을까요? 0 - 1 너비 우선 탐색 0 - 1 너비 우선 탐색은 다익스트라 알고리즘과 완전히 같은 아이디어로 작동합니다.(사실 0 - 1 너비 우선 탐색은 다익스트라 알고리즘을 최적화 한 것입니다.) 그저 가중치가 0 혹은 1 밖에 없는지라 priority queue를 사용하지 않을 수 있다는 것이 차별점이라 할 수 있겠습니다. 다익스트라에서 priority queue는 현재 queue에 들어있는 정점 중 시작 점으로 부터 가장 가까운(=현재 구한 최단 경로가 가장..

https://www.acmicpc.net/problem/14426 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 들어가며.. 이 포스팅에서 사용할 풀이는 해당 문제의 정해가 아닐 수 있다. 풀이 먼저, 트라이(Trie)는 문자열을 저장하고 검색하기 위한 자료구조로, 트라이에 저장된 모든 문자열은 만약 서로의 공통 접두사가 있을 때, 해당하는 노드들을 공유한다. 오른쪽의 그림은 트라이를 나타낸 그림이다. 그림을 보면 바로 이..

https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 일단 간단하게 2 개의 수가 있을 때를 생각해보자. Let. \(A,\;B \in \mathcal{N}\), \(A \equiv B \pmod{M} \) \(A \, = A \, - \, \lfloor \frac{A}{M} \rfloor \times M \, + R\) 이므로 (단, \(A \mod \, M \, = \, R\)) \( A \, - \, \lfloor \frac{A}{M} \rfloor \time..

Introduction 트리를 분할하는 방법으로는 대표적으로 Centroid Decomposition과 Heavy-Light Decomposition이 있다. Centroid Decomposition의 경우, 주로 트리에서 분할정복을 위해 이용되며, Heavy-Light Decomposition은 우리가 다루기 더 쉬운 형태인 선형 배열의 형태로 트리를 바꾸어 문제를 해결하기 위하여 사용한다. 이번 포스팅에서는 Heavy-Light Decomposition을 다룬다. Heavy-Light Decomposition Heavy-Light Decomposition(HLD)는 트리의 정점을 여러 경로의 집합으로 나누는 방법이다. HLD를 수행하기 위해서 일단 임의의 정점의 트리의 루트로 잡는다. 이후, 루트에서..

서론 그래프에서의 동형사상을 찾는 문제는 NP이다. 다만, 트리에서의 동형사상은 다항시간에 판정할 수 있다. 이번 포스팅에서는 두 rooted 트리에서의 동형사상을 찾는 알고리즘인 AHU Algorithm [Aho, Hopcroft and Ullman]과 unrooted tree의 동형사상을 찾는 방법을 다룰 것이다. 1. 동형인지 여부를 판정할 트리가 rooted tree 일 때 - AHU algorithm AHU algorithm에서는 트리를 몇 개의 튜플로 해싱하여 두 트리가 같은지 비교한다. 이때, depth 별로 tuple을 하나씩 형성해주어야 한다. 이 tuple을 이루는 항은 AHU algorithm에서는 각 depth별 vertex의 degree들이다. 또, tuple은 항상 정렬된 상태로..

\(O\)-표기 \(O\)-표기는 가장 흔하게 볼 수 있는 점근적 표기법입니다. 간단하게 말해 \(O\)-표기는 함수의 점근적 상한을 결정짓는 표기입니다. \(c g(n)\)이 특정한 상수 \(n_0\)보다 큰 모든 \(n\)에 대해 \(f(n)\)보다 크기만 하다면, \(f(n)\)을 \(O(g(n))\)으로 표기할 수 있습니다. \(O\)-표기가 많이 사용되는 이유 또한 이러한 특성 때문인데, Problem Solving을 할 경우에 특정 문제에 대해 적용한 풀이가 문제에서 주어진 시간제한을 넘어서는지 아닌지를 나타낼 수 있기 때문입니다. \(O\)-표기를 함수의 집합으로 나타내면 아래와 같습니다. \(O(g(n))\ =\ \{ f(n)\) : 모든 \( n \geqslant n_0 \) 에 대해 \..