함께 배우는 수업 · 컴퓨터/정보

그래프와 해시 테이블

정점(Vertex)과 간선(Edge)으로 복잡한 네트워크를 모델링하는 그래프 표현법과, 키(Key)를 해시 함수로 변환해 O(1) 조회를 달성하는 해시 테이블을 학습합니다.

이 수업에서 해 볼 일

그래프 연결 관계와 해시 충돌 처리의 의미를 설명한다

먼저 알면 좋은 것: 배열과 연결 리스트의 장단점 및 시간 복잡도 · 나머지(Modulo) 연산과 함수 매핑 개념 · 트리(Tree)와 일반 네트워크 구조의 차이

오늘의 목표

가입 없이 시작할 수 있어요. 설명을 읽고, 함께 연습한 뒤, 처음 보는 문제에서 직접 확인합니다.

판단 과정과 비교 사례

그래프는 정점 사이의 관계를, 해시 테이블은 키로 값을 찾는 배치를 표현한다. 간선이 적은 그래프는 실제 이웃만 저장하는 인접 리스트가 공간 면에서 유리한 경우가 많다.정점 100개에 간선 4개라면 모든 정점 쌍의 칸을 만드는 행렬보다 존재하는 연결만 기록하는 방식을 먼저 검토하자. 간선을 양방향으로 기록하는지도 함께 확인한다.해시값이 같다는 것은 키가 같다는 뜻이 아니다. 충돌 처리로 여러 키를 구분해야 하며, 적재율이 커져 성능이 나빠지면 확장 후 새 해시 배치를 계산할 수 있다.

1. 그래프(Graph)의 구조와 인접 행렬 vs 인접 리스트 비교

- 그래프의 구성: 객체들을 나타내는 정점(Vertex / Node, $V$ )의 집합과 정점들을 연결하는 간선(Edge, $E$ )의 집합

G = (V, E)

로 이루어진 가장 일반화된 비선형 자료구조입니다 (트리는 사이클이 없는 특수한 그래프). - 방향 유무에 따라 무방향 그래프와 방향 그래프(Directed Graph)로 나뉘며, 간선에 비용이나 거리가 부여된 경우 가중치 그래프(Weighted Graph)라고 합니다. - 그래프를 코드로 구현하는 2가지 방법:

비교 기준	인접 행렬 (Adjacency Matrix)	인접 리스트 (Adjacency List)
구현 방식	$V \times V$ 크기의 2차원 배열 `adj[u][v]`	각 정점마다 연결된 정점들의 동적 배열/리스트
메모리 공간	$O(V^2)$ (간선이 적어도 고정 소모)	$O(V + E)$ (실제 간선 수만큼만 소모)
두 정점 $(u, v)$ 연결 확인	$O(1)$ (`adj[u][v]` 즉시 조회)	$O(\text{degree}(u))$ (연결된 리스트 순회)
한 정점과 연결된 모든 노드 순회	$O(V)$ (해당 행 전체 $V$ 칸 확인)	$O(\text{degree}(u))$ (실제 이웃만 방문)
적합한 상황	간선이 매우 많은 밀집 그래프(Dense)	정점이 많고 간선이 적은 희소 그래프(Sparse)

코딩 테스트에서 정점 수 V가 100,000개일 때 인접 행렬(V × V)을 선언하면 100억 칸(약 40GB)이 필요해 즉시 메모리 초과(MLE)가 발생합니다! 정점이 수천 개 이상이면 무조건 '인접 리스트'를 사용하세요.

2. 해시 테이블(Hash Table)의 원리와 충돌(Collision) 해결 기법

- 해시 테이블 (파이썬 dict, 자바 HashMap, JS Map/Object): - 임의의 키(Key, 예: "apple")를 해시 함수(Hash Function)에 넣어 정수형 해시 코드로 변환한 뒤, 배열 크기

M

으로 나눈 나머지(

\text{index} = \text{hash}(\text{key}) \pmod M

)를 인덱스로 삼아 버킷(Bucket)에 값을 저장합니다. - 키만 알면 인덱스를 즉시 계산하므로 탐색·삽입·삭제의 평균 시간 복잡도가 $O(1)$ 이라는 경이로운 성능을 발휘합니다. - 해시 충돌 (Hash Collision): 서로 다른 두 키

K_1 \neq K_2

