그래프, DFS/BFS, 정렬, 탐색, 해싱

이번 절은 자료구조 파트의 마지막 압축 정리입니다.

지금까지 자료구조 흐름은 이렇게 왔습니다.

3장 1절: 자료구조 개념, 시간복잡도, 배열
3장 2절: 스택, 큐, 후위표기식
3장 3절: 연결리스트, 트리, 이진트리 순회
3장 4절: 그래프, 탐색, 정렬, 해싱

이번 절의 핵심은 다음과 같습니다.

그래프 = 복잡한 연결 관계 표현
DFS = 깊게 먼저 탐색, 스택/재귀 사용
BFS = 가까운 곳부터 탐색, 큐 사용
탐색 = 원하는 데이터를 찾는 방법
정렬 = 데이터를 순서대로 나열하는 방법
해싱 = 키를 이용해 빠르게 찾는 방법

이 내용은 자료구조 출제범위의 그래프 정의와 표현, 깊이 우선 탐색, 너비 우선 탐색, 신장 트리, 최소 비용 신장 트리, 최단 경로, 순차 탐색, 이진 탐색, 삽입·쉘·퀵·버블·합병·힙·선택·기수 정렬, 해싱과 충돌 처리에 해당합니다. 또 그래프는 이산수학의 그래프 개념, 그래프 표현방법, 오일러 경로, 평면그래프, 최단거리 알고리즘, 해밀턴 순회, 트리, 최소비용 생성트리와도 연결됩니다.

이번 절의 큰 그림

이번 절에서 배울 순서는 다음과 같습니다.

그래프 기본 개념
→ 그래프 표현 방법
→ DFS와 BFS
→ 신장 트리와 최소 비용 신장 트리
→ 탐색
→ 정렬
→ 해싱

이 절은 내용이 많습니다. 그래서 전부 깊게 파고들기보다 시험에 나오는 핵심 개념과 문제풀이 기준 중심으로 갑니다.

그래프 기본

그래프란?

그래프는 여러 대상 사이의 연결 관계를 표현하는 자료구조입니다.

예를 들어 다음은 전부 그래프로 표현할 수 있습니다.

정의: 그래프는 정점과 간선으로 이루어진 자료구조입니다.

기호로는 보통 이렇게 씁니다.

G = (V, E)

V = {A, B, C, D}
E = {(A, B), (A, C), (B, D)}

이면 A, B, C, D라는 정점들이 있고, A-B, A-C, B-D가 연결되어 있다는 뜻입니다.

그래프 용어

그래프에서는 용어가 중요합니다.

정점

정점은 그래프를 구성하는 점입니다.

vertex
node

라고도 합니다.

A, B, C, D

간선

간선은 정점과 정점을 연결하는 선입니다.

edge

라고 합니다.

(A, B)

는 A와 B가 연결되어 있다는 뜻입니다.

인접

두 정점이 간선으로 직접 연결되어 있으면 인접한다고 합니다.

A -- B

이면 A와 B는 인접합니다.

차수

정점에 연결된 간선의 개수를 차수라고 합니다.

A -- B
|
C

A는 B와 C에 연결되어 있으므로 차수는 2다.

경로

경로는 한 정점에서 다른 정점으로 가는 길입니다.

A → B → D

는 A에서 D로 가는 경로입니다.

사이클

시작 정점과 끝 정점이 같은 경로를 사이클이라고 합니다.

A → B → C → A

이것은 사이클입니다.

트리에는 사이클이 없다고 3장 3절에서 배웠습니다. 그래프에는 사이클이 있을 수도 있습니다.

무방향 그래프와 방향 그래프

그래프는 간선에 방향이 있느냐 없느냐에 따라 나뉩니다.

무방향 그래프

간선에 방향이 없습니다.

A -- B

이 경우 A에서 B로 갈 수도 있고, B에서 A로 갈 수도 있습니다.

친구 관계
도로 양방향 통행

방향 그래프

간선에 방향이 있습니다.

A → B

