이진 탐색과 해싱

이진 탐색(binary search)은 정렬된 줄의 가운데 값과 견줘 찾는 값이 없는 쪽 반을 버리기를 되풀이하는 탐색이고, 해싱(hashing)은 키를 해시 함수로 계산해 저장할 칸 번호를 바로 얻는 방법입니다. 앞에서부터 하나씩 견주는 순차 탐색은 n개면 최악 n번을 견주지만, 이진 탐색은 log₂ n번 남짓, 해싱은 칸이 겹치지 않으면 한 번에 찾습니다. 아래 그림은 정렬된 15칸에서 43을 찾는 과정과, 키가 해시 함수로 칸에 들어가다 부딪히는 모습을 차례로 보여 줍니다.

1이진 탐색 — 가운데를 보고 반을 버린다

이진 탐색은 줄이 정렬되어 있어야 쓸 수 있습니다. 찾는 구간의 처음과 끝 위치를 더해 2로 나눈 몫을 가운데로 삼고, 가운데 값이 찾는 값보다 작으면 오른쪽 반, 크면 왼쪽 반만 남깁니다. 1~15번 칸에서 43을 찾으면 8번(30), 12번(47), 10번(38)을 거쳐 11번에서 네 번째에 찾습니다. 앞에서부터 찾았다면 11번 견줄 자리입니다.

한 번 견줄 때마다 남은 칸이 반으로 줄어, 견주는 횟수는 많아야 ⌊log₂ n⌋ + 1번입니다(⌊ ⌋는 소수점 아래를 버린다는 뜻). 15칸이면 4번, 1000칸이면 10번이고, 시간 복잡도는 O(log n)입니다.

2해싱 — 키로 칸 번호를 계산한다

해싱은 키를 해시 함수(hash function)에 넣어 나온 칸 번호에 저장하고, 찾을 때도 같은 계산으로 그 칸을 바로 엽니다. 칸을 모은 표를 해시 테이블(hash table)이라고 합니다. 0~6번 칸에 키를 7로 나눈 나머지로 넣으면 12는 5번, 25는 4번, 31은 3번 칸입니다. 견주며 찾지 않으니 칸이 겹치지 않는 한 O(1)입니다.

해시 함수를 만드는 대표적인 방법은 다섯입니다.

파일 처리 기술: 파일 편성에서 직접 파일이 학번을 5로 나눈 나머지로 자리를 정한 것이 제산법입니다. 폴딩법은 자료에 따라 중첩법이라고도 부릅니다.

3충돌과 해결 — 같은 칸으로 계산되면

서로 다른 키가 같은 칸 번호로 계산되는 일을 충돌(collision)이라고 하고, 같은 칸으로 계산된 키들을 동의어(synonym)라고 합니다. 19는 7로 나눈 나머지가 5라 12가 든 5번 칸과 부딪힙니다. 충돌을 푸는 길은 둘입니다.

• 개방 주소법(open addressing): 해시 테이블 안에서 비어 있는 다른 칸을 찾아 넣습니다. 다음 칸부터 차례로 보는 선형 조사(linear probing)로는 19가 6번 칸에 들어갑니다. 부딪힌 키가 이웃 칸을 차지해 한곳에 몰리기 쉽습니다.
• 체이닝(chaining): 같은 칸으로 계산된 키를 그 칸에 연결 리스트로 이어 매답니다. 5번 칸에 12와 19가 줄줄이 달립니다. 테이블 칸이 모자라지 않지만, 찾을 때 매달린 줄을 따라가며 견줍니다.

예제

그림과 같은 크기의 빈 0~6번 테이블(키 mod 7)에 키 15, 22, 10, 8을 차례로 넣고, 충돌은 선형 조사로 풉니다. 한 줄에 한 키씩 적었습니다.

