mojo's Blog

문제 링크 => 6543번: 그래프의 싱크 (acmicpc.net) 6543번: 그래프의 싱크 각 테스트 케이스마다 한 줄에 걸쳐 bottom(G)의 모든 노드를 출력한다. 노드는 공백으로 구분해야 하며, 오름차순이어야 한다. 만약, bottom(G)가 공집합이면 빈 줄을 출력한다. www.acmicpc.net SCC를 활용한 문제이다. SCC에 대한 vector들의 정보들을 v1, v2, v3, ... ,vt 라고 하자. 이때 v1의 size값이 v1에 존재하는 정점들에 대해서 SCC로 묶인 정점들로만 이동 가능한지를 파악하면 끝이다. 자세한 설명을 위해 예제 입력 1을 살펴보도록 한다. ex) 1 => 3, 2 => 3, 3 => 1 으로 주어진 그래프에 대하여 SCC는 다음과 같이 묶인다. v1 :..

문제 링크 => https://www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 이항 계수 (N K) 를 구하는 문제이다. N, K 값의 범위가 최소 1에서부터 최대 4,000,000 으로 주어지며 테스트케이스는 최대 100,000까지 주어진다. 이항 계수 (N K) = N! / (N-K)!K! 에 대해서 Factorial를 구하는 방법을 생각해보면 O(N) 이 걸리는데 테스트케이스가 최대 100,000까지 주어졌으므로 O(NM), 즉, 시간초과가 난다. 따라서 F..

문제 링크 => https://www.acmicpc.net/problem/20412 20412번: 추첨상 사수 대작전! (Hard) 한 줄에 걸쳐 준표가 좋아하는 소수 m, 참가자들이 정한 Seed, 시연으로 공개된 X1, X2 이 주어진다. 항상 가능한 상황만 입력으로 주어진다. www.acmicpc.net 정수론 문제이다. 이 문제는 특별하게 m값이 소수로 주어지고 나머지 Seed, X1, X2 값은 0보다 크고 m 보다 작은 값으로 주어진다. 이때 a, c를 구하기 위해서 문제에서 주어진 식을 이용해서 a, c를 구해낼 수 있다. X1 = (a * Seed + c) (mod m) X2 = (a * X1 + c) (mod m) 위 식에서 아랫식을 윗 식을 빼주면 다음과 같은 결과를 얻는다. X2 - ..

문제 링크 => https://www.acmicpc.net/problem/14565 14565번: 역원(Inverse) 구하기 집합 Zn을 0부터 n-1까지의 정수 집합이라고 하자. Zn ∋ a, b, c 일 때, (a+b) mod n = 0이면 b는 a의 덧셈역이라고 하고 (a*c) mod n = 1이면 c는 a의 곱셈역이라고 한다. 정수 N, A가 주어졌을 때 Zn에서의 A의 www.acmicpc.net N과 A이 주어질 때, 덧셈에 대한 역원과 곱셈에 대한 역원을 구하는 문제이다. 덧셈의 역원 => A + x = 0 (mod N) 이므로 x = N - A 이다. 이때, 1 Ax = 1 (mod N) 인데 x를 구하는건 쉽지 않다. 따라서 Extended Euclidean Algorithm 을 이용해..

ax + by = gcd(a,b) 에 대해서 gcd(a,b), x, y 를 구하는 방법 a = bq + r 이라고 할 때, q는 a를 b로 나눈 quotient, r는 a를 b로 나눈 remainder 이다. 위에 있는 식을 ax + by = gcd(a,b) 를 대입하면 bx' + ry' = gcd 와 같이 변형이 가능하다. 따라서 gcd(a, b) = gcd(b, r) 를 얻는다. (a, b) => (b, r) 과정을 반복하면 r = 0 인 경우가 오는데 이 때의 a가 최대공약수 g가 될 것이다. ax + by = gcd(a,b) 에서 gcd(a,b), x, y 를 구하는 코드 pair xGCD(ll a, ll b) { // returns {g, {x, y}}, ax+by=g if(b==0) retur..

이 문제는 각 학교마다 학생이 본선에 진출할 수 있도록 하는 사람의 최댓값을 출력하도록 하는 문제이다. 이때 학교의 수는 200,000 이고 학생의 수는 최대 MAX = 2,000,000 이 주어진다. 본선에 진출할 수 있는 학생의 수를 x 라고 한다면 x 의 배수가 되도록 하는 학교의 학생수를 전부 counting 하고 이 때 두 팀 이상이 본선에 참가할 수 있다는 것을 고려해줘야 한다. 그렇다면 처음에 각 학교마다 학생의 수 a 를 받을 때 a 명이 전체 학교에서 몇명인지에 대해서 알기 위해 stu_Count 배열을 사용하였다. 그리고 에라스토테네스의 체 방법을 이용하여 O(MAX * log(MAX)) 만큼 시간이 소요된다. 위에서 말한것처럼 본선 진출 가능한 학생의 수를 x 라고 할 때, 학생 수가..