leejseo의 블로그

합동인 볼록 다각형으로 평면을 빈틈없이 채우는걸 테셀레이션이라고 합니다. 이때, 서로 다른 두 면은 변을 공유하지 않거나, 정확히 하나의 변을 "완전히" 공유해야 합니다. 예를 들어, 아래는 볼록 오각형을 이용한 테셀레이션입니다. 그렇다면, 볼록 $n$각형으로 평면을 테셀레이션 하는건 언제 가능할까요? $n = 3, 4, 6$일 때는 정 $n$각형을 활용하면 됩니다. $n = 5$인 경우에는 위의 그림과 같이 하면 됩니다. 이 글에서는 $n \ge 7$일 때, 볼록 $n$각형으로 테셀레이션을 하는 것이 불가능함을 보일 것입니다. 먼저, 볼록 $n$각형을 활용한 테셀레이션이 주어져 있다고 합시다. 일반성을 잃지 않고, 각 면의 넓이가 $1$이라고 가정할 수 있습니다. 이들은 정점과 변, 그리고 면 모두가 ..

관심을 가지고 있는 조합기하 분야의 전형적인 극단(Extremal) 문제들을 모아보았다. 전부 open problem이다. 아직 잘 정리된 글은 아니다. 1. Happy Ending Problem Problem. 평면 상의 점들의 집합 $P$가 general position 에 있다. 이는, $P$의 어느 세 점도 하나의 직선 위에 있지 않음을 의미한다. 이 때, $P$가 볼록 $n(\ge 3)$각형이 포함함이 보장되는 $|P|$의 최솟값을 구하여라. 이 문제에서 $|P|$의 최솟값을 $ES(n)$이라 표기하자. 작은 $n$에 대해 $ES(n)$의 값을 구해보자. $ES(3) = 3$이고, $ES(4) = 5$, $ES(5) = 9$이다. 사실, $ES(4)$와 $ES(5)$의 값 또한 자명한 결과는 아..

제 1회 UNIST 알고리즘 프로그래밍 경시대회 Uni-CODE에서 출제, 검수 및 운영의 일부분에 관여하였습니다. 문제들은 다음 링크에서 확인할 수 있고, 대회를 개최하는 과정에서 느낀점과 문제에 대한 풀이를 간략히 적어보았습니다. (Update: 풀이 파일도 추가했습니다.) https://www.acmicpc.net/category/detail/2105 Solution 문제들에 대한 풀이를 간략히 적어봤습니다. A. 커맨드 박원님이 출제하신 문제로, 가장 쉬운 문제입니다. 문자열을 입력 받고, 조건을 만족하는 문자열인지 조건문을 통해 판별하면 되는 문제입니다. 많은 사람들이 쉽게 해결했습니다. B. Baba is Rabbit 제가 출제한 문제입니다. 주어진 사물들을 적당한 자료구조(map/dict 등..

