우선순위 큐 코딩테스트: 정렬 함수만 쓰다가 효율성 터지는 이유

코딩테스트에서 굳이 우선순위 큐를 꺼내야 하는 시점

정렬 문제인 줄 알고 무심코 정렬 함수를 호출했다가 효율성 테스트에서 빨간 불을 본 경험은 누구나 있을 겁니다. 매번 데이터를 집어넣을 때마다 전체 배열을 다시 정렬하는 구조라면, 그 코드는 대규모 트래픽이나 거대한 입력값 앞에서 반드시 무너집니다. 코딩테스트와 실무 운영 환경의 공통점은 시간과 메모리가 무한하지 않다는 점입니다.

 

우선순위 큐(Priority Queue)는 모든 데이터를 정렬된 상태로 유지하는 낭비를 하지 않습니다. 오직 '가장 급한 놈 하나'만 맨 위로 올리는 힙(Heap) 구조를 취합니다. 이 특성이 필요한 문제들은 몇 가지 전형적인 냄새를 풍깁니다. 그 징후를 알아채는 것이 최적화의 첫걸음입니다.

이 패턴 보이면 무조건 힙(Heap) 구조다: 3가지 핵심 특징

1. 실시간으로 데이터가 추가되면서 최솟값/최댓값을 계속 요구할 때

고정된 데이터 집합이라면 단순 정렬 한 번으로 끝납니다. 하지만 루프를 돌 때마다 새로운 데이터가 밀려 들어오고, 그 와중에 현재 기준 가장 작은 값이나 큰 값을 꺼내야 한다면 정렬을 유지하는 비용이 눈덩이처럼 불어납니다. 배열 정렬은 $O(N \log N)$이지만, 우선순위 큐의 삽입과 삭제는 $O(\log N)$입니다. 이 차이가 수만 번 반복되는 루프 안에서 당락을 결정짓습니다.

2. 스케줄링, 시뮬레이션, 그리고 '가장 먼저 만료되는' 조건

운영체제의 CPU 스케줄링이나 네트워크 패킷 처리, 게임 서버의 이벤트 타임라인 같은 구조의 문제들입니다. 대기열에 작업이 계속 쌓이는데, 정해진 우선순위나 마감 기한이 가장 임박한 작업을 먼저 처리해야 하는 상황입니다. "가장 작업 시간이 짧은 것부터", "가장 먼저 썩는 수하물부터" 같은 조건이 붙는다면 십중팔구 우선순위 큐가 정답입니다.

3. 그래프 알고리스를 타야 하는 최단 경로와 최소 신장 트리

다익스트라(Dijkstra) 알고리즘과 프림(Prim) 알고리즘의 심장은 우선순위 큐입니다. 현재 방문 가능한 노드 중 가장 가중치가 작은 노드를 선택해 나가는 과정이 반복되기 때문입니다. 이걸 일반 배열로 순회하며 찾으면 $O(V^2)$이 걸려 대규모 인프라 구조를 표현한 문제에서 타임아웃이 납니다. 우선순위 큐를 쓰면 $O(E \log V)$로 시간 복잡도를 획기적으로 낮출 수 있습니다.

우선순위 큐 힙 구조 - 생성형 ai 이미지

실무와 코테의 접점: 힙으로 해결하는 전형적인 상황 유형

이해를 돕기 위해 코딩테스트와 실무 시스템에서 이 개념이 어떻게 똑같이 구르는지 매핑해 보겠습니다. 동작 원리는 완벽하게 동일합니다.

상황 유형	코딩테스트 핵심 조건	실무 아키텍처 적용 예시
데이터 스트리밍	매초 주식 가격이 들어올 때 미디언(중앙값) 구하기	실시간 금융 거래 사기 탐지(FDS) 점수 필터링
자원 할당 스케줄러	최소한의 회의실을 써서 모든 회의 배정하기	쿠버네티스(Kubernetes) 포드 스케줄링 및 자원 배분
그리디 최적화	가장 매운 음식 두 개를 섞어 특정 스코빌 지수 만들기	서버 리소스 한계 도달 시 우선순위 낮은 캐시 만료(LRU 변형)

