파이톨치

[문제] [출처 및 링크] https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net [어떻게 풀까?] 나는 어제 이 문제를 풀어 보았다가 실패하였다. 구현 자체는 그렇게 어렵지 않다고 생각한다. 하지만 백준에서 요구하는 시간을 초과하였고 나는 문제 풀이에 실패하였다. 왜 실패하였을까? 어떻게 해결할까? 하다가 아직 안 푼 문제중 소수 찾기라는 문제를 보게 되었다. 소수 찾기 라는 문제를 풀면서 더 효과적인 방법을 생각했고 이를 적용해..

[문제] [출처 및 링크] https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net [어떻게 풀까?] 이 문제는 에라스토테네스의 체를 이용해야 풀 수 있다. 이것을 써야 시간 복잡도가 작아지기 때문이다. 에레스토테네스의 체에 대한 개념은 다음 그림과 같다. 만약 2가 소수라면 2의 배수에 해당하는 수들을 모두 지워준다. 만약 3이 소수라면 3의 배수에 해당하는 수들을 모두 지워준다. 그렇게 되면 남은 수들은 모두 소수라는 이야기 이다. 이것을 코드로 구현하기 위해서는 수의 범위가 정해..

[문제 설명] [링크] https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net [코드] import sys def isPrime(a): if(a

https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 규칙을 찾기 위해서 일단 거리에 따른 최단 거리를 적어보자. 거리 최단 거리로 가는 방법 1 1 2 1, 1 3 1, 1, 1 4 1, 2, 1 5 1, 2, 1, 1 6 1, 2, 2, 1 7 1, 2, 2, 1, 1 8 1, 2, 2, 2, 1 9 1, 2, 3, 2, 1 이런식으로 구성이 된다. 이것만 봐도 간단한 규칙을 찾을 수 있다. 아직 못 ..