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$의 소스에서 싱크로 물건을 옮기는..
백준 15261 Donut Drone (CERC 2017 D)
문제 설명(링크): https://www.acmicpc.net/problem/15261 15261번: Donut Drone The first line contains two integers r and c (3 ≤ r, c ≤ 2 000) — the number of rows and the number of columns of the toroidal grid. The i-th of the following r lines contains a sequence of c integers ei,1, ei,2, . . . , ei,c (1 ≤ ei,j ≤ 109) — www.acmicpc.net 문제 요약 도넛처럼 생긴 격자판에서 각각의 높이가 있는데, 한 칸에서 시작할 때 다음으로 갈 칸은 왼쪽 위, 왼쪽, 왼쪽 ..
백준 16977 히스토그램에서 가장 큰 직사각형과 쿼리
문제 설명(링크) www.acmicpc.net/problem/16977 16977번: 히스토그램에서 가장 큰 직사각형과 쿼리 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3 www.acmicpc.net 문제 요약 [l, r]영역의 직사각형만 사용하여 너비가 w인 직사각형 중 가장 넓이가 큰 것을 출력하는 문제이다. 풀이 과정 너비가 정해져 있으므로, 높이가 가장 큰 것이 넓이가 가장 크다. 또, 높이가 h인 직사각형이 존재하면 h-1인 직사각형도 존재하므로, h에 대한 이분탐색을 할 수 있다. 높이가 h인 직사각형이 존재한다는 것의 필요충분조건은..
