자료구조 기초: 배열부터 스택, 큐, 트리, 해시 테이블까지

본 블로그의 글은 강의를 목적으로 작성되었습니다. 예제는 개념을 보여주기 위해 단순화했으며, 실제 프로젝트에서는 표준 라이브러리 컨테이너를 우선 검토해주세요.

자료구조를 배운다고 하면 push, pop, 연결 리스트 노드처럼 외울 것이 먼저 떠오른다. 하지만 자료구조의 핵심은 함수 이름이 아니다. 데이터를 어떤 모양으로 보관하면 필요한 작업을 싸고 명확하게 만들 수 있는지 판단하는 일이다.

같은 값 열 개를 저장하더라도 하는 일에 따라 알맞은 구조가 달라진다. 인덱스로 자주 찾으면 배열이 편하고, 가장 최근 작업을 되돌리려면 스택이 자연스럽다. 먼저 들어온 요청부터 처리하려면 큐가 맞다. 키로 빠르게 찾으려면 해시 테이블을 생각할 수 있다.

이 글에서는 추상 자료형과 실제 메모리 표현을 구분한 뒤 배열, 동적 배열, 연결 리스트, 스택, 큐, 덱, 해시 테이블, 트리, 힙, 그래프를 차례로 살펴본다. C++ 예제를 사용하지만 개념은 다른 언어에도 그대로 적용된다.

자료구조와 추상 자료형은 다르다

스택은 “마지막에 넣은 값을 먼저 꺼낸다”는 동작 규칙이다. 내부를 연속 배열로 만들 수도 있고 연결 리스트로 만들 수도 있다. 이처럼 사용자에게 보이는 연산과 규칙을 추상 자료형, 실제 저장 방식을 자료구조 또는 구현이라고 구분하면 이해가 쉬워진다.

예를 들어 스택이라는 추상 자료형은 보통 다음 연산을 제공한다.

• push는 맨 위에 값을 넣는다.
• pop은 맨 위의 값을 제거한다.
• top 또는 peek은 제거하지 않고 맨 위 값을 본다.
• empty는 비었는지 확인한다.
• size는 원소 수를 알려준다.

std::stack은 이런 인터페이스를 제공하는 컨테이너 어댑터다. 내부 컨테이너는 기본적으로 std::deque지만 조건을 만족하면 다른 컨테이너를 사용할 수도 있다.

시간 복잡도를 읽는 최소 기준

자료구조를 비교할 때는 입력 크기 N이 커질수록 연산량이 어떻게 변하는지 본다.

복잡도만 보고 결정해서는 안 된다. 메모리 사용량, 캐시 지역성, 재할당 비용, 구현 난이도도 실제 성능과 안정성에 영향을 준다.

배열은 가장 기본적인 연속 저장소다

배열은 같은 타입의 원소를 메모리에 연속으로 둔다.

int scores[5] = { 10, 20, 30, 40, 50 };

첫 원소의 주소와 원소 크기를 알면 원하는 인덱스의 주소를 바로 계산할 수 있다.

address(i) = base + i × sizeof(element)

그래서 인덱스 접근은 O(1)이다. 원소가 붙어 있으므로 CPU 캐시에도 유리한 경우가 많다.

반면 중간에 값을 끼워 넣으려면 뒤의 원소를 밀어야 한다.

[10, 20, 30, 40]
인덱스 1에 15 삽입
[10, 15, 20, 30, 40]

최악의 경우 거의 모든 원소를 이동하므로 삽입과 삭제는 O(N)이다.

고정 길이가 컴파일 시점에 정해진 C++ 배열이 필요하다면 std::array가 편하다.

#include <array>

std::array<int, 5> scores { 10, 20, 30, 40, 50 };

동적 배열과 std::vector

동적 배열은 실행 중에 원소 수를 늘릴 수 있는 연속 저장소다. C++에서 가장 먼저 검토할 컨테이너는 대개 std::vector다.

#include <vector>

std::vector<int> values;
values.push_back(10);
values.push_back(20);
values.push_back(30);

