자료구조 - 우선순위 큐 요약 및 소스 분석, 코드 개선 과제

1. 9장 큐 요점정리 (수업시간 요점 정리 내용)

큐는 컴퓨터 과학에서 중요한 자료구조로, 데이터의 저장 및 접근 방식을 정렬된 순서로 관리할 수 있도록 돕는다. 기본적으로 FIFO(First In First Out) 구조를 갖추고 있어, 먼저 들어온 데이터가 먼저 나가는 구조를 따른다. 큐는 주로 프로세스 관리, CPU 스케줄링, 그리고 데이터 스트리밍 등 다양한 분야에서 활용된다. 우선순위 큐는 일반 큐와는 달리 데이터에 우선순위를 부여하여 높은 우선순위를 가진 데이터가 먼저 처리되는 구조이다. 이 구조 때문에 우선순위 큐는 일반 큐보다 더 복잡한 동작을 하며, 여러 알고리즘의 성능을 개선하는 데 기여할 수 있다. 예를 들어, Dijkstra의 최단 경로 알고리즘이나 Prim의 최소 신장 트리 알고리즘 같은 경우에서 우선순위 큐를 효과적으로 활용한다. 우선순위 큐는 다양한 방법으로 구현할 수 있다. 배열, 연결 리스트, 힙 등의 자료구조를 사용하여 각기 다른 성능을 나타낸다. 배열을 사용하는 경우, 간단하게 구현할 수 있지만 삽입과 삭제의 경우 O(n) 시간복잡도를 가지게 되어 비효율적일 수 있다. 연결 리스트를 사용하는 방법도 있지만, 삽입 시 우선순위를 …