본문 바로가기
컴퓨터 공학/자료 구조

Priority Queue 우선순위 큐 개념과 이를 이용한 정렬 및 응용 문제 파이썬 구현

seungyoon 2021. 4. 9. 08:24

1. 우선순위 큐 ADT

  • 각 데이터 항목을 (키, 원소) 쌍으로 저장
  • ex) (학번, 점수), (주소, 우편물)
  • unordered : 삽입시 데이터 키를 고려하지 않기 때문에 빠르지만 삭제는 키의 순서로 고려해야 해서 느리다.
  • ordered: 삽입시 느리지만 삭제를 빠르다.
  • 삽입 삭제의 빈도에 따라 구현 방식을 결정한다.
    • 삽입시 키에 따라 정렬, 삭제시 키에 따라 정렬
    • 키를 저장하기 위한 자료구조로 우선순위 큐를 활용한다.
     

ADT 메소드

i) 주요 메소드

  • insertItem(k,e) : 키 k인 원소 e를 큐에 삽입
  • element removeMin() : 큐에서 최소 키를 가진 원소를 삭제하여 반환

ii) 일반 메소드

  • int size () : 큐의 항목 수 반환
  • bool isEmpty() : 큐가 비어있는지 여부 반환

iii) 접근 메소드

  • element minElement() : 큐에서 최소 키를 가진 원소를 반환
  • elemtent minKey() : 큐에서 최소 키를 반환

iv) 예외

  • emptyQueueException() : 비어 있는 큐에 삭제나 원소 접근을 시도할 경우 발령
  • fullQueueException() : 가득 찬 큐에 삽입을 시도할 경우 발령

2. 우선순위 큐를 이용한 정렬

일반정렬

  • 일반적인 정렬 방식 
/*L과 P는 특정 자료구조가 아닌 generic*/

Alg PQ-Sort(L)
	input list L       
	output sorted list L

1. P <- empty priority queue
2. while (!L.isEmpty())
			e <- L.remove(L.first())   
				// 첫번째 원소를 가져오면서 L 큐에서 삭제
			P.insertItem(e)
				// 큐에 원소를 정렬하면서 삽입 
3. while (!P.isEmpty())
			e <- P.removeMin()
				// 큐에서 키 값이 가장 작은 값을 가져오면서 삭제 
			L.insertLast(e)
				// L의 가장 마지막에 키 값이 가장 작은 값 삽입
4. return

 

  • 리스트를 기반으로 하는 우선순위 ㅋ 
    • unordered list로 구현 
      • 우선순위 큐의 항목들을 리스트에 임의의 순서로 저장
      • 삽입은 O(1) 시간 소요
      • 삭제는 순회가 필요해서 O(n) 시간 소요 
    • ordered list로 구현
      • 우선순위 큐의 항목들을 리스트에 키 정렬 순서로 저장
      • 삽입은 항목을 삽입할 곳을 찾아야 하기 때문에 O(n) 시간 소요
      • 삭제는 최소 키가 리스트 맨 앞에 있으므로 O(1) 시간 소요
  • 위 알고리즘에서 P 리스트를 구현할 때 ordered 또는 unordered로 구현할 수 있다. 
  • 삭입 삭제 빈도를 파악한 후 결정한다. 

선택정렬 (Selection sort)

  • 우선순위 큐가 unordered list로 구현된다.
  • 삽입시 O(n), 삭제시 O(n^2) 시간 소요
  • 항목 전체 중에 가장 작은 걸 찾아서 삽입 → 이 작업을 반복

삽입정렬 (Insertion sort)

  • 우선순위 큐가 ordered list로 구현된다.
  • 삽입시 O(n^2), 삭제시 O(n) 시간 소요
  • 가장 큰 원소를 큐에 삽입하고 그 다음 원소를 큐 내부의 가장 앞에 있는 원소와 비교하여 삽입 → 이 작업을 반복

3. 제자리 정렬

  • 정렬하려는 리스트 자체 공간 이외에 O(1) 만의 외부 공간을 사용한다면 in-place 수행이라고 한다.
  • 즉, 정렬 알고리즘에서 정렬 대상 개체를 위해 필요한 메모리가 오직 상수 메모리라면 제자리 정렬이라고 한다.
  • 시스템 자원 (메모리) 비용절감 측면에서 효율적이다.