이 경우 A에서 B로 가는 방향이 있습니다. B에서 A로 갈 수 있다는 뜻은 아닙니다.

인스타그램 팔로우
웹페이지 링크
일방통행 도로

정리하면 다음과 같습니다.

가중치 그래프

간선에 값이 붙어 있는 그래프를 가중치 그래프라고 합니다.

A --5-- B
B --2-- C
A --10-- C

여기서 5, 2, 10이 가중치입니다.

가중치는 상황에 따라 의미가 달라집니다.

가중치 그래프에서는 이런 문제가 나옵니다.

가장 짧은 경로는?
가장 비용이 적은 연결 방법은?

그래서 뒤에서 최단 경로와 최소 비용 신장 트리가 나옵니다.

연결 그래프와 비연결 그래프

연결 그래프

무방향 그래프에서 모든 정점 사이에 경로가 있으면 연결 그래프입니다.

A -- B -- C -- D

A에서 D까지 갈 수 있고, 모든 정점이 연결되어 있습니다.

비연결 그래프

어떤 정점들 사이에 경로가 없으면 비연결 그래프입니다.

A -- B      C -- D

A에서 C로 갈 수 없습니다. 이런 그래프는 비연결 그래프입니다.

그래프와 트리의 차이

트리는 그래프의 특수한 형태라고 볼 수 있습니다.

트리 = 사이클 없는 연결 그래프의 한 종류
그래프 = 더 일반적인 연결 관계

그래프 표현

그래프 표현 방법

그래프를 컴퓨터에 저장하는 방법은 대표적으로 두 가지입니다.

인접 행렬
인접 리스트

자료구조 범위에도 그래프 표현 방법으로 인접 행렬과 인접 리스트가 포함되어 있습니다.

인접 행렬

인접 행렬은 2차원 배열로 그래프를 표현하는 방법입니다.

정점이 A, B, C, D 네 개 있다고 가정하겠습니다.

A -- B
A -- C
B -- D

인접 행렬은 이렇게 만듭니다.

matrix[A][B] = 1
matrix[B][A] = 1

matrix[A][D] = 0

무방향 그래프의 인접 행렬은 대칭입니다.

matrix[i][j] = matrix[j][i]

인접 행렬의 장단점

정점이 n개면 인접 행렬은 n × n 공간이 필요합니다.

공간 복잡도 = O(n²)

간선이 적어도 n²칸을 모두 만들어야 합니다.

1000 × 1000 = 1,000,000칸

이 필요합니다.

인접 리스트

인접 리스트는 각 정점마다 연결된 정점 목록을 저장하는 방법입니다.

A -- B
A -- C
B -- D

A: B, C
B: A, D
C: A
D: B

C언어에서는 배열과 연결리스트를 합쳐서 표현할 수 있습니다.

정점 배열 + 각 정점의 연결리스트

인접 리스트의 장단점

O(V + E)

여기서는 다음과 같습니다.

간선이 적은 그래프에서는 인접 리스트가 유리합니다.

인접 행렬과 인접 리스트 비교

인접 행렬 = 빠른 확인, 메모리 많이 씀
인접 리스트 = 메모리 절약, 이웃 순회에 좋음

그래프 순회

순회 개요

그래프 순회는 그래프의 정점들을 방문하는 것입니다.

대표 방법은 두 가지입니다.

DFS = 깊이 우선 탐색
BFS = 너비 우선 탐색

자료구조 출제범위에도 그래프 순회로 깊이 우선 탐색과 너비 우선 탐색이 들어 있습니다.

DFS란?

DFS는 Depth First Search, 깊이 우선 탐색입니다.

말 그대로 갈 수 있는 곳까지 깊게 먼저 들어갑니다.

비유하면 미로 탐색입니다.

한 길을 끝까지 가봅니다.
막히면 되돌아옵니다.
다른 길을 갑니다.

DFS는 보통 스택 또는 재귀를 사용합니다.

DFS = 스택 / 재귀

3장 2절에서 스택은 “되돌아가기”에 적합하다고 했습니다. DFS가 바로 그 예입니다.

