똑똑한 코드 작성을 위한 실전 알고리즘

126

똑똑한 코드 작성을 위한 실전 알고리즘

배열

최선의 성능을 내기 위한 구조를 만들기 어려운 정렬되지 않는 엔트리의 배열.

enqueue

()

는

상수 시간 연산이지만

dequeue

()

는 가장 높은 우선순위 값을 찾아 제거하고 반환하기 위해 전

체 배열을 탐색해야 한다. 배열은 크기가 고정되어 있으므로 우선순위 큐가 가득 찰 수 있다.

내장 연산

순서가 없는 리스트로, 배열과 비슷한 성능으로 제공되는 파이썬 내장 연산을 통해 제어한다.

OrderA

엔트리의 우선순위가 점점 증가하도록 정렬된 배열.

enqueue

()

에서는 이진 배열 탐색 변형

([코드

2

-

4

] 참고 )을 사용해 엔트리가 위치할 곳을 찾고, 찾은 위치의 공간을 확보하기 위해

배열 엔트리를 수동으로 시프트한다.

dequeue

()

는 엔트리가 완전히 정렬되었으므로 상수 시

간에 배열의 마지막에서 우선순위가 가장 높은 엔트리를 찾는다. 배열은 크기가 고정되어 있으

므로 우선순위 큐가 가득 찰 수 있다.

연결 리스트

첫 번째 엔트리가 리스트 내에서 가장 큰 우선순위를 가지는 연결 리스트. 각 후속 엔트리는 이

전 엔트리보다 우선순위가 작거나 같다. 해당 구현은 연결 리스트의 적절한 위치에 새로운 값

을 넣도록 해

dequeue

()

를 상수 시간에 처리하도록 한다.

OrderL

우선순위가 점점 증가하도록 오름차순으로 엔트리를 포함하는 파이썬 리스트.

enqueue

()

에서

이진 배열 탐색 변형을 사용해 알맞은 위치에 엔트리를 동적으로 삽입한다. 우선순위가 가장

높은 엔트리는 리스트의 맨 마지막에 ...