홀의 정리는 홀의 결혼 정리라고도 불리우는 정리로, 이분 매칭에서 유용하게 쓰이거나 다른 그래프 이론의 다양한 정리들의 증명에 도움이 된다. 홀의 정리를 증명해 보았다. 그냥 검색해봐도 되지만, 홀의 정리 문제 상황과 유사한 구조에서 비슷한 논리를 이끌어내는 문제가 존재하기 때문에 이를 대비하기 위해서 별도의 특수한 도구 없이 증명하는 것을 목표로 잡았다. Theorem: $($모든 $S\subset X$에 대해 $|S|\le |N(S)|$를 만족$) \iff (\exists X$에서 $Y$로의 완전 매칭$)$ $[\Leftarrow]$는 자명한 명제이므로, $[\Rightarrow]$만 증명한다. 좌변의 조건을 "홀의 조건"이라고 부르자. 수학적 귀납법으로 접근해 보자. $|X|$의 크기에 대한 귀납법..

이 글에서는 구간 트리(segment tree), 펜윅 트리(fenwick tree), 느리게 갱신되는 구간 트리(segment tree with lazy propagation)들이 성립하는 조건을 알아볼 것이다. 다만, 이 글에는 한계가 존재한다. 구간 트리를 하나의 Black-Box(기능은 알지만 작동 원리를 이해할 수 없는 복잡한 기계 장치나 시스템, 물체)로 바라보기 때문에 직사각형들의 합집합의 넓이를 구하는 문제와 같이 구간 트리의 구조를 변형시키는 문제에는 이 글의 내용이 적용이 되지 않을 수 있다. 기본 질의응답의 대상인 배열은 $[a_1,a_2,\ldots,a_n]$이다. 배열 속 원소들을 포함하는 집합 $S$, 원소들 간의 이항 연산 $*$, 갱신 함수의 집합 $F$가 있다. 이때, 당연..

이 블로그의 "그래프에 관하여" 시리즈의 첫 번째 카테고리, ❮DFS 트리❯의 개요이다. DFS 트리는 DFS를 응용한 다양한 알고리즘들을 이해하기 위한 좋은 표현법이자 도구이다. 조금 어려운 감이 있지만 꼼꼼히 이해한다면 큰 도움이 될 것이라고 생각한다. DFS 트리/포레스트란? 어떤 연결 그래프에서 DFS 순회하는 과정을 그렸을 때 나타나는 유향 신장 트리(directed spanning tree)를 DFS 트리라고 한다. 당연히 여러 개가 존재할 수 있다. 연결 그래프가 아닐 경우에는 각 연결 컴포넌트마다 DFS 트리를 만들 수 있으니 DFS 포레스트로 확장해서 생각할 수 있다. 유향 그래프일 경우, DFS 트리의 간선들을 네 가지로 분류할 수 있다. 트리 간선(tree edge): DFS 트리에 ..

이 블로그의 "트리에 관하여" 시리즈의 첫 번째 카테고리, ❮Tree DP❯에서 다루는 첫 번째 주제이다. 이 테크닉은 다른 이름으로도 알려져 있다. KOI에 출제된 어떤 유명한 문제의 이름을 딴 것인데, 스포일러가 될 수 있으므로 연습 문제 목차에서 후술 하겠다. Square-order tree DP? 사실 이건 그 자체로 뭔가 해야 하는 테크닉은 아니다. 트리 DP 점화식이 2차원으로 나오고, 전이 과정을 합쳐서 대충 보기에는 $O(n^3)$의 시간 복잡도를 가져야 할 것으로 보이는 후술 할 조건을 만족하는 알고리즘이 사실 $O(n^2)$이라는 더 좋은 시간 복잡도를 갖는다는 사실을 이용하는 테크닉이다. 만족해야 하는 조건은 구한 점화식 $\text{dp}(x,y)$에 대해, $x$가 각 노드를 뜻하..

이 블로그의 "그래프에 관하여" 시리즈의 첫 번째 카테고리, ❮DFS 트리❯에서 다루는 첫 번째 주제이다. 편의를 위해 다음 표현을 정의하자. 정점 $v$의 방문 시작 시각: $s(v)$ 정점 $v$의 방문 종료 시각: $f(v)$ SCC란? 어떤 방향 그래프가 모든 정점에 대해, 다른 모든 정점으로 갈 수 있다면 강하게 결합(strongly connected)되었다고 한다. 모든 방향 그래프는 SCC(strongly connected component; 강결합 컴포넌트)로 나눌 수 있다. SCC란 모든 정점에서 다른 모든 정점으로 갈 수 있는 최대 크기의 정점 집합을 의미한다. 각 SCC를 새로운 정점으로 하고, 그 안의 모든 정점들에서 나가는 간선을 새로운 정점의 간선으로 갖게 하여 컴포넌트 그래프(..

계산기하의 기본 도구들을 소개합니다. 마음가짐 기하 문제는 예외 처리가 적고, 구현이 쉬운 형태의 표현 방법 및 풀이를 이용해야 한다. 그리고 실수 좌표보다는 정수 좌표를 이용해야 한다. 그래서 이 글은 실수를 적극적으로 이용하는 문제는 논외로 한다. 그래서 이중적 의미로 "실수 없는 계산기하"이다. 템플릿 기하를 여행하는 Competitive Programmer를 위한 안내서에서 소개된 편리한 표현 방법을 따른다. 위 글에서 참고한 예외 사항이다: 점이 [1, 2개 / 일직선상 / 위에 존재] 직선, 선분이 [평행 / 일직선상] 중복 존재 점과 벡터 complex을 사용한다. Unspecified Behavior임을 감안하여 몇몇 함수들을 재정의한다. Unspecified Behavior임에도 사용하는..

책 "알고리즘 산책"에서 다음과 같은 내용을 보았다. ...하지만 재귀 호출을 완전히 없애서 함수 호출에 따르는 오버헤드를 피해 보자. 정의 2.1 모든 형식 매개변수를 각각에 상응하는 인자로 사용하는 꼬리 재귀 호출을 순 꼬리 재귀 호출(strictly tail-recursive)이라고 한다. 재귀 호출을 하기 전에 변수의 값을 미리 설정해 주면 순 꼬리 재귀 호출로 고칠 수 있다. int mult_acc3(int r, int n, int a) { if (odd(n)) { r = r+a; if (n == 1) return r; } n = half(n); a = a+a; return mult_acc3(r,n,a); }​ 이제 꼬리 재귀 호출을 while(true) 구문으로 바꾸기만 하면 손쉽게 반복문 형..

*중요: 궁금한건 댓글로 남겨주세요!* int는 32개의 비트의 조합으로 표현된다. signed int의 경우 첫 비트가 부호를 나타내어 $[-2^{31},2^{31})$의 정수를 표현하고, unsigned int의 경우 첫 비트도 일반적인 비트로 사용되어 $[0,2^{32})$의 정수를 표현한다. * 만약 10진수를 2진수로 출력하고 싶다면 cout = 0; --k) cout >k&1); 집합 집합의 표현 정수 $x\in [-2^{31},2^{31})$와 정수 집합 $U=[0,32)$에 대해, $\displaystyle X:=\{k\in U|x\&2^k\neq 0\}$이다. 편의상 $f(x)=X$라고 표기하겠다. 또, $f^{-1}(X)=x$라 하자. 여러가지 집합 $f(0)=\varnothing$, ..