DFS 예제

그래프가 이렇게 있다고 가정하겠습니다.

A
├─ B
│  ├─ D
│  └─ E
└─ C
   └─ F

A-B, A-C, B-D, B-E, C-F

A에서 DFS를 시작하고, 알파벳 순서로 방문한다고 가정하겠습니다.

1. A 방문
2. A의 이웃 B로 이동
3. B의 이웃 D로 이동
4. D는 더 갈 곳 없음, 돌아감
5. B의 다음 이웃 E 방문
6. 돌아가서 A의 다음 이웃 C 방문
7. C의 이웃 F 방문

A → B → D → E → C → F

DFS는 깊게 들어갑니다.

DFS 재귀 코드 느낌

C 느낌으로 쓰면 다음과 같습니다.

void DFS(int v) {
    visited[v] = 1;
    printf("%d ", v);

    for (각 인접 정점 w) {
        if (!visited[w]) {
            DFS(w);
        }
    }
}

핵심은 다음과 같습니다.

방문 표시
인접 정점 중 방문하지 않은 곳으로 재귀 호출

방문 표시가 없으면 사이클이 있는 그래프에서 무한 반복할 수 있습니다.

DFS 특징

DFS = 깊게 먼저

BFS란?

BFS는 Breadth First Search, 너비 우선 탐색입니다.

가까운 정점부터 차례대로 방문합니다.

비유하면 물결처럼 퍼지는 탐색입니다.

시작점과 가까운 곳부터 방문
그다음 한 단계 떨어진 곳 방문
그다음 두 단계 떨어진 곳 방문

BFS는 큐를 사용합니다.

BFS = 큐

3장 2절에서 큐는 “먼저 들어온 것이 먼저 나가는 구조”라고 했습니다. BFS는 먼저 발견한 정점을 먼저 처리하기 때문에 큐가 알맞습니다.

BFS 예제

같은 그래프를 살펴보겠습니다.

A
├─ B
│  ├─ D
│  └─ E
└─ C
   └─ F

A에서 BFS를 시작하고, 알파벳 순서로 방문한다고 가정하겠습니다.

1. A 방문
2. A의 이웃 B, C를 큐에 넣음
3. B 방문
4. B의 이웃 D, E를 큐에 넣음
5. C 방문
6. C의 이웃 F를 큐에 넣음
7. D 방문
8. E 방문
9. F 방문

A → B → C → D → E → F

BFS는 가까운 층부터 갑니다.

A
B, C
D, E, F

이런 식입니다.

BFS 코드 느낌

void BFS(int start) {
    visited[start] = 1;
    enqueue(start);

    while (!isEmpty()) {
        v = dequeue();
        printf("%d ", v);

        for (각 인접 정점 w) {
            if (!visited[w]) {
                visited[w] = 1;
                enqueue(w);
            }
        }
    }
}

시작 정점을 큐에 넣습니다.
큐에서 꺼내 방문합니다.
인접 정점 중 방문하지 않은 정점을 큐에 넣습니다.

BFS 특징

BFS = 가까운 곳 먼저

DFS와 BFS 비교

DFS = 스택
BFS = 큐

그래프 응용

신장 트리

신장 트리는 그래프의 모든 정점을 포함하면서 사이클이 없는 부분 그래프입니다.

1. 모든 정점을 포함합니다.
2. 사이클이 없습니다.
3. 연결되어 있습니다.

n - 1개

예를 들어 정점이 5개면 신장 트리의 간선은 4개입니다.

그래프에서 DFS나 BFS를 수행하면 방문 과정에서 신장 트리를 만들 수 있습니다.

자료구조 범위에도 그래프 순회와 함께 신장 트리가 포함되어 있습니다.

최소 비용 신장 트리, MST

가중치 그래프에서 신장 트리 중 간선 가중치 합이 가장 작은 것을 최소 비용 신장 트리라고 합니다.

영어로는 MST, Minimum Spanning Tree다.

