목록CS/알고리즘 (9)

하루살이 개발자

[알고리즘] 소수찾기 - 에라토스테네스의 체

def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * n m = int(n ** 0.5) for i in range(2, m + 1): if sieve[i] == True: # i가 소수인 경우 for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정 sieve[j] = False # 소수 목록 산출 return [i for i in range(2, n) if sieve[i] == True] 임의의 자연수 n이 있으면 그 이하의 소수들을 전부 찾아내는 데 있어서 최적화된 알고리즘! * 관련 문제 https://thrainer.tistory.com/62?category=1007146 [Bae..
CS/알고리즘 2022. 2. 16. 15:44
[알고리즘] 우선순위 큐 (Priority Queue)

1. 우선순위 큐란? - 일반적인 큐(Queue)는 First in-First Out 구조이다. (부가적인 조건 없이 먼저 들어온 데이터가 먼저 나가는 구조) - 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것이다. - 우선순위 큐는 힙(Heap)이라는 자료구조를 가지고 구현할 수있다. - 큐나 스택과 비슷한 자료형이지만, 각 원소들은 우선순위를 가지고 있다. - 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 같은 우선순위를 가진다면, 먼저 들어온 원소를 처리한다. - 우선순위 큐는 힙(heap)이라는 자료 구조를 통해 구현할 수 있다. - 우선순위 큐는 최소한 두 가지 연산이 지원되어야 한다. 하나..
CS/알고리즘 2022. 2. 16. 13:31
이전 Prev 1 2 3 4 5 Next 다음