구사과

에 관해서 최근에 공부하고 발표자료를 만들었다.

VS Code에서 프리뷰는 띄워주면서 PDF export는 안해주는데 왠지는 아무도 모름marp ./asdf.md --pdf \ --timeout 120000 \ --allow-local-files \ --chrome-path "/Applications/Google Chrome.app/Contents/MacOS/Google Chrome"

CCC 2025 S1. Positioning Peter’s Paintings답은 $2 \min(\max(A, C) + B + D, A + C + \max(B, D))$ 입니다.CCC 2025 S3. Pretty Pens$Q = 0$ 인 경우의 풀이를 먼저 정리합시다. 변호사가 종류를 바꾸지 않을 경우, 각 종류에 대해서 덕의 최댓값을 구한 후 이를 합한 것이 정답이 됩니다. 종류를 바꾸게 된다면, 현재 최댓값으로 선정된 업보 중 덕을 최소화하는 것을 빼서, 선정되지 않은 업보로 교체하는 것이 최적입니다. 즉, 이 때 얻을 수 있는 이득은 (최댓값 중 덕 최솟값) - (최댓값 아닌 업보 중 덕 최댓값) 으로 계산할 수 있습니다. 이 이득 값이 $0$ 이상이면, 최댓값의 합에 이를 더해주면 됩니다. 이렇게 ..

그래프의 최대 독립 집합 문제는, 그래프가 주어졌을 때 최대 크기의 정점 부분집합 $S$를 골라서, $S$ 안에 있는 두 정점을 잇는 간선이 없게끔 하는 문제이다. 이 문제는 NP-complete임이 아주 잘 알려져 있다. 심지어 $O(n^{0.99})$-factor로 approximate할 수 있으면 $\textsf{NP} = \textsf{ZPP}$ 이다 (사실상 $\textsf{P} = \textsf{NP}$ 라는 뜻이다.) 어차피 제대로 못 푸는 문제이니 대신 다음과 같은 그리디 알고리즘을 생각해 볼 수 있다.순열 $\pi$ 를 잡고, 그 순서대로 정점을 순회한다. $\pi$ 는 모든 길이 $n$ 의 순열 중 랜덤하게 샘플.만약 현재 정점과 인접한 정점 중 $S$ 에 있는 정점이 없으면 현재 정점..

