자료구조는 데이터를 어떤 모양으로 담아 둘지 정하는 방법입니다. 같은 기능이라도 자료구조를 잘못 고르면 게임이 눈에 띄게 느려집니다. 이 글에서는 게임 프로그래머가 자주 쓰는 자료구조를 실제 게임 기능과 연결해 설명하고, 고르는 기준을 정리합니다.

왜 게임에서 자료구조가 중요한가

게임은 1초에 수십 번 화면을 다시 그리며, 그때마다 수많은 객체를 확인합니다. 한 프레임 안에서 몬스터 수백 마리의 위치를 갱신하고, 총알이 누구에게 맞았는지 찾고, 인벤토리에서 아이템을 꺼냅니다. 이때 '찾기', '넣기', '빼기'가 얼마나 빠른지가 자료구조에 따라 달라집니다.

이 빠르기를 표현할 때 빅오 표기법을 씁니다. O(1)은 데이터 양과 상관없이 일정한 시간, O(n)은 데이터 양에 비례하는 시간이라는 뜻입니다. 정확한 측정값이 아니라 데이터가 늘어날 때 얼마나 느려지는지를 비교하는 도구라고 이해하면 됩니다.

배열과 연결 리스트

배열은 데이터를 메모리에 나란히 붙여 저장합니다. 몇 번째 칸인지 알면 바로 꺼낼 수 있고, 메모리가 붙어 있어 CPU 캐시(자주 쓰는 데이터를 잠시 담아 두는 빠른 저장소)를 잘 활용합니다. 그래서 게임에서는 배열이나 동적 배열(C++ vector, C# List)이 가장 많이 쓰입니다.

연결 리스트는 각 데이터가 다음 데이터의 위치를 기억하는 방식입니다. 중간에 넣고 빼기는 쉽지만, 원하는 데이터를 찾으려면 처음부터 따라가야 하고 메모리가 흩어져 있어 캐시 효율이 떨어집니다. 이론상 유리해 보여도 실제 게임에서는 배열이 더 빠른 경우가 많다는 점을 기억해 두세요.

스택과 큐

• 스택: 마지막에 넣은 것을 먼저 꺼냄. 열린 UI 창을 닫을 때 가장 위의 창부터 닫는 구조, 실행 취소 기록
• 큐: 먼저 넣은 것을 먼저 꺼냄. 대전 매칭 대기열, 순서대로 처리할 이벤트 목록, 입력 버퍼
• 우선순위 큐: 정해진 기준이 높은 것부터 꺼냄. 길찾기 A*에서 가장 가능성 높은 칸 고르기

격투 게임의 커맨드 입력처럼 최근 입력 몇 개를 보관하는 기능에는 고정 크기 원형 큐가 자주 쓰입니다. 오래된 입력은 자동으로 밀려나고 새 입력만 남습니다.

해시 테이블과 트리

해시 테이블은 키를 계산해 저장 위치를 바로 정하는 방식으로, 아이템 ID나 퀘스트 ID로 정보를 찾을 때 매우 빠릅니다. C++의 unordered_map, C#의 Dictionary가 여기에 해당합니다. 대신 순서가 정해져 있지 않으므로 정렬된 목록이 필요하면 따로 처리해야 합니다.

트리는 데이터를 부모와 자식 관계로 연결합니다. 게임 엔진의 씬 계층(부모 오브젝트를 움직이면 자식도 따라 움직임), UI 계층, 행동 트리가 모두 트리 구조입니다. 공간을 네 칸, 여덟 칸으로 나누는 쿼드트리와 옥트리는 넓은 맵에서 가까운 대상만 빠르게 찾는 데 쓰입니다.

그래프와 상황별 선택 기준

그래프는 점(노드)과 선(간선)으로 관계를 나타냅니다. 맵의 이동 경로, 스킬 트리, 퀘스트 선후 관계가 그래프로 표현됩니다.

공부 방법

자료구조는 직접 만들어 볼 때 가장 잘 이해됩니다. 표준 라이브러리에 다 있더라도 동적 배열, 스택, 큐, 해시 테이블을 한 번씩 손으로 구현해 보면 각 연산이 왜 빠르고 느린지 감이 옵니다. 그다음 작은 게임에 적용해 보고, 엔진의 프로파일러(성능 측정 도구)로 실제 차이를 확인해 보세요.

코딩 테스트와 기술 면접에서도 자료구조는 거의 빠지지 않는 주제입니다. SBS아카데미게임학원 게임프로그래밍 과정은 C언어·C++ 단계에서 데이터 구조와 관리를 다루고 이후 게임 시스템 구현으로 이어집니다.

자주 묻는 질문