부트캠프18 에라토스테네스의 체 (Python) 자연수 n 이하 소수의 개수를 출력하는 함수를 에라토스테네스의 체로 구현하는 방법이다. 에라토스테네스의 체는 다음과 같은 순서로 소수를 걸러낸다. 현재 남아있는 수 중 가장 작은 수는 소수 (크기 순으로 정렬되어 있고 걸러지지 않았으니) 이 수를 p라고 하면 2p 부터 n 까지 남아있는 p의 배수를 전부 제거한다. 현재 남아있는 가장 작은 수가 $\sqrt{n}$ 보다 커지면 정지한다. $\sqrt{n}$ 미만까지 직접 나눠서 나눠지는 숫자를 빼는 방식도 가능하지만, n이 커지면 연산 시간이 너무 늘어난다. 따라서 집합이나 리스트의 인덱스로 접근하는 것이 좋다. - 집합(set) def num_primes1(n) : nums = set(range(2, n+1)) root_n = int(n ** (1/2).. 2022. 11. 22. 백준 10870번 : 피보나치 수 5 (Python) https://www.acmicpc.net/problem/10870 def fib(n) : if n == 0 or n == 1 : return n else : return fib(n - 1) + fib(n - 2) n = int(input()) print(fib(n)) 가장 기본적인 재귀 알고리즘 문제이다. 함수의 출력값으로 그 함수를 다시 주면 알아서 답이 나올때까지 계산한다. 참고로 마지막에 print를 안 붙이고 fib(n)만 입력하면 백준에선 틀렸다고 채점한다. 2022. 11. 20. 백준 9020번 : 골드바흐의 추측 (Python) 출처 : https://www.acmicpc.net/problem/9020 t = int(input()) sol = [] # 에라토스테네스의 체로 n 이하 소수로 이루어진 리스트 생성 for i in range(t) : n = int(input()) check = [True] * (n+1) check[0] = check[1] = False root_n = int(n**(1/2)) for i in range(2, root_n+1) : if check[i] == True : for j in range(i*2, n+1, i) : check[j] = False prime = [] for i in range(2, n+1) : if check[i] == True : prime.append(i) # 소수 리스트를 두.. 2022. 11. 15. 백준 1015번 : 수열 정렬 (Python) 출처 : https://www.acmicpc.net/problem/1015 n = int(input()) a = list(map(int, input().split())) b = list('_'*n) for i in range(n) : b[a.index(min(a))] = i a[a.index(min(a))] = min(a) + max(a) for j in b : print(j, end=" ") 리스트 a와 길이가 같은 빈 리스트 b를 생성한다. 현재 a의 최소값의 인덱스를 받아와서 b의 해당 인덱스에 순위를 저장하고, a의 최소값을 최대값을 더한 값으로 대체한다. 그러면 굳이 해당 값을 pop이나 remove로 제거하지 않고도 다음 a의 최소값을 min 메소드로 구할 수 있다. 2022. 11. 8. 이전 1 2 3 4 5 다음