다음과 같은 상황을 생각해보자. $n$명의 사람이 있고, 이들 중 일부는 연인 관계를 맺고 있을수도, 그렇지 않을 수도 있다. 이 때, 연인 관계로 가능한 경우의 수는 총 얼마인가? Thanks to: Chan Bae (이 분과 대화를 나누다 나온 이야기입니다.) 짚어두기. ${}_n C_r = {n \choose r}$이다. 여러 답이 나왔는데, 개인적으로는 마지막 답에 동의하는 바이다. 1. $2^{n \choose 2}$가지 $n$명의 사람으로 이루어진 simple graph를 생각하자. 두 명의 사람이 연인 관계에 있다면, 해당하는 사람 사이에 간선을 긋는다. 그러면, graph들과 연인 관계들은 1-1 대응된다. 따라서, $2^{n \choose 2}$가지가 있다. 2. $2^{n+1 \choo..

근 며칠 사이에 위스키를 좀 마셨다. 요근래 마신 위스키 중 좋았던 세 개에 관해 블로그에 짧게나마 남겨두고 싶었다. 1. Maker's Mark 버번 위스키의 기본적인 특징을 가장 잘 담고 있다고 생각된다. 이것을 마시면 "이게 바로 버번이지!"라는 생각이 딱 든다. 2. Knob Creek 최근에 버번에 꽂혀서, 버번을 기존에 비해 좀 많이 마셨다. 바닐라 향이 좀 났던 것 같다. 훈연 같은 느낌도 있었던 것 같고. 3. Glenkinchie 로우랜드 지방의 위스키 중 가장 유명한 위스키라 들어보기는 많이 들어봤지만, 며칠 전에 처음 마셔봤다. 바텐더분이 서비스(!)로 한 잔 주셨는데, 만족스러웠다. 가볍고 상큼했다.

Statement. 하나의 Ground Set $E$ 상의 세 개의 매트로이드 $M_1$, $M_2$, $M_3$가 있다. 이 때, $M_1$, $M_2$, $M_3$ 모두에서 independent 한 $E$의 가장 큰 subset을 구하여라. Proof of NP-Hardness. Hamiltonian path 문제로 부터의 reduction을 구성할 것이다. $E$를 임의의 directed graph $G$의 edge set으로 놓자. $X \subseteq E$에 대해: - $X$가 $M_1$에서 independent 함을 $X$에 속하는 간선만을 볼 때, 각 정점의 in-degree가 $1$ 이하임으로 정의하자. - $X$가 $M_2$에서 independent 함을 $X$에 속하는 간선만을 볼 때..

ICPC 인터넷 예선을 앞둔 팀연습겸 해서 KAIST 교내 ICPC 모의대회에 참가했습니다. 저희 팀 명은 jungICPCmangja였고, 팀원은 ICPC 팀원과 같이 김정우(항공우주공학과)님과 박수빈(새내기과정학부)님이었습니다. 저희 팀은 A, B, D, E, G, 이렇게 총 5개의 문제를 해결하였고, H번은 아쉽게 해결하지 못했습니다. 아래는 프리즈가 풀리기 전의 스코어보드의 사진입니다. 해결한 문제 저희 팀이 해결한 문제 중 A, G는 박수빈님이, B, D, E는 제가 해결하였습니다. 제가 해결한 문제에 대한 풀이를 간략히 적습니다. B. And the Winner Is... Ourselves! 그리디하게 빠른 시간 안에 해결할 수 있는 문제부터 해결해주면 됩니다. D. Capital 문제의 제한이..

공부하면서 혼자 정리해보고 있습니다. 아직 Intuition이 다소 모자란 것 같네요. 계속 추가 예정. Definition 1. 함수들의 수열 $\{f_n\}$이 있다. 모든 $x$에 대해 $\{f_n(x)\}$가 수렴한다고 하자. 함수 $f$를 $$ f(x) = \lim_{n \to \infty} f_n(x) $$ 로 정의하자. 이 때, $\{f_n\}$의 극한을 $f$로 정의하고, $\{f_n\}$이 $f$로 pointwise converge 한다고 부른다. 참고로, 연속 함수들의 수열 $\{f_n\}$이 $f$로 점별 수렴할 때, $f$가 $x$에서 연속임은 $$\lim_{t \to x} f(t) = f(x)$$ 임을 의미하고, 이는 $$\lim_{t \to x} \lim_{n \to \infty..

올해 첫 ICPC를 참여합니다. 저와 KAIST 항공우주공학과의 김정우님과 KAIST 새내기과정학부의 박수빈씨, 이렇게 3명이서 팀을 이루어 참여합니다. 팀명은 jungICPCmangja입니다. 팀이 굉장히 늦게 결성되어 촉박하게 팀노트를 준비했지만, 누군가에게 도움이 될 수 있으리라 믿고 팀노트의 목차를 공유합니다. 세부 코드의 경우 오픈소스 코드를 가져온 것이 많아서 올리지 못하는 점 양해 바랍니다. 팀노트를 업데이트 하면 목차도 업데이트 하도록 하겠습니다. P.S. 리저널 가면 좋겠네요. 1. Setting 1.1 Compile Command 1.2 Easy Printing 1.3. OSRank 2. Math (Theory) 2.1 Vizing's Theorem 2.2 Green's Theorem ..

Theorem. 그래프 $G$가 이분그래프임과 $G$가 홀수 길이의 사이클을 포함하지 않음은 동치이다. Proof. $G$가 이분그래프이면 홀수 길이의 사이클을 포함하지 않음은 명백하다. $G$가 홀수 길이의 사이클을 포함하지 않는다고 하자. $G$가 여러개의 컴포넌트로 이루어져 있다면, 각 컴포넌트를 따로 고려해주면 된다. 따라서, $G$가 연결그래프임을 가정할 수 있다. 이제, $G$가 연결그래프이므로, $G$의 spanning tree $T$를 잡을 수 있다. $T$ 상의 아무 정점에서나 시작해서 dfs를 하며 2-coloring을 해줄 수 있다. 만약, $G$의 어느 간선이 색이 같은 두 정점 $u, v$를 잇는다면, $T$ 상의 $u, v$를 잇는 경로와 해당 간선으로 이루어진 사이클은 길이가 ..