자료구조는 데이터를 저장하고 꺼내고 수정하기 위한 방법이다.

같은 데이터라도 어떻게 저장하느냐에 따라 프로그램의 동작 방식과 성능이 달라진다.

예를 들어 게임에서 플레이어가 가지고 있는 아이템을 관리한다고 해보자.

아이템 목록-> 순서대로 저장-> 특정 아이템 검색-> 아이템 추가-> 아이템 삭제

이때 데이터를 배열에 넣을 수도 있고, Dictionary에 넣을 수도 있다.

둘 다 데이터를 저장할 수 있지만 사용하는 목적은 다르다.

Array-> 순서와 인덱스를 이용한 접근

Dictionary-> Key를 이용한 빠른 검색

자료구조를 공부하는 이유도 결국 여기에 있다.

문제에 맞는 데이터 저장 방식을 선택하는 것.

배열

가장 기본적인 자료구조는 배열이다.

같은 타입의 데이터를 연속된 공간에 저장하고 인덱스로 접근한다.

int[] scores = new int[5];

scores[0] = 10;
scores[1] = 20;
scores[2] = 30;

특정 위치의 데이터를 바로 가져올 수 있다는 것이 가장 큰 특징이다.

int score = scores[2];

인덱스를 알고 있다면 접근 비용은 일반적으로 O(1)이다.

scores[0]
scores[1]
scores[2]
...

몇 번째 데이터를 가져올지 알고 있기 때문에 처음부터 하나씩 찾을 필요가 없다.

반면 배열의 중간에 데이터를 삽입하거나 삭제하면 뒤에 있는 데이터를 이동시켜야 할 수 있다.

[ A ][ B ][ C ][ D ]

C 삭제

[ A ][ B ][ D ]

이 과정 때문에 삽입과 삭제는 상황에 따라 O(N)이 될 수 있다.

그래서 배열은 순차적인 데이터에 접근하거나 인덱스를 통한 빠른 접근이 필요한 경우에 적합하다.

동적 배열

실제 게임 개발에서는 데이터 개수가 항상 정해져 있지 않다.

플레이어가 아이템을 계속 획득할 수도 있고, 적이 생성되고 삭제될 수도 있다.

이런 상황에서는 고정 크기의 배열보다 동적 배열이 편하다.

C#의 List<T>가 대표적인 예다.

List<Enemy> enemies = new List<Enemy>();

enemies.Add(enemy);
enemies.Remove(enemy);

내부적으로는 배열과 비슷한 구조를 사용하지만 용량이 부족하면 더 큰 배열을 만들어 기존 데이터를 옮기는 방식으로 크기를 확장한다.

그래서 Add()가 항상 같은 비용으로 실행되는 것은 아니다.

대부분의 경우 빠르게 추가할 수 있지만, 용량을 늘리는 순간에는 여러 데이터를 복사하는 비용이 발생할 수 있다.

그래도 일반적인 게임 코드에서는 순차적으로 데이터를 관리할 때 List<T>가 상당히 자주 사용된다.

Linked List

Linked List는 데이터를 하나의 연속된 배열처럼 저장하지 않는다.

각 Node가 다음 Node를 가리키는 형태로 연결한다.

[A] -> [B] -> [C] -> [D]

Node 안에는 데이터와 다음 Node에 대한 참조가 들어간다.

그래서 중간 Node를 제거할 때 뒤의 데이터를 전부 이동시킬 필요가 없다.

[A] -> [B] -> [C] -> [D]

B 삭제

[A] ------> [C] -> [D]

다만 문제가 있다.

배열은

array[100]

처럼 인덱스로 바로 접근할 수 있지만 Linked List는 100번째 Node를 찾으려면 앞에서부터 연결을 따라가야 한다.

따라서 특정 위치에 접근하는 것은 O(N)이다.

결국 Linked List는 삽입과 삭제가 많은 구조에서는 장점이 있지만, 인덱스 기반 접근이 많은 경우에는 배열 계열이 더 적합한 경우가 많다.

게임 개발에서도 무조건 Linked List가 빠른 것은 아니다.

캐시 효율이나 메모리 접근 패턴까지 고려하면 실제 성능은 단순한 Big-O만으로 결정되지 않는다.

Stack

Stack은 LIFO(Last In, First Out) 구조다.

