[python] 백준 3036 : 링

[python] 백준 3036 : 링 3036번: 링 (acmicpc.net) 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 실버 3 수학, 정수론, 유클리드 호제법 접근 기약분수는 분모와 분자를 더이상 약분할 수 없는 분수를 뜻한다. 따라서 분모와 분자의 최대공약수로 나누는 방법으로 구할 수 있다. 12와 3의 경우 최대공약수가 3이므로 각각을 3으로 나누면 4와 1이 된다. 이를 분자/분모의 형태로 출력하도록 만들어야 한다. 코드 (최대공약수를 반환하는 라이브러리 사용) import sys; input = sys.stdin.readlin..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 19.
• textsms

[파이썬] 백준 9020 : 골드바흐의 추측

[파이썬] 백준 9020 : 골드바흐의 추측 https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 실버 1 정수론, 소수 판정 접근 먼저 아리토스테네스의 체를 이용해 소수를 판정한다. 제곱근보다 작은 수 범위에서 합성수를 걸러내면 빠르게 소수를구할 수 있다. 소수중에서 x2를 한 값이 입력한 값을 넘는 경우부터 구한 소수를 역순으로 탐색하면서 두 소수의 합이 입력한 값과 같은 경우일 때를 출력하도록 했다. 다만 이 방법은 입력한 ..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 4. 1.
• textsms

[파이썬] 백준 4948 : 베르트랑 공준

[파이썬] 백준 4948 : 베르트랑 공준 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 실버 2 정수론, 소수 판별 접근 에라토스테네스의 체로 소수를 판별하는 방법을 사용하면 간단하게 구할 수 있다. 다만 내가 작성한 방법은 pypy3에서만 통과되었다. 코드 import sys; input = sys.stdin.readline def isPrime(num): for i in range(2, int(num**0.5) + 1): if n..

• format_list_bulleted 알고리즘 문제 풀이
• · 2022. 3. 30.
• textsms