그리디 알고리즘은 그 발상에 따라 난이도가 천차만별이기로 유명하다. 회의실 배정과 같이 기초적인 그리디 문제는 실버에서 시작하는 반면, Scenery 같은 문제는 루비까지 올라가기도 한다. (사실 난 Scenery의 풀이를 잘 모르기 때문에 단순 그리디가 아닐 수도 있다.) 그리디 전략을 증명할 때 사용하는 방법 중 하나가 플로우를 이용하는 것이다. 플로우는 분명 OI 범위 밖이지만, 그리디 알고리즘은 OI 범위 안이고, 플로우를 이용한 증명은 플로우 없이도 할 수 있는 경우가 많아 OI에서 심심찮게 볼 수 있었다. 난 이러한 증명 방식에 대해 잘 몰랐기 때문에 이런 문제를 만날 때마다 힘들었는데, 이제는 공부해 볼 때가 되었다고 생각해 공부를 시작해 보았다. 이 글은 이해하는 데 초점을 맞추었기 때문에..
요즘 애드혹 감각이 좀 줄어든 것 같아서 백준에서 플래-다이아 애드혹 문제들을 랜덤하게 10개 뽑아 풀어 보았다. 괜찮은 문제도 있었던 반면 풀기 싫은 문제도 많이 있었다. 1. ? 정말 풀기 싫은 문제가 뽑혀서 안 풀고 넘어갔다. 무슨 문제였는지는 공개하지 않는다. 2. Монотонная подпоследовательность 길이가 $n$인 순열 중 LIS나 LDS의 길이 최댓값이 $k$인 것을 찾는 문제이다. Erdos-Szekeres Theorem에 의하면 길이가 $(r-1)(s-1)+1$ 이상인 수열은 길이 $r$의 증가부분수열이나 길이 $s$의 감소부분수열이 있다. $r=s=k+1$을 넣으면, $k^2+1$ 이상의 길이를 가진 수열은 길이 $k+1$ 이상의 IS/DS가 있다. 따라서 $n >..
BOJ 15481. 그래프와 MST 일단 원래 그래프의 MST를 구한다. 그리고 각 간선에 대해, 해당 간선의 양끝점을 잇는 경로에서 가장 큰 가중치를 가지는 간선을 빼 주고 해당 간선을 넣으면 이것이 가장 싼 MST가 된다. 구현은 LCA와 sparse table을 잘 이용하면 HLD + segment tree 없이도 할 수 있다. 시간 복잡도는 $\mathcal{O}(M \log N)$이다. BOJ 30896. 두 팀으로 나누기 두 팀의 $\min(A_i)$와 $\sum B_i$를 각각 $a_1$과 $a_2$, $b_1$과 $b_2$라고 하자. $a_1$과 $a_2$ 중 하나는 $\min_{1 \le i \le N} A_i$이다. WLOG $a_1$이라고 하자. $a_2$를 정하는 방법은 최대 $10..
tl;dr 글이 너무 길어서 읽기 귀찮다면 결론만이라도 읽자. 개요 요즘 커뮤니티 대회에 관해 말이 많다. 최근 여러 대회에서 대회 이후에 문제 오류가 발견되는 상황이 있었고, 현재의 대회 검수 시스템에 대한 전반적인 재정비의 필요성이 시사된 바 있다. 나 역시 현재의 검수 시스템에 문제가 있음에 동감하는 바이지만, 이 글에서 이야기하고자 하는 바는 아니다. 이 글에서 이야기하고자 하는 것은 문제의 질에 관한 것이다. 조금 민감한 주제일 수 있다는 것을 인지하고 있고, 이 글에 적힌 건 어디까지나 내 의견일 뿐, 절대적인 것이 아님을 전제로 읽어주셨으면 한다. (비고: 글을 올리기 전 몇몇 사람들에게 피드백을 받은 결과, "좋은 문제"의 의미가 조금 모호하다는 이야기를 들었다. 내가 이 글에서 이야기하고..
친구들과 함께 연습셋을 돌았다. 그 중 다이아 이상 문제 몇 개에 대해 간단히 정리해 둔다. BOJ 8473. Monopoly 좌표평면에 $N$개의 점이 주어질 때, 택시 거리가 $c$ 이하인 점들을 간선으로 연결하자. 연결 성분의 개수와 가장 큰 연결성분의 크기를 구하면 된다. 일단 좌표평면을 45도 회전해 생각하면 택시 거리는 체비셰프 거리 $\max(\Delta x, \Delta y)$ 가 된다. 이렇게 변형하면 한 점과 간선으로 직접 연결될 수 있는 점의 영역을 가로/세로 $2c$인 정사각형으로 생각할 수 있다. 이제 이러한 영역 안의 점을 빠르게 찾을 수 있는 방법을 생각해 보자. 위의 좌표 변환을 통해 다음처럼 문제를 변형할 수 있다. 각 점 $(a, b)$가 있고, $x$ 범위가 $[a-c,..
제목만 들어도 모두가 아는 이 전설의 문제는 ONTAK 2010에 출제된 문제다. ONTAK은 폴란드 국가대표 선발 캠프라고 알고 있는데, 자세한 내용은 찾아도 잘 안 나와서 딱히 깊이 알고 있지는 않다. 문제는 단순하다. 10개의 파일이 있고, 정수 하나를 입력받아 $(0 \le N \le 10)$ 그저 대응되는 파일의 내용을 출력하기만 하면 된다. 단 코드의 길이는 10만 바이트를 넘을 수 없고, 출력 파일은 예제 파일 $(N = 0)$을 제외하고 모두 20만 바이트를 가뿐히 넘는다는 게 특징. gen0.out 그냥 출력하면 된다. gen1.out 파일이 너무 커서 웬만한 프로그램으로 열려고 해도 열기 힘들다. 경험상 Visual Studio Code가 이럴 때 정말 좋은 역할을 해 준다. 파일을 열..
2월 3일에 열린 솔브드 아레나 파티 Div.1에 미러로 참가했다. 대회 장소가 집에서 멀기도 하고 아레나 #10~#16에 전혀 참가하지 않아서(Arena #16 운영 제외) 선정될 확률도 없었던 터라 본 대회에 참가 신청을 하진 않았다. 대회 결과 5솔브로 본 대회+미러 합산 8등을 했다. 막판에 H를 풀었다면 등수가 크게 올랐을 것 같아서 아쉽다. A. 정렬된 연속한 부분수열의 개수 (0:02) 문제의 조건을 만족하는 모든 $(i, j)$에 대해, $[i, j]$가 다음 조건을 만족하는 $[l, r]$ 중 정확히 하나의 부분구간임을 보일 수 있다. $A_l A_l$ $r=N$이거나 $A_r > A_{r+1}$ 다르게 말..