자료구조 — 배열, 연결 리스트, 트리와 그래프

자료구조는 탐색, 삽입, 삭제, 순회 같은 흔한 작업을 더 쉽게 만들기 위해 데이터를 정리하는 방식입니다. 배열, 연결 리스트, 트리, 그래프를 이해하고 싶다면 가장 빠른 방법은 두 가지를 묻는 것입니다. 데이터는 어떤 형태를 가지는가, 그리고 어떤 연산이 싸게 느껴져야 하는가?

데이터가 순서열이라면 보통 배열이 출발점입니다. 각 항목이 주로 다음 항목을 가리킨다면 연결 리스트가 맞을 수 있습니다. 데이터에 단계나 레벨이 있다면 트리를 사용합니다. 항목들이 여러 방향으로 연결될 수 있다면 그래프를 사용합니다.

가장 짧고 유용한 규칙은 다음과 같습니다.

• 배열: 인덱스로 정렬된 순서에 가장 적합
• 연결 리스트: 사슬처럼 이어진 국소 연결에 가장 적합
• 트리: 계층 구조에 가장 적합
• 그래프: 네트워크에 가장 적합

배열, 연결 리스트, 트리, 그래프는 실제로 무엇을 하는가

배열은 항목을 고정된 순서로 저장하고, "항목 $7$"처럼 특정 위치를 직접 가리킬 수 있게 해 줍니다. 일반적인 연속 메모리 구현에서는 이런 직접 인덱싱이 $O(1)$입니다.

연결 리스트는 항목을 노드로 저장하고, 각 노드가 다른 노드를 가리키는 구조입니다. 노드에서 노드로 이동할 수는 있지만, $n$번째 항목에 도달하려면 보통 앞의 노드들을 차례로 지나가야 하므로 위치로 접근하는 비용은 대개 $O(n)$입니다.

트리는 데이터를 여러 레벨로 저장합니다. 각 노드는 자식을 가질 수 있으므로, 폴더 안에 또 다른 폴더가 있는 것 같은 중첩 구조를 자연스럽게 표현합니다. 탐색과 갱신 비용은 트리의 종류와 균형이 유지되는지에 따라 달라집니다.

그래프는 노드와 간선을 저장합니다. 트리와 달리 하나의 노드는 여러 다른 노드와 임의의 방식으로 연결될 수 있고, 사이클도 허용됩니다. 그래서 그래프는 도로망, 소셜 네트워크, 의존성 지도 같은 것을 표현하는 자연스러운 모델입니다.

빠른 비교: 각 자료구조가 잘 맞는 경우

구조	가장 알기 쉬운 비유	보통 잘하는 일	흔한 한계
배열	번호가 매겨진 항목들의 한 줄	인덱스로 직접 접근	중간 삽입과 삭제 시 항목을 자주 밀어야 함
연결 리스트	노드가 이어진 사슬	이미 알고 있는 노드 근처에서 삽입 또는 삭제	임의 접근이 느림
트리	가지치는 계층 구조	레벨과 부모-자식 관계 표현	동작이 트리 종류에 크게 좌우됨
그래프	연결 관계의 네트워크	도달 가능성, 경로, 관계 표현	알고리즘이 더 복잡한 경우가 많음

예제로 보기: 하나의 캠퍼스 앱에서 구조 고르기

시간표 화면, 강의 카탈로그, 도보 지도를 갖춘 하나의 캠퍼스 앱을 만든다고 해 봅시다. 자료구조를 고르는 가장 쉬운 방법은 각 기능을 그 데이터의 형태에 맞추는 것입니다.

시간표 화면의 요일 탭은 자연스럽게 배열입니다.

$$[\text{Mon}, \text{Tue}, \text{Wed}, \text{Thu}, \text{Fri}]$$

핵심 기능은 위치로 직접 접근하는 것입니다. "탭 $3$을 보여줘"라는 요청이 자연스럽고, 순서도 중요합니다.

강의 카탈로그는 자연스럽게 트리입니다.

$$\text{Department} \rightarrow \text{Course} \rightarrow \text{Section}$$

각 레벨이 다음 레벨을 포함합니다. 이것은 계층 구조이므로 트리가 가장 깔끔한 모델입니다.

건물 사이의 보행로는 자연스럽게 그래프입니다. 하나의 건물은 여러 다른 건물과 연결될 수 있고, 경로가 다시 되돌아오는 순환도 생길 수 있습니다. 도서관에서 실험실까지의 최단 경로를 찾고 싶다면, 그것은 트리 문제가 아니라 그래프 문제입니다.

