본문 바로가기

전체 글

(18)
Patience Sort Patience sort는 다음과 같이 작동하는 정렬 알고리즘이다. (설명이 쉽지 않다. 더 아래에 있는 코드를 보는 것을 추천한다.) 작동 과정 $n$ 장의 카드 $C_1, C_2, \cdots, C_n$이 있고, 각 카드에 수가 적혀 있다고 할 때, 우리는 다음과 같은 과정을 수행하며, 각 카드를 차례로 카드 더미에 추가한다. (카드 더미를 스택이라 생각하면 좋다. 카드 더미들은 일렬로 나열되어 있다.) 초기에는 아무 카드 더미가 없다. 따라서, 처음에는 카드 1장으로 이루어진 카드 더미를 하나 만들고, 해당 더미에 $C_1$을 추가한다. 이후, $C_2$부터 차례로 카드 더미에 다음의 규칙을 따라 추가한다. 맨 위의 수가 자신보다 크거나 같은 카드 더미가 있다면, 그러한 카드 더미 중 가장 왼쪽의 ..
[수문연 세미나] Matroids and Greedy Algorithms 본인이 소속되어 있는 동아리인 "KAIST 수학문제연구회"에서 작년에 진행한 세미나의 발표자료이다.
Bijection from $2^\mathbb{N}$ to $\mathbb{R}$ 이 글에서는 $2^\mathbb{N}$과 $\mathbb{R}$의 크기가 같음을 Cantor-Bernstein 정리 없이 bijection을 직접 construct 하여 보인다. 1) 먼저, $f_1 : 2^\mathbb{N} \to \{0, 1\}^\mathbb{N}$은 다음과 같이 자연스럽게 잡아줄 수 있다: $S \subset \mathbb{N}$에 대해 $f(S)$는 $S$의 원소 번째 인덱스는 $1$, 나머지 인덱스는 $0$인 binary sequence 2) 이후, $f_2 : \{0, 1\} ^ \mathbb{N} \to [0, 1)$을 구성한다. 먼저, $\{0, 1\} ^ \mathbb{N}$을 다음의 세 집합으로 분할할 수 있습니다. $A_0$: 포함하는 $0$의 개수가 유한한 bina..