PS/BOJ
-
[BOJ] 13557 수열과 쿼리 10PS/BOJ 2020. 9. 12. 13:21
https://www.acmicpc.net/problem/13557 13557번: 수열과 쿼리 10 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. x1 y1 x2 y2: x1 ≤ i ≤ y1, x2 ≤ j ≤ y2, i ≤ j인 모든 (i, j)에 대해서 Ai + ... + Aj의 최댓값을 출력한다. www.acmicpc.net 알고리즘: Segment tree 시간복잡도: $O(N+MlogN)$ $A_i+...+A_j$의 최댓값을 구하는 것은 DP로 $O(N)$만에 해결이 가능하다. 다만 이 문제에선 주어지는 구간마다 최댓값을 구해줘야 한다. 쿼리 개수가 많으므로 $O(N)$이 아니라 그보다 더 빠른 시간안에 해결해야 한다. 따라서 seg..
-
[BOJ] 13553 수열과 쿼리 8PS/BOJ 2020. 9. 7. 23:28
https://www.acmicpc.net/problem/13553 13553번: 수열과 쿼리 8 길이가 N인 수열 A1, A2, ..., AN과 정수 K가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. l r: l ≤ i < j ≤ r이면서 abs(Ai - Aj) ≤ K인 (i, j) 쌍의 개수를 출력한다. www.acmicpc.net 알고리즘: Mo's, Fenwick tree 시간복잡도: $O((N+M)\sqrt NlogN)$ $|A_i-A_j|\le K$를 풀어쓰면, $A_i-K\le A_j \le A_i+K$가 된다. Mo's 로 접근해보면, $A_i$를 추가 및 삭제를 할 때 위 구간을 만족하는 $A_j$의 개수를 더해주거나 빼주면 된다. 특정 범위를 만족하는 수의 개수를 구하..
-
[BOJ] 13548 수열과 쿼리 6PS/BOJ 2020. 9. 7. 23:10
https://www.acmicpc.net/problem/13548 13548번: 수열과 쿼리 6 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다. www.acmicpc.net 알고리즘: Mo's 시간복잡도: $O((N+M)\sqrt N)$ 모스 알고리즘을 배우면서 풀어본 문제이다. 모스 알고리즘을 이용하면 데이터를 추가 및 삭제를 하는데 $O(1)$ 만에 해결할 수 있고, 포인터 이동(?)을 하는데 최대 $(N+M)\sqrt N$이므로 제한 시간 내 해답을 구할 수 있다. 답을 구하는데 필요한 배열은 총 2개이다. 1. $cnt[x]:$ $A_i=..
-
[BOJ] 16903 수열과 쿼리 20PS/BOJ 2020. 9. 7. 22:31
https://www.acmicpc.net/problem/16903 16903번: 수열과 쿼리 20 첫째 줄에 쿼리의 개수 M(1 ≤ M ≤ 200,000)이 주어진다. 둘째 줄부터 M개의 줄에 쿼리가 주어진다. 입력으로 주어지는 x의 범위는 109보다 작거나 같은 자연수이다. 3번 쿼리는 하나 이상 주어진다. www.acmicpc.net 알고리즘: Trie 시간복잡도: $O(Mlog10^9)$ 접근: M이 20만으로 꽤 크다. 따라서 매 쿼리마다 빠른 시간 안에(log) 해결해야한다. 여기서 주요 연산이 XOR 라는 것에 주목했다. 어차피 문제가 되는건 3번 쿼리다. (1, 2번은 단순 추가/삭제니...) A에 있는 모든 원소와 XOR 연산을 하고 최댓값을 구해야한다. 두가지 관찰만 하면 풀이에 쉽게 ..
-
[BOJ] 13547 수열과 쿼리 5PS/BOJ 2020. 8. 31. 00:34
https://www.acmicpc.net/problem/13547 13547번: 수열과 쿼리 5 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다. www.acmicpc.net 알고리즘: Merge sort tree 시간복잡도: $O(NlogN+Mlog^2N)$ 접근: [l, r] 구간에 속하는 $A_i$ 중 서로 다른 수의 개수를 구하는 문제이다. 매 쿼리마다 [l, r] 을 모두 살펴보면 $O(MN)$으로 TLE를 받게 된다. 따라서, 어떻게 하면 중복되는 $A_i$들의 값을 걸러낼 수 있을지 생각해봐야한다. 당연히 $A_i$의 값 그대로 세그먼트 트리에 ..
-
[BOJ] 16978 수열과 쿼리 22PS/BOJ 2020. 8. 24. 20:32
https://www.acmicpc.net/problem/16978 16978번: 수열과 쿼리 22 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v: Ai = v로 변경한다. 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다. www.acmicpc.net 알고리즘: Segment tree, Offline query 시간복잡도: $O((N+M)logN+MlogM)$ 접근: 2번 쿼리를 보면, 'k번째 1번 쿼리까지 적용되었을 때' 라는 문구를 볼 수 있다. 이걸 보면 쿼리들을 k 순서로 정렬하는 offline query를 쓰면 되겠구나 라고 생각할 수 있다. 쿼리들을 k에 대한 오름..
-
[BOJ] 16975 수열과 쿼리 21PS/BOJ 2020. 8. 24. 20:22
https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 알고리즘: Segment tree 시간복잡도: $O(MlogN)$ 접근: 이 문제는 분류를 보니 lazy propagation에 속해있던데 굳이 쓰지 않아도 쉽게 풀리는 문제다. 쿼리가 구간에 대해 묻는게 아니라 단순히 $A_x$를 출력하는거라서... [l, r]에 k를 더하는 것을 segment tree에서 [l, r] 구간을 대표하는 노드에 k 값을 더해준 후, $A_x$ ..