2019 ICPC 한국 리저널 인터넷예선 풀이
Note: 아직 미 완성인 글입니다. 20.06.03: A, B, C, D, F, H, I, J, L 풀이 수록 문제는 다음 사이트에서 일부 해결해볼 수 있다: 링크 A. All You Need is Dating $i$번째 IC 학생이 원하는 데이트의 최소 횟수를 $minIC_i$, 최대 횟수를 $maxIC_i$로 표기하자. 비슷하게 $minPC_j$와 $maxPC_j$를 정의하자. 그러면, 이 문제는 아래와 같이 간선을 지나가는 유량의 최소 제한과 최대 제한이 있는 플로우 그래프로 모델링 가능하다. 이는 전형적인 LR-flow 문제로, 해결법이 널리 알려져 있다. 일반적인 네트워크 플로우 알고리즘을 사용하여 해결하는 방법과 MCMF를 활용하는 방법이 있는데, 이 글에서는 생략한다. B. Balanced..
Patience Sort
Patience sort는 다음과 같이 작동하는 정렬 알고리즘이다. (설명이 쉽지 않다. 더 아래에 있는 코드를 보는 것을 추천한다.) 작동 과정 $n$ 장의 카드 $C_1, C_2, \cdots, C_n$이 있고, 각 카드에 수가 적혀 있다고 할 때, 우리는 다음과 같은 과정을 수행하며, 각 카드를 차례로 카드 더미에 추가한다. (카드 더미를 스택이라 생각하면 좋다. 카드 더미들은 일렬로 나열되어 있다.) 초기에는 아무 카드 더미가 없다. 따라서, 처음에는 카드 1장으로 이루어진 카드 더미를 하나 만들고, 해당 더미에 $C_1$을 추가한다. 이후, $C_2$부터 차례로 카드 더미에 다음의 규칙을 따라 추가한다. 맨 위의 수가 자신보다 크거나 같은 카드 더미가 있다면, 그러한 카드 더미 중 가장 왼쪽의 ..
Google Hash Code 2020 참가 후기
생애 처음으로 Google Hash Code에 참가했습니다. 저는 import_torch_as_tf 라는 이름의 팀으로 김민철, 김상범 님과 함께 참가했습니다. 최종 26,282,007점이라는 점수로 세계 1,119등, 한국 24등 이라는 다소 저조한 성적을 냈지만, 그래도 나름대로 재밌었습니다. 각 문제에 대해 저희 팀의 풀이를 소개하자면, 다음과 같습니다. 스포일러가 될 수 있으니 주의해주세요! B - read on / 5,822,900 데이터를 살펴보면 sign up time 순으로 출력하면 해결할 수 있음을 알 수 있습니다. C - incunabula / 5,521,060 Library를 sign up time이 작은 순으로 정렬하고, library 안의 책들을 그리디하게 정렬하면 충분한 보상을 ..