본문 바로가기

728x90
반응형

PS

병렬 이분 탐색(Parallel Binary Search) 주어진 문제의 답이 단조성을 갖는 경우에는 Parametric Search를 이용하여 해당 문제를 해결할 수 있다. Parametric Search에 대해서 이미 잘 알고 있다면 스크롤을 아래로 내리자. 예를 들어 "N명의 사람이 나이순으로 정렬되어 있을 때, 20세 이상이면서 나이가 가장 작은 사람의 나이를 구하시오"와 같은 문제가 있다고 하자. 앞에서부터 다 확인한다면 O(N)의 시간이 걸리게 되지만, Parametric Search를 이용하면 O(logN)만에 해결할 수 있다. 먼저, 답이 될 수 있는 범위의 중간지점을 확인한다. 19는 20세 미만이므로 답이 될 수 없다. 그러면 현재 위치보다 왼쪽에 있는 나이들은 당연히 19 이하이기 때문에 답이 될 수 없다. 따라서 왼쪽은 더 이상 볼 필요가 ..
Atcoder Beginner Contest 206 (ABC 206) 풀이 A. Maxi-Buying 단순 계산 문제이다. N을 입력받고, 1.08*N을 정수단위로 올림 했을 때 206과 대소 비교하는 문제이다. #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); double n; cin >> n; n *= 1.08; int ans = (int)n; if (ans == 206) cout = n) { cout > n; map mp; for (int i = 0; i < n; i++) { int a; cin >> a; mp[a]++; } ll ans = 0; for (auto [a, b] : mp) { ans += 1LL * b * (..
[Codeforces] Round #559 (Div. 2) A ~ E 풀이 21.03.05 23:35 virtual 참가 / performance = 2391 A. A pile of stones (*800) +가 주어질 때는 돌이 1개 증가하고, -가 주어질 때는 돌이 1개 감소한다. 처음에 보유할 수 있는 돌은 임의로 정할 수 있고, 중간에 돌이 0개일 때 -가 들어오면 안 될 때, 최종적으로 가능한 최소 돌의 개수를 구하는 문제이다. 처음의 돌 수를 직접 정할 수 있으므로, 단순하게 -가 들어오는 경우, 만약 현재 돌이 0개이면 그대로 유지시켜주면 된다. 이 과정이 결국 처음의 돌 수를 1개 증가시키는 과정과 동일하다. [소스 코드] #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin..
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..
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
Codeforces Round #690 (Div. 3) 풀이 A. Favorite Sequence 입력으로 문제의 그림과 같이 위치가 바뀐 수열이 들어온다. 다시 원래의 수열을 출력해주면 된다. (처음엔 바뀐 수열을 출력하라는 줄 알았다. 꽤나 비슷한 실수를 한 사람들이 많은 것 같다) #include using namespace std; int A[301]; int main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int T; cin >> T; while (T--) { int n; cin >> n; for (int i = 1; i > A[i]; for (int i = 1; i
Atcoder Beginner Contest 185 (ABC 185) 풀이 [문제 링크] atcoder.jp/contests/abc185 AtCoder Beginner Contest 185 - AtCoder AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp [풀이] A. ABC Preparation 각 점수별로 문제 수가 나와있고, 하나의 문제 set을 만들기 위해서는 점수별로 하나씩 문제가 필요하다. 따라서 네 정수 중 최솟값을 출력하면 된다. #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(n..
[BOJ 5670] 휴대폰 자판 [문제] www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net [난이도] - Platinum III (solved.ac 20.12.13 기준) [필요 개념] - 트라이 (Trie) [풀이] 자동 입력이 되는 순간은 현재 노드에서 끝나는 문자열이 없으면서, 자식 노드가 하나밖에 없는 경우이다. 따라서 트라이를 생성할 때 자식의 수를 저장해두고, 문자열을 탐색할 때 자식의 수가 둘 이상이거나, 현재 노드에서 끝나는 다른 문자열이 있고 자식의 수가 1이면 버튼을 눌러줘야 하..