연결 리스트는 같은 앱 안에서도 더 좁은 부분에 잘 맞습니다. 예를 들어 최근 방문한 화면들의 사슬이 있고, 주된 연산이 한 번에 한 단계씩 앞으로 또는 뒤로 이동하는 것이라면 그렇습니다. 이 경우 각 화면은 $20$번째 화면에 빠르게 접근하는 것보다 가까운 화면들과의 연결이 더 중요합니다.

핵심은 "최고"라는 말이 작업에 따라 달라진다는 점입니다. 하나의 제품 안에서도 데이터 관계가 서로 다르기 때문에 여러 자료구조를 함께 사용할 수 있습니다.

빠르게 구분하는 방법

많은 학생들은 처음에 이것들을 용어 암기처럼 배웁니다. 그래서 주제가 추상적으로 느껴지지만, 실제 질문은 더 단순합니다.

물어보세요. 어떤 연산이 싸게 느껴져야 하는가?

"위치 $i$로 바로 점프하기"가 싸야 한다면 배열이 강합니다. "다음 연결을 따라가기"가 싸야 한다면 연결 구조가 도움이 됩니다. "계층 아래로 내려가기"가 중요하다면 트리가 맞습니다. "두 대상이 연결되어 있는지 찾기"가 중요하다면 그래프가 맞습니다.

자료구조를 배울 때 흔한 실수

하나의 구조가 항상 가장 빠르다고 가정하기

항상 이기는 구조는 없습니다. "빠르다"는 것은 무엇을 가장 자주 하는지와 구현 방식에 따라 달라집니다.

트리는 자동으로 효율적이라고 생각하기

어떤 트리는 매우 효율적인 탐색을 지원하지만, 그것은 트리의 종류와 균형 같은 구조적 조건에 달려 있습니다. 모양이 나쁜 트리는 균형 잡힌 트리보다 훨씬 나쁘게 동작할 수 있습니다.

삽입이 싸 보인다는 이유만으로 연결 리스트를 고르기

삽입은 올바른 노드를 이미 알고 있을 때는 저렴할 수 있습니다. 하지만 그 노드를 찾는 데는 여전히 시간이 들 수 있습니다.

실제로는 그래프인 데이터를 트리로 사용하기

어떤 항목이 여러 부모를 가질 수 있거나, 교차 연결이나 사이클이 있다면, 그것을 억지로 트리에 넣는 것은 실제 구조를 가리고 이후 연산을 더 불편하게 만들 수 있습니다.

추상적인 구조와 프로그래밍 언어 기능을 혼동하기

프로그래밍 언어에서의 "array", "list", "map", "tree"는 메모리 사용량과 속도에 영향을 주는 구현 선택을 포함할 수 있습니다. 추상적인 개념과 실제 컨테이너는 관련은 있지만 완전히 같은 것은 아닙니다.

배열, 연결 리스트, 트리, 그래프는 언제 쓰이는가

배열은 순서 있는 컬렉션, 표, 버퍼처럼 위치가 중요한 경우에 사용됩니다.

연결 리스트는 임의 접근보다 국소적인 포인터 갱신이 더 중요한 특수한 구현에서 등장합니다.

트리는 파일 시스템, 문서 구조, 식 트리, 다양한 검색 인덱스처럼 계층적인 데이터에 사용됩니다.

그래프는 경로, 의존성 분석, 네트워크 모델링, 추천 연결, 그리고 일반적인 연결 문제에 사용됩니다.

올바른 자료구조를 고르는 방법

먼저 두 가지를 물어보세요.

1. 데이터는 어떤 관계를 가지는가: 순서열, 계층, 아니면 네트워크?
2. 어떤 연산이 가장 중요한가: 인덱싱, 국소 갱신, 계층 순회, 아니면 경로 찾기?

이 두 가지 답만으로도 보통 선택 범위를 빠르게 좁힐 수 있습니다.

그래도 확신이 서지 않는다면, 종이에 아주 작은 예시 데이터를 그려 보세요. 코드를 쓰기 전에 그림이 구조를 먼저 드러내는 경우가 많습니다.

직접 해보기

플레이리스트, 폴더 시스템, 대중교통 노선도처럼 익숙한 예시 세 가지를 골라 보세요. 각각이 주로 순서열인지, 계층인지, 네트워크인지 판단한 뒤, 핵심 연산이 쉬워지는 구조를 선택해 보세요. 스스로 더 연습할 사례가 필요하다면 GPAI Solver가 비슷한 분류 예시를 만들어 줄 수 있습니다.