전체 글 (89) 썸네일형 리스트형 소수 판별법에 대한 고찰 소수 판별은 기초적인 알고리즘이며 여전히 코딩 테스트에서도 자주 출몰하고 여러 문제에 섞여들어가고는 하는 단골 유형이다. 그렇다면 소수를 판별하는 방법에 대해 고민해보자. 단일 소수 판별법 하나에 자연수에 대해 소수인지 판별하는 경우 아래와 같은 시간복잡도로 해결할 수 있다. 1. O(N) - 모두 탐색 말 그대로 모두 탐색하면 된다. n=(int(input()) isPrime=True if n>1 else False for i in range(2,n): if n%i==0: isPrime=False break 위와 같이 코드를 작성하면 2~n-1 까지의 수로 모두 나눠보며 나눠진다면 최종적으로 isPrime은 False일 것이고 나눠지지 않는다면 최종적으로 isPrime은 True일 것이다. 하지만 이렇.. PS와 장비에 대한 고찰 (제 2회 KAUPC 후기) 싸지방에서 해보는 대회의 비공식참가 싸지방 컴퓨터의 컴퓨터, 모니터, 키보드, 마우스 그리고 난생 처음 보는 OS의 합작은 상상 이상으로 적응하기 힘들었다. 오타는 계속 나고.. 마우스는 자꾸 이상한데로 삐져나가고.. PS도 장비를 탄다는 것을 느꼈다. 그리고 역시 구현력은 구현을 잘 안푸니까 꽤나 많이 죽었다. 이번에도 저번처럼 한 문제에 2시간 가까이 쏟으며 시간을 버렸고, 끝까지 못맞췄다는 것도 동일했다. 물론 이번에는 왜 틀렸는지는 알았으나 손이 안따라주는 것은 오랜만이었다. 그와는 별개로 내 코드는 매우 더럽고, 난잡하며 세련되지 못한 코드였다. 원래 내 풀이 방식이 노트나 뭐 검정하면서 풀기 보다는 '어 이거 이렇게 하면 될 것 같은데?' 싶으면 그렇게 짜기 시작한 뒤 그 다음 다듬기 시작하는.. 소수 판별에 대한 고찰 소수 판별은 기초적인 알고리즘이며 여전히 코딩 테스트에서도 자주 출몰하고 여러 문제에 섞여들어가고는 하는 단골 유형이다. 그렇다면 소수를 판별하는 방법에 대해 고민해보자. 단일 소수 판별법 하나에 자연수에 대해 소수인지 판별하는 경우 아래와 같은 시간복잡도로 해결할 수 있다. 1. O(N) - 모두 탐색 말 그대로 모두 탐색하면 된다. n=(int(input()) isPrime=True if n>1 else False for i in range(2,n): if n%i==0: isPrime=False break 위와 같이 코드를 작성하면 2~n-1 까지의 수로 모두 나눠보며 나눠진다면 최종적으로 isPrime은 False일 것이고 나눠지지 않는다면 최종적으로 isPrime은 True일 것이다. 하지만 이렇.. 이전 1 ··· 8 9 10 11 12 13 14 ··· 30 다음