마지막에 들어온 데이터가 먼저 나온다.

Push A
Push B
Push C

Top
[C]
[B]
[A]

C를 먼저 꺼내게 된다.

대표적인 사용 사례가 실행 취소나 함수 호출 구조 같은 것이다.

게임에서도 사용할 수 있다.

예를 들어 플레이어의 상태 변화를 저장한다고 하자.

Idle-> Run-> Jump-> Attack

현재 상태에서 이전 상태로 되돌아가야 한다면 Stack 구조를 활용할 수 있다.

또한 DFS 같은 그래프 탐색 알고리즘에서도 Stack을 사용한다.

C#에서는 Stack<T>를 사용할 수 있다.

Stack<int> stack = new Stack<int>();

stack.Push(10);
stack.Push(20);

int value = stack.Pop();

결과는 20이다.

Queue

Queue는 Stack과 반대 방향의 구조다.

FIFO(First In, First Out) 방식이다.

먼저 들어온 데이터가 먼저 나온다.

입구
A -> B -> C

출구

A가 먼저 나감

게임에서는 작업 대기열이나 이벤트 처리 등에 사용할 수 있다.

예를 들어 서버에서 처리해야 할 작업이 들어온 순서대로 실행되어야 한다면 Queue가 자연스럽다.

Queue<Command> commands = new Queue<Command>();

commands.Enqueue(command);

Command next = commands.Dequeue();

BFS에서도 Queue가 사용된다.

BFS
-> 가까운 Node부터 탐색
-> Queue에 다음 Node 저장

자료구조와 알고리즘이 연결되는 대표적인 예다.

Hash Table

Hash Table은 Key를 이용해서 데이터를 빠르게 찾기 위한 자료구조다.

C#에서는 Dictionary<TKey, TValue>가 대표적이다.

Dictionary<int, Player> players = new();

players.Add(1001, player);

이후 ID를 알고 있다면

Player player = players[1001];

처럼 바로 접근할 수 있다.

배열에서 특정 데이터를 찾으려면

[Player A]
[Player B]
[Player C]
[Player D]
...

하나씩 비교해야 할 수 있다.

Dictionary는 Key를 Hash Function을 통해 특정 위치로 변환해서 데이터를 찾는다.

개념적으로는

Key-> Hash Function-> Hash-> 저장 위치

형태다.

평균적인 검색, 삽입, 삭제는 일반적으로 O(1)에 가깝다.

다만 Hash 충돌이나 내부 구조에 따라 실제 동작은 달라질 수 있다.

Hash Collision

Hash Table에서 중요한 문제가 하나 있다.

서로 다른 Key가 같은 위치를 가리킬 수 있다.

Key A -> Hash 10
Key B -> Hash 10

이것을 Collision이라고 한다.

Hash Table은 이런 충돌을 처리하기 위한 별도의 방법을 사용한다.

따라서 “Dictionary 검색은 무조건 O(1)”이라고 외우기보다는 평균적으로 O(1)에 가까운 성능을 제공한다고 이해하는 편이 정확하다.

그리고 Hash Table을 사용할 때는 Key의 특성과 Hash Function이 성능에 영향을 줄 수 있다는 것도 알아둘 필요가 있다.

Set

Set은 중복을 허용하지 않는 데이터를 관리할 때 사용한다.

C#에서는 HashSet<T>가 대표적이다.

HashSet<int> visited = new();

visited.Add(10);
visited.Add(20);
visited.Add(10);

마지막 10은 이미 존재하기 때문에 중복해서 들어가지 않는다.

게임에서는 방문한 Node를 관리할 때 사용할 수 있다.

if (!visited.Contains(node))
{
    visited.Add(node);
}

또는 이미 획득한 아이템 ID나 활성화된 이벤트 목록처럼 존재 여부 자체가 중요한 데이터를 관리할 때 적합하다.

Dictionary가

Key -> Value

라면 Set은

Value의 존재 여부

를 관리하는 구조라고 생각하면 편하다.

Heap과 Priority Queue

게임 알고리즘을 공부하면 Heap이라는 자료구조가 자주 등장한다.

Heap은 특정 우선순위를 가진 데이터를 빠르게 꺼내기 위한 자료구조로 활용된다.

대표적인 사용 방식이 Priority Queue다.

