알고리즘 공부방

문제 https://oj.uz/problem/view/JOI19_examination 문제 보기 - Examination (JOI19_examination) :: oj.uz 문제 보기 - Examination (JOI19_examination) oj.uz N개의 $(x, y)$점이 들어오고, Q개의 $(a, b, c)$쿼리가 들어온다. 쿼리의 의미는 $x>=a, y>=b, x+y>=c$를 만족하는 점들의 수를 세는 것이다. $N

문제 https://oj.uz/problem/view/IOI19_shoes 문제 보기 - Arranging Shoes (IOI19_shoes) :: oj.uz 문제 보기 - Arranging Shoes (IOI19_shoes) oj.uz 왼쪽 신발과 오른쪽 신발이 여러 개 있고, 각 신발마다 크기가 같은 신발끼리만 짝을 맞출 수 있다. 처음에는 신발들이 막 아무렇게나 섞여 있을 때, 이 신발들을 짝이 맞는 신발들끼리 붙어 있으며, 같은 짝에서는 왼쪽 신발, 오른쪽 신발 순서대로 배열해야 한다. 사용할 수 있는 연산은 인접한 두 신발을 swap하는 연산일 때, 연산의 최소 횟수를 구한다. ($N

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

세그먼트 트리와 매우 비슷하지만, 구현이 훨씬 간단한 펜윅 트리(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..