저는 자료구조를 ‘정밀하게’ 쓰려고 합니다
저는 코드를 짤 때 자료구조 선택을 대충 넘기지 않습니다. 습관적으로 리스트부터 선언하는 대신, 이 데이터가 앞으로 어떻게 다뤄질지를 먼저 따집니다.
기준은 세 가지입니다. 대량의 데이터가 들어왔을 때 search가 충분히 빠른가, delete가 빠른가, add가 빠른가. 데이터가 열 개일 때는 뭘 써도 똑같습니다. 문제는 그게 만 개가 되는 순간입니다.
Unity Korea의 게임 로직에 꼭 필요한 자료구조 방송에서도 같은 이야기를 합니다. 자료구조를 어떻게 잘 쓰고 적절하게 쓰냐가 성능과 직결되는 문제라는 것이죠. 게임뿐 아니라 모든 종류의 소프트웨어에 해당한다고 설명합니다.
그래서 제가 실제로 쓰는 기준을 아래 표로 먼저 정리했습니다.
| 상황 | 제가 고르는 것 | 이유 |
|---|---|---|
| 키로 자주 찾아야 함 | Dictionary | search가 빠르고 코드가 읽힘 |
| 고정된 데이터, 변하지 않음 | Array | 인덱스 접근, 메모리 적게 듦 |
| 삭제·추가가 매우 빈번 | List | 유연함. 단 search는 포기 |
| 순서를 반드시 지켜야 함 | Stack / Queue | 순서 자체가 보장됨 |
| 대량 데이터가 동적으로 늘고 검색도 필요 | 이진트리 | 범위 탐색이 빠름 |
Dictionary를 가장 많이 쓰는 두 가지 이유
제가 가장 많이 쓰는 자료구조는 Dictionary입니다. 이유는 두 가지입니다.
첫째, search가 빠릅니다. 키를 넣으면 값이 바로 나옵니다. 순차 탐색처럼 처음부터 하나씩 뒤지지 않습니다.
둘째, key/value 구조라서 readability가 뛰어납니다. 이게 생각보다 큽니다. items[3]보다 items["golden_apple"]이 훨씬 명확합니다. 6개월 뒤의 저에게도, 옆자리 동료에게도 그렇습니다.
앞서 언급한 Unity 방송에서는 Dictionary의 내부 동작을 이렇게 설명합니다. 키를 해시 함수에 넣어 숫자를 뽑고, 그 숫자를 인덱스로 써서 배열에 값을 넣습니다. 그래서 찾을 때도 키만 해시로 돌리면 몇 번째 칸인지 바로 나옵니다. 시간 복잡도로는 O(1), 즉 배열의 랜덤 액세스와 같은 수준입니다.
다만 해시값이 겹치는 충돌이 생길 수 있고, 이때는 내부적으로 링크드 리스트를 붙여 처리한다고 합니다. 방송에서는 실제로 쿠폰을 대량 발급하다가 해시가 겹쳐서 두 유저에게 같은 쿠폰이 나간 사례를 소개하기도 했습니다.
저는 이 내부 구조까지 알고 쓸 필요가 있다고 봅니다. “Dictionary는 빠르다"만 알면 무한정 빠른 줄 압니다. 하지만 키 개수가 커지면 충돌 확률도 올라가고, 키 자체를 해시로 바꾸는 비용도 공짜가 아닙니다. 키를 무거운 객체로 잡지 말아야 한다는 판단이 여기서 나옵니다.
변하지 않는 데이터는 Array가 정답입니다
고정되어 변하지 않는 데이터의 경우 저는 Array를 많이 씁니다.
인덱스를 미리 define으로 걸어두면 바로바로 접근할 수 있습니다. 메모리도 훨씬 적게 들고 안정적입니다. 크기가 고정이니 중간에 재할당이 일어날 일이 없습니다.
이 부분은 List와 비교하면 차이가 분명해집니다. Unity 방송의 설명에 따르면, C#의 List는 내부적으로 배열을 쓰되 여유 공간(capacity)을 미리 잡아둡니다. 그러다 공간이 꽉 차면 새 배열을 만들고, 기존 데이터를 전부 복사한 뒤, 크기를 두 배로 늘립니다. 1만짜리 배열이 넘치면 2만이 되고, 또 넘치면 4만이 됩니다.
이 복사 작업이 느린 작업이라는 점이 핵심입니다. 데이터가 안 변할 걸 아는데도 List를 쓰면, 쓰지도 않을 여유 공간을 들고 다니면서 재할당 위험까지 안는 셈입니다.
Array를 선택하기 전 체크리스트
- 이 데이터의 개수가 런타임에 바뀌는가? 안 바뀌면 Array
- 인덱스로 접근하는 규칙을 만들 수 있는가? 만들 수 있으면 Array
- 중간 삽입·삭제가 있는가? 있으면 Array는 후보에서 제외
- 이 데이터를 인스펙터나 설정 파일에서 편집해야 하는가? 그렇다면 Array나 List가 유리
List는 씁니다. 다만 즐겨 쓰진 않습니다
삭제와 추가가 빈번한 데이터에는 List를 가져다 쓰기도 합니다. 크기를 미리 정하지 않아도 되고, Add와 Remove가 편합니다.
그런데 저는 List를 즐겨 쓰지 않습니다. search가 약하기 때문입니다. 조건에 맞는 요소를 찾으려면 결국 처음부터 끝까지 순회해야 합니다. 최악의 경우 데이터 개수만큼 다 뒤져야 하고, 이걸 O(n)이라고 표현합니다.
데이터가 100개면 체감이 안 됩니다. 10만 개가 되고, 그 탐색이 매 프레임 돌아가면 그때는 얘기가 달라집니다.
그래서 제 기준은 이렇습니다. “찾는 일"이 주 업무면 Dictionary, “담고 빼는 일"이 주 업무면 List. 둘 다 필요하면 List로 담고 시작 시점에 Dictionary로 한 번 복사해 씁니다. Unity 방송에서 소개한 Creator Kit RPG 데모도 정확히 이 방식을 씁니다. 대화 데이터를 List로 선언해 인스펙터에서 기획자가 편집할 수 있게 하고, 실행 시점에 그걸 Dictionary로 옮겨 담아 런타임 접근을 빠르게 만듭니다.
Stack과 Queue는 ‘순서’를 코드가 아니라 자료구조로 보장합니다
저는 Stack과 Queue를 많이 씁니다. 이유는 하나입니다. 데이터의 순서를 보장하기 때문입니다.
특정 데이터의 순서를 반드시 지켜야 하는 상황이 있습니다. 이때 List에 담고 인덱스로 순서를 관리하면, 그 순서 규칙이 코드 여기저기에 흩어집니다. 누군가 중간에 요소 하나만 지워도 규칙이 깨집니다.
Stack과 Queue는 순서 규칙이 자료구조 자체에 들어 있습니다. 실수할 여지가 줄어듭니다.
- Queue(FIFO) — 먼저 들어온 게 먼저 나갑니다. 입력받은 순서대로 처리해야 하는 일에 씁니다.
- Stack(LIFO) — 나중에 들어온 게 먼저 나갑니다. 가장 최근 상태로 되돌아가야 하는 일에 씁니다.
Unity 방송에서는 이 둘의 대표 사례를 각각 보여줍니다. Stack은 커맨드 패턴 기반의 Undo/Redo입니다. 실행한 명령을 스택에 쌓아두고, Undo를 누르면 꺼내서 되돌립니다. Undo 스택과 Redo 스택 두 개를 두고 서로 옮겨 담는 구조입니다. Queue는 격투 게임의 콤보 입력 판정입니다. 버튼 입력을 커맨드 객체로 만들어 Queue에 쌓고, 들어온 순서대로 콤보 룰과 대조합니다.
두 사례 모두 “순서가 곧 기능"인 경우입니다. 이럴 때 List로 흉내 내는 건 손해입니다.
이진트리는 지도의 충돌 영역을 잡을 때 썼습니다
이진트리는 동적으로 추가되는 대량의 자료를 빠르게 검색해야 할 때 씁니다.
제 경우에는 지도의 충돌 위치 영역을 러프하게 잡을 때 썼던 기억이 있습니다. 맵 위에 있는 오브젝트들의 충돌 후보를 좁히는 작업이었습니다. 전부 다 검사하면 O(n²)에 가까워집니다. 트리로 공간을 나눠두면 애초에 검사 대상이 크게 줄어듭니다.
Unity 방송에서도 Unity 엔진 내부가 같은 접근을 쓴다고 설명합니다. 하이어라키가 트리 구조이고, 오클루전 컬링이나 카메라 프러스텀 컬링에서 공간을 효율적으로 관리하기 위해 옥트리를 씁니다. 3차원 공간을 여덟 개로 계속 쪼개는 트리입니다.
제가 썼던 방식도 결국 같은 원리입니다. 공간을 쪼개서 “여기는 볼 필요 없다"를 빠르게 판정하는 것. 반씩 잘라 들어가는 탐색이 O(log n)이 되는 이유와 정확히 같습니다.
한 가지 덧붙이자면, 이진트리는 앞서 나온 것들과 성격이 다릅니다. Dictionary나 Queue는 언어가 잘 만들어 제공하니 갖다 쓰면 됩니다. 하지만 트리나 그래프는 용도에 맞게 직접 구현해야 하는 경우가 많습니다. Unity 방송에서도 FSM이나 비헤이비어 트리 같은 건 직접 구현하는 경우가 굉장히 많다고 언급합니다. 그래서 원리를 아는 것이 실제 코드로 이어집니다.
바이브 코딩 시대에 자료구조 지식은 오히려 더 중요합니다
여기서부터는 제 의견입니다.
자료구조 지식은 개발을 하면 할수록 중요하다는 생각이 듭니다. 그리고 바이브 코딩의 시대에 오히려 더 그렇습니다.
이유는 이렇습니다. AI에게 코드를 시키면 대체로 동작하는 코드가 나옵니다. 문제는 그다음입니다. AI가 뽑아준 코드에 대고 “이거 최적화 한번 더 봐줘"라고 요청하려면, 뭘 최적화해야 하는지에 대한 감각이 있어야 합니다. 그 감각의 근거가 바로 자료구조 지식입니다.
“이 조회가 매 프레임 돌아가는데 List 순회로 되어 있네, Dictionary로 바꾸면 어떨까?” — 이런 질문은 자료구조를 모르면 나오지 않습니다. AI는 물어보지 않으면 대체로 먼저 고쳐주지 않습니다.
Unity 방송에서도 비슷한 맥락의 이야기가 나옵니다. 요즘 IDE와 AI가 박싱 같은 성능 이슈를 미리 경고해준다고요. 다만 저는 여기서 한 걸음 더 나가야 한다고 봅니다. 경고를 읽고 판단하는 것과, 경고가 없는 곳에서 문제를 의심하는 것은 다른 능력입니다. 후자는 여전히 사람 몫입니다.
뛰어난 개발자가 되려면 자료구조는 반드시 숙지해야 합니다. 도구가 좋아질수록, 도구에게 던지는 질문의 수준이 결과를 가릅니다.
마치며
- 자료구조 선택 기준은 세 가지입니다. 대량 데이터에서 search, delete, add가 각각 충분히 빠른지 따져보십시오.
- 저는 Dictionary를 가장 많이 씁니다. 빠른 검색과 key/value의 가독성 때문입니다.
- 변하지 않는 데이터는 Array, 삽입·삭제가 잦으면 List, 순서가 곧 기능이면 Stack/Queue를 씁니다.
- 이진트리는 공간을 쪼개 검사 대상을 줄이는 용도로 유용합니다. 저는 지도 충돌 영역 판정에 썼습니다.
- AI가 코드를 써주는 시대일수록 자료구조 지식이 중요합니다. 최적화를 요청할 근거가 거기서 나오기 때문입니다.
자주 묻는 질문
Q. Dictionary와 List 중 뭘 써야 할지 모르겠습니다. 기준이 있나요?
그 데이터를 주로 “찾는지” 아니면 “담고 빼는지"로 나누십시오. 키로 특정 항목을 자주 조회한다면 Dictionary, 전체를 순회하거나 추가·삭제가 주 업무라면 List입니다. 둘 다 필요하면 List로 데이터를 받고 초기화 시점에 Dictionary로 복사해두는 방법이 있습니다.
Q. C#의 List는 크기가 자동으로 늘어나는데, 그럼 그냥 List만 써도 되지 않나요?
자동으로 늘어나긴 하지만 공짜가 아닙니다. 여유 공간이 꽉 차면 새 배열을 만들고 기존 데이터를 전부 복사한 뒤 크기를 두 배로 늘립니다. 데이터가 만 단위로 커지면 이 복사 비용이 부담이 됩니다. 최대 크기를 예측할 수 있다면 생성 시점에 capacity를 지정해두는 편이 좋습니다.
Q. ArrayList는 왜 쓰지 말라고 하나요?
타입을 지정하지 않아 모든 요소를 object로 저장하기 때문입니다. 꺼낼 때마다 캐스팅이 필요하고 그 과정에서 박싱·언박싱이 일어납니다. 이게 쌓이면 가비지 컬렉터 부하로 돌아옵니다. 제네릭 버전인 List<T>는 컴파일 시점에 타입이 확정되므로 이 문제가 없습니다.
Q. Stack과 Queue를 List로 대신 구현하면 안 되나요?
동작은 합니다. 다만 순서 규칙을 코드로 직접 관리해야 해서 실수할 여지가 생깁니다. Stack과 Queue는 순서 보장이 자료구조 자체에 들어 있어, 규칙이 코드 여기저기로 흩어지지 않습니다.
Q. 자료구조를 직접 구현해봐야 하나요?
Array, List, Queue, Stack, Dictionary처럼 언어가 제공하는 것들은 이미 충분히 최적화되어 있어 직접 만들 일이 거의 없습니다. 다만 내부 동작 원리는 알아야 제대로 골라 쓸 수 있습니다. 반대로 트리나 그래프는 용도에 맞게 직접 구현해야 하는 경우가 많습니다.