PS/BOJ
-
[BOJ] 13172 ΣPS/BOJ 2022. 7. 18. 22:12
https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 알고리즘: 분할정복(제곱) $\frac{S_1}{N_1}+\frac{S_2}{N_2}에서,\\$ $\frac{S_1}{N_1}: a_1 \times b_1^{-1}\ \left(mod\ X\right)\\$ $\frac{S_2}{N_2}: a_2 \times b_2^{-1}\ \left(mod\ X\right)\\$ $\frac{S_1}{N_1}+\frac{S_2}{N_2} : a_1 \times b_1^{-1}\ \left(mod\ X\right)..
-
[BOJ] 5639 이진 검색 트리PS/BOJ 2022. 7. 18. 21:41
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 알고리즘: 트리 순회, 재귀 트리의 전위순회를 후위순회로 바꾸면 AC 좌노드 방문 -> 우노드 방문 -> 방문할 곳이 없으면 자기 자신 출력 구간을 [l, r]로 잡아주고, 왼쪽 자식을 탐색할 때: [l, 부모 노드 값) 오른쪽 자식을 탐색할 때: (부모 노드 값, r] 로 구간이 바뀐다는 이진 트리의 특성을 이용하여 재귀함수 구현 더보기
-
[BOJ] 단계별로 풀어보기 - 최단 경로PS/BOJ 2021. 6. 15. 22:46
https://www.acmicpc.net/step/26 최단 경로 단계 간선을 사용하는 비용과 예산 제약이 있을 때 다이나믹 프로그래밍으로 최단거리를 찾는 문제 www.acmicpc.net 코딩 구현 속도와 베이스를 다지기 위해 백준 단계를 하나씩 다 풀어보는 중 ... 1. 1753 최단경로: https://www.acmicpc.net/problem/1753 Dijkstra 더보기 2. 1504 특정한 최단 경로: https://www.acmicpc.net/problem/1504 주어진 두 정점을 반드시 거쳐야한다 (제약조건) + Dijkstra Dist(u, v) = u ~ v까지 최단 거리 라고 하면, $Dist(1, v_1)+Dist(v_1,v_2)+Dist(v_2,N)$ 또는, $Dist(1,..
-
[BOJ] 수열과 쿼리 13PS/BOJ 2020. 10. 23. 22:43
www.acmicpc.net/problem/13925 13925번: 수열과 쿼리 13 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) 2 x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y www.acmicpc.net 알고리즘: Segtree, Lazy propagation 시간복잡도: $O((N+M)logN)$ 1, 2번 쿼리를 보면 구간에 있는 모든 원소에 특정 값을 연산한다. 따라서, Lazy propatagion을 써야한다는 것을 알 수 있다.' 1, 2번 쿼리를 통해 $a\rightarrow ax+b$로 바꼈다고 생각해보..
-
[BOJ] 13545 수열과 쿼리 0, 13550 수열과 쿼리 7PS/BOJ 2020. 10. 23. 21:15
www.acmicpc.net/problem/13545 13545번: 수열과 쿼리 0 1과 -1로만 이루어져 있는 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 합이 0이면서 가장 긴 연 www.acmicpc.net www.acmicpc.net/problem/13550 13550번: 수열과 쿼리 7 길이가 N인 수열 A1, A2, ..., AN과 정수 K가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. l r: l ≤ i ≤ j ≤ r이면서 (Ai + Ai+1 + ...+ Aj) mod K = 0인 가장 긴 연속 부분 수열의 길이를 www.acmicpc.ne..
-
[BOJ] 13546 수열과 쿼리 4PS/BOJ 2020. 10. 22. 00:25
더보기 https://www.acmicpc.net/problem/13546 13546번: 수열과 쿼리 4 1보다 크거나 같고, K보다 작거나 같은 수로 이루어져 있는 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. l r: max{|x − y| : l ≤ x, y ≤ r and Ax = Ay www.acmicpc.net 알고리즘: Mo's (+ 평방 분할) 시간복잡도: $O((N+M)\sqrt N)$ Mo's 알고리즘과 관련된 문제들을 보면, 구간 [l, r]에서 특정 값이 몇 번 등장하는지를 구하는 문제들이 빈번히 등장한다. push $A_i$: cnt[$A_i$]++ pop $A_i$: cnt[$A_i$]-- 이런 방식으로 말이다. 이를 ..
-
[BOJ] 16979 수열과 쿼리 23PS/BOJ 2020. 9. 12. 18:18
https://www.acmicpc.net/problem/16979 16979번: 수열과 쿼리 23 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. s e: s ≤ i Aj인 (i, j) 쌍의 개수를 출력한다. (1 ≤ s ≤ e ≤ N) www.acmicpc.net 알고리즘: Mo's, Fenwick tree 시간복잡도: $O((N+M)\sqrt NlogN)$ Mo's로 해결하였다. $A_i>A_j$를 구하는 것이므로, $A_i$를 왼쪽에서 추가 혹은 삭제를 할 때는 $A_i$보다 작은 원소의 개수를 더해주거나 빼주고, $A_i$를 오른쪽에서 추가 혹은 삭제를 할 때는 $A_i$보다 큰 원소의 개수를 더해주거나..
-
[BOJ] 13704 수열과 쿼리 11PS/BOJ 2020. 9. 12. 18:03
https://www.acmicpc.net/problem/13704 13704번: 수열과 쿼리 11 길이가 N인 수열 A1, A2, ..., AN과 정수 K가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. l r: l ≤ i ≤ j ≤ r이면서 Ai, Ai+1, ..., Aj를 XOR한 값이 K인 (i, j) 쌍의 개수를 출력한다. www.acmicpc.net 알고리즘: Mo's 시간복잡도: $O((N+M)\sqrt N)$ XOR 연산을 하는 문제다. 아래 두가지 관찰만 하면 쉽게 접근이 가능하다. 1. a ^ a = 0 : 자기 자신을 xor하면 0이 나옴 2. a ^ 0 = a : xor 0을 하면 자기 자신이 나옴 따라서 $a[i]=A_1$^$A_2$^...^$A_i$ 로 두면, $..