이번에는 배열에 대한 이야기를 해보려고 합니다.
자료구조를 공부하다 보면 배열은 가장 먼저 배우는 자료구조입니다.
그래서인지 배열을 너무 단순하게 생각하는 경우가 많습니다.
같은 타입의 데이터를 여러 개 저장하는 공간이고, 인덱스로 접근할 수 있는 가장 기본적인 자료구조 정도로 받아들이기 쉽습니다.
오히려 링크드 리스트, 트리, 그래프, 해시 테이블 같은 자료구조가 더 고급스럽고, 실무적인 자료구조처럼 생각할 수 있습니다.
하지만 실제 프로그램 구조를 조금 더 깊게 살펴보면 생각이 조금 달라집니다.
특히, 게임 엔진이나 성능이 중요한 프로그램을 보다 보면 생각보다 많은 구조가 결국 배열 기반으로 동작한다는 것을 알게 됩니다.
물론 배열이 모든 상황에서 가장 좋은 자료구조라는 뜻은 아닙니다.
하지만 일반적인 상황에서 배열은 굉장히 강력한 기본 자료구조입니다.
그리고 그 이유는 단순히 사용하기 쉽기 때문만은 아닙니다.
배열은 컴퓨터 메모리 구조와 굉장히 잘 맞는 자료구조이기 때문입니다.
배열은 같은 타입의 데이터를 연속된 메모리에 저장한다
배열의 가장 중요한 특징은 데이터가 연속된 메모리 공간에 배치된다는 점입니다.
아래와 같은 배열이 있습니다.
int numbers[5] = { 10, 20, 30, 40, 50 };
이 배열은 메모리에서 대략 아래와 같은 형태로 배치됩니다.
[10][20][30][40][50]
각 데이터가 서로 떨어져 있는 것이 아니라, 바로 옆에 붙어서 저장됩니다.
이 구조는 단순해 보이지만 굉장히 중요합니다.
왜냐하면 CPU는 메모리에 있는 데이터를 하나씩 독립적으로 읽는 것이 아니라, 주변 데이터까지 함께 가져오는 경우가 많기 때문입니다.
이전 글에서 Cache Locality에 대해 이야기했지만, 배열은 이 Cache Locality를 활용하기에 굉장히 좋은 구조입니다.
예를 들어 numbers[0]을 읽을 때, CPU는 그 주변에 있는 numbers[1], numbers[2] 같은 데이터도 함께 Cache에 올릴 가능성이 높습니다.
그리고 이어서 numbers[1], numbers[2]를 읽게 되면 이미 Cache에 올라온 데이터를 빠르게 사용할 수 있습니다.
이게 배열이 단순하지만 강력한 이유입니다.
배열의 인덱스 접근은 왜 빠를까?
배열을 사용할 때 가장 익숙한 문법은 인덱스 접근입니다.
int value = numbers[3];
이 코드는 numbers 배열의 네 번째 값을 가져오는 코드입니다.
겉으로 보기에는 그냥 대괄호 안에 숫자를 넣는 문법처럼 보입니다.
하지만 내부적으로는 주소 계산이 일어납니다.
배열의 시작 주소를 알고 있고, 각 원소의 크기를 알고 있다면 특정 인덱스의 위치를 바로 계산할 수 있습니다.
개념적으로는 아래와 비슷합니다.
원소 주소 = 배열 시작 주소 + 인덱스 * 원소 크기
예를 들어 int가 4바이트이고, 배열의 시작 주소가 1000번지라고 생각해보겠습니다.
numbers[0]은 1000번지에 있습니다.
numbers[1]은 1004번지에 있습니다.
numbers[2]는 1008번지에 있습니다.
numbers[3]은 1012번지에 있습니다.
즉, 배열은 특정 위치의 데이터를 찾기 위해 앞에서부터 하나씩 순회할 필요가 없습니다.
인덱스만 알면 바로 위치를 계산할 수 있습니다.
그래서 배열의 인덱스 접근은 굉장히 빠릅니다.
이 특징은 단순한 장점처럼 보이지만, 실제 프로그램에서는 매우 큰 의미를 가집니다.
게임에서 수천 개의 위치 데이터, 체력 데이터, 렌더링 데이터, 충돌 데이터를 반복해서 다룰 때 배열 기반 구조가 자주 사용되는 이유도 여기에 있습니다.
배열은 반복 처리에 강하다
배열은 반복문과 굉장히 잘 어울립니다.
for (int ix = 0; ix < 5; ++ix)
{
std::cout << numbers[ix] << "\n";
}
이 코드는 배열에 들어 있는 데이터를 앞에서부터 순서대로 읽습니다.
그리고 이런 순차 접근은 CPU 입장에서 굉장히 처리하기 좋은 패턴입니다.
데이터가 메모리에 연속적으로 배치되어 있고, 접근 순서도 앞에서 뒤로 일정하게 진행되기 때문입니다.
그래서 CPU는 다음에 어떤 데이터가 필요할지 예측하기 쉽습니다.
이런 구조는 Cache에도 유리하고, prefetch에도 유리합니다.
따라서 배열은 단순히 데이터를 저장하는 자료구조가 아니라, CPU가 데이터를 효율적으로 읽을 수 있게 해주는 구조에 가깝습니다.
이 관점이 중요합니다. 자료구조를 공부할 때는 보통 삽입, 삭제, 탐색 같은 연산의 시간 복잡도를 중심으로 보게 됩니다.
물론 자료구조의 복잡도를 이해하는 것 또한 중요합니다.
하지만 실제 프로그램 성능에서는 데이터가 메모리에 어떻게 배치되어 있고, CPU가 그 데이터를 어떤 순서로 읽는지도 굉장히 중요합니다.
배열은 이 부분에서 굉장히 강한 자료구조입니다.
배열은 단순해서 오히려 강하다
배열은 구조가 단순합니다.
별도의 노드가 필요하지 않습니다.
각 원소마다 다음 원소를 가리키는 포인터가 필요하지도 않습니다.
데이터를 저장하기 위한 부가 정보가 적습니다.
이 단순함은 실제 프로그램에서 큰 장점이 됩니다.
예를 들어, 링크드 리스트는 각 노드마다 다음 노드를 가리키는 포인터가 필요합니다.
양방향 링크드 리스트라면 이전 노드를 가리키는 포인터도 필요합니다.
즉, 실제 데이터 외에 연결 정보를 위한 추가 메모리가 필요합니다.
반면, 배열은 같은 타입의 데이터가 그냥 연속해서 저장됩니다.
이 구조는 메모리 사용량 측면에서도 단순하고, 접근 방식도 예측하기 쉽습니다.
자료구조를 처음 배울 때는 복잡한 구조일수록 더 좋은 자료구조처럼 느껴질 수 있습니다.
하지만 실제 개발에서는 단순한 구조가 더 강력한 경우가 많습니다.
특히 성능이 중요한 코드에서는 더 그렇습니다.
복잡한 구조는 유연성을 제공하지만, 그만큼 메모리 접근이 복잡해지고 예측하기 어려워질 수 있습니다.
반면 배열은 유연성은 떨어질 수 있지만, 데이터 접근 패턴이 단순하고 명확합니다.
이 점이 배열의 큰 장점입니다.
배열의 단점도 분명하다
그렇다고 배열이 모든 상황에서 좋은 자료구조라는 뜻은 아닙니다.
배열은 단점도 분명합니다.
가장 대표적인 단점은 크기가 고정되어 있다는 점입니다.
C++의 기본 배열은 한 번 크기를 정하면 실행 중에 크기를 바꾸기 어렵습니다.
int numbers[5] = { };
이 배열은 int 값 5개를 저장할 수 있습니다.
그런데 나중에 10개가 필요해졌다고 해서 이 배열이 자동으로 커지지는 않습니다.
더 큰 공간이 필요하면 새로운 배열을 만들고, 기존 데이터를 옮겨야 합니다.
이런 불편함 때문에 C++에서는 std::vector 같은 동적 배열을 많이 사용합니다.
vector는 내부적으로 배열과 비슷하게 연속된 메모리 구조를 사용하면서도, 필요할 때 용량을 늘릴 수 있도록 만들어진 컨테이너입니다.
vector는 배열의 장점을 유지하면서 크기 변경 문제를 어느 정도 해결한 구조라고 볼 수 있습니다.
다만 이 글에서는 vector 자체보다는 배열의 기본적인 성격을 이해하는 것에 더 집중하고자 합니다.
vector를 제대로 이해하려면 결국 배열을 먼저 이해해야 하기 때문입니다.
배열은 중간 삽입과 삭제에 약하다
배열의 또 다른 단점은 중간 삽입과 삭제가 불편하다는 점입니다.
아래와 같은 배열이 있다고 해보겠습니다.
[10][20][30][40][50]
여기서 20과 30 사이에 25를 넣고 싶다면 어떻게 해야 할까요?
결과는 아래와 같아야 합니다.
[10][20][25][30][40][50]
문제는 30, 40, 50을 뒤로 한 칸씩 밀어야 한다는 점입니다.
삭제도 비슷합니다.
중간에 있는 30을 삭제하면 뒤에 있는 40, 50을 앞으로 당겨야 합니다.
즉, 배열은 중간 삽입과 삭제에서 데이터 이동 비용이 발생합니다.
그래서 자료구조 시간에 배열은 중간 삽입과 삭제가 느리다고 배우게 됩니다.
이 설명은 맞습니다만, 이 설명만으로 배열을 낮게 평가하면 조금 아쉽습니다.
실제 프로그램에서는 중간 삽입과 삭제보다 순차 접근과 반복 처리가 훨씬 많이 발생하는 경우가 많기 때문입니다.
특히, 게임 엔진이나 그래픽스, 물리, 애니메이션 같은 시스템에서는 대량의 데이터를 매 프레임 반복해서 읽는 일이 굉장히 많습니다.
이런 경우에는 중간 삽입과 삭제 비용보다 배열의 순차 접근 성능이 더 중요해질 수 있습니다.
결국 중요한 것은 배열이 좋다, 나쁘다가 아닙니다.
내가 다루는 데이터가 어떤 방식으로 사용되는지를 이해하는 것입니다.
배열은 자료구조 학습의 기준점이다
배열은 너무 기본적인 자료구조라서 가볍게 넘어가기 쉽습니다.
하지만 사실 배열은 다른 자료구조를 이해하기 위한 기준점이 됩니다.
링크드 리스트를 배울 때도 배열과 비교하게 됩니다.
스택과 큐를 구현할 때도 배열을 사용할 수 있습니다.
해시 테이블도 내부적으로는 배열을 기반으로 동작하는 경우가 많습니다.
힙(Heap) 자료구조도 배열로 구현할 수 있습니다.
그래프도 인접 행렬 방식으로 표현하면 배열 기반 구조가 됩니다.
즉, 많은 자료구조가 결국 배열을 직접 사용하거나, 배열과 비교하면서 이해하는 과정을 거칩니다.
이런 관점에서 보면 배열은 단순한 입문용 자료구조가 아닙니다.
오히려 자료구조 전체를 이해하기 위한 기준이며 기반이 되는 자료구조입니다.
그래서 저는 수업에서 종종 배열이 굉장히 중요하다고 강조합니다.
조금 과하게 표현하면 “자료구조의 왕은 배열”이라고 말하기도 합니다.
물론 이 표현이 모든 상황에서 배열이 최고라는 뜻은 아닙니다.
그만큼 배열이 많은 자료구조의 기반이 되고, 실제 성능 측면에서도 매우 중요한 위치에 있다는 의미에 가깝습니다.
게임 개발에서 배열이 특히 중요한 이유
게임 개발에서는 배열 기반 사고가 특히 중요합니다.
게임은 매 프레임 반복되는 프로그램입니다.
플레이어 입력을 처리하고, 오브젝트를 업데이트하고, 충돌을 검사하고, 애니메이션을 갱신하고, 렌더링할 데이터를 준비합니다.
이 과정에서 많은 데이터를 반복해서 순회합니다.
다음과 같이 여러 적을 순회하면서 처리할 수도 있습니다.
for (int ix = 0; ix < enemyCount; ++ix)
{
enemies[ix].Update(deltaTime);
}
총알 목록을 순회할 수도 있습니다.
for (int ix = 0; ix < bulletCount; ++ix)
{
bullets[ix].Move(deltaTime);
}
충돌 판정을 위해 충돌 대상을 순회합니다.
for (int ix = 0; ix < colliderCount; ++ix)
{
CheckCollision(colliders[ix]);
}
이런 상황에서는 데이터가 연속적으로 배치되어 있고, 순차적으로 접근할 수 있다는 것이 큰 장점이 됩니다.
물론 실제 게임 엔진에서는 단순한 배열만 사용하는 것은 아닙니다.
std::vector, Unreal의 TArray, Unity에서는 C#의 List 같은 다양한 배열 기반의 자료구조를 사용합니다.
대부분 동적 배열을 사용하지만 핵심은 비슷합니다.
연속된 메모리 구조로 데이터를 저장하고, 그 데이터를 빠르게 순회하려는 의지를 확인할 수 있습니다.
이것이 바로 게임 개발에서 배열을 기반으로 생각할 수 있는 능력이 중요한 중요한 이유입니다.
배열을 이해하면 vector도 더 잘 이해된다
제 블로그에서 게임 엔진에서 vector를 많이 사용하는 이유에 대해 따로 정리한 적이 있습니다.
그 글에서는 vector가 왜 게임 엔진 구조와 잘 맞는지, linked list와 비교했을 때 어떤 장점이 있는지를 중심으로 설명했습니다.
이번 글은 그보다 더 기본적이고 직관적인 관점에서 배열을 그리고 연속적인 데이터 배치가 중요하다는 관점에서 글을 작성했습니다.
vector가 왜 좋은지 이해하려면 먼저 배열이 왜 좋은지 이해해야 합니다.
vector는 결국 동적 배열이기 때문입니다. 내부적으로는 연속된 메모리를 확보하고, 그 안에 데이터를 저장합니다.
용량이 부족하면 더 큰 메모리 공간을 확보한 뒤 기존 데이터를 옮깁니다.
즉, vector의 핵심적인 성격은 배열에서 출발합니다.
그래서 배열을 단순히 초급 문법으로만 보면 안 됩니다.
배열을 제대로 이해하면 vector, TArray, List, SoA, ECS 같은 구조도 훨씬 자연스럽게 연결됩니다.
최근 엔진들이 왜 데이터 배치와 순차 접근을 중요하게 보는지도 조금 더 쉽게 이해할 수 있습니다.
모든 자료구조를 배열로 해결해야 하는 것은 아니다
배열이 중요하다고 해서 모든 자료구조를 배열로 해결해야 한다는 뜻은 아닙니다.
이 부분은 정말 중요합니다.
실제로 트리, 해시 테이블, 그래프, 링크드 리스트 같은 자료구조가 더 적합한 상황도 분명히 존재합니다.
빠른 검색이 필요할 수도 있습니다.
계층 구조를 표현해야 할 수도 있습니다.
연결 관계 자체가 중요한 문제도 있습니다.
삽입과 삭제가 매우 빈번한 구조가 필요할 수도 있습니다.
이런 경우에는 배열만으로 문제를 해결하려고 하면 오히려 코드가 더 복잡해질 수 있습니다.
중요한 것은 배열을 맹신하는 것이 아닙니다.
배열을 기준점으로 삼고, 다른 자료구조가 왜 필요한지 이해하는 것입니다.
배열로 충분한 상황인지, 아니면 다른 자료구조가 필요한 상황인지를 판단할 수 있어야 합니다.
이 판단력이 자료구조 공부에서 굉장히 중요하다고 생각합니다.
마무리
배열은 가장 먼저 배우는 자료구조라서 너무 단순하게 느껴질 수 있습니다.
하지만 실제 프로그램 구조를 깊게 살펴보면 배열은 여전히 굉장히 강력하고 매력적인 자료구조입니다.
특히, 메모리 연속성, 인덱스 접근, 순차 처리, 캐시 효율이라는 관점에서 보면 배열은 컴퓨터 구조와 굉장히 잘 맞습니다.
그래서 많은 고성능 시스템들이 결국 배열 기반 구조로 돌아오는 경우가 많습니다.
게임 엔진도 마찬가지입니다.
겉으로는 Actor, Component, System 같은 다양한 구조가 보이지만, 내부를 살펴보면 많은 데이터가 배열 기반으로 저장되고 처리됩니다.
자료구조를 공부할 때 중요한 것은 더 복잡한 구조를 많이 아는 것이 아닙니다.
각 자료구조가 어떤 상황에서 강하고, 어떤 상황에서 약한지를 이해하는 것입니다.
실무 면접에서도 자료구조의 복잡함을 이해하는 능력을 먼저 보지 않습니다.
각 자료구조의 특징을 잘 이해하고, 상황에 맞게 자료구조를 선택할 수 있는 판단 능력을 검증하고 싶어합니다.
그리고 그 기준점에 배열이 있습니다.
그래서 배열은 단순한 입문용 자료구조가 아니라, 자료구조 전체를 이해하기 위한 가장 중요한 출발점이라고 생각합니다.
👉 게임 엔진 구조를 더 깊이 이해하고 싶다면
아래 강의를 통해 직접 구현해보는 것을 추천드립니다.
👉 C++로 만드는 게임 엔진 프레임워크 강의 바로가기