본문 바로가기
728x90

알고리즘3

약수의 합 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.
나머지 연산 - 백준 4375번 [Python] 문제에서 "정답을 ~~~로 나눈 나머지를 출력하라 (경우의 수를 구하는 문제)" 라는 말이 있는 경우 정답이 int나 long long과 같은 저료형의 범위를 넘어가기 때문이다. 따라서 나머지 연산을 통해 해결하면 된다. 특히, Python의 경우 정수의 크기 제한이 없지만 2^31-1이 넘어간다면 속도의 문제(O(수의 길이))가 발생하기 때문에 나머지 연산을 통해 해결한다. Example) https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 문제 해석) 1로만 이루어진 N의 배수를 찾는다 > 1%N, 11.. 2021. 7. 15.
728x90

티스토리툴바