예를 들어 다음과 같은 작업이 있다고 하자.

작업 A -> 우선순위 3
작업 B -> 우선순위 1
작업 C -> 우선순위 2

일반 Queue라면 A, B, C 순서로 처리한다.

Priority Queue라면 우선순위가 높은 작업부터 처리하도록 만들 수 있다.

B-> C-> A

A*와 Dijkstra에서도 이런 구조가 사용된다.

현재 가장 비용이 낮은 Node를 먼저 꺼내야 하기 때문이다.

A*-> Priority Queue-> 가장 우선순위가 높은 Node 선택

자료구조 하나를 이해하면 알고리즘의 구현이 같이 이해되는 이유가 이런 부분이다.

Tree

Tree는 계층적인 관계를 표현하는 자료구조다.

하나의 Root에서 여러 Node가 아래로 연결된다.

게임에서는 Tree 구조를 상당히 자주 볼 수 있다.

예를 들어 게임 오브젝트 구조 자체가 계층 구조를 가진다.

AI에서도 Tree가 사용된다.

대표적인 것이 Behavior Tree다.

Selector-> Attack-> Chase-> Patrol

파일 시스템이나 UI 계층 구조도 Tree 형태로 표현할 수 있다.

Tree는 단순히 데이터를 저장하는 구조라기보다 계층 관계를 표현하는 데 적합한 구조라고 이해하면 좋다.

Binary Search Tree

Tree 중에서도 각 Node가 최대 두 개의 자식을 가지는 구조를 Binary Tree라고 한다.

Binary Search Tree에서는 왼쪽에 작은 값, 오른쪽에 큰 값을 배치하는 규칙을 사용한다.

이 규칙이 유지되면 값을 찾을 때 탐색 범위를 계속 줄일 수 있다.

다만 Tree가 한쪽으로 심하게 치우치면

사실상 Linked List와 비슷한 구조가 되어 검색 성능이 O(N)까지 떨어질 수 있다.

그래서 실제 구현에서는 균형을 유지하는 Balanced Tree 계열 자료구조가 사용되기도 한다.

Graph

Graph는 Node와 Edge의 관계로 데이터를 표현한다.

게임에서 상당히 중요한 자료구조다.

맵의 이동 관계를 표현할 수도 있고, 도시 간 연결이나 스킬의 선행 조건, NPC 관계 등을 표현할 수도 있다.

특히 Pathfinding을 생각하면 Graph가 자연스럽게 등장한다.

Start-> Node-> Node-> Goal

여기서 실제 경로를 찾는 것은 알고리즘의 역할이고, 어떤 Node들이 연결되어 있는지를 표현하는 것은 자료구조의 역할이다.

이 차이를 구분하면 자료구조와 알고리즘의 관계가 조금 더 명확해진다.

자료구조와 알고리즘은 같이 봐야 한다

자료구조만 따로 공부하면 각각의 특징을 외우는 데 그치기 쉽다.

하지만 실제로는 알고리즘과 함께 사용된다.

예를 들어 BFS는 Queue를 사용한다.

BFS-> Queue

DFS는 Stack을 사용한다.

DFS-> Stack

Dijkstra와 A*는 Priority Queue를 활용할 수 있다.

A*-> Priority Queue

객체의 빠른 검색이 필요하면 Hash Table을 사용할 수 있다.

ID-> Dictionary-> Object

중복 없는 데이터가 필요하면 Set을 사용한다.

Visited Node-> HashSet

이런 식으로 문제를 해결하기 위해 어떤 데이터를 어떤 형태로 관리해야 하는가를 먼저 생각하면 자료구조 선택이 자연스러워진다.

Big-O만 보고 판단하면 안 된다

자료구조를 공부하면 Big-O를 많이 보게 된다.

대략적인 성능을 비교하는 데는 유용하다.

자료구조	주요 특징
Array	인덱스 접근
List	동적 배열
Linked List	Node 연결
Stack	LIFO
Queue	FIFO
Dictionary	Key 기반 검색
HashSet	중복 없는 집합
Priority Queue	우선순위 기반 처리
Tree	계층 구조
Graph	관계 표현

하지만 실제 게임 개발에서는 Big-O만 보고 결정하면 부족하다.

