반응형 공부52 [백준] 8단계 - 4948번 (파이썬) check! 4948번 https://www.acmicpc.net/problem/4948 애증의 소수....😫 이번에도 '시간초과' 문제가 계속 발생했다. 어떤 분이 '에라토스테네스의 체'를 살펴보라고 하셔서 에라토스테네스의 체를 이용해서 문제를 풀었더니 다행히 문제가 풀렸다. 위키백과에 있는 에라토스테네스의 체 코드를 그대로 이용하는 방식(버전1)과 해당 코드를 응용해서 문제에 맞게 변형하여 푼 방식(버전2), 총 2가지 방법으로 문제를 풀어봤다. (참고로 버전1이 더 깔끔한 것 같긴 하다...) # 버전1 # n 미만의 소수 찾기(에라토스테네스의 체). def prime_list(n): # 초기화: n개 요소에 True 설정(소수로 간주) ans = [True] * n for i in range(2, int(n .. 2022. 6. 29. 에라토스테네스의 체(소수 찾기) 백준 4948번을 푸는데 또 계속 시간초과가 떠서 결국 백준에서 질문을 검색해봤는데, '에라토스테네스의 체'에 대해 공부해보라는 답글을 발견했다. 그래서 '에라토스테네스의 체'에 대해서 한번 알아봤다. https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 ko.wikipedia.org '에라토스테네스의 체'는 에라토스테네스(Eratosthenes)라는 수학자가 찾은, 소수 찾는 방법이라고 한다. 가장 작은 소수(2)를 하나 찾으면 그 소수의 배수들을 전부 제외시킴. → 남은 것들 중 가장 작은 소수 하나.. 2022. 6. 29. 소수 구하는 함수 (파이썬) 백준 풀면서 짜본 소수 구하는 함수. 나중에 더 효율적인 코드를 짜게 되면 업데이트할 예정. (아래 코드는 2022.06.28일 기준.) # n이하의 소수를 모두 포함한 리스트 출력. def prime(n): ans = list(range(2,n+1)) for i in list(range(2,n+1)): for z in range(2, int(i**(1/2))+1): if (i%z == 0): ans.remove(i) break return ans + 에라토스테네스의 체를 이용한 소수 구하는 함수 (위의 코드보다 효율적) (2022.06.29) # n 이하가 아닌 n 미만의 소수 찾는 함수임을 주의!! def prime_list(n): # 초기화: n개 요소에 True 설정(소수로 간주) ans = [T.. 2022. 6. 28. [백준] 8단계 - 1929번 (파이썬) check! 1929번 https://www.acmicpc.net/problem/1929 이번에도 계속 '시간초과'가 떴다... 소수 문제 정말 너무 싫다... (그래도 다행인 건 아래의 블로그에서 힌트만 얻어서 문제를 해결했다는 점.ㅎㅎ) 1929번은 소수 여부를 판단할 때 제곱근까지만 살펴봄으로써 더 빠르게 소수를 찾으라는 의도의 문제였다. 근데 이 방식...지난번에 소인수분해 문제 풀 때 시도했다가 포기했었다ㅋㅋㅋ 내가 잘못 접근한 건가 했는데 다행히 그건 아니였나 보다.ㅋㅋㅋ 참고: https://deokkk9.tistory.com/17 [python 파이썬] 백준 1929번: 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 .. 2022. 6. 28. 이전 1 2 3 4 5 6 7 ··· 13 다음 반응형
