알고리즘 공부방

문제 https://www.acmicpc.net/problem/1507 어떤 그래프에서의 임의의 두 정점 간의 최단거리가 모두 주어졌을 때, 조건을 만족하며 간선의 개수를 최소화할 수 있는 그래프를 찾는 문제이다. 풀이 기본적인 풀이는 $N^2$ 개의 간선을 모두 생성한 후, 필요 없는 간선을 하나씩 지워 가며 문제를 해결한다. 그렇다면 과연, 필요 없는 정점을 어떻게 구할 수 있을까? u->v 의 간선을 삭제하기 위해서는 u->w->v 의 경로와의 거리와 비교해 볼 필요가 있다. 1) adj[u][v]v 의 간선을 삭제해서는 안된다. u->v 의 최단거리는 다른 경유점을 거쳐 가면 안됀다는 뜻이기 떄문이다. 2) adj[u][v]==adj[u][w]+adj[w][v] u->v 의 간선을 굳이 놔둘 필요..

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

문제 https://www.acmicpc.net/problem/1395 스위치 n개에 대하여 특정 구간의 스위치를 모두 반전시키거나, 구간에 있는 켜져 있는 스위치의 수를 세는 쿼리를 해결하는 문제이다. 풀이 세그먼트 트리를 이용한다. 세그먼트 트리의 각 노드가 해당 구간의 켜져 있는 스위치들의 수를 갖고 있다면, 2번째 쿼리는 쉽게 해결할 수 있다. 문제는 첫번째 쿼리가 하나의 스위치를 반전시키는 것이 아니라, 특정 구간의 모든 스위치들을 반전시키는 것이다. 따라서 세그먼트 트리 레이지 프로파게이션을 사용해야 한다. 레이지 배열에는 그 구간에 대한 반전 연산이 적용되었는가 여부를 저장한다. 구간합에 대한 레이지처럼 구간 업데이트를 할 때 자신이 완전히 속한 노드에 대해서, 레이지값을 자식들에게 넘겨주며..

문제 https://www.acmicpc.net/problem/2243 i번째 맛의 사탕을 추가/삭제 하는 쿼리와, 상자 안에 들어있는 사탕들 중 k번째로 맛있는 사탕을 뽑는 쿼리를 처리하는 문제이다. 풀이 각 사탕의 맛을 인덱스로 하는 펜윅 트리로 쿼리를 처리한다. 펜윅 트리는 추가/삭제 쿼리를 $O(logN)$ 안에 할수 있다. 두번째 k번째 사탕을 뽑는 쿼리는 1~i까지의 사탕의 개수에 대해서 이분탐색을 해주면 된다. 사탕의 개수를 묻는 쿼리가 $O(logN)$, 이분탐색이 $O(logN)$ 이므로 2번째 쿼리를 $O(log^2N)$ 안에 처리해 줄수 있다. 시간 복잡도 : $O(Qlog^2N)$ #include using namespace std; typedef long long ll; typed..

문제 https://www.acmicpc.net/problem/3653 1~n까지의 영화가 순서대로 쌓여 있을때 i번째 영화 위의 영화의 개수를 출력하고, i번째 영화를 맨 위로 올려놓는 과정을 반복하는 문제이다. 풀이 문제 설명 그대로 시뮬레이션을 하면 된다. N+M개의 칸을 준비해놓고, 영화는 마지막 N개 칸에 모두 넣어 놓은 다음, 하나씩 앞의 칸으로 옮겨 준다. 이때 각 영화 위의 영화 수를 찾아내기 위해서 펜윅 트리의 구간합을 사용한다. 시간 복잡도 : $O((N+M)lg(N+M))$ #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int MAXN = 1e5; struct BI..

문제 https://www.acmicpc.net/problem/7578 문제를 변형해보면 "Inverse의 수를 세는 문제"로 바꿀 수 있다. 풀이 세그먼트 트리나 BIT 를 사용할 때 많은 경우에 좌표 압축하여 해싱 느낌으로 사용한다. Inverse 의 수를 셀 때도 각 값을 볼때마다, 자기 전에 나온것들 중, 자신보다 큰 것들의 갯수를 카운팅 해준다. 각 수를 인덱스로 하는 배열을 생각해 보면, 각 수를 볼때마다 1. arr[i]~n 까지의 칸들중 등장한 칸의 개수를 세어 준다. -> arr[i]~n 구간의 합을 구한다. 2. arr[i]번 칸에 체크를 해 준다 -> arr[i] 칸에 1을 업데이트 해준다. 두 연산 모두 BIT 연산으로 처리 가능하다. 시간복잡도 : $O(NlogN)$ #includ..

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