[자료구조/알고리즘] 핵심 정렬 알고리즘 & 트리 핵심 요약 (모바일 최적화 관점)
안녕하세요! 오늘은 게임 개발자, 특히 모바일(Android Vulkan) 환경을 타겟으로 하는 클라이언트 프로그래머가 반드시 숙지해야 할 핵심 정렬 알고리즘과 트리 구조의 성능 트레이드오프를 정리해 봅니다. 단순히 이론을 암기하는 것을 넘어 실무 프로젝트에 어떻게 적용하고 한계를 방어할 것인지에 초점을 맞추었습니다.
1. 삽입 정렬 (Insertion Sort)
교과서적 정의
정렬되지 않은 데이터를 이미 정렬된 부분 배열의 적절한 위치에 차례로 '삽입'하여 전체 데이터를 정렬하는 알고리즘입니다. 인덱스를 하나씩 늘려가며 정렬 영역을 확장하며, '정렬되지 않은 영역'의 데이터(Key)를 꺼내 '이미 정렬된 영역'의 뒤에서부터 앞으로 비교해가며 자리를 찾아 비집고 들어갑니다.
- 시간 복잡도: 평균/최악
O(N^2), 최선(이미 거의 정렬된 상태)O(N) - 공간 복잡도:
O(1)(In-place 정렬) - 안정성: Stable Sort (동일한 값의 상대적 순서 유지)
"두 번째 인덱스부터 시작해서 앞의 정렬된 부분과 비교해 알맞은 자리에 삽입하는 알고리즘입니다. 평균 시간 복잡도는 O(N^2)이지만, 최선의 경우 O(N)이 나와서 정렬이 이미 많이 되어 있는 데이터에 사용하면 좋습니다."
[문제 인식] 모바일 소울라이크 게임에서는 매 프레임 수많은 오브젝트를 정렬해야 할 때가 있으며, 무조건 O(N log N) 정렬을 쓰는 것이 항상 정답은 아닙니다.
[전략적 판단] 삽입 정렬은 '이미 대부분 정렬된 데이터'를 다룰 때 그 어떤 알고리즘보다 빠르고 오버헤드가 적으며, 추가 메모리를 쓰지 않는 인-플레이스(In-place) 안정 정렬입니다.
[스피드 및 실무 적용] 프레임 간 시간 간격이 매우 짧아 이전 프레임의 정렬 순서가 거의 유지되는 '몬스터 거리별 UI 표시 기능' 구현 시 삽입 정렬 개념을 활용했습니다. 퀵 정렬의 재귀 호출 오버헤드를 제거하여 모바일 CPU 연산을 최적화했습니다.
[수치 결과 및 한계 인식] 데이터가 완전히 역순일 경우 O(N^2)으로 치닫기 때문에, 데이터의 최대 개수를 제한(N < 50)하는 안전장치를 두어 실무 안정성을 확보했습니다.
- 모바일 관점의 문제점: 대용량 데이터가 역정렬 상태일 때 데이터 이동(Shifting) 연산이 폭증하여 모바일 CPU에 큰 부담을 줍니다. 소규모 데이터에만 한정해야 합니다.
- 더 나은 대안: 언리얼 엔진의
Sort()함수도 내부적으로 크기가 작을 때는 퀵 정렬 대신 삽입 정렬을 혼합하는 하이브리드(인트로 정렬) 방식을 씁니다. - 하드웨어 특징: 데이터가 연속 메모리에 배치된
TArray구조라면, 인접 메모리를 순차 탐색하므로 CPU 캐시 적중률(Cache Hit Rate)이 매우 뛰어납니다.
2. 퀵 정렬(Quick Sort) vs 병합 정렬(Merge Sort)
분할 정복(Divide and Conquer) 알고리즘을 기반으로 하는 대표적인 두 정렬은 분할과 합치기 방식에서 극명한 차이를 보입니다.
1) 퀵 정렬 (Quick Sort)
- 분할 방식: 기준점(Pivot)을 정해 피벗보다 작은 무리와 큰 무리로 배열을 대충 반으로 쪼개며 내려갑니다. (분할 단계에서 정렬 발생)
- 합치기: 쪼갤 때 이미 정렬 조건을 맞췄으므로 다 쪼개고 나면 별도의 합치기 연산이 없습니다.
- 복잡도: 평균
O(N log N)/ 최악(피벗이 치우친 경우)O(N^2)/ 공간 복잡도O(1) ~ O(log N)(Unstable Sort)
2) 병합 정렬 (Merge Sort)
- 분할 방식: 피벗 없이 배열의 정중앙(Middle)을 기준으로 무조건 기계적으로 정확히 반씩 쪼갭니다. 데이터가 1개 남을 때까지 비교를 하지 않습니다.
- 합치기: 분할이 끝나면 두 개의 정렬된 부분 배열을 순서에 맞게 임시 배열에 크기를 비교해가며 '병합(Merge)'합니다. 이 합치는 과정이 핵심 연산입니다.
- 복잡도: 최선/평균/최악 모두
O(N log N)/ 공간 복잡도O(N)(임시 배열 필요, Stable Sort)
[문제 인식] 병합 정렬은 항상 균일한 속도와 안정 정렬을 보장하지만, 원본 배열 크기만큼의 추가 메모리 공간이 필요한 O(N)의 공간 복잡도를 가집니다.
[전략적 판단] 가용한 RAM 용량이 타이트한 모바일 기기에서 매 프레임 임시 메모리 할당/해제가 반복되면 메모리 단편화와 가비지 컬렉션 부하가 치명적입니다.
[스피드 및 실무 적용] 일반 3D 액터나 트랜스폼 정렬에는 제자리 정렬 방식인 퀵 정렬(언리얼의 기본 Sort)을 사용하고, 생성 시간 순서가 절대 흐트러지면 안 되는 드랍 아이템 리스트나 버프 적용 순서에는 병합 정렬(언리얼의 StableSort)을 선택했습니다.
[수치 결과 및 한계 인식] 런타임 동적 할당 리스크를 방지하기 위해, 초기 로딩 시점에 고정 크기의 풀링(Pooling)용 버퍼 메모리를 미리 확보하고 재사용하는 방식을 취해 오버헤드를 방지했습니다.
- 모바일 관점의 문제점: C++에서 병합 정렬을 순진하게 구현하면
new나std::vector의 동적 할당이 난무하여 치명적인 성능 저하를 유발합니다. - 더 나은 대안: 언리얼 엔진 내에서 순서 유지가 필요할 때는 직접 구현하지 말고 내부적으로 최적화된
TArray::StableSort()를 사용하는 것이 이상적입니다.
3. 비교 기반 정렬 vs 값 기반 정렬 (계수 정렬)
1) 비교 기반 정렬 (Comparison-Based Sort)
삽입, 선택, 버블, 퀵, 병합, 힙 정렬 등이 속하며, 데이터를 1대1로 직접 비교합니다. 수학적으로 아무리 최적화해도 평균 O(N log N)의 벽을 넘을 수 없음이 증명되어 있습니다.
2) 값 기반 / 분산 기반 정렬 (Non-Comparison-Based Sort) - 계수 정렬(Counting Sort)
데이터끼리 절대 비교하지 않고, 데이터의 '값' 자체를 메모리 인덱스로 바로 매핑하여 개수를 세어 출력하는 방식입니다. 비교를 생략하므로 O(N log N)의 벽을 깨고 무조건 O(N + K) (K는 데이터의 최댓값) 영역으로 진입합니다.
- 치명적인 제약 조건: 정수형처럼 인덱싱이 가능해야 하며, 음수 값이 없어야 하고, 데이터의 최댓값(K)이 너무 크지 않아야 합니다. (데이터는 5개인데 최댓값이 10억이면 10억 칸짜리 배열이 필요해 메모리가 고갈됩니다.)
[문제 인식] 퀵 정렬과 계수 정렬은 '비교 여부'와 '메모리 사용 방식'에서 극단적인 트레이드오프 관계에 있습니다.
[전략적 판단] 데이터 범위가 좁고 명확할 때 비교 연산을 생략하는 계수 정렬을 선택하면 CPU 연산 속도를 O(N) 수준으로 전개할 수 있습니다.
[스피드 및 실무 적용] 아이템 등급(Normal~Legendary, 0~3 범위)이나 몬스터 종류별 통계 정렬 등 범위가 극히 제한적인 데이터에는 계수 정렬을 적용해 부하를 줄였습니다. 반면, 예측 불가능한 유저 스코어보드나 3D 벡터 거리 정렬에는 피벗 안전장치를 둔 퀵 정렬 기반 알고리즘을 선택했습니다.
[수치 결과 및 한계 인식] 데이터 범위(K)가 데이터 개수(N)보다 작거나 유사할 때만 계수 정렬을 활성화하도록 컴파일 타임 및 런타임 검증을 거쳐 모바일 메모리 단편화 및 캐시 미스 리스크를 방어했습니다.
- 모바일 관점의 문제점: RAM 용량이 제한적인 보급형 모바일 기기에서 범위가 넓은 데이터를 계수 정렬하면 OOM(Out Of Memory) 크래시의 직접적인 원인이 됩니다.
- 더 나은 대안: 정수 데이터이되 자릿수가 너무 크다면(예: 유저 고유 UID), 자릿수별로 쪼개어 정렬하는 기수 정렬(Radix Sort)이 공간 복잡도를 타협할 수 있는 훌륭한 대안이 됩니다.
4. 힙 정렬 (Heap Sort)
교과서적 정의
부모 노드가 자식 노드보다 항상 크거나 작은 규칙을 만족하는 완전 이진 트리인 이진 힙(Binary Heap) 자료구조를 기반으로 합니다. 루트 노드에 항상 최댓값 또는 최솟값이 위치한다는 특징을 이용해, 최대 힙을 빌드한 후 루트 노드의 값을 하나씩 뽑아 배열의 뒤쪽부터 채워나가는 제자리 정렬(In-place) 방식입니다.
- 시간 복잡도: 최선 / 평균 / 최악 모두
O(N log N) - 공간 복잡도:
O(1) - 안정성: Unstable Sort
[문제 인식] 모바일 프레임 환경에서는 특정 데이터 정렬 시 연산 속도가 최악으로 치닫는 '워스트 케이스'를 원천 차단하여 프레임 드랍(Stuttering)을 방지해야 합니다.
[전략적 판단] 힙 정렬은 제자리 정렬이면서도 어떤 최악의 배열이 들어와도 성능 저하 없이 항상 균일한 O(N log N)을 보장하는 절대적 안정성을 가집니다.
[스피드 및 실무 적용] 언리얼 엔진의 TArray::Sort()도 내부적으로 퀵 정렬로 시작해 재귀 깊이가 깊어지면 최악의 상황(O(N^2))을 피하고자 힙 정렬로 전환하는 인트로 정렬(Introsort)을 씁니다. 이를 벤치마킹하여 연산 폭탄이 우려되는 대규모 가시성(Culling) 액터 정렬 구간에 방어 코드로 구축했습니다.
[수치 결과 및 한계 인식] 다만, 힙 정렬은 인덱스가 배수로 뛰어넘는 트리 탐색 특성상, 순차 배열 탐색에 비해 CPU 지역성(Locality)이 떨어져 캐시 미스 확률이 높습니다. 따라서 데이터 규모가 작을 때는 무조건적인 힙 정렬보다 삽입/퀵 정렬이 친화적임을 인지하고 스케일에 따른 보완 설계를 적용했습니다.
정렬 알고리즘 핵심 요약표
| 정렬 알고리즘 | 최선 복잡도 | 최악 복잡도 | 공간 복잡도 | 안정성 (Stable) | 하드웨어 특징 / 추천 실무 상황 |
|---|---|---|---|---|---|
| 삽입 정렬 | O(N) |
O(N^2) |
O(1) |
정적 (Stable) | 캐시 적중률 최고. 프레임 간 변동이 적고 이미 거의 정렬된 소규모 데이터군에 최적. |
| 퀵 정렬 | O(N log N) |
O(N^2) |
O(log N) |
부정 (Unstable) | 실무 범용 정렬의 표준. 연속 메모리 참조로 평균 속도 최고. 피벗 리스크 방어 필요. |
| 병합 정렬 | O(N log N) |
O(N log N) |
O(N) |
정적 (Stable) | 언제나 고른 속도 보장. 데이터 순서 보존이 필수인 UI 로그, 타겟팅 큐에 활용. 메모리 버퍼 풀링 권장. |
| 힙 정렬 | O(N log N) |
O(N log N) |
O(1) |
부정 (Unstable) | 최악의 데이터 상황 방어용(안전장치). 추가 메모리가 없으면서 절대적 타임아웃 보장. |
| 계수 정렬 | O(N + K) |
O(N + K) |
O(K) |
정적 (Stable) | 특수 조건(정수, 좁은 범위 K)에서만 발동하는 치트키. 아이템 등급, 종류 ID 정렬에 최적. |
5. 트리(Tree) 구조와 탐색의 오개념 교정
1) 트리의 오해와 진실
- 모든 트리는 이진 트리인가? 아닙니다. 트리는 단순히 '사이클이 없는 계층형 자료구조'일 뿐이며, 자식 노드가 4개인 쿼드 트리(Quad Tree), 8개인 옥트 트리(Octree) 등 공간 분할 및 시야 컬링 시스템에 다양하게 쓰입니다.
- 이진 트리의 탐색은 무조건
O(log N)인가? 아닙니다! 데이터가 정렬된 순서대로 들어와 한쪽으로만 길게 늘어선 편향 트리(Skewed Tree)가 되면 구조만 트리일 뿐 연결 리스트와 다름없어져 탐색 성능이O(N)으로 치닫습니다. 좌우 균형이 예쁘게 맞는 '균형 트리'일 때만 높이가log N이 되어 탐색 성능을 보장합니다.
2) 레드-블랙 트리 (Red-Black Tree)
노드에 색상을 부여하여 스스로 균형을 맞추는 자가 균형 이진 탐색 트리(Self-Balancing BST)입니다. C++ 표준 라이브러리의 std::map이 내부적으로 이 구조로 구현되어 있으며, 삽입/삭제 시 회전 연산 오버헤드가 발생하지만 최악의 순간에도 탐색 시간 복잡도를 완벽히 O(log N)으로 묶어주어 실시간 프레임 방어에 유리합니다.
- 모바일 관점의 문제점: 일반적인 노드 기반 트리 자료구조는 메모리 상에 사방으로 파편화되어 포인터 널뛰기(Pointer Chasing)를 유발하므로, CPU 캐시 미스가 잦아 실제 런타임 속도가 느려질 수 있습니다.
- 더 나은 대안: 완전 이진 트리 성질을 가진 '힙(Heap)'은 포인터 없이 일반 순차 배열(
TArray)에 빽빽하게 채워 넣을 수 있어 캐시 효율이 좋습니다. 따라서 탐색 빈도가 극도로 높은 틱(Tick) 로직이나 데이터가 100개 미만인 구간에는 트리 대신 언리얼의TMap이나 정렬된TArray를 통한 선형/이진 탐색 복합 채택이 유리합니다.
3) 탐색 알고리즘 핵심 비교
- 선형 탐색 (Linear Search): 데이터의 처음부터 끝까지 순차 확인. 정렬 불필요,
O(N). 데이터가 소규모(예: 30개 이하)일 때 가장 직관적이고 빠름. - 이진 탐색 (Binary Search): 정렬된 데이터에서 범위를 절반씩 날리며 탐색,
O(log N). 대규모 데이터 정렬이 선행되어 있을 때 최고. - 해시/배열 탐색: 값의 범위가 한정적일 때 인덱스를 직접 활용하는 치트키,
O(1). 속도가 물리적으로 가장 빠름.