• 10은 충돌하지 않았지만, 22가 2번 칸을 차지한 뒤로 1~3번 칸이 이어져 8이 세 칸을 지나 4번에 들어갔습니다. 선형 조사에서 키가 한곳에 몰리는 모습입니다.
• 체이닝이었다면 1번 칸에 15, 22, 8이 매달리고, 10은 3번 칸에 홀로 들어갑니다.

시험 포인트

• 필기(시험에서는 1과목): 이진 탐색은 정렬된 줄에서만 쓰고, 가운데를 보고 반씩 버려 O(log n)입니다 — '정렬하지 않아도 된다'는 보기가 함정입니다. 견주는 횟수를 세게도 합니다. 해시 함수를 만드는 방법(제산법·제곱법·폴딩법·기수 변환법·숫자 분석법)과 충돌을 푸는 방법(개방 주소법·체이닝)을 섞어 놓고 해시 함수가 아닌 것을 고르게 합니다 — 개방 주소법은 충돌을 푸는 방법입니다.
• 실기: 이름을 한글 이름과 영문으로 씁니다 — 이진 탐색(Binary Search), 해시 함수(Hash Function), 해시 테이블(Hash Table), 충돌(Collision), 개방 주소법(Open Addressing), 선형 조사(Linear Probing), 체이닝(Chaining). 해시 함수를 만드는 방법은 한글로 씁니다 — 제산법, 제곱법, 폴딩법, 숫자 분석법.

확인 문제

1. 해시 테이블이 0~99번 칸입니다. 키 4721의 칸 번호를 폴딩법으로 정한 것을 고르세요.

• ① 4721을 8진수로 보고 10진수로 바꾼 2513의 끝 두 자리 → 13번 칸
• ② 4721을 97로 나눈 나머지 → 65번 칸
• ③ 4721을 47과 21로 끊어 더한 값 → 68번 칸
• ④ 4721을 제곱한 22287841의 가운데 두 자리 → 87번 칸

2. (가)~(라)에 맞는 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 제목순으로 꽂힌 책장에서 가운데 책을 보고, 찾는 책이 없는 쪽 반을 통째로 빼놓기를 되풀이하는 찾기
• (나) 회원 번호를 넣으면 계산을 거쳐 사물함 칸 번호를 내주는 함수
• (다) (나)가 내준 번호대로 회원 정보를 넣어 두는 칸들의 표
• (라) 번호가 서로 다른 두 회원의 칸 번호가 똑같이 계산된 일

3. 해시 함수를 만드는 방법의 이름을 한글로 쓰세요. 해시 테이블은 0~99번 칸입니다. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 상품 코드를 테이블 크기에 가까운 소수 97로 나눈 나머지를 칸 번호로 씁니다.
• (나) 상품 코드 38을 두 번 곱한 1444에서 가운데 두 자리 44를 칸 번호로 씁니다.
• (다) 상품 코드 120534를 12, 05, 34로 끊어 더한 51을 칸 번호로 씁니다.
• (라) 모든 상품 코드에 똑같은 앞 네 자리는 버리고, 값이 고르게 퍼진 끝 두 자리만 골라 칸 번호로 씁니다.

4. 충돌을 푸는 방법의 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 충돌이 나면 해시 테이블 안에서 비어 있는 다른 칸을 찾아 넣는 방법들을 통틀어 부르는 이름
• (나) (가) 가운데, 계산된 칸 바로 다음 칸부터 하나씩 차례로 보며 빈칸을 찾는 방법
• (다) 같은 칸으로 계산된 키들을 그 칸에 연결 리스트로 이어 달아 두는 방법

5. 두 가지를 풀어 보세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (1) 정렬된 줄 5, 9, 12, 18, 23, 27, 31, 36, 40, 44(위치 1~10)에서 이진 탐색으로 12를 찾습니다. 가운데는 (처음 + 끝) ÷ 2의 몫입니다. 몇 번 견주나요?
• (2) 0~10번 칸 해시 테이블에 키 mod 11로 23, 45, 34를 차례로 넣고, 충돌은 선형 조사로 풉니다. 34는 몇 번 칸에 들어가나요?