테마
09. 자료구조 기초 - 선형과 비선형
학습 목표
- 자료구조가 무엇이며, 왜 필요한지 이해한다
- 선형 자료구조(배열, 스택, 큐)의 특징과 동작 원리를 설명할 수 있다
- 비선형 자료구조(이진 트리, 이진 탐색 트리)의 구조와 검색 원리를 설명할 수 있다
- 선형 검색과 이진 탐색 트리 검색의 성능 차이를 비교할 수 있다
- 데이터베이스 인덱스에 비선형 구조가 사용되는 이유를 이해한다
전체 구조
1. 자료구조란?
정의
자료구조(Data Structure)란 데이터를 효율적으로 저장하고 관리하기 위한 체계적인 구조를 말한다. 프로그래밍에서 데이터를 다루는 일은 피할 수 없고, 그 데이터의 양이 많아질수록 "어떻게 정리해 놓느냐"가 성능을 결정짓는 핵심 요소가 된다.
왜 필요한가?
데이터가 10개일 때는 어떤 방식으로 저장하든 큰 차이가 없다. 하지만 데이터가 100만 개, 1000만 개로 늘어나면 이야기가 완전히 달라진다. 빠르게 찾고, 빠르게 추가하고, 빠르게 삭제하려면 데이터를 체계적으로 정리해 놓아야 한다. 잘 정리해 놔야 원하는 시점에 원하는 정보를 빠르게 액세스할 수 있다.
실생활 비유: 정리된 방 vs 어질러진 방
방이 어질러져 있다고 생각해 보자. 책, 옷, 열쇠, 서류가 바닥 여기저기에 흩어져 있다. 열쇠를 찾으려면 방 전체를 뒤져야 한다. 하지만 서랍장에 종류별로 잘 정리해 놓았다면? "열쇠는 첫 번째 서랍"이라는 것만 알면 바로 꺼낼 수 있다.
자료구조도 마찬가지다. 데이터를 어떤 규칙으로 정리해 놓느냐에 따라 검색, 삽입, 삭제의 속도가 천차만별이다.
자료구조의 분류
자료구조는 크게 두 가지로 나뉜다.
| 분류 | 특징 | 대표 예시 |
|---|---|---|
| 선형 자료구조 | 데이터가 일렬로 나열됨. 순서가 있음 | 배열, 스택, 큐, 연결 리스트 |
| 비선형 자료구조 | 데이터가 계층적이거나 네트워크 형태 | 트리, 그래프 |
2. 선형 자료구조 - 배열 (Array)
개념
배열은 데이터를 연속된 메모리 공간에 순서대로 나열한 구조다. 각 데이터에는 고유한 번호(인덱스)가 붙어 있어서, 이 번호만 알면 해당 데이터에 즉시 접근할 수 있다.
인덱스: [0] [1] [2] [3] [4]
데이터: | 사과 | 바나나 | 포도 | 딸기 | 수박 |array[0]은 "사과", array[3]은 "딸기"에 바로 접근한다.
장점
- 인덱스로 즉시 접근 가능: 몇 번째 데이터든 O(1), 즉 한 번에 접근할 수 있다. 배열 크기가 아무리 커도 인덱스 접근 속도는 동일하다.
단점
- 중간 삽입/삭제가 비효율적: 중간에 데이터를 끼워 넣으려면 뒤의 모든 데이터를 한 칸씩 밀어야 한다. 삭제할 때도 빈 자리를 메우기 위해 뒤의 데이터를 당겨야 한다.
실생활 비유: 극장 좌석
영화관에서 좌석이 일렬로 배치되어 있다고 생각하자. "B열 7번 좌석"이라고 하면 바로 찾아갈 수 있다. 하지만 이미 모두 앉아 있는 상태에서 중간에 한 사람이 끼어들려면? 그 뒤의 모든 사람이 한 자리씩 옆으로 이동해야 한다. 매우 번거롭다.
3. 선형 자료구조 - 스택 (Stack)
개념
스택은 LIFO(Last In, First Out) 원칙을 따르는 자료구조다. 마지막에 넣은 데이터를 가장 먼저 꺼낸다. 데이터를 넣는 행위를 Push, 꺼내는 행위를 Pop이라 한다.
실생활 비유: 접시 쌓기
식당에서 접시를 하나씩 쌓는다고 상상하자. 접시를 꺼낼 때는 맨 위에 있는 접시부터 꺼내야 한다. 맨 아래 접시를 꺼내려면 위의 접시를 모두 치워야 한다. 이것이 바로 스택의 원리다.
동작 흐름
핵심 정리
| 연산 | 설명 | 시간 복잡도 |
|---|---|---|
| Push | 스택 맨 위에 데이터 삽입 | O(1) |
| Pop | 스택 맨 위에서 데이터 꺼내기 | O(1) |
| Peek | 맨 위 데이터를 꺼내지 않고 확인만 | O(1) |
실전 활용 사례
- 함수 호출 스택: 프로그램이 함수를 호출하면 호출 정보가 스택에 쌓이고, 함수가 끝나면 스택에서 빠진다. 함수 A가 함수 B를 호출하고, B가 C를 호출하면 C부터 먼저 종료된다.
- 브라우저 뒤로가기: 방문한 페이지가 스택에 쌓인다. "뒤로가기"를 누르면 가장 최근에 방문한 페이지(스택의 Top)로 돌아간다.
- Undo 기능: 텍스트 편집기에서 Ctrl+Z를 누르면 가장 마지막 작업부터 취소된다. 작업 이력이 스택에 저장되어 있기 때문이다.
4. 선형 자료구조 - 큐 (Queue)
개념
큐는 FIFO(First In, First Out) 원칙을 따르는 자료구조다. 먼저 넣은 데이터를 먼저 꺼낸다. 데이터를 넣는 행위를 Enqueue, 꺼내는 행위를 Dequeue라 한다.
실생활 비유: 편의점 계산대 줄
편의점 계산대 앞에 줄을 서는 상황을 떠올리자. 먼저 줄을 선 사람이 먼저 계산하고 나간다. 새로 온 사람은 줄 맨 뒤에 선다. 새치기는 허용되지 않는다. 이것이 큐의 원리다.
동작 흐름
핵심 정리
| 연산 | 설명 | 시간 복잡도 |
|---|---|---|
| Enqueue | 큐의 뒤(Rear)에 데이터 삽입 | O(1) |
| Dequeue | 큐의 앞(Front)에서 데이터 꺼내기 | O(1) |
| Front | 맨 앞 데이터를 꺼내지 않고 확인만 | O(1) |
실전 활용 사례
- 프린터 대기열: 인쇄 요청이 들어온 순서대로 출력된다. 먼저 요청한 문서가 먼저 인쇄된다.
- 작업 스케줄링: 운영체제가 프로세스를 실행할 때, 대기 중인 작업을 큐에 넣고 순서대로 처리한다.
- 메시지 큐: 서버 간 통신에서 메시지를 순서대로 처리하기 위해 큐를 사용한다 (RabbitMQ, Kafka 등).
스택 vs 큐 비교
| 항목 | 스택 (Stack) | 큐 (Queue) |
|---|---|---|
| 원칙 | LIFO (후입선출) | FIFO (선입선출) |
| 비유 | 접시 쌓기 | 줄서기 |
| 삽입 | Push (위에 쌓기) | Enqueue (뒤에 줄서기) |
| 삭제 | Pop (위에서 꺼내기) | Dequeue (앞에서 나가기) |
| 활용 | Undo, 뒤로가기, 함수 호출 | 프린터, 스케줄링, 메시지 처리 |
5. 선형 자료구조의 검색 한계
문제 제기
선형 자료구조에서 특정 데이터를 찾으려면 어떻게 해야 할까? 기본적으로 순차 검색(Linear Search), 즉 처음부터 끝까지 하나씩 확인하는 방법밖에 없다.
예시 1: 5개 데이터에서 "5"를 찾기
데이터: [3, 1, 4, 2, 5]
- 3 확인 -- 아님
- 1 확인 -- 아님
- 4 확인 -- 아님
- 2 확인 -- 아님
- 5 확인 -- 찾았다!
최악의 경우 5번 비교해야 찾을 수 있다.
예시 2: 7개 데이터에서 "없는 값"을 찾기
데이터: [1, 3, 4, 5, 8, 9, 10]에서 "6"을 찾는 경우
- 1 확인 -- 아님
- 3 확인 -- 아님
- 4 확인 -- 아님
- 5 확인 -- 아님
- 8 확인 -- 아님
- 9 확인 -- 아님
- 10 확인 -- 아님
반드시 7번 전부 비교해야 "6은 없다"고 판단할 수 있다. 하나라도 빠뜨리면 "혹시 있을지도 모른다"는 불확실성이 남기 때문이다.
핵심 문제: Worst Case
순차 검색의 최악의 경우(Worst Case)는 전체 데이터를 모두 뒤져야 하는 상황이다. 데이터가 n개이면 최악의 경우 n번 비교해야 한다. 이를 **O(n)**이라고 표현한다.
데이터가 100개면 최악 100번, 10만 개면 최악 10만 번, 1000만 개면 최악 1000만 번 비교해야 한다. 데이터가 늘어날수록 검색 시간이 선형으로 증가하는 것이다. 이는 대규모 데이터를 다룰 때 치명적인 문제가 된다.
검색 과정 시각화
결론: 선형 자료구조에서의 검색은 데이터가 많아지면 너무 느리다. 더 나은 방법이 필요하다.
6. 비선형 자료구조 - 이진 트리 (Binary Tree)
트리란?
트리(Tree)는 계층적 구조로 데이터를 배치하는 자료구조다. 일상에서 볼 수 있는 회사 조직도, 파일 탐색기의 폴더 구조, 가계도 등이 모두 트리 구조다.
이진 트리란?
이진 트리(Binary Tree)는 각 노드가 최대 2개의 자식(왼쪽, 오른쪽)을 가지는 트리다.
핵심 용어
| 용어 | 설명 |
|---|---|
| 루트(Root) | 트리의 최상단 노드. 트리의 시작점 |
| 부모(Parent) | 자식 노드를 가지는 상위 노드 |
| 자식(Child) | 부모 노드 아래에 연결된 하위 노드 (왼쪽 자식, 오른쪽 자식) |
| 리프(Leaf) | 자식이 없는 말단 노드. 트리의 끝 지점 |
| 깊이(Depth) | 루트에서 해당 노드까지의 거리 (루트의 깊이는 0) |
| 높이(Height) | 트리에서 가장 깊은 리프까지의 거리 |
이진 트리 구조 시각화
- 파란색 노드 5가 루트(Root)
- 초록색 노드 3과 9는 부모이자 자식 (5의 자식이면서 각각 하위 노드의 부모)
- 노란색 노드 1, 4, 8, 10은 리프(Leaf) -- 더 이상 자식이 없는 말단 노드
실생활 비유: 토너먼트 대진표
스포츠 토너먼트 대진표를 떠올리면 된다. 결승전(루트)에서 시작해 아래로 내려가면 준결승(자식), 8강(그 아래 자식)이 있다. 맨 아래 첫 경기를 치르는 선수들이 리프 노드다.
7. 이진 탐색 트리 (Binary Search Tree, BST)
개념
이진 탐색 트리(BST)는 이진 트리에 정렬 규칙을 추가한 것이다.
규칙: 왼쪽 자식 < 부모 < 오른쪽 자식
이 단순한 규칙 하나가 검색 성능을 극적으로 향상시킨다.
BST 예시
5
/ \
3 9
/ \ / \
1 4 8 10- 5의 왼쪽(3)은 5보다 작고, 오른쪽(9)은 5보다 크다
- 3의 왼쪽(1)은 3보다 작고, 오른쪽(4)은 3보다 크다
- 9의 왼쪽(8)은 9보다 작고, 오른쪽(10)은 9보다 크다
- 모든 노드에서 이 규칙이 성립한다
BST에서 "6"을 검색하는 과정
위 트리에 저장된 데이터는 1, 3, 4, 5, 8, 9, 10으로 총 7개다. 여기서 "6"이 있는지 찾아보자.
- 루트(5)와 비교: 6 > 5 -- 오른쪽 방향으로 간다 (왼쪽은 전부 5 이하이므로 볼 필요 없음)
- 9와 비교: 6 < 9 -- 왼쪽 방향으로 간다 (오른쪽은 전부 9 이상이므로 볼 필요 없음)
- 8과 비교: 6 < 8 -- 왼쪽으로 가야 하는데, 8의 왼쪽 자식이 없음 -- "6은 존재하지 않음"
단 3번의 비교로 부재 판단 완료!
같은 데이터 7개를 선형 검색하면 7번 비교해야 "없다"고 판단할 수 있었다. BST는 절반 이하의 비교로 결론을 내린다.
BST 검색 과정 시각화
- 주황색: 실제로 비교한 노드 (3개만 방문)
- 회색: 방문하지 않은 노드 (확인할 필요 없음)
왜 빠른가?
BST의 핵심은 매 비교마다 탐색 범위가 절반으로 줄어든다는 점이다.
1단계에서 루트와 비교하면 왼쪽 절반 또는 오른쪽 절반을 통째로 제외할 수 있다. 2단계에서 다시 절반을 제외한다. 이런 식으로 매 단계마다 후보가 반씩 줄어들기 때문에, 전체를 다 뒤지지 않고도 빠르게 결론에 도달한다.
8. 선형 검색 vs 이진 탐색 트리 검색 성능 비교
시간 복잡도 비교
| 구분 | 선형 검색 | BST 검색 (균형 트리) |
|---|---|---|
| 최선 (Best) | O(1) -- 첫 번째에 발견 | O(1) -- 루트에 있는 경우 |
| 평균 (Average) | O(n/2) | O(log n) |
| 최악 (Worst) | O(n) -- 끝까지 또는 없음 | O(log n) -- 균형 트리인 경우 |
실제 비교 횟수로 체감하기
| 데이터 수 (n) | 선형 검색 최악 | BST 검색 최악 | 차이 |
|---|---|---|---|
| 10 | 10번 | 약 4번 | 2.5배 |
| 100 | 100번 | 약 7번 | 14배 |
| 1,000 | 1,000번 | 약 10번 | 100배 |
| 10,000 | 10,000번 | 약 14번 | 714배 |
| 100,000 | 100,000번 | 약 17번 | 5,882배 |
| 1,000,000 | 1,000,000번 | 약 20번 | 50,000배 |
데이터가 100만 개일 때, 선형 검색은 최악 100만 번 비교해야 하지만, BST는 단 약 20번이면 충분하다. log2(1,000,000) = 약 20이기 때문이다.
데이터가 많아질수록 BST의 우위는 압도적이다.
비유로 이해하기
선형 검색은 1000페이지 사전에서 첫 페이지부터 한 장씩 넘기면서 단어를 찾는 것과 같다.
BST 검색은 사전을 반으로 펼치고, 찾는 단어가 앞쪽인지 뒤쪽인지 판단해서 다시 반으로 펼치는 것과 같다. 1000페이지를 10번만 반으로 나누면 1페이지까지 좁힐 수 있다.
성능 비교 시각화
9. 데이터베이스와 비선형 구조
DB에서 검색 성능이 중요한 이유
데이터베이스(DB)는 수백만, 수천만 건의 데이터를 관리하는 시스템이다. 사용자가 검색할 때마다 수천만 건을 처음부터 끝까지 훑는다면 서비스가 마비될 것이다. DB에서 검색 성능은 곧 서비스의 생명이다.
DB 인덱스와 트리 구조
DB는 빠른 검색을 위해 **인덱스(Index)**를 만든다. 이 인덱스의 내부 구조가 바로 비선형 트리 구조다.
B-트리 (B-Tree)
B-트리는 이진 탐색 트리를 확장한 고성능 트리다.
- 한 노드에 여러 개의 키를 저장할 수 있다 (이진 트리는 한 노드에 1개)
- 자식 노드의 수도 2개를 넘길 수 있다
- 디스크 I/O를 최소화하도록 설계되었다 -- 한 번 디스크를 읽을 때 최대한 많은 키를 가져와서 비교 횟수를 줄인다
- 항상 균형을 유지하므로 최악의 경우에도 안정적인 성능을 보장한다
B+트리 (B+ Tree)
B+트리는 B-트리의 변형으로, 현대 RDBMS의 핵심 자료구조다.
- 실제 데이터는 리프 노드에만 저장된다 (내부 노드는 검색 안내 역할만 수행)
- 리프 노드끼리 연결 리스트로 연결되어 있다 -- 범위 검색(예: "가격이 1000원 ~ 5000원인 상품")에 매우 유리하다
- MySQL의 InnoDB 엔진, PostgreSQL 등 대부분의 RDBMS가 B+트리 기반 인덱스를 사용한다
B+트리 구조 개념도
- 보라색 노드: 내부 노드 (검색 방향을 안내하는 이정표 역할)
- 초록색 노드: 리프 노드 (실제 데이터가 저장됨)
- 리프 노드 사이의 "연결": 연결 리스트로 이어져 있어 순차 접근과 범위 검색이 빠름
왜 B+트리가 범위 검색에 유리한가?
"가격이 10 ~ 20인 상품"을 찾는다고 하자. B+트리에서는 먼저 10을 트리를 타고 내려가서 찾은 뒤, 리프 노드의 연결 리스트를 따라 20까지 순서대로 읽으면 된다. 다시 루트로 올라갈 필요가 없다.
만약 이진 탐색 트리(BST)였다면 10, 11, 13, ... 각각에 대해 루트부터 다시 탐색해야 할 수 있다.
10. 자료구조 학습 조언
반드시 공부해야 하는 이유
자료구조는 프로그래밍의 기초 체력과 같다. 어떤 언어를 쓰든, 어떤 분야(웹, 앱, AI, 게임)에서 일하든, 데이터를 다루는 한 자료구조 지식은 필수다.
- 코딩 테스트 및 기술 면접의 핵심 출제 범위
- 시스템 성능 문제를 이해하고 해결하는 데 필수적인 기반 지식
- 데이터베이스, 검색 엔진, 운영체제 등 모든 소프트웨어의 내부 동작 원리
학습 로드맵
- 기초 단계: 배열, 스택, 큐를 이해하고 직접 구현해 본다
- 중급 단계: 연결 리스트, 이진 트리, 이진 탐색 트리를 직접 구현해 본다
- 심화 단계: B-트리, B+트리, 레드-블랙 트리, 해시 테이블 등 고성능 자료구조를 학습한다
- 응용 단계: 이런 자료구조가 DB 인덱스, 파일 시스템, 메모리 관리 등에 어떻게 쓰이는지 연결 짓는다
직접 구현해 보기를 권장
개념만 이해하는 것과 직접 코드로 구현하는 것은 완전히 다른 차원의 학습이다. C언어 또는 Python으로 다음을 직접 구현해 볼 것을 강력히 권장한다.
- 배열 기반 스택과 큐
- 연결 리스트 기반 스택과 큐
- 이진 탐색 트리 (삽입, 검색, 삭제)
직접 구현하면서 "왜 이 구조가 효율적인지", "어디에서 비효율이 발생하는지"를 체감할 수 있다.
핵심 암기 포인트
| 번호 | 내용 |
|---|---|
| 1 | 자료구조: 데이터를 효율적으로 저장하고 관리하기 위한 구조 |
| 2 | 배열: 인덱스로 즉시 접근 O(1), 중간 삽입/삭제 비효율 |
| 3 | 스택: LIFO (Last In, First Out) -- 접시 쌓기. Push/Pop |
| 4 | 큐: FIFO (First In, First Out) -- 줄서기. Enqueue/Dequeue |
| 5 | 선형 검색: 최악 O(n). 데이터 늘수록 비례해서 느려짐 |
| 6 | 이진 탐색 트리(BST): 왼쪽 < 부모 < 오른쪽. 검색 O(log n) |
| 7 | BST는 선형 구조보다 검색이 압도적으로 빠름 (100만 개 기준: 100만번 vs 20번) |
| 8 | DB 인덱스는 B-트리/B+트리 사용 -- 비선형 구조가 대규모 데이터 검색의 핵심 |
확인 질문
Q1. 스택과 큐의 차이는?
스택은 LIFO(후입선출)로 마지막에 넣은 것을 먼저 꺼내고, 큐는 FIFO(선입선출)로 먼저 넣은 것을 먼저 꺼낸다. 스택은 접시 쌓기, 큐는 줄서기에 비유할 수 있다.
Q2. 이진 탐색 트리에서 검색이 빠른 이유는?
"왼쪽 < 부모 < 오른쪽" 규칙 덕분에, 매 비교마다 탐색 범위가 절반으로 줄어들기 때문이다. n개의 데이터에서 최대 log2(n)번만 비교하면 결과를 알 수 있다.
Q3. 7개 데이터에서 없는 값을 찾을 때, 선형 검색과 BST 검색의 비교 횟수 차이는?
선형 검색은 7개 전부를 확인해야 하므로 7번 비교가 필요하다. BST(균형 트리)에서는 최대 약 3번(log2(7) = 약 2.8)의 비교로 부재를 판단할 수 있다. 7번 vs 3번으로, BST가 2배 이상 빠르다.
Q4. B+트리가 범위 검색에 유리한 이유는?
B+트리는 실제 데이터가 리프 노드에만 저장되고, 리프 노드끼리 연결 리스트로 이어져 있다. 범위의 시작점을 트리를 타고 찾은 후, 연결 리스트를 따라 순서대로 읽기만 하면 되기 때문이다.
Q5. 자료구조를 공부해야 하는 이유는?
자료구조는 데이터를 효율적으로 다루는 모든 소프트웨어의 기반이다. 프로그래밍 실력, 시스템 성능 이해, 기술 면접 대비 모두에 필수적이며, 데이터베이스 인덱스 같은 핵심 기술이 자료구조 위에 세워져 있기 때문이다.