mojo's Blog

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 라고 할 때, 학생 수가..

문제 링크 => https://www.acmicpc.net/problem/16563 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 2~5,000,000 범위의 숫자들이 1~1,000,000 개가 주어질때 각각의 숫자들을 소인수분해하여 소인수들을 오름차순으로 출력하는 문제이다. 우리가 일반적으로 알고있는 factorize 의 시간복잡도는 O(N^(1/2)) 이므로 대략 5,000,000의 루트에 1,000,000을 곱한다면 2,236,067,977.499789... 이므로 시간초과가 난다는 것은 확실하다. 따라서 이..

특정 범위 내에서 소수를 전부 구하고 싶을때 효율적인 방법은 에라토스테네스의 체이다. O(N) 만큼의 Memory를 사용하여 O(Nlog(logN)) 만에 특정 범위 내의 소수를 전부 구할 수 있다. 에라스토테네스의 체를 구하는 Code bool is_prime[1000005]; void sieve() { for(int i=2; i

임의의 실수 x에 대하여 factorize 하는 방법 [2, N^(1/2)] 의 수들로 나눠 볼 때 나누는 수가 소수인지 확인할 필요가 없다!!! 만약에 N이 2로 나눠 떨어진다면 N값을 2로 나눠서 다시 2로 나눠 떨어지는지를 확인하고 그렇지 않은 경우 3으로 나눠 떨어지는지 확인하고 ... 반복한다. 이 과정을 반복하면 소수가 아닌 인수는 자연스럽게 없어지는 것을 확인할 수 있다. 따라서 Time Complexity O(N^(1/2)) 이 나온다. factorize 하는 코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #defi..

문제 링크 => 4256번: 트리 (acmicpc.net) 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 트리를 이용한 분할정복 문제이다. 이 문제는 preorder와 inorder가 주어졌을때 postorder를 구하는 문제인데 약간 까다로웠다. 먼저 예시를 살펴보도록 한다. preorder : 3 6 5 4 8 7 1 2 inorder : 5 6 8 4 3 1 2 7 preorder의 맨 앞부분 3은 트리의 가장 위에 있는 노드이다. 그리고 inorder를 살펴보면 3을 기준으로 5 6 8 4..