컴퓨터시스템기사 실기 03 — 자료구조 II (그래프·인덱스·해싱)
출제기준(실기) 4. 자료구조 활용 — 4-3 그래프 활용(그래프 구현·탐색), 4-4 인덱스와 해싱 활용
2026 개편에서 새로 들어온 항목이라 기출 직접 출제는 적지만, 개념 + 짧은 계산 형태로 나올 수 있어요.
최단 거리 표와 해시 주소 계산을 손으로 풀어 보세요!
이전 편(02편)에서는 스택·큐·트리·정렬·탐색을 정리했습니다.
이번 편은 자료구조 항목의 나머지인 그래프, 인덱스, 해싱입니다.
이번 편의 출제기준 위치
| 코드 | 세세항목 |
| 4-3-1 | 그래프를 구현할 수 있다 |
| 4-3-2 | 주어진 그래프를 탐색할 수 있다 |
| 4-4-1 | 주어진 자료에서 인덱스를 활용할 수 있다 |
| 4-4-2 | 주어진 자료에서 해시 함수를 활용할 수 있다 |
실기 출제 포인트
복원 기출 정리 파일에서 확인한 출제 현황입니다.
| 유형 | 확인된 회차 | 중요도 |
| A*에서 h(n)=0이면 어떤 알고리즘? → 다익스트라 | 2026-1 Q12 | ⭐⭐ |
| 해시 테이블 데이터 수 ÷ 슬롯 수 지표 → Load Factor | 2026-1 Q15 | ⭐⭐ |
| McCabe 순환 복잡도 (구 범위, 그래프 계산) | 2026-1 Q11 (원문 불완전: 간선 11, 노드 9) | ⭐⭐ |
| 그래프 구현·BFS/DFS·인덱스 직접 출제 | 확인 안 됨 (A·B형 전체에서 0건) | ⭐ (신규 항목이라 대비) |
⚠️ 그래프·해싱은 2026년 1회에서 처음 확인되는 신규 유형입니다.
앞으로 출제 방식이 바뀔 수 있으니, 용어 문제뿐 아니라 표를 채워 가며 계산하는 문제도 대비해 두세요.
키워드 박스 (답안 필수 단어)
그래프 — 정점(Vertex), 간선(Edge), 차수, 방향·무방향, 가중치, 경로, 사이클
구현 — 인접 행렬 (V×V 배열), 인접 리스트 (정점별 연결 리스트)
탐색 — BFS(큐, 너비 우선), DFS(스택·재귀, 깊이 우선)
최단 경로 — 다익스트라(음수 가중치 불가), A*(f = g + h), h = 0이면 다익스트라
인덱스 — 검색 속도 향상용 별도 구조, B-Tree(범위 검색) / 해시(등호 검색)
해싱 — 해시 함수, 충돌(Collision), 체이닝, 개방 주소법, Load Factor(α = n / m)그래프 이해와 구현 ⭐⭐
기본 용어
정점(V) : 노드 간선(E) : 정점을 잇는 선
차수 : 정점에 연결된 간선 수
가중치 그래프 : 간선에 비용(거리, 시간 등)이 붙은 그래프
최대 간선 수 : 정점이 n개일 때
무방향 그래프 → n(n−1)/2
방향 그래프 → n(n−1) (자기 간선·중복 간선 제외)
예) 정점 5개 방향 그래프 → 5 × 4 = 20인접 행렬과 인접 리스트
그래프: 1─2, 1─3, 2─4, 3─4
인접 행렬 인접 리스트
1 2 3 4 1 : [2, 3]
1 0 1 1 0 2 : [1, 4]
2 1 0 0 1 3 : [1, 4]
3 1 0 0 1 4 : [2, 3]
4 0 1 1 0| 구분 | 인접 행렬 | 인접 리스트 |
| 공간 | O(V²) | O(V + E) |
| 간선 존재 확인 | O(1) | 해당 정점의 이웃 수만큼 |
| 모든 이웃 순회 | O(V) | 이웃 수만큼 |
| 유리한 경우 | 간선이 많은 조밀 그래프 | 간선이 적은 희소 그래프 |
int adj[5][5]; /* 인접 행렬 */
adj[u][v] = 1; adj[v][u] = 1; /* 무방향 간선 u-v : 대칭으로 둘 다 표시 */
adj[u][v] = 1; /* 방향 간선 u→v : 한쪽만 표시 */그래프 탐색 BFS·DFS ⭐⭐⭐
| 구분 | BFS (너비 우선) | DFS (깊이 우선) |
| 사용 구조 | 큐 | 스택 또는 재귀 |
| 탐색 방식 | 시작점에서 가까운 정점부터 레벨 순으로 | 한 방향으로 끝까지 갔다가 되돌아옴 |
| 대표 용도 | 간선 수 기준 최단 경로 | 연결 요소 찾기, 사이클 검사 |
| 시간 복잡도 | O(V + E) (인접 리스트) | O(V + E) (인접 리스트) |
BFS: 큐에 시작점 넣고 방문 표시
큐가 빌 때까지: dequeue → 방문 → 안 가 본 이웃을 방문 표시 후 enqueue
DFS: dfs(v): 방문 표시 → v의 이웃 w 중 안 가 본 w에 대해 dfs(w)그래프 (이웃은 번호가 작은 순서로 본다)
1
/ \
2 3
/ \ / \
4 5 6 7
인접 리스트 1:[2,3] 2:[1,4,5] 3:[1,6,7] 4:[2] 5:[2] 6:[3] 7:[3]
BFS: 큐 [1] → 1 방문, [2,3] → 2 방문, [3,4,5] → 3 방문, [4,5,6,7] → 나머지
방문 순서: 1 2 3 4 5 6 7
DFS: 1 → 2 → 4 (되돌아옴) → 5 (되돌아옴) → 1로 복귀 → 3 → 6 → 7
방문 순서: 1 2 4 5 3 6 7
⚠️ 함정 패턴
"BFS는 스택, DFS는 큐를 사용한다" → 오답! (BFS = 큐, DFS = 스택)
"이웃을 보는 순서는 상관없다" → 문제 조건 확인! (번호 작은 순, 알파벳 순 등으로 정해 줌)
"방문 표시 없이 탐색" → 사이클이 있으면 무한 루프최단 경로: 다익스트라와 A* ⭐⭐⭐
다익스트라(Dijkstra)
조건 : 간선 가중치가 모두 0 이상 (음수 가중치는 불가 → 벨만-포드 사용)
방법 : 시작점 거리 0, 나머지 ∞ 로 시작
① 확정 안 된 정점 중 거리가 가장 작은 정점 선택 → 확정
② 그 정점을 거쳐 가는 이웃의 거리를 더 짧으면 갱신
③ 모든 정점이 확정될 때까지 반복
복잡도 : 우선순위 큐 사용 시 O((V + E) log V)
예) 무방향 그래프, 간선 A–B 4, A–C 1, B–C 2, B–D 1, C–D 5, D–E 3 일 때 A에서 출발
| 단계 | 확정 정점 | A | B | C | D | E |
|---|---|---|---|---|---|---|
| 단계 | 확정 정점 | A | B | C | D | E |
| 시작 | — | 0 | ∞ | ∞ | ∞ | ∞ |
| 1 | A (0) | 0 | 4 | 1 | ∞ | ∞ |
| 2 | C (1) | 0 | min(4, 1+2) = 3 | 1 | 1+5 = 6 | ∞ |
| 3 | B (3) | 0 | 3 | 1 | min(6, 3+1) = 4 | ∞ |
| 4 | D (4) | 0 | 3 | 1 | 4 | 4+3 = 7 |
| 5 | E (7) | 0 | 3 | 1 | 4 | 7 |
A→E 최단 거리 = 7, 경로 = A → C → B → D → EA* (A-star)
f(n) = g(n) + h(n)
g(n) : 시작점에서 n까지 실제 비용
h(n) : n에서 목표까지의 추정 비용 (휴리스틱)
h가 실제 비용을 넘지 않으면(허용 가능) 최적해 보장
h(n) = 0 이면 f(n) = g(n) → 다익스트라와 같아짐 ← 2026-1 Q12 기출| 알고리즘 | 용도 |
| BFS | 가중치가 없거나 같을 때 최소 간선 수 경로 |
| 다익스트라 | 음수 없는 가중치 그래프의 최단 경로 |
| A* | 목표가 정해져 있을 때 휴리스틱으로 탐색 범위를 줄임 |
| 벨만-포드 | 음수 가중치가 있는 그래프 |
인덱스 ⭐⭐
인덱스(색인) : 데이터를 빨리 찾기 위해 키 값과 위치를 따로 모아 둔 구조
- 인덱스가 없으면 처음부터 끝까지 순차 탐색 O(n)
- B-Tree 인덱스 : 균형 트리, 탐색 O(log n), 범위 검색에 유리
- 해시 인덱스 : 평균 O(1), 등호(=) 검색에 유리, 범위 검색에는 부적합
- 단점 : 추가 저장 공간, 삽입·삭제 때 인덱스도 갱신해야 해서 쓰기가 느려짐| 구분 | 설명 |
| 기본(Primary) 인덱스 | 데이터가 정렬된 키 기준으로 만든 인덱스 |
| 보조(Secondary) 인덱스 | 정렬 키가 아닌 다른 속성으로 만든 인덱스 |
| 밀집(Dense) | 모든 레코드에 인덱스 항목이 있음 |
| 희소(Sparse) | 일부 레코드(블록 단위)에만 인덱스 항목이 있음 |
⚠️ "인덱스"라는 단어가 나오는 다른 문제와 헷갈리지 마세요.
인덱스 레지스터 : 인덱스 주소 지정 방식에서 EA = IX + A (2022-1, 2023-1 정답이 "인덱스") → 04편에서 정리
i-node (Index Node) : UNIX 파일 시스템에서 파일의 소유자, 크기, 시간, 권한, 데이터 블록 주소를 담은 블록 (2017-3)
(파일 이름은 i-node가 아니라 디렉터리 엔트리에 있음)
자료구조의 인덱스 : 이번 편의 검색용 색인해시 함수와 해시 테이블 ⭐⭐⭐
해시 테이블 : 키를 해시 함수에 넣어 나온 값으로 저장 위치(슬롯)를 정하는 구조
평균 탐색·삽입 O(1)
해시 함수 : h(k) → 0 ~ m−1 (m = 슬롯 수)해시 함수 종류
| 방법 | 설명 |
| 나눗셈법 | h(k) = k mod m (m은 소수가 좋음) |
| 곱셈법 | 키에 상수를 곱해 소수 부분을 이용 |
| 폴딩 | 키를 몇 조각으로 나눠 더함 |
| 중간 제곱법 | 키를 제곱해 중간 부분을 사용 |
충돌과 해결
충돌(Collision) : 서로 다른 키가 같은 슬롯으로 가는 것
체이닝(Chaining) : 같은 슬롯의 키들을 연결 리스트로 이어 붙임
개방 주소법(Open Addressing) : 비어 있는 다른 슬롯을 찾아 저장
선형 탐사 : h(k), h(k)+1, h(k)+2, ...
이차 탐사 : h(k), h(k)+1², h(k)+2², ...
이중 해싱 : h1(k) + i × h2(k)적재율(Load Factor) ⭐⭐⭐
α = 저장된 데이터 수(n) / 슬롯 수(m) ← 2026-1 Q15 기출
α가 클수록 충돌이 많아져 성능이 떨어짐
개방 주소법은 α ≤ 1, 체이닝은 α > 1도 가능
α가 너무 커지면 슬롯 수를 늘려 다시 해싱(재해싱, Rehashing)계산 예
h(k) = k mod 7, 키 50, 700, 76, 85, 92를 순서대로 저장
50 mod 7 = 1 → 슬롯 1
700 mod 7 = 0 → 슬롯 0
76 mod 7 = 6 → 슬롯 6
85 mod 7 = 1 → 충돌!
92 mod 7 = 1 → 충돌!
[선형 탐사] [체이닝]
슬롯 0 : 700 슬롯 0 : 700
슬롯 1 : 50 슬롯 1 : 50 → 85 → 92
슬롯 2 : 85 (1 충돌 → 2) 슬롯 6 : 76
슬롯 3 : 92 (1, 2 충돌 → 3)
슬롯 6 : 76
Load Factor = 5 / 7 ≈ 0.71
⚠️ 함정 패턴
"해시 함수 = SHA-256" → 헷갈림 주의!
자료구조의 해시 함수 : 빠른 주소 계산이 목적, 충돌이 있어도 됨
암호학적 해시 함수 : 무결성 검증이 목적, 충돌을 찾기 어렵게 설계
"Load Factor = 충돌 횟수" → 오답! (데이터 수 ÷ 슬롯 수)
"체이닝도 슬롯이 가득 차면 저장 못 한다" → 오답! (연결 리스트로 계속 이어짐)구 범위 보충: McCabe 순환 복잡도 ⭐⭐
출제기준(실기)에는 없지만 2026년 1회 Q11에 간선 11, 노드 9로 나왔습니다.
원문(그림과 정확한 질문)은 복원되지 않았으니 계산 방법만 알아 두세요.
V(G) = E − N + 2 (E = 간선 수, N = 노드 수, 연결 그래프 가정)
= 판단(분기) 노드 수 + 1
= 닫힌 영역 수 (외부 영역 포함)
예) 간선 11, 노드 9 → V(G) = 11 − 9 + 2 = 4
순환 복잡도는 프로그램의 독립적인 실행 경로 수이고, 기초 경로 검사(화이트박스 테스트)에서 필요한 최소 테스트 케이스 수와 같습니다. 2017-1에도 "화이트 박스 테스트 2가지"(기초 경로 검사, 제어 구조 검사)가 출제되었습니다.
소프트웨어 테스트는 09편의 구 범위 보충에서 이어서 정리합니다.
기출 Q&A
Q. A* 알고리즘에서 휴리스틱 h(n) = 0이면 어떤 탐색 알고리즘과 같아지는가?
A. 다익스트라(Dijkstra) 알고리즘
(2026-1 Q12) f(n) = g(n) + h(n)에서 h = 0이면 f = g가 되어, 시작점에서 가장 가까운 정점부터 확정하는 다익스트라와 같아집니다. 복원 메모 기준 답입니다.
Q. 해시 테이블에서 전체 데이터 수를 슬롯 수로 나눈 값, 즉 성능을 나타내는 지표는?
A. Load Factor(적재율)
(2026-1 Q15) α = n / m. 클수록 충돌이 많아집니다.
Q. (구 범위) 제어 흐름 그래프의 간선이 11개, 노드가 9개일 때 McCabe 순환 복잡도는?
A. 4
(2026-1 Q11, 원문 불완전) V(G) = E − N + 2 = 11 − 9 + 2 = 4 (연결 그래프 가정)
예상 문제 (직접 만든 문제)
Q1. 위 다익스트라 예시 그래프에서 A에서 D까지의 최단 거리와 경로는?
A1. 4, A → C → B → D (1 + 2 + 1)
Q2. 정점 5개인 방향 그래프의 최대 간선 수는? (자기 간선·중복 간선 제외)
A2. 20 (5 × 4)
Q3. 해시 테이블의 슬롯이 50개이고 데이터를 30개 저장했을 때 Load Factor는?
A3. 0.6 (30 / 50)
Q4. BFS와 DFS가 사용하는 자료구조를 각각 쓰시오.
A4. BFS = 큐, DFS = 스택(또는 재귀 호출)
💡 실무에서는?
- 그래프: 네트워크 토폴로지가 곧 그래프입니다. OSPF는 SPF 알고리즘(다익스트라)으로 최단 경로 트리를 계산하고, 인터페이스 cost를 바꾸는 것은 간선 가중치를 바꾸는 일입니다. 서비스 간 호출 관계나 의존성도 그래프로 그리면 장애 영향 범위를 DFS·BFS로 따라갈 수 있습니다.
- 해싱: 로드 밸런서의 해시 기반 분산(IP 해시)이나 캐시 키 설계에서 같은 원리를 씁니다. 보안 시스템에서 쓰는 SHA 계열 해시는 이번 편의 해시 함수와 목적이 달라서, 시험에서는 둘을 구분해서 써야 합니다.
- 인덱스: DB 튜닝에서
EXPLAIN으로 인덱스 사용 여부를 확인합니다. 등호 조건이 대부분이면 해시, 범위 조건이 있으면 B-Tree가 맞습니다. 인덱스를 너무 많이 만들면 쓰기 성능이 떨어집니다.
핵심 정리
✅ 그래프 구현 = 인접 행렬 O(V²) / 인접 리스트 O(V+E)
✅ 방향 그래프 최대 간선 n(n−1), 무방향 n(n−1)/2
✅ BFS = 큐(레벨 순) / DFS = 스택·재귀(깊이 순)
✅ 다익스트라 = 음수 가중치 불가, 가까운 정점부터 확정
✅ A* f = g + h, h = 0 이면 다익스트라
✅ 인덱스: B-Tree = 범위 검색, 해시 = 등호 검색
✅ Load Factor α = n / m, 클수록 충돌 증가
✅ 충돌 해결: 체이닝 / 개방 주소법(선형·이차·이중 해싱)
✅ (구 범위) McCabe V(G) = E − N + 2
다음 편에서는 프로세서와 명령어 (ALU·레지스터, 명령어 형식, 파이프라인)로 이어갑니다!
궁금한 점은 댓글로 남겨주세요!
'자격증 정복 > 컴퓨터시스템기사' 카테고리의 다른 글
| 컴퓨터시스템기사 실기 05 — 기억장치와 캐시 (주기억장치·보조기억장치·캐시메모리·연관기억장치) (0) | 2026.10.15 |
|---|---|
| 컴퓨터시스템기사 실기 04 — 프로세서와 명령어 (레지스터·명령어 형식·주소지정·제어·파이프라인) (0) | 2026.10.14 |
| 컴퓨터시스템기사 실기 02 — 자료구조 I (스택·큐·트리 순회·정렬·탐색) (0) | 2026.10.11 |
| 컴퓨터시스템기사 실기 01 — 시리즈 소개와 실기 출제 맵 (2026 개편 출제기준) (0) | 2026.10.11 |
| 컴퓨터시스템기사 필기 시험 후기 — 벼락치기로 63.75점? (2026년 3회차) (0) | 2026.08.25 |