2022 나코더 송년대회 후기 (+ 풀이)
* 이 글에서는 대회 후기+복기 위주로 작성하고, 어려운 문제는 따로 글로 작성할 예정이다. 경기과학고 ps 동아리 나코더에서 12월 27일 송년대회가 열렸는데, 나는 [BIG SHOT]이라는 팀 이름으로 같은 39기인 박종경, 김기범과 함께 참가했다. 5시간동안 12문제를 풀어야 했고, A, B, E, I, J, K를 풀고 2등과 근소한 차이(패널티 40차이)로 3등을 했다. 0:00 ~ 0:13 내가 ABCD, 기범이가 EFGH, 종경이가 IJKL을 읽었다. A에 넥슨 그림이 있어서 넥슨 스폰서 문제임을 알게 되었고, 특별상이 걸린 넥슨 스폰서 문제면 어려운 문제는 아닐 것으로 추측하고 바로 풀었다. 오타내고 1번 틀려서 2번만에 맞았다.(0:13:19) A는 두 수열 $A_i$와 $B_i$가 주어지..
최대 유량 알고리즘 1 (Ford-Fulkerson, Max Flow Minimum Cut Theorem)
최근 유량 알고리즘들을 공부해 봤는데, 정리와 증명이 명확하게 정리된 블로그가 잘 없는 것 같아서 정리한다. * 모바일 환경에서 레이텍이 깨지는 현상이 있는 것 같다. 구글 크롬의 경우, 우측 상단의 점 세 개를 눌러 메뉴를 열고 "데스크톱 보기"를 활성화하는 것으로 해결할 수 있다. 0. 용어 정의 다음과 같이 그래프, 소스 정점, 싱크 정점, 용량 함수가 주어졌다고 하자. graph $G=(V, E)$, source $s \in V$, sink $t \in V (s \ne e)$, 용량 함수 $c : V \times V \longmapsto \mathbb{R}^{+}$ (수학에서는 이 네 요소 $(G, c, s, t)$를 flow network라 한다.) 이때, $G$의 소스에서 싱크로 물건을 옮기는..
