leejseo의 블로그

근 며칠 사이에 위스키를 좀 마셨다. 요근래 마신 위스키 중 좋았던 세 개에 관해 블로그에 짧게나마 남겨두고 싶었다. 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$를 잇는 경로와 해당 간선으로 이루어진 사이클은 길이가 ..

BOJ 문제 링크: https://www.acmicpc.net/problem/16287 아는 분의 블로그(링크)에 이 문제에 대한 풀이가 올라온김에 풀어보았다. 해당 블로그에서는 $O(N^2 \log N)$ 풀이를 설명하고 있다. 이 글에서는 $O(N^2 + \max\{A_i\})$ 풀이와 다른 형태의 $O(N^2 \log N)$ 풀이를 설명한다. Problem 서로 다른 $N$개의 정수 $\{A_i\}_{i=1}^{N}$가 주어진다. 이들 중 4개를 골라 합하여 $W$가 될 수 있는지 판단하는 문제이다. $A_i \le 200,000$이고, $N \le 5,000$이다. Solution $A_i + A_j + A_k + A_l = W$인 $i, j, k, l$의 존재성을 찾는 문제인데, 이 문제의 경우..

이번 Codeforces 라운드는 그래도 A~E까지 5개의 문제를 해결했다. 하지만, 여전히 한 문제를 말려서 못푸는건 마찬가지인 것 같다. F번에 대해 $O(Q\sqrt{N} + 2^6 Q)$ 정도의 풀이를 생각했지만, 포함배제 구현 미스로 대회가 끝났고, 너무 복잡하게 생각해서 케이스를 많이 나누었던게 화근인(화끈이 아님) 것 같다. 해결한 문제에 대한 풀이를 간단히 작성하였다. 대회 문제는 다음 링크에서 풀어볼 수 있다. 링크: https://codeforces.com/contest/1207 A. There Are Two Types Of Burgers 비프 패티 버거를 최대 $p$개, 치킨 패티 버거를 최대 $f$개 만들 수 있다. $pf$개의 모든 경우에 대해 따져보면서, 실제로 만들 수 있는지(..

Round #578에서 레이팅이 18 떨어져서 이번에 Div. 2를 쳤다. 놀랍게도 레이팅이 정확히 18 올라서 원래대로 돌아왔다. 사소한 오류 때문에 D를 8번 내서 맞았다는 것이 너무나도 뼈아팠다. 대회 시작 후 1시간 만에 AC 받을 문제를 2시간 가까이 붙들고 있어서 E번을 볼 시간이 없었다. 해결한 문제에 대한 풀이를 작성하도록 하겠다. 링크: https://codeforces.com/contest/1206 Div 2A Choose Two Numbers 총 $O(NM)$개의 $(a_i, b_j)$ 쌍을 직접 확인하면서 $a_i + b_j \in A \cup B$인지 체크해주면 된다. 이대로 구현하면 $O(NM(N+M))$이고, $A$와 $B$의 원소들의 크기가 작음을 이용하면 $O(NM)$에도 ..

PS 하면서 약수의 개수와 관련된 문제를 종종 볼 수 있다. 그래서 글을 작성중이었는데, 마침 NYPC에 이 글의 내용 중 일부를 그대로 쓰면 되는 문제가 나왔다고 한다. 그래서 글을 날렸고, NYPC 예선이 끝난 이제야 업로드한다. 글을 날렸던 만큼 다듬어지지 않았을 수 있다. 나중에 수정할 예정이다. 1. 약수의 개수 구하기 양의 정수 $N$이 주어지고, $N$의 약수의 개수를 구한다고 해보자. $O(\sqrt{N})$ 알고리즘 부터 소개하겠다. 이 알고리즘은 간단하다. $N = xy$로 나타내어 진다고 할 때, $x$와 $y$중 하나는 $\sqrt{N}$ 이하이고, 다른 하나는 $\sqrt{N}$ 이상이다. 따라서, $\sqrt{N}$ 이하의 수들만 봐도 약수의 개수를 구할 수 있다. C++ 구현은..