정답
변형된 선형조사법: 네트워크 교과목의 충돌 횟수는 0회, 저장 버킷 번호는 0번이다.
이차조사법: 총 충돌 횟수는 10회이고, 버킷 번호 3에 있는 교과목 코드는 25(인공지능)이다.
출제 의도
해시 함수와 해시 테이블에서의 오버플로를 선형조사법과 이차조사법으로 처리하는 과정을 이해하고, 주어진 키들을 삽입하면서 실제로 충돌 횟수와 최종 저장 위치를 계산할 수 있는지를 평가한다.
풀이 과정
버킷 수는 13개이고, 기본 해시 함수는 \( h(k) = k \bmod 13 \) 이다. 저장 순서는 코드 값 \(89, 15, 12, 13, 4, 25, 30, 9, 2, 5, 21, 72, 45\) 이다. 네트워크 교과목의 코드는 13이다.
먼저 변형된 선형조사법에서의 삽입을 살펴본다. 변형된 선형조사법은 해시로 계산된 버킷이 이미 차 있으면, 그보다 앞의 버킷들(번호를 감소시키며)을 차례대로 조사하고, 0번까지 가면 다시 12번으로 되돌아가며 빈 슬롯을 찾는 방식이다.
각 코드에 대해 \( h(k) = k \bmod 13 \) 을 계산하면 다음과 같다. \(89 \rightarrow 11,\; 15 \rightarrow 2,\; 12 \rightarrow 12,\; 13 \rightarrow 0,\; 4 \rightarrow 4,\; 25 \rightarrow 12,\; 30 \rightarrow 4,\; 9 \rightarrow 9,\; 2 \rightarrow 2,\; 5 \rightarrow 5,\; 21 \rightarrow 8,\; 72 \rightarrow 7,\; 45 \rightarrow 6\).
초기에는 모든 버킷이 비어 있으므로, 89(11번), 15(2번), 12(12번)는 충돌 없이 각 버킷에 저장된다. 다음으로 네트워크 코드 13의 해시 값은 \( h(13) = 0 \) 이고, 0번 버킷이 비어 있으므로 역시 충돌 없이 0번 버킷에 저장된다.
따라서 변형된 선형조사법을 사용할 때 네트워크(코드 13)는 충돌 횟수 0회, 저장 버킷 번호 0번이다.
이제 이차조사법을 사용한 경우를 본다. 이차조사법에서는 해시 함수 \( g(k) = k \bmod 13 \) 으로 시작하고, \(i\)번째 조사 위치는
$$ \bigl(g(k) + i^2\bigr) \bmod 13 \quad (i = 0, 1, 2, \dots) $$
이다. 각 키를 순서대로 삽입하면서, 이미 차 있는 버킷을 만날 때마다 충돌 1회를 기록한다.
버킷의 상태를 추적하면 다음과 같다.
① 89: \(g(89)=11\). 11번 비어 있음 → 11번에 저장, 충돌 0회. ② 15: \(g(15)=2\). 2번 비어 있음 → 2번에 저장, 충돌 0회. ③ 12: \(g(12)=12\). 12번 비어 있음 → 12번에 저장, 충돌 0회. ④ 13: \(g(13)=0\). 0번 비어 있음 → 0번에 저장, 충돌 0회. ⑤ 4: \(g(4)=4\). 4번 비어 있음 → 4번에 저장, 충돌 0회.
⑥ 25: \(g(25)=12\). \(i=0\): 12번(12가 있음) → 충돌 1회. \(i=1\): \((12+1^2)\bmod13 = 0\)번(13이 있음) → 충돌 2회. \(i=2\): \((12+2^2)\bmod13 = 3\)번(비어 있음) → 3번에 저장. → 25의 충돌 횟수 2회.
⑦ 30: \(g(30)=4\). \(i=0\): 4번(4가 있음) → 충돌 1회. \(i=1\): \((4+1^2)\bmod13 = 5\)번 비어 있음 → 5번에 저장. → 30의 충돌 횟수 1회.
⑧ 9: \(g(9)=9\). 9번 비어 있음 → 9번에 저장, 충돌 0회.
⑨ 2: \(g(2)=2\). \(i=0\): 2번(15가 있음) → 충돌 1회. \(i=1\): \((2+1^2)\bmod13 = 3\)번(25가 있음) → 충돌 2회. \(i=2\): \((2+2^2)\bmod13 = 6\)번 비어 있음 → 6번에 저장. → 2의 충돌 횟수 2회.
⑩ 5: \(g(5)=5\). \(i=0\): 5번(30이 있음) → 충돌 1회. \(i=1\): \((5+1^2)\bmod13 = 6\)번(2가 있음) → 충돌 2회. \(i=2\): \((5+2^2)\bmod13 = 9\)번(9가 있음) → 충돌 3회. \(i=3\): \((5+3^2)\bmod13 = 14\bmod13 = 1\)번 비어 있음 → 1번에 저장. → 5의 충돌 횟수 3회.
⑪ 21: \(g(21)=8\). 8번 비어 있음 → 8번에 저장, 충돌 0회. ⑫ 72: \(g(72)=7\). 7번 비어 있음 → 7번에 저장, 충돌 0회.
⑬ 45: \(g(45)=6\). \(i=0\): 6번(2가 있음) → 충돌 1회. \(i=1\): \((6+1^2)\bmod13 = 7\)번(72가 있음) → 충돌 2회. \(i=2\): \((6+2^2)\bmod13 = 10\)번 비어 있음 → 10번에 저장. → 45의 충돌 횟수 2회.
모든 삽입이 끝난 후 버킷 배열(0번~12번)은 다음과 같다.
0번: 13, 1번: 5, 2번: 15, 3번: 25, 4번: 4, 5번: 30, 6번: 2, 7번: 72, 8번: 21, 9번: 9, 10번: 45, 11번: 89, 12번: 12
따라서 버킷 번호 3에는 코드 25(인공지능)가 저장되어 있다.
총 충돌 횟수는 각 코드의 충돌 횟수를 모두 더한 값이다.
25: 2회, 30: 1회, 2: 2회, 5: 3회, 45: 2회 \(\Rightarrow 2 + 1 + 2 + 3 + 2 = 10\)회
정리하면, 이차조사법 사용 시 총 충돌 횟수는 10회이고, 버킷 3에는 코드 25(인공지능)가 저장된다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>