구사과

Garey / Johnson의 1981년 논문 "Scheduling Unit-time tasks with Release time and Deadline" 를 읽고 내용을 정리해 보았다. Competitive Programming에서는 2017년 ICPC World Finals에서 한 명도 풀지 못했던 문제인 "Scenery"의 풀이로 유명한 논문이다. 이 글에서는 $O(n^2)$ 알고리즘까지만 정리했으며, $O(n\log n)$ 알고리즘은 하지 못했다. ㅠㅠ 이 문제의 $O(n^2)$ 알고리즘은 매우 아름답다. 혼자 생각하지 못하더라도 보고 배울 가치가 충분하니 일독을 권한다. 여담 : 예전에 breakun 님이 BOJ 슬랙에 질문했던 문제 중 하나이다. $N$개의 구간 $[S_i, T_i]$ 가 주어진..

이전에 Off-line dynamic connectivity에서 썼던 내용의 연장선으로, Dynamic MST 문제를 오프라인으로 푸는 알고리즘에 대한 글을 써 보았다.

5월 22일 KAIST RUN에서 봄 대회를 진행하였다. 대회는 백준 온라인 저지에서 진행하였으나 Open Contest의 경우 Codeforces Gym에서도 진행하였다.아래는 본 대회의 Scoreboard이다.ProblemsOpen Contest ScoreboardCodeforces Gym ArticleEditorialTests & Checker & Solutions

수학적 귀납법 글의 20번 문제 풀이를 적어보았다. 삼성전자 소프트웨어 멤버쉽 과제의 일환으로 써서 글이 많이 길다. 고로 PDF로 따로 첨부한다.

1. POI디스크립션을 차근차근 읽으면서, 문제의 점수, 참가자의 점수, 참가자의 등수를 문제에 적혀있는 그대로 계산하면 됩니다. 2. 내일 할 거야문제를 쉽게 변형해서, 과제 리스트가 주어졌을 때 모든 과제를 마칠 수 있는지를 yes / no로 판별하는 문제를 생각해 봅시다. 이 경우 과제를 데드라인 순으로 정렬한 후 처리하는 그리디 알고리즘이 최선임을 증명할 수 있습니다. (데드라인이 큰 것을, 데드라인이 작은 것보다 먼저 처리할 이유가 없음) 한편, T일 쉰다는 것은, 사실 모든 데드라인을 T일 앞당긴 후 과제를 시작한다는 것과 동치입니다. 고로 과제를 하는 순서가 바뀌지 않습니다. 실제 T를 구하는 것은 과제를 역순으로 보면서 할 수 있습니다. 3. Archery Tournament원은 빠르게 다..

(2017.10.01 초판)(2018.01.27 문제집 추가)내가 만든 문제집을 내가 찾기 힘들어서, 정리하고자 만들었다. 이렇게 돌아보니까 근본 없다.. 전부 소개하기는 아까우니까, 별점 붙여서 별점 높은 것만 소개. convex hull trick https://www.acmicpc.net/workbook/view/476 (★★★★)컨벡스 헐 트릭 연습 문제집. 난이도는 쉽지 않다.FFT https://www.acmicpc.net/workbook/view/824 (★★★★★)FFT 연습 문제집. 이것도 쉽지 않다. FFT 쓰는 문제를 거의 전부 모은 것 같다.Segtrees are too mainstream https://www.acmicpc.net/workbook/view/912 (★★★★☆)Spl..

POI 2009/2010. Pilots$N$개의 수가 주어질 때, 연속 구간 중 (구간 내 최댓값) - (구간 내 최솟값) $\leq T$를 만족하는 최대 길이의 연속 구간을 찾는 문제이다. $N \leq 3000000$을 만족한다.데큐를 사용해서 Sliding window로 구간 최댓값 / 최솟값을 구하는 알고리즘이 잘 알려져 있다. 이 알고리즘에 inchworm을 적용하여서 문제를 해결할 수 있다. 처음에 [1, 1] 구간에서 시작하여. (최댓값) - (최솟값) $ \leq T$ 를 만족할 때까지 구간의 끝점을 늘린다. 더 이상 늘릴 수 없으면, 시작점을 늘리면서 계속한다. 이러한 식으로 구간의 길이를 최대화하면서 데큐를 관리해 주면 최대 구간의 길이를 알 수 있다. 고려대학교 2017 경시대회. L..

1. 제로스택을 구현하면 되는 단순한 문제입니다. 2. 공항비행기가 올 때 공항 게이트를 골라야 하는 데, 각 상황에서 고를 수 있는 공항 게이트 중 가장 큰 것을 골라야 한다는 그리디 접근을 생각해 볼 수 있습니다. 그 위치를 비워두면서 도착하는 비행기의 수를 늘릴 수 없기 때문입니다. ($i$번째 비행기가 비워둔 자리가 끝까지 비었다면 비우는 의미가 없으니 모순입니다. 그렇지 않다면, 비워둔 자리를 다른 비행기 ($j$번째, $j > i$)가 채울 것인데, 그렇게 하느니 $i$번째 비행기와 위치를 바꾸는 것이 이득입니다. 이런 식으로 계속 진행하면 그리디 알고리즘이 최적임을 증명할 수 있습니다.) 이 알고리즘을 그대로 구현하면 $O(PG)$ 시간이 걸려 시간 초과가 납니다.이를 해결하는 방법은, st..

ARC074 D. Lotus Leaves전형적인 Minimum cut 문제이다. 결국 문제에서 연결하라고 하는 대로 연결 하면 그래프가 나오고, 할 수 있는 것은 그 그래프에서 정점을 제거하는 것이다. 고로, 그래프에서 S / T를 제외한 최소 몇개의 정점을 제거해야 S - T로 가는 경로가 없는지를 구해야 한다. Minimum cut 문제는 몇개의 간선을 제거하냐는 문제인데, 정점 제거 역시 쉽게 간선 제거로 환원할 수 있다. $in(i) -> out(i)$ 로 가는 유랑 1의 간선을 만들어주고, 간선은 끊지 못하게 ($\infty$ 유량) 을 주면 되기 때문이다. 옛날에 글로도 썼다. 시간 복잡도는 $O(N^2M^2)$. ARC075 D. Mirrored내 풀이가 약간 이상했었던.. 시간 제한을 간신..

(2017.04.01 초본) 집나간 PS실력을 살리기 위해 앳코더 문제를 풀어보려고 한다. 일단 제일 어려운 것만...(실제로는 저대로 안 썼습니다. 스샷 다시 찍기 귀찮아서)이 스크립트가 제대로 작동하는 가장 옛날 라운드인 ARC035부터 돌기로 했다. (그전에는 _4 로 suffix를 붙인듯) + Grand Contest F를 추가했다. 진짜 다 풀 수 있을까 (...) + (2018.01.17 : 오랫동안 동결된 걸 보고 역시 현실성이 없다는 걸 깨달았습니다 (...) 문제를 쓰는 것 뿐만 아니라 제대로 된 풀이까지 써야 해서 더 부담이 됐던 것 같습니다. 번역이 안 된 ARC를 제외하고는 전부 리스트에서 삭제했습니다. 여기 있는 ARC 정도만 클리어하는 걸 목표로 하겠습니다. 여기 원래 적혀있던 ..