알고리즘 공부방

문제 https://oj.uz/problem/view/JOI19_ho_t5 문제 보기 - Unique Cities (JOI19_ho_t5) :: oj.uz 문제 보기 - Unique Cities (JOI19_ho_t5) oj.uz 트리가 주어지고, 각 정점에 색이 칠해져 있을 때, 정점 $x$에 대한 unique한 정점 $y$를 다음과 같이 정의한다. $x$와 $y$의 거리가 $d$일 때 $x$에서 거리가 $d$인 $y$가 아닌 다른 정점 $z$가 존재하지 않는다. 각 정점에 대해, unique한 정점들의 서로 다른 색들의 개수를 구해야 한다. $M=dep-H[now]) cnt[V.back().second]--, V.pop_back(); if(chk[now]) ans[now]=V.size(); } els..

문제 https://oj.uz/problem/view/IOI19_rect 문제 보기 - Rectangles (IOI19_rect) :: oj.uz 문제 보기 - Rectangles (IOI19_rect) oj.uz N*M 크기의 격자가 들어올 때, 다음 조건을 만족하는 직사각형의 개수를 세야 한다. $2

문제 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. 나와 그 소 사이의 모든 소는 나보다 작아야 한다. 이것을 어떻게 이용할 수 있을까? 한번 손으로 직접 그 수열에서 각 소가 보여지는 소들의 리스트를 만들어 보면, 내림차순이 됨을 알 수 있다. 이제 이것을 이용하여 이미 ..