컴퓨터시스템기사 실기 03 — 자료구조 II (그래프·인덱스·해싱)

올드 IT직장인 2026. 10. 13. 00:30

컴퓨터시스템기사 실기 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 → E

A* (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·레지스터, 명령어 형식, 파이프라인)로 이어갑니다!

궁금한 점은 댓글로 남겨주세요!

저작자표시 비영리 동일조건 (새창열림)