상위 99.99%의 PS

https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 간선의 개수를 최소로 해서 모든 정점을 잇는 그래프는 트리이고, 이때 간선의 개수는 N - 1 개이다. 간선의 정보는 사용할 필요가 없다. 템플릿 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41..

https://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 Lazy Propagation in Segment Tree 1번 쿼리는 (ax + b) * 1 + v = ax + b + v 2번 쿼리는 (ax + b) * v + 0= (v * a)x + v * b 3번 쿼리는 (ax + b) * 0 + v = v 꼴로 갱신할 수 있다. 곱하는 값, 더하는 값에 대해..

https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net Lazy Propagation 기초 문제이다. 모른다면 읽고 오자. https://m.blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=kks227&logNo=220824350353 기존 세그먼트 트리의 방식으로라면 갱신 하나에 O(NlgN)이라는 시간이 걸려 총 O(MNlgN)이라..

https://www.acmicpc.net/problem/18937 18937번: 왕들의 외나무다리 돌게임 길이 6짜리의 외나무다리에 흰 돌이 3번 칸에 있고, 검은 돌이 5번 칸에 있으면, 흰 돌은 1, 2, 4번 칸 중 하나로 이동할 수 있으며, 검은 돌은 4, 6번 칸 중 하나로 이동할 수 있다. 돌을 상대 돌로 www.acmicpc.net 외나무다리의 길이가 n이면, 그런디 수는 n - 2이다. 여기서 뒤로 가는 것은 승패에 영향을 끼치지 않으므로, 그냥 xor해주면 끝이다. 코드 bo 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def ip(): return int(input()) def sp(): return str(input().rstrip()) def m..

https://www.acmicpc.net/problem/11871 11871번: 님 게임 홀짝 koosaga와 cubelover가 님 게임 홀짝 버젼을 하고 있다. 님 게임은 돌을 차곡 차곡 위로 쌓아올린 돌 더미 k개를 이용한다. 각각의 돌 더미에는 한 개 이상의 돌이 있다. 두 사람은 서로 턴을 번갈아가 www.acmicpc.net 노트에 8정도까지만 써보면 규칙이 보인다. 홀수면 (i + 1) / 2, 짝수면 (i - 2) / 2이다. 모두 xor해서 승자를 찾으면 끝이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def ip(): return int(input()) def sp(): return str(input().rstrip()) def mip(): return ..

https://www.acmicpc.net/problem/8462 8462번: 배열의 힘 자연수 \(n\)개로 이루어진 배열 \(a_1,a_2,a_3,\dots ,a_n\)이 있다. \(l\)부터 \(r\)까지 부분 배열은 \(a_l,a_{l+1},\dots , a_r\) 이다. \(K_s\)는 부분 배열 안에 있는 자연수 \(s\)의 개수이다. 부분 배열의 힘이란 www.acmicpc.net [사용한 알고리즘] Mo's Sqrt Decomposition 엄청 신기하고 강력한 기술인 모쓰, 제곱근 분할법 기초문제이다. 모른다면 보고 오자. 진짜 별거 없지만, 오프라인 쿼리 문제에서 잘 써먹을 수 있다. https://justicehui.github.io/hard-algorithm/2019/06/17/Mo..

https://www.acmicpc.net/problem/15520 15520번: Prime-Factor Prime A positive integer is called a "prime-factor prime" when the number of its prime factors is prime. For example, 12 is a prime-factor prime because the number of prime factors of 12 = 2 × 2 × 3 is 3, which is prime. On the other hand, 210 is not a prime-f www.acmicpc.net [사용한 것] 에라토스테네스의 체 1. 나누려는 소수 \(i\)의 범위 정하기 어떤 수가 소수인지 확인하는 방법..

https://www.acmicpc.net/problem/17408 17408번: 수열과 쿼리 24 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오 1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 l r: l ≤ i

https://www.acmicpc.net/problem/13544 13544번: 수열과 쿼리 3 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 정렬된 배열 \(A\)가 있다고 하자. 이 \(A\) 내에서 어떤 수 \(k\)보다 큰 수의 개수를 \(O(N)\)보다 빠른 시간에 구하려면, 이진 탐색을 사용하여 \(O(lgN)\)에 구할 수 있다. 그런데 이 문제는 배열이 정렬되어 있지 않고, 그리고 구간을 나누어 쿼리에 답하라고 한다. 만약, 배열을 잘 잘라서 정렬된 상태로 가지고 있으면, 그 잘려진 배열 ..

https://www.acmicpc.net/problem/11574 11574번: CYK의 너무너무 재밌는 그래프 만들기 놀이 N (1 ≤ N ≤ 100)개의 정점의 개수가 주어지고, K (1 ≤ K ≤ 3)개의 가능한 색깔이 주어진다. 각 정점들을 1 부터 N까지 차례로 번호를 매기고, 그 정점들에 K개의 색깔중 하나를 임의로 부여한다. www.acmicpc.net 간단한 DP k = 1일때 무조건 1가지이다. k = 2일때 맨 뒤에 색 1 추가, 혹은 색 2를 추가하는 경우가 있다. \(dp[n][k] = n번째에서 색 1을 k개 사용하였을 때, 경우의 수\) 라고 하자. 색 1을 붙일 때: 간선을 잇는 경우는 색 2의 개수이고, 잇지 않는 경우는 1가지이므로, \(dp[n - 1][k - 1] * ..