자료구조 공부 순서와 연습 문제

이 글과 연결된 과정게임프로그래밍 과정 알아보기

게임은 사람이 동시에 즐기는 경우가 많아 서버와 네트워크 지식도 중요합니다. 과정 후반에는 여러 명이 접속하는 간단한 멀티플레이 기능을 구현해 보며 클라이언트…

자료구조를 공부하기 전에 확인할 준비 조건

자료구조는 문법 공부 다음 단계입니다. 반복문과 함수가 익숙하고, C나 C++라면 포인터와 구조체를, C#이라면 클래스와 참조 개념을 알고 있어야 막히지 않습니다. 이 기초가 흔들리면 자료구조 코드에서 문법 오류와 개념 오류가 섞여 무엇이 문제인지 알기 어려워집니다.

또 하나 미리 알아 두면 좋은 것이 시간 복잡도입니다. 데이터가 많아질 때 작업 시간이 얼마나 늘어나는지를 나타내는 표현으로, 흔히 빅오 표기법이라고 부릅니다. 데이터가 두 배가 되면 시간도 두 배인지, 거의 그대로인지, 네 배가 되는지를 구분하는 정도면 충분합니다. 자료구조마다 장단점을 비교할 때 이 기준이 계속 쓰입니다. 게임은 한 프레임 안에 많은 계산을 끝내야 하므로, 적이 열 마리일 때 괜찮던 코드가 수백 마리가 되면 느려지는 일이 실제로 생깁니다. 자료구조를 고르는 감각은 이런 문제를 미리 피하는 힘입니다.

1단계: 배열과 연결 리스트로 기본기 다지기

배열은 같은 크기의 칸이 메모리에 나란히 붙어 있는 구조입니다. 번호로 바로 찾아갈 수 있어 읽기가 빠르지만, 중간에 끼워 넣거나 빼려면 뒤의 칸을 모두 밀거나 당겨야 합니다. 연결 리스트는 칸마다 다음 칸의 위치를 들고 있는 구조라서 끼워 넣기는 쉽지만, 특정 번호를 찾으려면 처음부터 따라가야 합니다.

• 연습 1: 크기가 자동으로 늘어나는 배열 직접 만들기
• 연습 2: 단일 연결 리스트의 삽입, 삭제, 탐색 구현하기
• 연습 3: 연결 리스트 뒤집기
• 게임 생각해 보기: 인벤토리 슬롯은 배열과 연결 리스트 중 무엇이 맞을까

직접 만든 배열과 언어가 기본 제공하는 동적 배열을 비교해 보면, 표준 라이브러리가 내부에서 무슨 일을 하는지 이해할 수 있습니다. 이 감각이 있어야 나중에 엔진 코드를 읽을 때 성능 문제를 예상할 수 있습니다.

2단계: 스택과 큐, 넣고 빼는 순서의 차이

스택은 마지막에 넣은 것을 먼저 꺼내는 구조이고, 큐는 먼저 넣은 것을 먼저 꺼내는 구조입니다. 접시를 쌓는 것과 줄을 서는 것에 비유하면 쉽습니다. 둘 다 배열이나 연결 리스트로 구현할 수 있어서 1단계 복습도 겸합니다.

1. 배열로 스택을 구현하고 괄호 짝 맞추기 문제 풀기
2. 원형 배열로 큐를 구현하기
3. 스택으로 실행 취소 기능 흉내 내기
4. 큐로 턴제 전투의 행동 순서 처리하기

게임에서는 메뉴 화면이 겹겹이 열리고 뒤로 가기로 닫히는 구조가 스택과 닮았고, 네트워크로 들어오는 입력이나 이벤트를 차례대로 처리하는 것은 큐와 닮았습니다. 원형 큐를 만들 때 맨 끝에서 다시 처음으로 돌아가는 계산을 나머지 연산으로 처리하는 부분이 첫 번째 고비입니다.

3단계: 트리와 힙, 계층과 우선순위 다루기

트리는 하나의 뿌리에서 가지가 갈라지는 구조입니다. 폴더 구조나 게임 오브젝트의 부모와 자식 관계가 트리 모양입니다. 그중 이진 탐색 트리는 왼쪽에는 작은 값, 오른쪽에는 큰 값을 두어 찾기를 빠르게 합니다. 힙은 가장 크거나 작은 값을 빠르게 꺼내는 데 특화된 트리로, 우선순위 큐를 만들 때 씁니다.

• 이진 탐색 트리의 삽입과 탐색, 세 가지 순회 구현하기
• 트리의 높이 구하기를 재귀로 풀기
• 배열 기반 힙으로 우선순위 큐 만들기
• 게임 생각해 보기: 여러 적 중 가장 위협적인 대상을 고르는 데 힙을 쓸 수 있을까

트리는 재귀 함수와 붙어 다닙니다. 재귀가 아직 낯설다면 트리 순회를 종이에 그리며 함수가 호출되고 돌아오는 순서를 화살표로 따라가 보세요. 힙은 길찾기 알고리즘에서 다시 만나게 됩니다.

4단계: 해시 테이블과 그래프, 실전에 가까운 구조

해시 테이블은 키를 계산해 저장 위치를 바로 정하는 구조입니다. 아이템 고유 번호로 아이템 정보를 찾거나, 플레이어 아이디로 계정 데이터를 찾는 것처럼 이름표로 빠르게 찾아야 할 때 씁니다. 연습으로는 간단한 해시 함수를 만들고, 두 키가 같은 자리에 들어가는 충돌을 연결 리스트로 해결하는 구현을 해 봅니다.

그래프는 점과 선으로 관계를 나타내는 구조로, 맵의 지점과 길, 퀘스트의 선후 관계, 친구 관계가 모두 그래프입니다. 인접 리스트로 그래프를 저장하고 너비 우선 탐색과 깊이 우선 탐색을 구현해 보세요. 격자 맵에서 출발점부터 도착점까지 최단 칸 수를 구하는 문제는 너비 우선 탐색의 대표 연습이며, 이후 길찾기 알고리즘을 배우는 디딤돌이 됩니다.

공부 루틴과 이해했는지 확인하는 방법

한 자료구조마다 개념 읽기, 직접 구현, 문제 풀기, 게임 예시 떠올리기의 네 단계를 거칩니다. 평일에는 하루 한두 시간을 쓰고, 주말에는 그 주에 배운 구조를 작은 콘솔 프로그램에 넣어 봅니다. 예를 들어 스택과 큐를 배운 주에는 턴제 전투 시뮬레이터를, 해시를 배운 주에는 아이템 도감 검색 기능을 만들어 보는 식입니다.

이해했는지 확인하는 가장 좋은 방법은 표준 라이브러리 없이 빈 파일에서 다시 구현해 보는 것입니다. 그리고 왜 이 상황에 이 구조를 골랐는지 한 문장으로 설명할 수 있어야 합니다. 면접에서도 구현보다 선택 이유를 묻는 경우가 많습니다. 어떤 구조에서 막혔는지, 다음에 무엇을 공부할지 정리가 필요하다면 SBS아카데미게임학원 게임프로그래밍 과정 상담에서 구현 코드를 함께 보며 순서를 잡을 수 있습니다.

자주 묻는 질문

가까운 캠퍼스에서 게임프로그래밍 알아보기

사는 곳과 가까운 캠퍼스를 고르면 수업 내용, 오시는 길, 상담 신청을 한 번에 볼 수 있습니다.

함께 읽으면 좋은 글