A --1-- B
A --4-- C
B --2-- C
B --5-- D
C --3-- D

모든 정점을 연결하되 비용 합이 최소가 되도록 간선을 고릅니다.

Prim 알고리즘
Kruskal 알고리즘
Sollin 알고리즘

자료구조 범위에도 최소 비용 신장 트리로 Prim, Kruskal, Sollin 방법이 포함되어 있습니다.

처음에는 이렇게만 정리합니다.

시험에서는 보통 Prim과 Kruskal이 중요합니다.

최단 경로

최단 경로는 한 정점에서 다른 정점까지 가는 비용이 가장 작은 경로를 찾는 문제입니다.

A에서 D까지 가장 짧은 길은?

가중치가 없는 그래프에서는 BFS로 최단 거리를 구할 수 있습니다.

가중치가 있는 그래프에서는 대표적으로 다익스트라 알고리즘을 씁니다.

이산수학과 자료구조 범위 모두 그래프의 응용으로 최단거리 또는 최단 경로를 다룹니다.

지금 단계에서는 이렇게만 기억하자.

무가중치 최단 경로 = BFS
가중치 최단 경로 = 다익스트라 같은 알고리즘

탐색

탐색이란?

이제 탐색으로 넘어갑니다.

탐색은 데이터 집합에서 원하는 값을 찾는 작업입니다.

학생 목록에서 학번 2024001 찾기
전화번호부에서 이름 찾기
배열에서 숫자 30 찾기
회원 목록에서 ID 찾기

순차 탐색
이진 탐색
피보나치 탐색
탐색 트리를 이용한 탐색
해싱

자료구조 출제범위에도 탐색으로 순차 탐색, 이진 탐색, 피보나치 탐색, 탐색 트리를 이용한 탐색이 포함되어 있습니다.

순차 탐색

순차 탐색은 처음부터 끝까지 하나씩 비교하면서 찾는 방법입니다.

[10, 30, 20, 50, 40]

여기서 50을 찾는다고 가정하겠습니다.

10 비교 → 아님
30 비교 → 아님
20 비교 → 아님
50 비교 → 찾음

for (i = 0; i < n; i++) {
    if (arr[i] == key) {
        return i;
    }
}
return -1;

정렬되어 있지 않아도 가능합니다.

데이터가 많으면 느립니다.

시간 복잡도는 다음과 같습니다.

이진 탐색

이진 탐색은 정렬된 데이터에서 가운데를 기준으로 절반씩 줄여가며 찾는 방법입니다.

조건이 중요합니다.

이진 탐색은 데이터가 정렬되어 있어야 합니다.

[10, 20, 30, 40, 50, 60, 70]

50을 찾자.

1. 가운데 40 확인
2. 50은 40보다 큽니다
3. 오른쪽 절반만 봅니다

[50, 60, 70]

4. 가운데 60 확인
5. 50은 60보다 작습니다
6. 왼쪽 절반 확인

[50]

찾음.

이진 탐색 코드 느낌

