본문 바로가기

알고리즘

병렬 이분 탐색(Parallel Binary Search) 주어진 문제의 답이 단조성을 갖는 경우에는 Parametric Search를 이용하여 해당 문제를 해결할 수 있다. Parametric Search에 대해서 이미 잘 알고 있다면 스크롤을 아래로 내리자. 예를 들어 "N명의 사람이 나이순으로 정렬되어 있을 때, 20세 이상이면서 나이가 가장 작은 사람의 나이를 구하시오"와 같은 문제가 있다고 하자. 앞에서부터 다 확인한다면 O(N)의 시간이 걸리게 되지만, Parametric Search를 이용하면 O(logN)만에 해결할 수 있다. 먼저, 답이 될 수 있는 범위의 중간지점을 확인한다. 19는 20세 미만이므로 답이 될 수 없다. 그러면 현재 위치보다 왼쪽에 있는 나이들은 당연히 19 이하이기 때문에 답이 될 수 없다. 따라서 왼쪽은 더 이상 볼 필요가 ..

[BOJ 1396] 크루스칼의 공 [문제] https://www.acmicpc.net/problem/1396 1396번: 크루스칼의 공 첫째 줄에는 그래프의 정점의 개수 n과 간선의 개수 m이 주어진다. 그리고 두 번째 줄에서 m+1번째 줄까지는 a b c의 형태로 a와 b를 잇는 간선의 고유값이 c라는 의미이다. m+2번째 줄에는 알고 싶은 www.acmicpc.net [난이도] - Platinum I (21.06.10 기준) [필요 개념] - Union-Find - Parallel Binary Search (병렬 이분 탐색) or LCA [풀이] 이 문제는 크게 두 풀이로 나뉜다. 첫 번째로는 PBS(병렬 이분 탐색)이다. 흔히 PBS의 대표 예제 문제로 알려져 있는데, 조만간 PBS에 대한 글을 따로 작성할 예정이라 자세한 풀이는 ..

Platinum DP 문제들 풀이 (1) 요즘 DP에 약한 기분이 많이 들어서, 플래티넘 DP 문제 중 특별한 기법이나 최적화를 이용하지 않는 문제들을 푼 사람 수로 정렬해서 안 푼 문제들을 선별하여 조금씩 풀고 있다. 푼 사람 수로 정렬한 문제라 이미 남들에겐 웰논일지도 모른다. 많이 풀린 문제들답게 플래티넘임에도 불구하고 꽤 잘 풀리는 것도 있는 반면 해설 없이는 못 풀었을 문제들도 많았다. 아마 DP라는 걸 모르고 풀었다면 체감 난이도가 훨씬 높았을 것 같다. [BOJ 1126] 같은 탑 (Platinum III) N = 50개의 블록을 이용하여 높이가 같은 두 개의 탑을 만든다. 모든 블록을 사용할 필요는 없으며, 각 블록의 높이는 최대 50만이고, 모든 블록의 높이의 합이 50만 이하이다. 이때, 만들 수 있는 탑의 높이의 최댓값을 구..

PS를 위한 정수론 - (4) 이항 계수 (nCr mod P) 구하는 다양한 방법 이항 계수 $_{n}C_r$을 소수 $p$로 나눈 나머지를 빠르게 구하는 다양한 방법들을 알아보자. 기본적으로 특정 $n$과 $r$에 대해서 이항 계수 $_{n}C_r$을 구하는 시간은 $O(1)$이 되어야 할 때, 즉, 많은 쿼리가 들어와도 문제가 없는 경우를 고려한다. 지금부터 소개하는 방법들의 시간복잡도는 전처리하는데 필요한 시간을 의미한다. 너무 작은 $n$과 $r$에 대해서 직접 분자와 분모를 모두 곱하는 경우는 생략한다. 1. $O(n^2)$ www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 파스칼의 삼각형을 이용하는 ..

