알고리즘 공부방

문제 https://codeforces.com/contest/482/problem/B 길이 N의 배열에 l~r 구간에 대해 모든 값들을 & 한 결과값들이 m개 주어져 있을 때, 이 모든 조건을 만족하는 배열을 구하는 문제이다. 풀이 bitwise 연산이 들어간 문제의 대다수는 각 비트를 따로 생각해주면 풀리는 경우가 많다. 이 문제도 n번째 칸의 i번째 비트가 켜져 있는지, 꺼져 있는지 각각 구해주자. 만약 l~r 까지의 & 값이 켜져 있다는 말은, l~r 의 i번째 비트는 모두 다 켜져 있다는 뜻이다. 따라서 먼저 모든 m을 보며 l~r의 i번째 비트를 켜준다. 그 후에 켜져 있지 않은 비트는 무조건 꺼져 있다고 생각해도 답에 영향을 미치지 않는다. 마지막으로 꺼져 있는 비트에 대해서 검사를 하며, l..

문제 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..

기본적인 세그먼트 트리는 구간에 대한 쿼리와, 특정 값을 업데이트하는 연산밖에 안된다. 만약 구간에 대해 업데이트 하는 연산이 필요하다면 Lazy Propagation 을 사용해야 한다. 간단한 원리는 업데이트해야하는 구간에 완전히 속한 노드들에게 lazy 값을 올려준 후, 나중에 그 노드를 방문할 때가 됬을때 lazy 값을 꺼내서 실제 값에 업데이트 해주는 방식이다. *더 구체적인 설명은 https://www.acmicpc.net/blog/view/26을 참고한다. struct SEG { int n; vector tree, lazy; SEG() {} SEG(int n) : n(n), tree(n*4+10), lazy(n*4+10) { init(1, 1, n); } void init(int node, i..

문제 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..

세그먼트 트리와 매우 비슷하지만, 구현이 훨씬 간단한 펜윅 트리(Fenwick Tree) 에 대해 알아보자. 펜윅 트리도 구간 수정과 쿼리를 수행할 수 있지만, $1$~$i$ 까지의 구간에 대해서만 연산할 수 있다. 때문에 보통은 누적합에 대한 쿼리와 수정 연산에 사용된다. 펜윅 트리의 동작 과정에 대한 간략한 설명만 하고 자세한 설명은 생략한다. *https://www.acmicpc.net/blog/view/21 *https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/ 위 그림과 같이 BIT 에서의 배열의 각 칸은 자신으로부터 이진수 표현의 마지막 비트 전까지의 구간을 의미한다. struct BI..

트리에서의 지름이란, 트리에서 가장 멀리 떨어진 두 점 사이의 거리를 구하는 문제이다. 2가지 솔루션이 있고, 2개 모두 알아두도록 하자. SOL 1) 전체적인 알고리즘은, 1. 임의의 한 점으로부터 제일 멀리 떨어진 점을 잡고, (A) 2. 그 점으로부터 제일 멀리 떨어진 점을 잡는다. (B) 이때 A, B는 지름을 구성하는 요소이다. => dfs 2번으로 답을 구한다. 더보기 만약 A가 지름을 구성하는 두 점중 하나가 맞다면 2는 자명하다. 따라서 A가 지름을 구성하는 점임을 보여 보자. (귀류법) 임의의 정점에서 제일 멀리 떨어진 점 X를 잡았는데, 그 점이 지름 A, B 모두 아니라 하자. 위 그림에서 루트 R과 제일 멀리 떨어진 점 X를 골랐다 하자. (X!=A, X!=B) 1. 지름이 루트를 ..

엄청나게 중요한 자료구조인 세그먼트 트리에 대하여 알아보고 가자. 세그먼트 트리의 목적은 구간에 대한 질의와 수정을 빠르게 하는 것이다. 아이디어는 다음과 같다. 구간 트리의 루트는 배열의 전체 구간인 [1, n]을 표현하며, 그 왼쪽 노드는 [1, mid], 오른쪽 노드는 [mid+1, n]을 포함하게 함으로서 재귀적으로 구간에 대한 정보를 이진 트리에 저장한다. 만약 구간에 대한 쿼리가 떨어진다면 그 쿼리의 구간에 해당하는 노드들을 몇개 잡아 그 그 부분에 대해서만 계산하면 된다. 세그먼트 트리 자체의 원리에 대한 자세한 내용은 다른 블로그나 종만북을 복습하도록 하고, 구현과 시간복잡도에 초점을 맞춰 보자. *세그먼트 트리의 이론 및 구현 : https://www.acmicpc.net/blog/vie..

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