본문 바로가기
728x90

알고리즘/[python] 백준 BOJ328

[python] 백준 11689 GCD(n, k) = 1 https://www.acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 n의 약수 중 소수인 것을 $p_{1}, p_{2}, ... p_{a}$ 라 할 때 소수의 개수는 다음과 같이 구할 수 있다. $\phi$ (n) = n $\times \prod_{i=1}^{a} (1-\frac{1}{p_{i}})$ 시간초과가 나지 않게 리스트를 사용하지 않고 for문을 돌면서 소수를 찾으면 ans -= ans/p 를 한 다음 n에서 소수 p의 흔적을 없앤다. p를 약수로 갖지 않을 때 까지 계속 나눠준다는 것이다... 2023. 2. 24.
[python] 백준 1747 소수&팰린드롬 https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 문제 해결 n이상의 소수에서 찾는 것이므로 리스트의 원소 개수를 1,000,000(n의 최댓값)보다 커야한다. ($\times$ 10 함) 소수는 에라토스테네스체로 걸러낸다. CODE import sys input = sys.stdin.readline import math n = int(input()) A = [0]*(10000001) for i in rang.. 2023. 2. 23.
[python] 백준 1456 거의 소수 https://www.acmicpc.net/problem/1456 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 문제 해결 편하게 0부터 끝 수(b)까지 리스트 만들어 놓고 하면 메모리 초과가 걸린다. 따라서 int(sqrt(b))+1 개의 리스트 공간을 만들어 놓고 소수인 인덱스를 제곱, 세제곱 하면서 a와 b 사이에 들어오는지를 확인해야 할 것이다. CODE import math import sys input = sys.stdin.readline a, b = map(int, input().split()) A = [.. 2023. 2. 23.
[python] 백준 1744 수 묶기 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 해결 1보다 큰 양수는 더하는 것 보다 곱하는 것이 이득 1은 더하는 것이 이득 0은 아무런 영향이 없지만 음수가 있을때 음수를 곱해주면 0을 만들 수 있다. 음수는 음수끼리 곱하면 양수가 된다. 우선순위 큐를 통해 1보다 큰 양수, 음수를 따로 리스트를 분리해서 배열한 후 그 안에서 각각 절대값이 큰 것끼리 곱한다. 양수 리스트에 수가 남으면 더한다. 음수 리스트에 수가 남았고 0인 수가.. 2023. 2. 23.
728x90