어제 오류가 있던 부분
완전 이진트리
마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨의 노드들은 왼쪽부터 순서대로 채워져 있는 이진트리
포화 이진트리
모든 내부 노드가 자식 노드를 정확히 2개씩 가지고, 모든 리프 노드가 같은 레벨에 있는 이진트리
우선순위 큐
정의
우선순위 큐는 큐와 같이 enqueue와 dequeue를 핵심 기능으로 가지고 있지만, 삽입 순서가 아닌 설정된 우선순위에 따라 데이터가 꺼내지는 순서가 결정되는 자료구조이다.
특징
배열, 연결리스트, 힙을 통해 구현할 수 있지만, 일반적으로 힙을 통해 구현하는 경우가 많다.
힙
정의
힙은 완전 이진트리의 일종으로, 부모 노드와 자식 노드의 값이 정해진 대소관계를 만족하도록 구성된 자료구조이다.
특징
주로 배열을 기반으로 구현되며, 삽입과 삭제가 일어날 때마다 부모와 자식의 값을 비교하여 힙의 속성을 유지한다.
질문 1
우선순위 큐는 왜 힙을 통해 구현하는 것이 효율적인가?
배열과 연결리스트는 정렬 상태를 유지하는 경우 삽입 또는 삭제 시 최악의 경우 O(N)의 시간 복잡도가 들 수 있다.
특히 배열은 삽입과 삭제 과정에서 데이터를 밀거나 당겨야 할 수도 있다.
반면 힙은 삽입과 삭제를 모두 O(logN)에 처리할 수 있어, 우선순위 큐를 구현하기에 더 효율적이다.
질문 2
힙은 왜 배열을 통해 구현하는 것이 효율적인가?
힙은 완전 이진트리이기 때문에 노드가 빈칸 없이 순서대로 배치된다.
따라서 배열로 구현하면 마지막 위치에 바로 삽입할 수 있고, 부모와 자식의 위치도 인덱스로 쉽게 계산할 수 있다.
반면 연결리스트로 구현하면 마지막 노드에 삽입하거나 부모/자식 위치를 찾는 과정이 비효율적일 수 있다.
그래서 힙은 배열로 구현하는 것이 더 적합하다.
질문 3
배열의 5번째 인덱스에 있는 노드의 부모, 왼쪽 자식, 오른쪽 자식의 인덱스
1번 인덱스부터 시작하는 배열 기준
- 부모 노드 인덱스:
5 / 2 = 2 - 왼쪽 자식 인덱스:
2 * 5 = 10 - 오른쪽 자식 인덱스:
2 * 5 + 1 = 11
일반식
- 부모 노드:
index / 2 - 왼쪽 자식:
index * 2 - 오른쪽 자식:
index * 2 + 1
우선순위 큐와 힙의 실사용 예시
우선순위 큐와 힙은 가장 우선순위가 높은 데이터 또는 가장 작은/큰 값을 빠르게 꺼내야 하는 상황에서 자주 활용된다.
1. 작업 스케줄링
운영체제나 프로그램에서는 여러 작업 중 더 중요한 작업을 먼저 처리해야 하는 경우가 있다.
이때 우선순위 큐를 사용하면 우선순위가 높은 작업을 먼저 꺼내 처리할 수 있다.
예시
- 운영체제의 프로세스 스케줄링
- 긴급 작업 우선 실행
- 백그라운드 작업과 사용자 입력 처리 우선순위 구분
2. 다익스트라 알고리즘
그래프에서 최단 경로를 구할 때 사용된다.
현재까지 발견한 경로 중 비용이 가장 작은 정점을 먼저 선택해야 하므로 최소 힙 기반 우선순위 큐가 효율적이다.
예시
- 지도 길찾기
- 네트워크 최단 경로 계산
- 게임 내 이동 경로 탐색
3. 프림 알고리즘
최소 신장 트리를 구할 때 사용된다.
현재 선택 가능한 간선 중 가중치가 가장 작은 간선을 빠르게 꺼내기 위해 최소 힙을 사용한다.
예시
- 네트워크 연결 비용 최소화
- 전선 연결 비용 최소화
- 그래프 기반 최적 연결 문제
4. 이벤트 시뮬레이션
시간 순서대로 이벤트를 처리해야 하는 상황에서 사용된다.
가장 빨리 발생할 이벤트를 먼저 꺼내 처리하면 전체 흐름을 효율적으로 관리할 수 있다.
예시
- 게임 이벤트 예약 처리
- 네트워크 패킷 처리 시뮬레이션
- 시스템 이벤트 스케줄 관리
5. 실시간 순위 처리
데이터가 계속 들어오는 상황에서 상위 K개를 유지하거나, 가장 큰 값 또는 가장 작은 값을 빠르게 관리할 때 사용된다.
예시
- 실시간 랭킹 시스템
- 점수 상위 N명 유지
- 스트리밍 데이터에서 상위 K개 추출
6. 중앙값 유지
숫자가 계속 들어오는 상황에서 중앙값을 빠르게 구해야 할 때 사용된다.
보통 최대 힙과 최소 힙을 함께 사용해 중앙값 기준으로 데이터를 나누어 관리한다.
예시
- 실시간 통계 처리
- 온라인 데이터 분석
- 입력이 계속되는 수열의 중앙값 계산
7. 병합 문제
항상 가장 작은 두 개의 데이터를 선택해 합쳐야 하는 문제에서 사용된다.
최소 힙을 이용하면 가장 작은 두 값을 빠르게 꺼낼 수 있다.
예시
- 카드 정렬하기
- 파일 합치기
- 허프만 코딩
8. 게임 개발에서의 활용
8-1. AI 행동 우선순위 관리
캐릭터가 여러 행동 후보를 가질 때, 우선순위가 높은 행동을 먼저 선택할 수 있다.
예시
- 회피 > 공격 > 추적 > 대기
- 긴급 상황 시 행동 우선순위 변경
8-2. 이벤트 예약 시스템
시간이 지나면 발생해야 하는 이벤트를 관리할 때 활용할 수 있다.
예시
- 일정 시간 뒤 폭발
- 버프 종료 시점 처리
- 투사체 수명 만료 처리
- 컷신 트리거 예약
- 컷신 / 연출 타이밍 제어
연출 중 특정 시간에 카메라 전환, 대사 출력, 이펙트 실행 등을 예약할 수 있다.- 0.5초 뒤 카메라 흔들림
- 1.2초 뒤 폭발 이펙트
- 2.0초 뒤 대사 출력
8-3. 리소스 로딩 우선순위 관리
화면에 더 중요한 리소스를 먼저 불러와야 할 때 사용할 수 있다.
예시
- 플레이어 주변 리소스 우선 로딩
- 가까운 오브젝트 먼저 스트리밍
- 중요한 UI 리소스 선로딩
8-4. 경로 탐색
경로 탐색 알고리즘에서 가장 유리한 후보 노드를 먼저 선택할 때 사용된다.
예시
- A* 알고리즘
- 다익스트라 기반 경로 탐색