개념 정리
그래프와 해시 테이블
단원 개요
정점(Vertex)과 간선(Edge)으로 복잡한 네트워크를 모델링하는 그래프 표현법과, 키(Key)를 해시 함수로 변환해 O(1) 조회를 달성하는 해시 테이블을 학습합니다.선수 개념
필수 키워드:그래프의 구성정점(Vertex / Node, )간선(Edge, )무방향 그래프방향 그래프(Directed Graph)가중치 그래프(Weighted Graph)그래프를 코드로 구현하는 2가지 방법구현 방식메모리 공간
1
그래프(Graph)의 구조와 인접 행렬 vs 인접 리스트 비교
•
그래프의 구성: 객체들을 나타내는 정점(Vertex / Node, )의 집합과 정점들을 연결하는 간선(Edge, )의 집합 로 이루어진 가장 일반화된 비선형 자료구조입니다 (트리는 사이클이 없는 특수한 그래프).
•
방향 유무에 따라 무방향 그래프와 방향 그래프(Directed Graph)로 나뉘며, 간선에 비용이나 거리가 부여된 경우 가중치 그래프(Weighted Graph)라고 합니다.
•
그래프를 코드로 구현하는 2가지 방법:
| 비교 기준 | 인접 행렬 (Adjacency Matrix) | 인접 리스트 (Adjacency List) |
|---|---|---|
| 구현 방식 | 크기의 2차원 배열 `adj[u][v]` | 각 정점마다 연결된 정점들의 동적 배열/리스트 |
| 메모리 공간 | (간선이 적어도 고정 소모) | (실제 간선 수만큼만 소모) |
| 두 정점 연결 확인 | (`adj[u][v]` 즉시 조회) | (연결된 리스트 순회) |
| 한 정점과 연결된 모든 노드 순회 | (해당 행 전체 칸 확인) | (실제 이웃만 방문) |
| 적합한 상황 | 간선이 매우 많은 밀집 그래프(Dense) | 정점이 많고 간선이 적은 희소 그래프(Sparse) |
학습 도움말
코딩 테스트에서 정점 수 V가 100,000개일 때 인접 행렬(V × V)을 선언하면 100억 칸(약 40GB)이 필요해 즉시 메모리 초과(MLE)가 발생합니다! 정점이 수천 개 이상이면 무조건 '인접 리스트'를 사용하세요.2
해시 테이블(Hash Table)의 원리와 충돌(Collision) 해결 기법
•
해시 테이블 (파이썬
dict, 자바 HashMap, JS Map/Object):•
임의의 키(Key, 예:
"apple")를 해시 함수(Hash Function)에 넣어 정수형 해시 코드로 변환한 뒤, 배열 크기 으로 나눈 나머지()를 인덱스로 삼아 버킷(Bucket)에 값을 저장합니다.•
키만 알면 인덱스를 즉시 계산하므로 탐색·삽입·삭제의 평균 시간 복잡도가 이라는 경이로운 성능을 발휘합니다.
•
해시 충돌 (Hash Collision): 서로 다른 두 키 가 우연히 같은 버킷 인덱스로 매핑되는 현상입니다 (비둘기집의 원리에 의해 필연적으로 발생).
1
분리 연결법 (Separate Chaining): 같은 인덱스에 충돌한 데이터들을 연결 리스트(또는 Red-Black 트리)로 줄줄이 매달아 저장합니다 (Java
HashMap 채택 방식, 버킷에 8개 이상 쌓이면 트리로 전환하여 최악 보장).2
개방 주소법 (Open Addressing): 연결 리스트를 쓰지 않고 배열 내부의 다른 빈칸을 찾아 저장합니다.
•
선형 탐사 (Linear Probing): 충돌 시 바로 다음 칸()을 검사 (특정 영역에 데이터가 뭉치는 일차 군집화 Primary Clustering 문제 발생).
•
제곱 탐사 (Quadratic Probing) 및 이중 해싱 (Double Hashing): 보폭을 제곱수()나 두 번째 해시 함수로 넓혀 군집화를 방지합니다 (Python
dict는 개방 주소법 계열 사용).풀이
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]번 인덱스에 저장됩니다.
3
적재율(Load Factor)과 리해싱(Rehashing) 실무 포인트
•
적재율 (Load Factor, ): 전체 버킷 크기 대비 현재 저장된 데이터 개수 의 비율입니다.
•
적재율이 높아질수록(보통 ) 충돌 확률이 급격히 상승하여 해시 테이블의 성능이 평균 에서 최악 으로 떨어집니다.
•
따라서 적재율이 임계치(예: 0.75)를 넘으면 버킷 배열의 크기를 2배로 늘리고 모든 키의 해시 인덱스를 다시 계산해 배치하는 리해싱(Rehashing)을 수행합니다.
•
불변(Immutable) 객체만 해시 키가 될 수 있는 이유:
•
파이썬
dict나 set에서 리스트(list)는 키로 쓸 수 없고 튜플(tuple)이나 문자열(str)만 키로 쓸 수 있습니다. 만약 키 객체의 내부 값이 저장 후 변경되면 해시값도 바뀌어 버려, 원래 저장했던 버킷 위치를 영영 찾을 수 없게 되기 때문입니다.핵심 원리
해시 테이블의 시간 복잡도는 '평균 O(1), 최악 O(N)'입니다. 모든 키가 동일한 버킷으로 충돌(Hash DoS 공격 등)하면 연결 리스트를 끝까지 탐색해야 하므로 O(N)이 걸린다는 점을 반드시 기억하세요.핵심 요약
- ✓그래프 표현에서 인접 행렬은 두 정점의 연결 확인이 O(1)로 빠르고, 인접 리스트는 메모리 사용량이 O(V+E)로 효율적이다.
- ✓해시 테이블은 해시 함수를 통해 Key를 배열 인덱스로 직접 변환하여 평균 O(1)의 검색·삽입·삭제 속도를 제공한다.
- ✓해시 충돌 해결 기법으로는 연결 리스트를 활용하는 분리 연결법(Chaining)과 빈 버킷을 탐색하는 개방 주소법(Open Addressing)이 있다.
- ✓적재율(Load Factor)이 임계치를 넘으면 충돌을 줄이기 위해 테이블 크기를 확장하는 리해싱(Rehashing)이 수행된다.