in-place selection sort

  • 리스트 앞 부분을 정렬상태로 유지해야 한다.
  • 리스트 변경하는 대신 swapElement를 사용한다
    • 최소 키를 가진 데이터를 맨 앞 데이터와 swap
    • swap을 거친 데이터는 output 큐에 있다고 간주한다.
Alg inPlaceSelectionSort(A)
	input array A of n keys
	output sorted array A
// 가장 작은 걸 찾아서 맨 앞으로! 

1. for pass <- 0 to n-2
			minLoc <- pass
			for j <- (pass+1) to (n-1)
				 if(A[j] < A[minLoc])
							micLoc <- j
							// 위치 정보 찾기 
			A[pass] <-> A[minLoc]
2. return

in-place insertion sort

  • 리스트의 앞 부분을 정렬상태로 유지해야 한다.
  • 리스트 변경하는 대신 swapElement를 사용한다.
    • 초기에는 리스트 전체가 L
    • 가장 왼쪽 데이터를 오른쪽의 데이터와 비교하면서 자신의 자리를 찾아간다. (즉, P 내부에서 비교를 하면서 swapping)
    • 자신의 자리를 찾은 데이터들은 왼쪽에 P output 리스트에 자리를 잡는 것이다.
Alg inPlaceSelectionSort(A)
	input array A of n keys
	output sorted array A

1. for pass <- 1 to n-1
			 save <- A[pass]
			for j <- pass-1
				 while((j>=0) & (A[j] > save))
						A[j+1] <- A[j]
						j <- j-1
						// 자리 확보를 위한 작업 
				A[j+1] <- save

2. return

 

4. 선택 정렬 vs 삽입정렬

공통점

  • 전체적으로 O(n^2) 시간 소요
  • → 내부 반복 O(n) 선형탐색 + 외부 반복 O(n) 패스
  • in-place 버전은 O(1) 공간 소요
  • 구현이 단순
  • 데이터가 적을 경우 유용

차이점

  • 초기 리스트가 완전히/거의 정렬된 경우(내부 반복문인 O(1) 시간 소요되기 때문에 전체적으로 O(n) 시간이 수행된다.)
  • → in-place insertion sort가 더 빠르다.
  • swap 시간이 많이 걸리는 경우(swap 하는 작업은 O(1) 시간이 걸리지만 in-place insertion sort에서는 swap 작업이 최악의 경우 O(n) 시간 소요될 수 있다.)
  • → in-place selection sort가 더 빠르다.

성능 요약

5. 응용문제

1. 정렬 - 다음 입력 리스트에 대한 제자리 선택 정렬과 제자리 삽입 정렬의 수행 내용을 예시하라.

  • 입력 리스트 : 22 15 36 44 10 39 13 29 25
  • (priority queue) 로 표시한다.

2. 알고리즘 실습

[문제1] 선택정렬 ; N개의 중복 가능한 양의 정수를 입력 받아 아래에서 설명하는 선택 정렬을 이용하여 정렬하는 프로그램을 작성하시오

  • 가장 큰 값을 찾는 버전— 제자리 정렬 사용
    • 배열의 뒷 부분을 정렬상태로 유지
    • 크기가 N인 배열을 동적 할당
    • 매 반복마다 최대 한번의 스왑 연산 사용
  • PQ에 들어가진 않은 값들 중 가장 큰 값을 찾아 PQ에 들어가지 않은 값 중 가장 오른쪽에 있는 값을 swap

  • 내가 푼 알고리즘 source code 
def selection_sort(q,n):
    for i in range(0, n-1):
        # 리스트의 모든 원소 n-1개에 대해 (마지막 원소 제외)
        min = i
        for j in range(i+1, n):
            # 해당 원소 다음 원소부터 리스트 끝까지 해당 원소와 비교 
            if q[j] < q[min]:
                # min이 해당 원소를 임시로 저장해둔 변수인데 해당 원소가 리스트 순회하면서 자기보다 작은 원소를 찾으면
                min = j
                # 그 원소가 min이 된다. 
        q[i], q[min] = q[min], q[i]
        # 해당 원소와 가장 작았던 원소 min 의 위치를 swap!
        # 이 과정을 n-1번 수행하면 오름차순으로 정렬됨.  

n = int(input())

q = list(map(int, input().split()))

selection_sort(q,n)

for i in q:
    print(i, end=' ')

 

 

 