이건 직접 구현하고 운영해 보면 체감이 확 됩니다. 정렬된 상태를 유지하기 위해 매번 전체 데이터를 흔드는 작업이 시스템에 얼마나 큰 리딩 피로도를 주는지 알게 되면, 자연스럽게 힙 구조를 찾게 됩니다.

사람들이 자주 물어보는 질문: "그냥 자바의 TreeSet이나 내장 정렬 쓰면 안 되나요?"

많은 주니어 개발자나 취준생들이 하는 실수 중 하나가 자바의 TreeSet이나 TreeMap을 우선순위 큐 대용으로 쓰는 것입니다. 이 둘은 이진 탐색 트리 기반이라 최솟값, 최댓값을 항상 정렬된 상태로 가지고 있으니 똑같아 보입니다. 하지만 내부를 뜯어보면 트레이드오프가 확실합니다.

 

TreeSet은 중복을 허용하지 않습니다. 값이 같은 데이터가 들어오면 무시하거나 별도의 처리를 해야 합니다. 게다가 자바의 Red-Black Tree 구조는 노드의 균형을 맞추기 위해 삽입/삭제 시마다 내부적으로 복잡한 포인터 회전 연산이 일어납니다. 반면 일반적인 이진 힙 구조 기반의 PriorityQueue는 단순 배열 트리 형태라 메모리 오버헤드가 훨씬 적고 캐시 지역성(Cache Locality) 측면에서 비교가 안 될 정도로 빠릅니다. 중복 데이터 처리가 필요한 코딩테스트에서 TreeSet을 쓰면 성능 저하로 이어질 확률이 높습니다.

작성 시 주의해야 할 구현상의 함정과 메모리 이슈

우선순위 큐를 쓸 때 가장 흔하게 터지는 실패 패턴은 '객체 비교(Comparator) 정의의 실수'와 '무한 루프에 의한 메모리 고갈'입니다.

• 원시 타입 변환 오버플로우: 두 수의 차를 비교하기 위해 (a, b) -> a - b 방식을 자바에서 무심코 쓰다가 오버플로우가 나면 대소 관계가 뒤집힙니다. 안전하게 Integer.compare(a, b)를 써야 합니다.
• 동적 객체 내부 값 변경: 큐에 이미 들어가 있는 객체의 내부 필드 값을 꺼내지 않고 외부에서 수정해 버리면, 힙의 정렬 구조가 깨집니다. 큐는 내부 값이 바뀐 것을 인지하지 못하므로, 정렬이 깨진 상태로 엉뚱한 값을 루트 노드에 유지하게 됩니다. 값을 수정하려면 반드시 큐에서 꺼내고(poll), 수정 후 다시 넣어야(add) 합니다.
• 메모리 누수: 코딩테스트 입력 데이터가 100만 건인데 조건에 따라 큐에 넣기만 하고 적절히 빼주지 않으면 힙 크기가 커져 Heap Memory Limit을 초과합니다. 굳이 들고 있을 필요가 없는 낡은 데이터는 조건 검사 후 즉시 버려야 합니다.

결국 어떤 선택을 해야 하는가?

코딩테스트 문제를 만났을 때 머릿속에 지도를 그리십시오.

 

데이터의 추가와 삭제가 빈번하게 일어나면서도 기준은 언제나 극단적인 값(최소/최대) 하나라면 우선순위 큐가 유일한 돌파구입니다. 전체가 완벽하게 정렬될 필요는 없다는 점을 기억하십시오. 맨 위 뚜껑에 있는 데이터 하나만 정학하면 된다면 주저 없이 언어별 내장 힙 라이브러리(PriorityQueue, heapq 등)를 선언하면 됩니다.

 

반대로 데이터의 변동이 없고 탐색만 많이 일어난다면 최초 1회 정렬 후 이진 탐색(Binary Search)을 쓰는 것이 맞고, 인덱스를 통한 중간 데이터 접근이 빈번하다면 우선순위 큐는 최악의 선택이 됩니다. 힙 구조는 맨 위 노드 제외하고는 완전 정렬을 보장하지 않기 때문입니다. 문제의 데이터가 '흐르는 물'인지 '고인 물'인지 파악하는 것이 선택의 본질입니다.

 

스프링 시큐리티 로그인 흐름 완전 정복: 인증의 시작부터 SecurityContext까지