링크: https://www.acmicpc.net/problem/2887 모든 행성을 터널로 연결할건데, 그 비용의 합이 최소가 되게 만드는 최소 스패닝 트리 문제이다. 문제는 \(N\)이 너무 커서, 행성 사이의 간선을 전부 살피는 건 힘들다는 것이다. 두 행성 A와 B의 거리를 \(min(|x_A - x_B|, |y_A - y_B|, |z_A - z_B|)\) 로 정의했기 때문에 어떤 행성에서 가장 가까울 행성의 후보가 확 줄어든다. 행성 A에서 가장 가까운 행성 B는 \(|x_A - x_B|\)가 최소이거나 \(|y_A - y_B|\)가 최소이거나, \(|z_A - z_B|\)가 최소인 것 3개 중 하나이다. \(x, y, z\)마다 정렬하면 된다.

링크: https://www.acmicpc.net/problem/2718[이전 게시글로부터 글 옮김]2x1 크기의 타일로 4xN 크기의 타일을 채우는 경우의 수를 구하는 문제이다.문제를 작은 문제로 쪼개야하는 데 발상보다는 과정이 쉽게 떠오르지 않아서 해결하는 데 오랜 시간이 걸렸다.2xN 타일 크기의 문제와 똑같이 왼쪽부터 1줄씩 채워나가면서 완성해나간다. 하지만 이 문제는 높이가 4N이기 때문에 1줄을 채울 때 여러 개의 경우가 나온다. [그림 1] 한 줄의 상태를 비트로 표현할 때의 정수 외의 경우(1010 이나 0001 등의 형태)는 나올 수 없다. 왜냐하면 "이전의 줄의 모든 칸은 채워져있다."라는 가정에서 나타나는 상태이기 때문이다. 이 가정이 성립하지 않으면 타일은 채워질 수 없다. [그림 ..

문제링크: https://www.acmicpc.net/problem/9373복도에 센서들이 있고 센서들을 피해 복도를 통과할 수 있는 가장 큰 원의 반지름을 구하는 문제이다. 복도의 너비가 주어지고, 각 센서들의 좌표 x, y와 반지름 r이 주어진다.처음에는 센서와 센서 사이에 존재할 수 있는 원들로 어떻게 MST를 잘 만들면 되지 않을까했는데, 가장 큰 원의 반지름을 구하기가 힘들었다. 하루 정도 계속 틀리고 고민하고를 반복하다 솔루션을 찾아봤다. 솔루션을 보자마자 와 이게 뭐지 싶었다. 이렇게 풀 수도 있구나 신기했다.풀이최소 신장 트리 문제는 맞았고 원과 원 사이의 끼인 원으로 어떻게 하는 것도 맞았다. 근데 최종형태가 이런 식이었다.양쪽 벽을 큰 집합이라고 생각하고 두 집합이 연결될 때까지 MST..

문제 링크 : http://119.201.123.184/30stair/sumofinte/sumofinte.php 정답 코드 중에서 실행 시간이 644ms로 1위다. 이럴 날이 별로 없어서 캡쳐 주륵..문제수열의 길이 N과 질문의 수 Q가 주어지는 데, 둘 다 N, Q sum = L.sum + R.sum

Red Black Tree란, Binary Search Tree의 일종으로 입력 순서에 따라 BST가 한쪽으로 기울어지는(skewed) 걸 막기 위해 스스로 균형을 맞추는(self-balanced) 트리이다. 트리가 skewed하면 연결리스트랑 다를 바 없어서 \(O(N)\)의 시간복잡도를 갖기 때문이다. 균형을 맞춘다는 것은 어떤 노드의 (자신 아래의) 모든 리프까지의 거리가 최대한 같도록 조정한다는 말인데, 균형을 잘 맞추면 트리의 깊이가 \( \log_{2}{N} \)이기 때문에 빠르게 검색할 수 있다. 레드블랙트리는 아래의 규칙을 만족하도록 조정된다. 1. 노드는 레드 혹은 블랙 중의 하나이다. 2. 루트 노드는 블랙이다. 3. 모든 리프 노드는 블랙이다. 4. 레드 노드의 자식노드 양쪽은 언제나..

확장 유클리드 알고리즘(Extended Euclidian Algorithm)은 유클리드 호제법을 확장한 것이다. \(as + bt = gcd(a,b)\)을 만족하는 정수 \(s\), \(t\) 짝을 찾아낼 수 있다. 증명은 생략하고 어떻게 사용하는가를 적어볼까 한다. 초기 조건 \(s_0 = 1, s_1 = 0, ~~t_0 = 0, t_1 = 1, ~~r_0 = a, r_1 = b\) 진행 $$ \begin{align} q_i \leftarrow & \lfloor~r_{i-1}~/~r_i~\rfloor & (i \ge 1)\\ r_i \leftarrow & ~r_{i-2} - r_{i-1} \cdot q_{i-1} & (i \ge 2)\\ s_i \leftarrow & ~s_{i-2} - s_{i-1} ..

​중국인의 나머지 정리(CRT; Chinese Remainder Theorem)연립 합동식의 유일한 해를 찾는 정리이다. 예를 들면서 설명과 함께 전개하는 게 가장 이해하기 쉽다. 개념 이해를 위해 연립 합동식이 2개일 때만 생각해보자.$$ \begin{cases} x \equiv 3 ~ (mod~ 5)~\dashrightarrow~ (a) \\ x \equiv 4~ (mod~ 7)~\dashrightarrow ~(b) \end{cases} $$위 두 합동식 (a), (b)를 모두 만족하는 어떤 정수 \(x\)는 어떻게 찾을 수 있을까?어떤 수 \(x\)는 위 두 합동식을 모두 만족하기 위해 (a), (b)의 해를 각각 \(A_1\), \(A_2\)라고 하면 아래의 형태가 된다.$$ x \equiv A_..

[이전 블로그로부터 글 옮김] GCJ 링크 : https://code.google.com/codejam/contest/6254486/dashboardProblem A - Counting SheepN이 주어지면 N, 2N, ..., kN까지 진행했을 때, 0~9을 모두 사용하게 되는 시점 k에서의 kN을 구하는 문제이다. 문제 그대로 시뮬레이션하면 된다. large set에서 범위가 \(0 \le N \le 10^6\) 이지만 0~9가 모두 나오게 되는건 최대 100배이므로 int 범위로 충분히 표현할 수 있다. Problem B - Revenge of the Pancakes앞에서부터 k번째까지를 뒤집을 수 있다. (0~k 를 k~0으로 뒤집고 모든 -를 +로 뒤집는다. +-- 를 전부 뒤집는다면 ++- ..