[문제2] 삽입 정렬 ; N개의 중복 가능한 양의 정수를 입력 받아 아래에서 설명하는 삽입 정렬을 이용하여 정렬하는 프로그램을 작성하시오

  • PQ는 왼쪽
  • PQ에서 작은 수일 수록 왼쪽에 배치
  • PQ에 들어가지 않은 값들 중 대상 값을 따로 저장해두고, PQ의 값들과 비교하며 들어갈 위치를 찾아 삽입

  • 내가 푼 알고리즘 source code
def insertion_sort(q,n):
    for i in range(1,n):
        key = i
        for j in range(0,i):
            if q[key] < q[j]:
                t = q[j]
                q[j] = q[key]
                q[key] = t
        


n = int(input())
q = list(map(int, input().split()))
insertion_sort(q,n)
for i in q:
    print(i, end=' ')

[문제3] 다양한 입력에 대해 선택 정렬과 삽입 정렬의 실행 시간을 측정 비교 하라

  • 표준 입력으로 정렬할 원소의 개수 N을 입력 받고, 크기가 N인 정수 배열 A와 B를 동적 할당한다.
  • 난수 발생 함수 (srand, rand 등)를 사용하여 N 개의 정수 난수로 배열 A와 B를 동일하게 초기화한다.
  • 배열 A에 대해서는 선택 정렬을, 배열 B에 대해서는 삽입 정렬을 수행하여 시간 측정 함수 (clock) 등을 이용하여 각 정렬에 수행된 시간을 표준 출력으로 출력한다.

  • 내가 푼 알고리즘 source code
def insertion_sort(q,n):
    comparison_count = 0
    for i in range(1,n):
        key = i
        for j in range(0,i):
            if q[key] < q[j]:
                t = q[j]
                q[j] = q[key]
                q[key] = t
                comparison_count += 1
        # print(i+1, "번째",q)
    return comparison_count


print("**********Insertion Sort**********")

print("\n1. unordered list")
UL = [7,2,3,1,8,4,9,5,6,0]
print(UL)
UL_res = insertion_sort(UL,len(UL))
print(UL)
print("the number of swapping : %d " %(UL_res))
print("")

print("2. ordered list")
OL = [0,1,2,3,4,5,6,7,8,9]
print(OL)
OL_res = insertion_sort(OL,len(OL))
print(OL)
print("the number of swapping : %d " %(OL_res))
print("")

print("3. reversed ordered list")
ROL = [9,8,7,6,5,4,3,2,1,0]
print(ROL)
ROL_res = insertion_sort(ROL,len(ROL))
print(ROL)
print("the number of swapping : %d " %(ROL_res))
print("")
def insertion_sort(q,n):
    comparison_count = 0
    for i in range(1,n):
        key = i
        for j in range(0,i):
            if q[key] < q[j]:
                t = q[j]
                q[j] = q[key]
                q[key] = t
                comparison_count += 1
        # print(i+1, "번째",q)
    return comparison_count


print("**********Selection Sort**********")

print("\n1. unordered list")
UL = [7,2,3,1,8,4,9,5,6,0]
print(UL)
UL_res = insertion_sort(UL,len(UL))
print(UL)
print("the number of swapping : %d " %(UL_res))
print("")

print("2. ordered list")
OL = [0,1,2,3,4,5,6,7,8,9]
print(OL)
OL_res = insertion_sort(OL,len(OL))
print(OL)
print("the number of swapping : %d " %(OL_res))
print("")

print("3. reversed ordered list")
ROL = [9,8,7,6,5,4,3,2,1,0]
print(ROL)
ROL_res = insertion_sort(ROL,len(ROL))
print(ROL)
print("the number of swapping : %d " %(ROL_res))
print("")

 

References

  • 성균관대학교 안용학 교수님의 2020-2 <데이터사이언스와 컴퓨팅 (알고리즘)> 수업을 들으며 공부한 내용입니다. 

'컴퓨터 공학 > 자료 구조' 카테고리의 다른 글

자료구조/Python3) 연결리스트로 스택 구현  (0) 2022.06.07
자료구조) 딕셔너리 ADT  (0) 2021.04.09
자료구조/C) 연결리스트를 이용한 실습 문제 풀이  (0) 2021.04.09
자료구조/C) 연결리스트 ADT  (0) 2021.04.09
자료구조/C) 이진탐색트리 BST 응용 문제 소스 코드  (1) 2021.04.09

'컴퓨터 공학/자료 구조' Related Articles

티스토리툴바