728x90 코딩테스트25 최대공약수/최소공배수 - 백준 2609 [Python] 최대공약수 (GCD )를 구하는 빠른 방법은 유클리드 호제법을 이용하면 된다. a를 b로 나눈 나머지를 r이라고 했을 때 GCD(a,b) = GCD(b,r)과 같다. r이 0이면 그때 b가 최대 공약수이다. GCD(24,16) = GCD(16,8) = GCD(8,0) = 8 최소공배수 (LCM) 도 최대공약수를 구한 것과 비슷하게 적용하여 구하면 된다. LCM(A,B) = GCD(A,B) * (A/GCD(A,B)) * (B/GCD(A,B)) Example) https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net Ans.. 2021. 7. 16. 약수의 합 - 백준 17425 [Python] 문제해석) 문제에서 주의할 점은, 약수의 합2 문제와는 다르게 테스트 케이스의 수가 주어져 시간복잡도를 잘 고려해야한다는 점이다. 따라서 변하지 않는 값일 경우, 매번 테스트 케이스마다 구하는 것이 아니라 한번에 미리 구해둔 다음 그 값을 이용하는 방식으로 문제를 해결한다. 문제 해결을 위해 N보다 작거나 같은 모든 자연수는 N의 약수와 약수가 아닌 수로 나눌 수 있다. 약수의 개수는 약수가 아닌 수의 개수보다 매우 작다. 불필요한 연산을 줄이기 위해서 배수를 이용해 약수를 구할 수 있다. 이 방법을 이용한다면, 시간 복잡도는 O(NlgN)이 된다. 정답) MAX = 1000000; d = [1]*(MAX+1) s = [0]*(MAX+1) for i in range(2, MAX+1): j=1 while .. 2021. 7. 15. 약수의 합 2 - 백준 17427 [Python] Example) https://www.acmicpc.net/problem/17427 문제해석) f(A) - O(루트A) (1~A를 모두 나누어보는 방법) - O(A) (1~A를 모두 나누어보는 방법) g(N) - N*O(루트N) = O(N루트N) - N*O(N) = O(N^2) 이때, 시간 제한이 0.5초기 때문에 약수를 구한다음 더하는 방법은 불가능하게 된다. 따라서 약수의 반대는 배수이다. 라는 아이디어로 문제를 해결해 본다. ( 3의 배수는 3을 약수로 갖는 수 / 5의 배수는 5를 약수로 갖는 수 라는 컨셉을 이용 ) N이하의 자연수 중에서 1을 약수로 갖는 수의 개수는 [N/1]개 N이하의 자연수 중에서 2를 약수로 갖는 수의 개수는 [N/2]개 N이하의 자연수 중에서 3를 약수로 갖는 수의 개.. 2021. 7. 15. 약수 - 백준 1037 [Python] C가 A의 약수라면, A/C도 A의 약수가 되어야 한다. 또 C가 A/C인 경우도 있는데, 이때는 A = C^2이라는 수식이 성립하는 경우이다. 따라서 약수를 구할때, 루트 A를 까지 구한 다음, 모든 약수를 구하여 시간복잡도를 줄일 수 있다. 왜냐하면, A만큼 나누어 보는 것이 아니라, 루트 A까지 약수를 구하기 때문에 O(N) > O(루트N)이 되기 때문이다. Example 1) https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 문제 .. 2021. 7. 15. 이전 1 ··· 3 4 5 6 7 다음 728x90