알고리즘 공부방

https://apio2019.ru/https://oj.uz/problems/source/389https://koosaga.com/232 내가 참가한 첫번째 apio 대회이다. 대회 결과는... 30점으로 매우 참혹한 점수가 나왔다.나는 대회시간에 device 를 읽고 어려운 수학문제라 판단하여 기본적인 부분점수만 긁고 풀지 않았는데, 이것이 가장 쉬운 문제였다. 대신 나는 마지막 문제였던 lamps에 모든 시간을 쏟아부었고, 결국 완벽한 풀이를 찾은 후 2D segment tree 구현, 경로압축까지 구현을 끝냈는데 MLE가 나서 결국 이것도 섭태밖에 긁지 못했다. 나중에 다시 풀어보니 경로압축 없이 fenwick + dynamic segment tree 하나만 있어도 AC가 나왔다...이번 년도의 문..

문제 https://oj.uz/problem/view/JOI14_scarecrows 문제 보기 - 허수아비 (JOI14_scarecrows) :: oj.uz JOI 마을에 있는 넓은 황무지에는 $N$명의 신성한 허수아비가 서 있어, 주민들은 일 년에 몇 번씩 허수아비를 둘러싸고 축제를 하고 있었습니다. JOI 마을의 촌장은 "허수아비들의 말씀을 들었다"고 주장하며 황무지에 밭을 하나 만들 계획을 세웠습니다. 허수아비들의 말에 따르면 밭은 다음 조건을 충족해야 한다고 합니다. 각 변이 동서 방향 또는 남북 방향으로 놓인 직사각형이어야 합니다. 남서쪽의 꼭짓점과 북동쪽의 꼭짓점에는 허수아비가 서 있어야 합니다. oj.uz 평면 상에 N개의 점들이 주어져 있을때 다음 조건을 만족하는 점들의 순서쌍의 수를 세는..

문제 https://www.acmicpc.net/problem/7626 직사각형 여러개가 주어졌을 때, 그 합집합의 넓이를 구하는 문제이다. 풀이 이 문제에 대한 풀이는 https://codedoc.tistory.com/421 에 매우 자세히 나와 있다. 직사각형들의 x좌표에 대해 직사각형의 왼쪽 변은 +1, 오른쪽 변은 -1을 해주는 이벤트로 생각할 수 있다. 따라서 그러한 이벤트들을 모두 x좌표에 대해 정리한 후 오른쪽으로 쭉 한번 훑어주면서 넓이를 구할 수 있다. 이제 잘 나눈 x좌표들에 대한 구간으로 그 구간 사이의 넓이만 구해주면 된다. x좌표들에 대한 이벤트로 정렬을 때린 후 구간을 나눴으니, 하나의 구간 내에선 구해야 하는 영역의 넓이는 변하지 않는다. 따라서 이벤트들을 잘 관리해주는 자료구..

문제 https://www.acmicpc.net/problem/1725 히스토그램에서 얻을 수 있는 직사각형의 최대 넓이를 구하는 문제이다. 풀이 저번에 Divide & Conquer + Greedy 로 $O(NlogN)$ 에 푼 경험이 있는 문제 이다. 하지만 이 문제의 정해는 $O(N)$ 으로 솔브가 가능하며, 바로 스택을 사용한 라인 스위핑이다. i번째 그래프에 대하여 그 그래프를 최소 높이로 가지는 직사각형은 양 끝에 h[i]보다 낮은 그래프를 가질 수밖에 없다. 이를 이용하여 $O(N^2)$ 도 가능하지만, dnc 보다도 못한 결과가 나온다. 여기서도 전에 사용했던 정보를 재활용하면 풀 수 있다. 만약에 아직 자신보다 높이가 낮은 오른쪽 좌표를 결정하지 못한 그래프들이 있다고 하자. 방금 새로운..

문제 https://www.acmicpc.net/problem/6198 Bad Hair Day 문제로, 자신의 오른쪽에서 자기보다 큰 키의 소가 나오기 전까지 소들의 수를 세주는 문제이다. 풀이 $O(N^2)$ 풀이로는, 각 소를 기준으로 자신보다 높은 소가 나올때까지 카운팅해서 풀 수도 있다. 이럴 땐 한번 관점을 바꾸어 생각해 보자. 나의 입장에서 보이는 소들의 수를 세는 것이 아니라, 내가 보여지는 소들의 수를 셀 수는 없을까? 내가 보여지는 소들은 1. 나보다 뒤에 있으며 2. 나와 그 소 사이의 모든 소는 나보다 작아야 한다. 이것을 어떻게 이용할 수 있을까? 한번 손으로 직접 그 수열에서 각 소가 보여지는 소들의 리스트를 만들어 보면, 내림차순이 됨을 알 수 있다. 이제 이것을 이용하여 이미 ..