전체 글
-
멘토교육 1주차 - IOI 2016 Day1정보/PS 2025. 5. 8. 10:06
Detecting Molecule이 쉬운 문제라는 사실을 안 상태로 시작했다. (3문제의 정확한 티어는 몰랐음)결과 / 100 + 100 + 31 = 231~30minMolecule을 풀었다.가장 쉬운 문제라는 것도 알고있었고, CEOI에서 풀어본 문제와 유사하여 금방 풀이를 찾을 수 있었다.~2hr2번 3번 문제를 읽었다. 어렵다. 하지만 시간이 많아서 좀 오래 생각했다. 2번은 꽤나 유의미한 관찰을 했고, 3번은 자명섭테 말고 모르겠다.2번에서 가설을 하나 세웠는데, 반례를 찾았다.2번에서 비트디피로 34점을 긁었다.2번 문제에서 오일러 회로의 접근 방법으로, 최초로 비자명해보이는 섭테인 2번 30점을 긁었다.2번을 계속 생각한다.2hr 30min2번 풀이를 찾은 것 같다. 구현이 살짝 난이도가 있어..
-
-
-
-
Matroid Theory 2 - Basis, Circuit정보/이론 2025. 4. 6. 12:27
저번 글에서 매트로이드의 정의에 대해 알아보았습니다.이번 글에선 본격적으로 매트로이드에서 정의될 수 있는 여러 가지 개념들을 알아보겠습니다.저번 글에서 언급했듯이 모든 개념은 Linear Matroid 또는 Graphic Matroid 관점에서 예시를 들어 설명할 것이므로, 기초적인 선형대수학과 그래프이론 지식이 있으면 좋습니다.Reminder매트로이드 $M = (S, \mathcal{I}), \ \mathcal{I} \subseteq 2^S$ 는 다음 3가지 공리를 만족해야 합니다.[I1] $\phi \in \mathcal{I}$.[I2] Independent Set의 부분집합은 Independent Set이다.$\forall A \subseteq B \subseteq S$ then $B \in \ma..
-
Matroid Theory 1 - What is Matroid?정보/이론 2025. 3. 29. 22:02
옛날부터 배워보고 싶었던 매트로이드를 배워봤습니다.사실 이걸 배운다고 해서 실전 PS에 쓸 일은 없을 것 같지만순수한 호기심, 루비를 날먹할 수 있고, 수학/정보적 소양을 기를 수 있지 않을까 하는 생각에 배워봤습니다저는 잘 모르지만 매트로이드는 현대 조합론에서 꽤나 중요한 역할을 하고 있는 것 같습니다.허준이 교수의 필즈상을 받게 된 연구 중에서 매트로이드와 관련된 것도 있다고 하고요. 기초적인 선형대수학, 그래프 이론과, 최소 스패닝 트리(MST) 알고리즘을 알고 있다는 전제 하에 작성합니다.코드포스 글 https://codeforces.com/blog/entry/69287MIT 강의 https://math.mit.edu/~goemans/18438.html를 참고했습니다.용어 정리$A \setminu..