PS를 위한 정수론 - (3) 페르마의 소정리와 활용 (이항 계수, 밀러-라빈) [목차] 1. 페르마의 소정리 2. 오일러 정리 3. 활용 1) 이항 계수 nCr 빠르게 구하기 4. 활용 2) 밀러-라빈(Miller-Rabin) 소수 판별법 1. 페르마의 소정리 (Fermat's little theorem) 페르마의 소정리는 다음과 같다. "소수 $p$와 정수 $a$에 대해서 $a^p \equiv a \; (mod\;p)$" 만약 $a$와 $p$가 서로소이면 $a^{p-1} \equiv 1 \; (mod \;p)$ 를 만족한다. 짧지만 생각보다 PS에서 되게 많이 사용되므로 꼭 알아두는 것이 좋다. 증명 과정은 수학적 귀납법을 이용한다. (이 블로그를 참고했다) 먼저, $a$가 $p$ 이상이면, modular의 성질에 의해서 $p$로 나눈 나머지로 계산해도 동일하므로, $0 \leq..

USACO 2020 US Open Contest [Bronze] 풀이 1. [BOJ 18880] Social Distancing I Gold V [문제 설명] 일렬로 N개의 공간이 있고, 각 공간은 소가 들어있거나(1) 들어있지 않다(0). 그리고 빈 두 공간을 골라 소를 넣어주는데, 이때 소가 들어있는 두 공간 사이의 간격의 최솟값을 D라고 하면 D가 최대가 되어야 한다. [풀이] Case work 문제이다. 경우들을 잘 처리해주어야 한다. 지금부터 말하는 '구간'은 소가 배정되어있지 않은 연속된 공간을 의미한다. 우선, 가장 긴 구간에서 하나를 뽑아서 구간을 나눈 후, 다시 가장 긴 구간에서 하나를 뽑는 것이 최적일 것이라고 생각할 수 있다. 하지만 이 문제에서는 공간을 두 개 고르기 때문에 단순히 이 방식으로는 D를 최대로 만들지 못한다. 예를 들어 1, 10, 13..

PS를 위한 정수론 - (2) 유클리드, 확장 유클리드 호제법 [목차] 1. 유클리드 호제법 2. 확장 유클리드 호제법 3. 모듈러(modular) 연산에서의 곱셈의 역원 4. 예시 문제 1. 유클리드 호제법 유클리드 호제법은 정수론을 조금이라도 공부했다면, 혹은 공부하지 않았더라도 충분히 들어봤을 것이다. 유클리드 호제법은 자연수 $a$, $b$ 가 주어졌을 때, $gcd(a, b)$ 즉, $a$와 $b$의 최대 공약수를 구하는 방법이다. $a$를 $b$로 나눈 몫을 $q$라고 하고, 나머지를 $r$이라고 하면 $a = bq + r$ 로 나타난다. 이때, $gcd(a, b) = gcd(b, r)$을 만족한다. 이유는 $gcd(a, b) = g$라고 하면, $g|a$, $g|b$ 를 만족하게 되고, $r = a - bq$이므로 $g|(a - bq) = r$ 을 만족..

PS를 위한 정수론 - (1) 에라토스테네스의 체 활용 기본적인 '에라토스테네스의 체' 개념을 아직 모른다면 wogud6792.tistory.com/46 글을 먼저 읽는 것을 추천한다. 크게 어렵지는 않다. 그렇다면 이제 이 에라토스테네스의 체를 활용하는 여러 가지 방법들을 알아보자. 1. 각 2부터 n까지의 자연수 k에 대해, "k가 갖는 가장 작은 소인수"를 계산하는 방법 이는 사실 매우 간단하다. 에라토스테네스의 체 원리를 생각해보면 현재 수가 아직 걸러지지 않았다면 소수이고, 현재 수의 배수들을 제거해나가는 방식이다. 이때, 제거되는 수는 합성수이고 제일 처음 제거될 때 이용되는 소수가 $k$가 갖는 가장 작은 소인수이다. int prime[1000001]; int main(void) { int N = 1000000; for (int i = 1; i

이전 1 2 3 4 ··· 7 다음

티스토리툴바