int binarySearch(int arr[], int n, int key) {
    int left = 0;
    int right = n - 1;
    int mid;

    while (left <= right) {
        mid = (left + right) / 2;

        if (arr[mid] == key) {
            return mid;
        } else if (arr[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

중앙값과 비교
찾는 값이 크면 오른쪽
작으면 왼쪽

O(log n)

순차 탐색과 이진 탐색 비교

정렬 안 됨 → 순차 탐색
정렬됨 → 이진 탐색 가능

정렬

정렬이란?

정렬은 데이터를 일정한 순서대로 나열하는 것입니다.

정렬 전: 30, 10, 50, 20, 40
정렬 후: 10, 20, 30, 40, 50

작은 것 → 큰 것

큰 것 → 작은 것

정렬은 탐색과 연결됩니다. 예를 들어 이진 탐색을 하려면 데이터가 정렬되어 있어야 합니다.

자료구조 출제범위에는 정렬로 삽입 정렬, 쉘 정렬, 퀵 정렬, 버블 정렬, 2원 합병 정렬, 힙 정렬, 선택 정렬, 기수 정렬, 외부 정렬이 포함되어 있습니다.

버블 정렬

버블 정렬은 이웃한 두 값을 비교해서 큰 값을 뒤로 보내는 방식입니다.

[5, 3, 4, 1]

5와 3 비교 → 교환 → [3, 5, 4, 1]
5와 4 비교 → 교환 → [3, 4, 5, 1]
5와 1 비교 → 교환 → [3, 4, 1, 5]

가장 큰 5가 맨 뒤로 갑니다.

다음 패스에서 4가 제자리로 갑니다.

특징은 다음과 같습니다.

버블 정렬 = 큰 값이 거품처럼 뒤로 올라감

선택 정렬

선택 정렬은 남은 데이터 중 가장 작은 값을 선택해서 앞에 놓는 방식입니다.

[5, 3, 4, 1]

1. 전체에서 최솟값 1 선택
2. 맨 앞 5와 교환

[1, 3, 4, 5]

이제 첫 번째는 정렬 완료.

[3, 4, 5]

최솟값 3은 이미 앞에 있습니다.

특징은 다음과 같습니다.

선택 정렬 = 가장 작은 것 골라 앞으로

삽입 정렬

삽입 정렬은 앞쪽의 정렬된 부분에 새 값을 알맞은 위치에 끼워 넣는 방식입니다.

[5, 3, 4, 1]

처음 5는 정렬되어 있다고 봅니다.

[3, 5, 4, 1]

[3, 4, 5, 1]

[1, 3, 4, 5]

특징은 다음과 같습니다.

삽입 정렬 = 알맞은 자리에 끼워 넣기

퀵 정렬

퀵 정렬은 기준값, 즉 피벗을 정하고 피벗보다 작은 값과 큰 값을 나누어 정렬하는 방식입니다.

피벗 선택
피벗보다 작은 값은 왼쪽
피벗보다 큰 값은 오른쪽
왼쪽과 오른쪽을 다시 정렬

[5, 3, 8, 4, 2]

작은 값: 3, 4, 2
피벗: 5
큰 값: 8

이제 왼쪽 [3, 4, 2]도 같은 방식으로 정렬합니다.

특징은 다음과 같습니다.

퀵 정렬 = 기준 잡고 작은 것/큰 것 나누기

합병 정렬

합병 정렬은 데이터를 반으로 나누고, 각각 정렬한 뒤 합치는 방식입니다.

반으로 나눕니다.
또 반으로 나눕니다.
하나씩 될 때까지 나눕니다.
정렬하면서 합칩니다.

[5, 3, 8, 4]

[5, 3] [8, 4]
[5] [3] [8] [4]

[3, 5] [4, 8]
[3, 4, 5, 8]

특징은 다음과 같습니다.

합병 정렬 = 쪼개고 정렬하며 합치기

힙 정렬

힙 정렬은 힙이라는 자료구조를 이용한 정렬입니다.

힙은 완전 이진트리를 기반으로 합니다.

최대 힙에서는 부모가 자식보다 크거나 같습니다.

부모 ≥ 자식

최대 힙을 만듭니다.
루트, 즉 최댓값을 꺼냅니다.
다시 힙을 정리합니다.
반복합니다.

특징은 다음과 같습니다.

자료구조 범위에도 트리 단원에 히프, 우선순위 큐, 최대 히프 삽입과 삭제가 포함되어 있습니다.

쉘 정렬

쉘 정렬은 삽입 정렬을 개선한 방식입니다.

삽입 정렬은 가까운 위치로 조금씩 이동하기 때문에 멀리 떨어진 값이 제자리로 가는 데 시간이 걸립니다.

쉘 정렬은 일정한 간격을 두고 비교하며 정렬합니다.

처음에는 큰 간격
점점 간격을 줄임
마지막에는 간격 1

특징은 다음과 같습니다.

기수 정렬

기수 정렬은 숫자의 자리수별로 정렬하는 방식입니다.

170, 45, 75, 90, 802, 24

1의 자리 기준으로 정렬하고, 10의 자리 기준으로 정렬하고, 100의 자리 기준으로 정렬합니다.

비교 기반 정렬이 아니라 자리값을 이용합니다.

특징은 다음과 같습니다.

정렬 알고리즘 비교표

시험 초반에는 최소한 다음과 같이 암기합니다.

버블/선택/삽입 = O(n²)
퀵/합병/힙 = O(n log n)

단, 퀵 정렬은 최악의 경우 O(n²)가 될 수 있습니다.

해싱

해싱이란?

이제 마지막 주제, 해싱입니다.

해싱은 키 값을 해시 함수에 넣어서 저장 위치를 계산하는 방법입니다.

예를 들어 학생 학번이 있다고 가정하겠습니다.

2024001

이 값을 배열의 어느 위치에 저장할지 해시 함수가 계산합니다.

h(key) = key % table_size

table_size = 10
key = 2024001
h(key) = 2024001 % 10 = 1

그러면 인덱스 1번에 저장합니다.

hashTable[1] = 데이터

자료구조 범위에도 해싱 단원에 심볼 테이블, 해싱 개념, 해싱 테이블, 해싱 함수, 충돌과 오버플로우, 오버플로우 처리 기법이 포함되어 있습니다.

해싱의 목적

해싱의 목적은 빠른 검색입니다.

배열에서 순차 탐색을 하면 O(n)입니다.

이진 탐색은 O(log n)이지만 정렬이 필요합니다.

O(1)

에 가까운 검색이 가능합니다.

키 → 해시 함수 → 주소 → 바로 접근

이 흐름입니다.

해시 테이블

해시 테이블은 해싱으로 데이터를 저장하는 배열 같은 구조입니다.

index: 0  1  2  3  4  5  6  7  8  9
value:    A        B           C

해시 함수가 인덱스를 계산합니다.

h(key) = key % 10

23 % 10 = 3

인덱스 3에 저장합니다.

47 % 10 = 7

인덱스 7에 저장합니다.

충돌

해싱에서 중요한 문제가 있습니다.

바로 충돌입니다.

충돌은 서로 다른 키가 같은 해시 주소를 갖는 경우입니다.

table_size = 10
h(key) = key % 10

23 % 10 = 3

33 % 10 = 3

둘 다 인덱스 3으로 갑니다.

이것이 충돌입니다.

충돌 = 서로 다른 키가 같은 위치를 차지하려는 상황

해싱에서 충돌은 피하기 어렵습니다. 중요한 것은 충돌을 어떻게 처리하느냐입니다.

충돌 처리 방법

대표적인 충돌 처리 방법은 두 가지로 나눌 수 있습니다.

개방 주소법
체이닝

개방 주소법

충돌이 나면 해시 테이블 안의 다른 빈칸을 찾는 방식입니다.

선형 조사
이차 조사
이중 해싱

선형 조사

충돌이 나면 바로 다음 칸을 봅니다.

h(key), h(key)+1, h(key)+2, ...

23 → 3번 칸
33 → 3번 칸 충돌 → 4번 칸 확인

비어 있으면 4번에 저장합니다.

구현이 쉽습니다.

데이터가 한쪽에 뭉치는 군집화가 생길 수 있습니다.

체이닝

체이닝은 같은 해시 주소에 여러 데이터를 연결리스트로 저장하는 방식입니다.

index 3: 23 → 33 → 43

즉, 해시 테이블의 각 칸이 연결리스트의 시작점이 됩니다.

충돌이 나도 리스트에 이어 붙이면 됩니다.

충돌이 많아지면 리스트가 길어져 탐색이 느려집니다.

여기서 3장 3절의 연결리스트가 다시 나옵니다.

해싱 + 연결리스트 = 체이닝

좋은 해시 함수

좋은 해시 함수는 키를 테이블 전체에 골고루 퍼뜨립니다.

좋지 않은 해시 함수는 특정 위치에 데이터가 몰립니다.

계산이 빠릅니다.
주소를 고르게 분포시킵니다.
충돌을 적게 만듭니다.

가장 단순한 해시 함수는 나머지 연산입니다.

h(key) = key % table_size

하지만 실제로는 데이터 특성에 맞게 더 신중히 설계해야 합니다.

해싱 시간 복잡도

해싱은 충돌이 적으면 매우 빠릅니다.

왜 최악이 O(n)일까?

모든 키가 같은 위치로 충돌하면 결국 연결리스트를 전부 뒤져야 할 수 있습니다.

index 0: A → B → C → D → E → ...

이러면 순차 탐색과 비슷해집니다.

그래서 해싱에서는 충돌을 줄이는 것이 중요합니다.

탐색 방법 비교

그냥 찾기 = 순차 탐색
정렬되어 있으면 = 이진 탐색
트리 구조면 = 탐색 트리
키로 바로 찾고 싶으면 = 해싱

자주 혼동되는 출제 포인트

혼동 포인트 1. DFS와 BFS 자료구조

DFS = 스택 또는 재귀
BFS = 큐

이것은 반드시 정리해 둡니다.

혼동 포인트 2. BFS는 가까운 곳부터 탐색합니다

무가중치 그래프에서 최단 거리를 구할 때 BFS가 중요합니다.

혼동 포인트 3. 인접 행렬과 인접 리스트 차이

인접 행렬 = O(V²) 공간, 연결 확인 빠름
인접 리스트 = O(V+E) 공간, 간선 적을 때 유리

혼동 포인트 4. 이진 탐색은 정렬되어 있어야 합니다

정렬 안 된 배열에서 이진 탐색을 쓰면 안 됩니다.

혼동 포인트 5. 버블·선택·삽입 정렬은 보통 O(n²)

기본 정렬 3종은 느린 편입니다.

버블, 선택, 삽입 = O(n²)

혼동 포인트 6. 퀵 정렬은 평균은 빠르지만 최악은 O(n²)

평균 O(n log n)
최악 O(n²)

혼동 포인트 7. 합병 정렬은 O(n log n)이지만 추가 메모리가 필요합니다

쪼갠 뒤 합칠 때 임시 공간이 필요할 수 있습니다.

혼동 포인트 8. 해싱은 항상 O(1)이 아닙니다

충돌이 많으면 느려집니다.

평균 O(1)에 가까움
최악 O(n)

혼동 포인트 9. 충돌은 서로 다른 키가 같은 주소로 가는 것

23 % 10 = 3
33 % 10 = 3

이런 상황이 충돌입니다.

혼동 포인트 10. 체이닝은 연결리스트를 사용합니다

충돌난 데이터들을 같은 위치에서 연결리스트로 이어 붙입니다.

이번 절의 핵심 정리

그래프

정점과 간선으로 이루어진 연결 관계
G = (V, E)

그래프 표현

인접 행렬 = 2차원 배열
인접 리스트 = 각 정점의 연결 목록

DFS

깊이 우선 탐색
스택 또는 재귀 사용

BFS

너비 우선 탐색
큐 사용

신장 트리

모든 정점을 포함하고 사이클이 없는 연결 부분 그래프
정점 n개 → 간선 n-1개

최소 비용 신장 트리

가중치 합이 최소인 신장 트리
Prim, Kruskal

순차 탐색

처음부터 하나씩 찾음
O(n)

이진 탐색

정렬된 배열에서 절반씩 줄이며 찾음
O(log n)

정렬

버블/선택/삽입 = O(n²)
퀵/합병/힙 = O(n log n) 평균 또는 보통

해싱

키를 해시 함수에 넣어 저장 위치 계산
평균 O(1)에 가까운 검색 가능

충돌

서로 다른 키가 같은 해시 주소를 갖는 것

핵심 한 문장

이번 절의 핵심을 한 문장으로 정리하면 다음과 같습니다.

그래프는 복잡한 연결 관계를 표현하고, DFS는 스택으로 깊게 탐색하며, BFS는 큐로 가까운 곳부터 탐색하고, 탐색·정렬·해싱은 데이터를 빠르게 찾기 위해 사용하는 핵심 알고리즘입니다.

그래프 = 연결 관계
DFS = 스택
BFS = 큐
정렬 = 순서 만들기
탐색 = 찾기
해싱 = 키로 바로 찾기

확인 문제

문제 1

그래프를 구성하는 두 핵심 요소는?

① 스택과 큐 ② 정점과 간선 ③ 배열과 인덱스 ④ 루트와 리프만

문제 2

그래프를 2차원 배열로 표현하는 방법은?

① 인접 리스트 ② 인접 행렬 ③ 연결리스트 ④ 해시 테이블

문제 3

각 정점마다 연결된 정점 목록을 저장하는 그래프 표현 방식은?

① 인접 행렬 ② 인접 리스트 ③ 순서리스트 ④ 원형 큐

문제 4

DFS에서 주로 사용하는 자료구조는?

① 큐 ② 스택 ③ 해시 테이블 ④ 배열만 사용 가능

문제 5

BFS에서 주로 사용하는 자료구조는?

① 큐 ② 스택 ③ 힙 ④ 이중 포인터

문제 6

무가중치 그래프에서 가까운 정점부터 탐색하며 최단 거리를 구하는 데 적합한 탐색은?

① DFS ② BFS ③ 선택 정렬 ④ 해싱

문제 7

정점이 n개인 신장 트리의 간선 수는?

① n개 ② n+1개 ③ n-1개 ④ 2n개

문제 8

순차 탐색의 평균 시간 복잡도는?

① O(1) ② O(log n) ③ O(n) ④ O(n²)

문제 9

이진 탐색의 조건으로 가장 중요한 것은?

① 데이터가 반드시 문자열이어야 합니다 ② 데이터가 정렬되어 있어야 합니다 ③ 데이터가 연결리스트여야 합니다 ④ 데이터가 중복되면 안 됩니다

문제 10

이진 탐색의 시간 복잡도는?

① O(1) ② O(log n) ③ O(n) ④ O(n²)

문제 11

인접한 두 원소를 비교하며 큰 값을 뒤로 보내는 정렬은?

① 버블 정렬 ② 선택 정렬 ③ 합병 정렬 ④ 힙 정렬

문제 12

남은 원소 중 최솟값을 선택해 앞쪽에 배치하는 정렬은?

① 버블 정렬 ② 선택 정렬 ③ 삽입 정렬 ④ 퀵 정렬

문제 13

정렬된 부분에 새 원소를 알맞은 위치에 끼워 넣는 정렬은?

① 삽입 정렬 ② 기수 정렬 ③ 힙 정렬 ④ 합병 정렬

문제 14

피벗을 기준으로 작은 값과 큰 값을 나누는 정렬은?

① 버블 정렬 ② 선택 정렬 ③ 퀵 정렬 ④ 기수 정렬

문제 15

데이터를 반으로 나누고 정렬하면서 합치는 정렬은?

① 합병 정렬 ② 선택 정렬 ③ 버블 정렬 ④ 순차 정렬

문제 16

해싱에서 서로 다른 키가 같은 해시 주소를 갖는 상황은?

① 정렬 ② 충돌 ③ 순회 ④ 전치

문제 17

충돌 처리 방법 중 같은 해시 주소의 데이터들을 연결리스트로 이어 저장하는 방식은?

① 선형 조사 ② 체이닝 ③ 이진 탐색 ④ 전위순회

문제 18

해싱의 평균적인 탐색 시간으로 가장 알맞은 것은?

① O(1)에 가까움 ② O(n²) ③ O(2ⁿ) ④ 항상 O(n log n)

정답과 해설은 절별 확인문제 정답해설에서 확인합니다.

다음 4장 1절은 컴퓨터 기본구조, 시스템 버스, 명령어입니다. 이제 자료구조 블록이 끝났고, 다시 컴퓨터 내부로 들어가서 CPU가 명령어를 어떻게 가져오고 실행하는지를 배웁니다.