가 우연히 같은 버킷 인덱스로 매핑되는 현상입니다 (비둘기집의 원리에 의해 필연적으로 발생). 1. 분리 연결법 (Separate Chaining): 같은 인덱스에 충돌한 데이터들을 연결 리스트(또는 Red-Black 트리)로 줄줄이 매달아 저장합니다 (Java HashMap 채택 방식, 버킷에 8개 이상 쌓이면 트리로 전환하여 최악

O(\log N)

보장). 2. 개방 주소법 (Open Addressing): 연결 리스트를 쓰지 않고 배열 내부의 다른 빈칸을 찾아 저장합니다. - 선형 탐사 (Linear Probing): 충돌 시 바로 다음 칸(

+1, +2, +3\dots

)을 검사 (특정 영역에 데이터가 뭉치는 일차 군집화 Primary Clustering 문제 발생). - 제곱 탐사 (Quadratic Probing) 및 이중 해싱 (Double Hashing): 보폭을 제곱수(

+1^2, +2^2, +3^2\dots

)나 두 번째 해시 함수로 넓혀 군집화를 방지합니다 (Python dict는 개방 주소법 계열 사용).

예제로 살펴보기

크기가 7인 해시 테이블(인덱스 0~6)에서 해시 함수가 h(k) = k mod 7이고 충돌 해결 방식으로 '선형 탐사(Linear Probing)'를 사용할 때, 키 10, 15, 24, 31을 순서대로 삽입한 후 각 키가 저장되는 최종 인덱스를 구하시오.

1) k = 10 삽입: h(10) = 10 mod 7 = 3 ➔ 3번 버킷이 비어 있으므로 인덱스 [3]에 10 저장. 2) k = 15 삽입: h(15) = 15 mod 7 = 1 ➔ 1번 버킷이 비어 있으므로 인덱스 [1]에 15 저장. 3) k = 24 삽입: h(24) = 24 mod 7 = 3 ➔ 3번 버킷에 이미 10이 있어 충돌(Collision) 발생! 선형 탐사로 다음 칸인 (3 + 1) mod 7 = 4번 버킷을 확인하니 비어 있으므로 인덱스 [4]에 24 저장. 4) k = 31 삽입: h(31) = 31 mod 7 = 3 ➔ 3번(10 점유) 충돌 ➔ 4번(24 점유) 연속 충돌! 한 칸 더 이동한 5번 버킷이 비어 있으므로 인덱스 [5]에 31 저장. 최종 결과: 15는 [1], 10은 [3], 24는 [4], 31은 [5]번 인덱스에 저장됩니다.

확인: 그래프 표현에서 인접 행렬은 두 정점의 연결 확인이 O(1)로 빠르고, 인접 리스트는 메모리 사용량이 O(V+E)로 효율적이다.

3. 적재율(Load Factor)과 리해싱(Rehashing) 실무 포인트

- 적재율 (Load Factor, $\alpha = N / M$ ): 전체 버킷 크기

M

대비 현재 저장된 데이터 개수

N

의 비율입니다. - 적재율이 높아질수록(보통

\alpha > 0.75

) 충돌 확률이 급격히 상승하여 해시 테이블의 성능이 평균

O(1)

에서 최악 $O(N)$ 으로 떨어집니다. - 따라서 적재율이 임계치(예: 0.75)를 넘으면 버킷 배열의 크기를 2배로 늘리고 모든 키의 해시 인덱스를 다시 계산해 배치하는 리해싱(Rehashing)을 수행합니다. - 불변(Immutable) 객체만 해시 키가 될 수 있는 이유: - 파이썬 dict나 set에서 리스트(list)는 키로 쓸 수 없고 튜플(tuple)이나 문자열(str)만 키로 쓸 수 있습니다. 만약 키 객체의 내부 값이 저장 후 변경되면 해시값도 바뀌어 버려, 원래 저장했던 버킷 위치를 영영 찾을 수 없게 되기 때문입니다.해시 테이블의 시간 복잡도는 '평균 O(1), 최악 O(N)'입니다. 모든 키가 동일한 버킷으로 충돌(Hash DoS 공격 등)하면 연결 리스트를 끝까지 탐색해야 하므로 O(N)이 걸린다는 점을 반드시 기억하세요.

참고 근거와 확인 범위

Harvard CS50 · Lecture 5: Data structures ↗
해시 함수·충돌·해시 테이블의 연결 구조

설명·예제·문제 구성 및 오류 수정 책임: 프리런. 위 자료는 표시한 주제를 확인하거나 더 읽기 위한 근거이며, 외부 기관의 공식 수업이나 감수본을 뜻하지 않습니다.

참고 자료 연결 점검: 2026-11-02. 제작 방식·검수 범위와 수정 기록에서 확인 범위를 볼 수 있습니다. 오류는 상단의 의견 보내기 또는 contact@freelearn.io로 알려 주세요.

이 단원의 개념서 읽기 →