구사과

(4/19 추가: 권한 WRITE로 해주세요! READ로 하니까 업로드가 안되네요. 뭐 안할건데 걱정되시면 clone해서 주시면 됩니다)BOJ 서비스 종료에 관해서 Qingyu님과 이야기를 나누었는데, Qingyu님이 기존 문제를 QOJ.ac로 마이그레이션하는 데 있어 도움을 주실 의향이 있다고 해 주셔서 마이그레이션 신청을 받고자 합니다. 도움을 주신 Qingyu님에게 큰 감사를 표합니다.이미 본인의 문제가 QOJ에 등록되어 있으나 출제자로 본인이 표시되어 있지 않음이 Google Form을 통해서 신청해 주세요.BOJ에만 등록되어 있는 본인 문제를 QOJ에 등록하고 싶음이 Google Form을 통해서 신청해 주세요. 아래 사항을 꼭 읽어주세요:Polygon package가 있다면 따로 데이터 압축 ..

Thatchaphol Saranurak 강의를 듣고 안 까먹으려고 작성1. Warmup: Two Action Setting$n$ 명의 전문가와 함께 주식 시장을 $T$일에 걸쳐 예측하려고 한다. 매일 다음과 같은 일이 일어난다:각각의 전문가가 오늘의 주식 시장이 상승인지 하락인지 예측한다.당신은 이를 보고 오늘 주식 시장이 상승인지 하락인지 결정한다.이후 주식 시장의 결과가 나온다. (주식 시장은 adversarial할 수 있다. 즉 당신의 결정의 반대만 찍는 등의 일이 발생할 수 있음)Loss를 결과를 못 맞춘 날의 수로 정의하자. 주식 시장이 무조건 내가 찍은 것의 반대만 찍는다면 Loss가 $T$ 가 나오는 것은 어렵지 않다. 고로 목표는 최고의 전문가에 비해서 그렇게 못하지 않는 전략을 찾는 것이..

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

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시 비행기를 예약하고, 가방 하나만 들고 샌프란시스코를 향했다.친구 집에 도착해서 굴국밥을..