vector는 보통 세 가지 상태를 관리한다.

• data()가 가리키는 연속 메모리
• 현재 원소 수인 size()
• 재할당 없이 담을 수 있는 수인 capacity()

공간이 남아 있으면 뒤에 추가하는 작업은 일정한 시간에 가깝다. 공간이 모자라면 더 큰 메모리를 확보하고 기존 원소를 옮긴다. 한 번의 재할당은 O(N)이지만 여러 번의 push_back 전체에 비용을 나눠 보면 평균적으로 상수 시간이다. 이를 amortized O(1)이라고 한다.

원소 수를 대략 알고 있다면 reserve로 재할당을 줄일 수 있다.

std::vector<int> values;
values.reserve(1'000);

for (int i = 0; i < 1'000; ++i)
{
    values.push_back(i);
}

재할당이 일어나면 기존 원소를 가리키던 포인터, 참조, 반복자가 무효가 될 수 있다. vector를 사용할 때 매우 자주 만나는 버그다.

연결 리스트는 노드가 다음 노드를 가리킨다

단일 연결 리스트의 각 노드는 값과 다음 노드의 위치를 가진다.

struct Node
{
    int value;
    Node* next;
};

노드는 메모리에서 서로 떨어져 있어도 된다. 알고 있는 노드 바로 뒤에 새 노드를 연결하는 작업은 포인터 몇 개만 바꾸므로 O(1)에 할 수 있다.

void insertAfter(Node* current, Node* newNode)
{
    newNode->next = current->next;
    current->next = newNode;
}

하지만 100번째 원소를 찾으려면 첫 노드부터 99개의 연결을 따라가야 한다. 임의 접근은 O(N)이다.

연결 리스트에는 다음 비용도 있다.

• 노드마다 포인터 저장 공간이 더 필요하다.
• 노드가 흩어져 있어 캐시 적중률이 낮을 수 있다.
• 직접 구현하면 메모리 소유권과 삭제를 실수하기 쉽다.

중간 삽입이 많다는 이유만으로 항상 리스트가 vector보다 빠른 것은 아니다. 삽입 위치를 찾는 비용과 메모리 접근 비용까지 측정해야 한다.

C++ 표준 라이브러리에는 단일 연결 리스트인 std::forward_list와 이중 연결 리스트인 std::list가 있다.

스택은 마지막 값을 먼저 꺼낸다

스택은 LIFO, Last In First Out 규칙을 사용한다. 접시를 쌓아 올린 모습을 생각하면 쉽다. 새 접시는 위에 놓고, 꺼낼 때도 위에서 꺼낸다.

#include <stack>

std::stack<int> numbers;
numbers.push(10);
numbers.push(20);
numbers.push(30);

int top = numbers.top();
numbers.pop();

위 코드가 끝나면 top은 30이고 스택에는 10과 20이 남는다.

pop은 값을 반환하지 않는다

C++의 std::stack::pop()은 맨 위 원소를 제거할 뿐 값을 반환하지 않는다. 값을 사용하려면 먼저 top()으로 읽고 그다음 pop()을 호출한다.

if (!numbers.empty())
{
    int value = numbers.top();
    numbers.pop();
    use(value);
}

제거와 값 복사를 분리하면 복사 또는 이동 중 예외가 발생했을 때 컨테이너 상태를 다루기 쉬워진다. 무엇보다 빈 스택에서 top()이나 pop()을 호출하지 않도록 먼저 확인해야 한다.

배열로 직접 만든 스택

스택의 내부 동작을 이해하기 위한 작은 구현이다.

#include <stdexcept>
#include <vector>

template <typename T>
class SimpleStack
{
public:
    void push(const T& value)
    {
        values_.push_back(value);
    }

    void pop()
    {
        if (values_.empty())
        {
            throw std::underflow_error("empty stack");
        }
        values_.pop_back();
    }

    T& top()
    {
        if (values_.empty())
        {
            throw std::underflow_error("empty stack");
        }
        return values_.back();
    }

    bool empty() const
    {
        return values_.empty();
    }

    std::size_t size() const
    {
        return values_.size();
    }

private:
    std::vector<T> values_;
};

뒤쪽 삽입과 삭제가 빠른 동적 배열을 사용했으므로 push, pop, top은 평균적으로 O(1)이다.

스택은 어디에 쓰일까?

스택은 최근 상태로 돌아가는 문제에 잘 맞는다.

• 함수 호출과 지역 변수를 관리하는 호출 스택
• 편집기의 실행 취소 기록
• 괄호가 올바르게 닫혔는지 검사
• 깊이 우선 탐색
• 후위 표기식 계산
• 재귀 알고리즘을 반복문으로 바꾸기

괄호 검사 예제를 보면 LIFO의 의미가 잘 드러난다.

#include <stack>
#include <string_view>

bool isBalanced(std::string_view text)
{
    std::stack<char> openings;

    for (char ch : text)
    {
        if (ch == '(' || ch == '[' || ch == '{')
        {
            openings.push(ch);
            continue;
        }

        if (ch != ')' && ch != ']' && ch != '}')
        {
            continue;
        }

        if (openings.empty())
        {
            return false;
        }

        char open = openings.top();
        openings.pop();

        bool matches = (open == '(' && ch == ')')
                    || (open == '[' && ch == ']')
                    || (open == '{' && ch == '}');

        if (!matches)
        {
            return false;
        }
    }

    return openings.empty();
}

큐는 먼저 들어온 값을 먼저 꺼낸다

큐는 FIFO, First In First Out 규칙을 사용한다. 대기 줄처럼 먼저 온 요청을 먼저 처리한다.

#include <queue>

std::queue<int> jobs;
jobs.push(101);
jobs.push(102);
jobs.push(103);

int first = jobs.front();
jobs.pop();

first는 101이다. 스택과 마찬가지로 pop()은 값을 반환하지 않는다.

큐의 대표적인 용도는 다음과 같다.

• 작업 스케줄링
• 메시지와 이벤트 처리
• 프린터 작업 목록
• 너비 우선 탐색
• 네트워크 패킷 버퍼

배열 큐와 원형 버퍼

배열의 맨 앞 원소를 지울 때마다 나머지를 당기면 O(N)이 든다. 대신 처음과 끝의 인덱스를 따로 관리하면 원소를 옮기지 않아도 된다.

고정 크기 배열의 끝에 도달했을 때 인덱스를 0으로 되돌려 공간을 재사용하는 구조를 원형 버퍼라고 한다.

#include <array>
#include <cstddef>
#include <stdexcept>

template <typename T, std::size_t Capacity>
class RingQueue
{
public:
    void push(const T& value)
    {
        if (size_ == Capacity)
        {
            throw std::overflow_error("full queue");
        }

        data_[tail_] = value;
        tail_ = (tail_ + 1) % Capacity;
        ++size_;
    }

    void pop()
    {
        if (size_ == 0)
        {
            throw std::underflow_error("empty queue");
        }

        head_ = (head_ + 1) % Capacity;
        --size_;
    }

    T& front()
    {
        if (size_ == 0)
        {
            throw std::underflow_error("empty queue");
        }
        return data_[head_];
    }

private:
    std::array<T, Capacity> data_ {};
    std::size_t head_ = 0;
    std::size_t tail_ = 0;
    std::size_t size_ = 0;
};

실시간 오디오, 게임 이벤트, 생산자와 소비자 사이의 고정 버퍼처럼 최대 크기를 정할 수 있는 곳에서 유용하다. 여러 스레드가 함께 쓴다면 이 코드만으로는 안전하지 않으며 별도의 동기화나 전용 concurrent queue가 필요하다.

덱은 양쪽 끝을 모두 사용한다

deque는 double-ended queue의 줄임말이다. 앞과 뒤에서 모두 삽입하고 삭제할 수 있다.

#include <deque>

std::deque<int> values;
values.push_front(10);
values.push_back(20);
values.pop_front();
values.pop_back();

작업 훔치기 스케줄러, 슬라이딩 윈도우, 양방향 대기열에 잘 맞는다. std::deque는 vector처럼 전체가 하나의 연속 메모리라는 보장은 없으므로 data() 기반의 단일 배열이 필요한 API에는 맞지 않는다.

우선순위 큐는 가장 중요한 값을 먼저 꺼낸다

일반 큐가 도착 순서를 지킨다면 우선순위 큐는 우선순위가 가장 높은 원소를 먼저 제공한다.

#include <queue>

std::priority_queue<int> scores;
scores.push(30);
scores.push(10);
scores.push(50);

int highest = scores.top();
scores.pop();

highest는 50이다. 내부에는 보통 힙을 사용한다.

대표 연산의 복잡도는 다음과 같다.

• 최댓값 또는 최솟값 확인은 O(1)이다.
• 삽입은 O(log N)이다.
• 최상위 원소 제거는 O(log N)이다.

경로 탐색의 방문 후보, 이벤트 시뮬레이션, 작업 우선순위 관리에 자주 사용한다.

해시 테이블은 키를 배열 위치로 바꾼다

해시 테이블은 키에 해시 함수를 적용해 저장할 버킷을 찾는다. C++의 대표 컨테이너는 std::unordered_map과 std::unordered_set이다.

#include <string>
#include <unordered_map>

std::unordered_map<std::string, int> health;
health["knight"] = 120;
health["mage"] = 70;

int mageHealth = health.at("mage");

분포가 괜찮고 부하율이 관리되면 검색, 삽입, 삭제가 평균 O(1)이다. 하지만 서로 다른 키가 같은 버킷을 선택하는 충돌은 피할 수 없다. 구현은 보통 체이닝이나 개방 주소법으로 충돌을 처리한다.

최악의 경우 한 버킷에 값이 몰려 O(N)이 될 수 있다. 좋은 해시 함수, 적절한 버킷 수, 공격자가 키를 조절할 수 있는지 여부가 중요하다.

해시 함수가 지켜야 할 성질

같은 키는 같은 실행 조건에서 같은 해시 결과를 내야 한다. 서로 다른 키는 가능한 한 고르게 퍼지는 편이 좋다. 암호학적 해시가 항상 필요한 것은 아니지만, 보안 경계의 입력에는 충돌 공격도 고려해야 한다.

사용자 정의 키를 unordered_map에 넣으려면 동등 비교와 해시가 같은 의미를 사용해야 한다. 두 키가 같다고 판단된다면 해시값도 반드시 같아야 한다.

트리는 계층 관계를 표현한다

트리는 노드가 자식 노드를 가지는 계층 구조다. 파일 시스템, UI 위젯, 장면 그래프, 문서 구조를 표현하기 좋다.

#include <memory>
#include <string>
#include <vector>

struct TreeNode
{
    std::string name;
    std::vector<std::unique_ptr<TreeNode>> children;
};

트리에서 자주 쓰는 용어가 있다.

• root는 부모가 없는 시작 노드다.
• parent와 child는 직접 연결된 위아래 노드다.
• leaf는 자식이 없는 노드다.
• depth는 root에서 얼마나 내려왔는지 나타낸다.
• height는 해당 노드에서 가장 먼 leaf까지의 거리다.
• subtree는 어떤 노드와 그 아래의 모든 노드다.

이진 탐색 트리

이진 탐색 트리의 각 노드는 최대 두 자식을 가진다. 흔한 규칙에서는 왼쪽 subtree에 더 작은 키를, 오른쪽 subtree에 더 큰 키를 둔다.

균형이 잘 잡혀 있으면 검색, 삽입, 삭제가 O(log N)이다. 하지만 정렬된 값을 단순한 이진 탐색 트리에 차례대로 넣으면 한쪽으로 길어져 연결 리스트처럼 될 수 있고 연산이 O(N)으로 나빠진다.

그래서 표준 라이브러리의 정렬 연관 컨테이너는 보통 red-black tree 같은 균형 트리를 사용한다.

#include <map>
#include <string>

std::map<std::string, int> scores;
scores["alice"] = 90;
scores["bob"] = 80;

std::map은 키 순서를 유지하고 대표 연산이 O(log N)이다. 순서가 필요 없고 평균 상수 시간 조회가 더 중요하면 std::unordered_map을 검토한다.

힙은 완전히 정렬된 트리가 아니다

최대 힙은 각 부모가 자식보다 작지 않다는 규칙을 지킨다. 최소 힙은 반대로 부모가 자식보다 크지 않다. 형제 사이의 순서나 전체 정렬은 보장하지 않는다.

완전 이진 트리 모양이므로 배열에 효율적으로 저장할 수 있다. 0부터 시작하는 인덱스를 쓴다면 노드 i의 관계는 다음과 같다.

left child  = 2 × i + 1
right child = 2 × i + 2
parent      = (i - 1) / 2

새 값을 배열 끝에 넣고 부모와 비교하며 올리는 과정을 sift up, 최상위 값을 제거한 뒤 마지막 값을 루트에 놓고 내리는 과정을 sift down이라고 한다.

힙은 최솟값이나 최댓값을 반복해서 꺼내는 일에는 강하지만 특정 값을 찾는 데는 일반적으로 O(N)이 필요하다.

트라이에는 문자열의 접두사를 저장한다

trie는 키의 각 문자나 비트를 경로로 사용하는 트리다. car, card, care는 car까지의 경로를 공유할 수 있다.

검색 시간은 저장된 전체 키 수보다 찾는 키 길이 L에 영향을 받아 보통 O(L)로 설명한다. 자동 완성, 사전, 접두사 검색, IP 라우팅에 사용할 수 있다. 자식 포인터가 많아지면 메모리 사용량이 커지므로 압축 trie나 다른 표현을 검토하기도 한다.

그래프는 일반적인 연결 관계를 표현한다

그래프는 vertex와 edge로 구성된다. 도로, 친구 관계, 퀘스트 의존성, 네트워크 연결처럼 계층 하나로 정리하기 어려운 관계를 나타낸다.

방향이 있을 수도 있고 없을 수도 있다. edge에 거리나 비용 같은 가중치를 둘 수도 있다.

인접 행렬

정점 수가 V일 때 V × V 표를 두고 연결 여부나 가중치를 저장한다.

• 두 정점의 연결 확인은 O(1)이다.
• 메모리는 O(V²)다.
• 연결이 많은 dense graph에 어울린다.

인접 리스트

각 정점마다 연결된 이웃 목록을 저장한다.

#include <vector>

using Graph = std::vector<std::vector<int>>;

Graph graph(4);
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(3);

메모리는 대략 O(V + E)이므로 연결이 드문 sparse graph에 적합하다. BFS는 큐를 사용하고 DFS는 재귀 호출 스택이나 명시적인 스택을 사용해 구현할 수 있다.

자료구조별 대표 복잡도

아래 표는 흔한 구현의 평균적인 기준이다. 구현과 조건에 따라 달라질 수 있다.

스택과 큐는 제한된 연산을 제공하는 추상 자료형이므로 구현에 적합한 컨테이너를 골라 성능이 결정된다.

어떤 구조를 선택해야 할까?

다음 질문부터 적으면 선택이 빨라진다.

1. 가장 자주 하는 연산은 무엇인가?
2. 순서를 유지해야 하는가?
3. 인덱스로 접근해야 하는가?
4. 키로 찾는가, 최솟값이나 최댓값을 반복해서 찾는가?
5. 원소 수의 최대치를 알 수 있는가?
6. 포인터와 참조의 안정성이 중요한가?
7. 메모리가 연속이어야 하는 외부 API와 연결하는가?
8. 여러 스레드가 동시에 접근하는가?

일반적인 값 목록이라면 std::vector부터 시작하는 것이 좋다. 실제 요구가 확인됐을 때 다른 구조로 바꾸는 편이 불필요한 복잡성을 줄인다.

자주 하는 실수

빈 스택과 큐에서 꺼낸다

top, front, back, pop을 호출하기 전에 비어 있지 않은지 보장해야 한다. 호출하는 쪽의 논리로 보장할 수도 있고, 안전한 래퍼에서 오류를 처리할 수도 있다.

pop이 값을 반환한다고 생각한다

C++ 표준의 stack과 queue에서 pop은 제거만 한다. 값을 먼저 읽고 제거한다.

vector 재할당 뒤의 포인터를 사용한다

push_back으로 capacity가 늘어나면 기존 저장소가 옮겨질 수 있다. 장기간 유지할 식별자가 필요하면 인덱스, 안정적인 핸들, 별도 소유 저장소 같은 방법을 검토한다.

연결 리스트가 삽입에 항상 빠르다고 생각한다

삽입할 노드를 이미 알고 있을 때만 포인터 변경이 O(1)이다. 위치를 찾는 데 O(N)이 들 수 있고, 작은 데이터에서는 vector의 연속 메모리가 더 빠른 경우가 흔하다.

해시 테이블을 항상 O(1)이라고 말한다

평균 복잡도와 최악 복잡도를 구분해야 한다. 재해시도 한 번에는 많은 원소를 옮긴다. 순회 순서도 안정적으로 유지된다고 가정하면 안 된다.

재귀 DFS의 깊이를 무시한다

그래프나 트리가 매우 깊으면 호출 스택을 소진할 수 있다. 입력 깊이가 제어되지 않는다면 명시적인 stack을 사용하는 반복 구현을 검토한다.

소유권 없는 원시 포인터로 트리를 만든다

누가 노드를 삭제하는지 명확하지 않으면 누수와 중복 삭제가 생긴다. 값 저장, arena, std::unique_ptr, 인덱스 기반 노드 풀 등 소유 구조를 먼저 정한다.

작은 연습 문제

개념은 직접 구현하고 관찰할 때 오래 남는다.

1. vector 하나로 stack을 만들고 빈 상태의 오류 정책을 정해본다.
2. 고정 배열로 원형 queue를 만들고 가득 찬 상태와 빈 상태를 구분한다.
3. 문자열의 괄호가 올바른지 stack으로 검사한다.
4. queue를 사용해 격자 지도의 최단 칸 수를 구한다.
5. unordered_map으로 단어 빈도를 센다.
6. 최소 힙으로 가장 작은 값 세 개를 차례대로 꺼낸다.
7. 인접 리스트 그래프를 BFS와 DFS로 각각 순회한다.
8. vector와 list의 중간 삽입 시간을 여러 데이터 크기에서 직접 측정한다.

마지막 문제에서는 삽입 위치를 찾는 시간과 실제 삽입 시간, 최적화 빌드 여부를 따로 생각해야 한다. 자료구조의 이름만으로 성능을 단정하지 않는 연습이다.

정리

배열과 동적 배열은 빠른 임의 접근과 좋은 캐시 지역성을 제공한다. 연결 리스트는 이미 알고 있는 위치의 연결을 바꾸기 쉽지만 임의 접근과 메모리 지역성에 비용이 있다.

스택은 최근 값을 먼저 처리하고, 큐는 먼저 들어온 값을 먼저 처리한다. 덱은 양쪽 끝을 쓰고, 우선순위 큐는 가장 중요한 값을 먼저 제공한다. 해시 테이블은 평균적으로 빠른 키 검색을, 균형 트리는 정렬된 순서와 로그 시간 연산을 제공한다. 힙은 최솟값이나 최댓값을 반복해서 꺼내는 데 알맞고, 그래프는 자유로운 연결 관계를 표현한다.

좋은 자료구조는 가장 어려워 보이는 구조가 아니다. 프로그램이 실제로 자주 하는 연산을 단순하고 예측 가능하게 만드는 구조가 좋은 선택이다.