최대 차수가 $\Delta$ 인 그래프를 $(\Delta + 1)$ 개의 색으로 색칠하는 문제를 생각해 보자. 이 문제는 정점을 아무 순서로 보면서 남는 색을 배정해 주면 선형 시간에 쉽게 해결할 수 있다. 그러니 간선이 추가되고 삭제되는 쿼리를 넣어보자. 쿼리당 $O(\Delta)$ 시간에 문제를 해결하는 것은 쉽다:간선이 삭제되면 아무것도 하지 않는다.간선이 추가되었고, 만약 두 정점의 색이 다르다면, 한 정점에 대해서 남는 색을 배정해 준다. 남는 색을 찾아줘야 하기 때문에 $O(\Delta)$ 시간이 필요하다.더 빠른 알고리즘은 없을까? 이 문제를 처음 다룬 것은 내가 알기로는 Bhattacharya et al. 2018 이고, 당시에는 expected amortized $O(\log \Delta..

알고리즘을 모델링하는 여러 방법 중 하나는 Decision Tree이다. Decision Tree에서 알고리즘은 입력의 특정 부분을 읽어서 읽은 결과에 따라 YES / NO verdict를 결정하고, 비교 결과에 따라서 두 상태 중 하나로 분기한다. 예를 들어서 비교 정렬에서는 $x_i, x_j$ 를 읽은 다음에, $x_i - x_j$ 의 부호에 따라서 YES / NO verdict를 결정하고, 이 결과에 따라서 두 개의 자식 상태 중 하나로 분기한다.Decision Tree의 최대 깊이는 보통 알고리즘 시간 복잡도의 lower bound를 구성하는데 자주 쓰인다. 비교 정렬에서는 결과 상태가 최소 $n!$ 개이니, 최대 깊이가 적어도 $\log_2 (n!) = O(n \log n)$ 이고, 그래서 모든..

Part 3. Oregon Coast보스턴으로 가는 비행기가 밤 11시 정도로 잡혀 있어서 Oregon Coast를 크게 한 바퀴 돌고 올 계획을 짰다. Oregon Hwy 34가 뭔가 구불구불하고 재밌어 보여서, 그 길로 서쪽으로 들어간 다음에 해안을 따라 북쪽으로 올라오고, 남는 시간에 따라 적당히 포틀랜드로 복귀할 생각을 대충 했다.가는 길에 Alsea Falls라고 하는 곳을 들렀다. 작은 강이 폭포를 이루고 있다.몰랐는데 이 지역은 rainforest가 형성되어 있어서 특이한 이끼가 낀 나무들을 많이 볼 수 있었다. 올림픽 반도 같은 곳에만 있는 줄 알았는데, 오리건 해안가에도 rainforest가 있다고 한다.더 달려서 해안가에 도착했다. Hwy 34는 그냥 나무가 많고 되게 구불구불했다. 추..

Part 1: San Francisco, CA7.18이 전날 밤에 하루 종일 잠을 못 자고 밤을 샜다. 생활 패턴 문제가 아니라 누워서 못 잔 것이고, 잠을 못 잘만한 개인적인 이유도 있었다. 당연히지만 뜬 눈으로 밤을 지새우니 고문이 따로 없었고, 사람을 보러 나가지 않으면 해결이 안 될 것 같았다. 내가 보스턴에서는 당분간 볼 만한 친구가 없어서, 이 연옥을 탈출하기 위해서는 샌프란시스코라도 가야 하나 하는 생각이 들었다. 그렇게 더 생각해 보다 지금 내가 할 수 있는 최선인것 같아 바로 추진했다.오전 11시 반에 친구한테 소파에서 잘 수 있는지를 물어봤고, 와도 된다는 답장을 받았다. 답장을 받은 즉시 오후 2시 비행기를 예약하고, 가방 하나만 들고 샌프란시스코를 향했다.친구 집에 도착해서 굴국밥을..

대회 시작 전컴퓨터 세팅 설정 시간을 몇 분 준다. 근데 워낙 이상한 환경이라서 설정 시간 안에 제대로 세팅하기가 쉽지 않다. 다행이도 옆자리에 앉아있던 신민철 (fefe) 가 환경 변수 설정 등을 알려줘서 VS Code를 사용할 수 있게 되었다. 이 세팅 때문에 우승 여부가 갈렸을 수도 있다. 무한한 감사를 표한다.1번아주 간단한 문제였는데, 이런 버그를 만들고 찾지 못했다.int ret = 0; { int ret = 0; ...} return ret;컴파일도 사실상 처음 해 본 거라, 여러 상황을 의심하다가 오래 걸렸던 것 같다. 결국 20분 걸려서 솔브.2번빡빡해 보이는 제한이 있는 문제였다. 열을 8개씩 묶으면 될 거라고 생각했는데, python이 깔려있지 않아 손으로 $256 * 125 ..

볼리비아 수크레에서 IOI 2025 Day 2 대회가 진행되었다. 한국 학생들의 최종 성적은 다음과 같다.우민규, 100 / 99.33 / 93 / 100 / 82.45 / 100, 574.78점, 2등 (금메달)이유찬, 100 / 58.89 / 86 / 66 / 72.89 / 83, 466.77점, 16등 (금메달)정민찬, 100 / 79.77 / 100 / 66 / 30 / 83, 458.77점, 19등 (금메달)변재우, 39 / 76.25 / 86 / 100 / 64.45 / 83, 448.7점, 24등 (금메달)한국 팀은 Day 2에도 기세를 이어 대단히 좋은 성적을 내었다. 우민규 학생은 Day 1에도 4등의 성적으로 대회를 마무리했는데, Day 2에서는 이를 더 끌어올려 종합 2등의 아주 우수..