예를 들어 Array와 Linked List가 이론적으로 특정 연산에서 각각 유리하더라도 실제 CPU Cache 효율이나 메모리 배치 때문에 결과가 달라질 수 있다.

게임은 특히 프레임 단위로 많은 데이터를 처리하기 때문에 메모리 접근 패턴과 캐시 효율도 중요하다.

따라서

Big-O
+ 메모리 사용량
+ 데이터 크기
+ 접근 패턴
+ 실행 빈도
+ 실제 프로파일링

을 같이 봐야 한다.

어떤 자료구조를 선택할 것인가

자료구조를 선택할 때는 먼저 데이터의 사용 방식을 생각하는 게 좋다.

인덱스로 자주 접근한다-> Array / List

앞뒤로 데이터를 넣고 뺀다-> Queue / Deque

마지막에 넣은 데이터를 먼저 꺼낸다-> Stack

Key로 데이터를 빠르게 찾는다-> Dictionary

중복 여부와 존재 여부가 중요하다-> HashSet

우선순위가 높은 데이터를 먼저 꺼낸다-> Priority Queue

계층 구조를 표현한다-> Tree

객체 간 연결 관계를 표현한다-> Graph

자료구조 이름을 보고 선택하는 것보다 데이터를 어떻게 사용할지를 먼저 정의하는 것이 중요하다.

게임 개발에서의 예

게임에서 플레이어의 아이템을 관리한다고 해보자.

아이템의 순서가 중요하고 인덱스로 접근해야 한다면

List<Item> inventory;

가 자연스럽다.

반대로 아이템 ID로 빠르게 찾아야 한다면

Dictionary<int, Item> items;

가 적합할 수 있다.

중복 아이템 ID를 제거하거나 이미 처리한 ID를 관리한다면

HashSet<int> processedIds;

를 사용할 수 있다.

AI의 이동 경로를 찾는다면

Graph+A* + Priority Queue + HashSet

같이 여러 자료구조가 하나의 알고리즘 안에서 함께 사용될 수도 있다.

실제 개발에서는 이런 조합이 더 일반적이다.

자료구조를 공부하는 이유

자료구조는 특정 클래스나 API를 외우는 공부가 아니다.

핵심은 데이터를 어떤 형태로 배치하고 접근할 것인가를 판단하는 능력이다.

예를 들어

"플레이어 ID로 캐릭터를 찾아야 한다."

라는 요구사항이 있다면 자연스럽게 Dictionary가 떠올라야 한다.

"처리하지 않은 Node를 관리해야 한다."

라면 HashSet이 후보가 될 수 있다.

"가장 비용이 낮은 Node부터 탐색해야 한다."

라면 Priority Queue를 생각할 수 있다.

"Node 간 이동 관계를 표현해야 한다."

라면 Graph가 필요하다.

이런 식으로 문제에서 자료구조를 역으로 추론할 수 있어야 한다.

정리

자료구조는 데이터를 저장하는 방법을 정하는 문제다.

그리고 그 선택은 알고리즘의 성능과 구현 방식에 직접적인 영향을 준다.

문제-> 데이터의 사용 방식 파악-> 자료구조 선택-> 알고리즘 선택-> 구현-> 성능 확인

대표적인 자료구조를 다시 정리하면 다음과 같다.

Array-> 인덱스 기반 접근

List-> 크기가 변하는 순차 데이터

Stack-> LIFO

Queue-> FIFO

Dictionary-> Key 기반 검색

HashSet-> 중복 없는 데이터

Priority Queue-> 우선순위 기반 처리

Tree-> 계층 관계

Graph-> 연결 관계

게임 개발에서는 자료구조 하나만 사용하는 경우보다 여러 자료구조를 조합하는 경우가 많다.

특히 Pathfinding 같은 알고리즘을 구현하다 보면 Graph, Queue, Priority Queue, HashSet 등이 자연스럽게 함께 등장한다.

결국 자료구조를 공부한다는 것은 “이 자료구조의 정의가 무엇인가?”를 외우는 것보다 주어진 문제에서 어떤 데이터를 어떤 방식으로 관리해야 효율적인지를 판단하는 것에 가깝다.

알고리즘이 문제를 해결하는 방법이라면, 자료구조는 그 알고리즘이 데이터를 다루는 방식이라고 생각하면 정리가 잘 된다.

자료구조 핵심 정리

배열