알고리즘

[Python] 소인수분해

# n 보다 작은 모든 소수의 리스트를 반환 def eratosthenes(n): sieve = [True] * n for i in range(2, n): if sieve[i] == True: for j in range(i+i, n, i): sieve[j] = False return [ i for i in range(2,n) if sieve[i] == True] def primeFactor(n): # n과 같거나 작은 모든 소수를 원소로 가지는 리스트 생성 l = eratosthenes(n+1) # l에 담긴 각 소수가 n의 소인수인지 확인해봅니다. i = 0 result = [] while i < len(l): # To-do - pass는 지우고 코드를 작성해주세요. # 1. 만약 현재 소수가 n의 소..

[Python] n번째 소수 찾기

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def nthPrime(n): # To-do # 충분히 큰 크기(1000000 정도)를 가진 리스트를 생성하고 # 에라토스테네스의 체를 사용해 n번째의 소수를 찾아 반환하세요. a = [False, False] + [True] * 999998 Primes = [] for i in range(2, 999998): if a[i]: Primes.append(i) for j in range(i+i, 999998, i): a[j] = False return Primes[n-1] # 결과 출력을 위한 코드입니다. 자유롭게 값을 바꿔보며 확인해보세요. print(nthPrime(1)) cs

순차탐색&이진탐색

순차탐색 : 맨앞에서부터 순서대로 탐색을 진행하는 알고리즘 알고리즘의 시간복잡도 분석 "최악의 경우"를 계산 이진탐색 : 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘 -참조: 윤성우의 열혈 자료구조