🧭 선수 개념 — 이 문서는 다음을 안다는 전제로 쓰였어요: 나눗셈 (초등) · 자연수 (초등)
정의
나머지 연산은 자연수 $a$를 자연수 $n$으로 나누었을 때 남는 나머지를 구하는 연산이다. $a$를 $n$으로 나눈 나머지를 $a \bmod n$($a$ 모드 $n$이라 읽는다)으로 쓴다. 예를 들어 $17 \div 5 = 3 \cdots 2$ 이므로 $17 \bmod 5 = 2$ 이다.
**해시(hash)**는 크기가 제각각인 데이터(숫자, 문자열 등)를 정해진 범위 안의 값 하나로 바꾸어 주는 규칙이다. 이런 규칙을 만드는 함수를 해시 함수라 부르고 $h(x)$로 나타낸다. 가장 간단한 해시 함수는 나머지 연산을 이용한 $h(x) = x \bmod n$ 이다.
직관
12시간짜리 시계를 생각해 보자. 13시는 시계 위에서 1시로 보이고, 25시는 1시로 보인다. 시계는 큰 수를 12개의 자리 중 하나로 "압축"해서 보여 주는 셈인데, 나머지 연산이 바로 이런 역할을 한다.
해시는 이 원리를 데이터 정리에 응용한 것이다. 수천 개의 물건을 딱 100개의 칸에 나눠 담아야 한다면, 물건마다 번호를 매기고 그 번호를 100으로 나눈 나머지를 칸 번호로 정하면 된다. 물건이 아무리 많아도 칸은 항상 0번부터 99번까지, 즉 정해진 개수로만 있으면 된다.
학번 3자리 수 234, 187, 109를 $h(x) = x \bmod 4$ 로 해시하면 각각 $2, 3, 1$ 이 되어 0~3번 상자 중 하나로 정해진다.
🌍 실생활 예시
프로그램에서 많은 자료를 빠르게 찾기 위해 쓰는 해시 테이블은 자료의 키(key) 값을 나머지 연산으로 저장 위치(버킷)로 바꾼다. 예를 들어 저장 공간이 100칸이라면 키 값을 100으로 나눈 나머지를 그 자료가 들어갈 칸 번호로 삼는다. 그러면 자료가 아무리 많아도 "칸 번호로 바로 찾아가기"만 하면 되므로 검색이 매우 빨라진다. 다만 서로 다른 키가 같은 칸 번호를 받는 충돌이 생길 수 있어, 이를 처리하는 방법을 함께 설계해야 한다.
⚠️ 흔한 실수
잘못된 생각: $10 \bmod 3$을 계산할 때 몫인 3을 답으로 쓴다. → 왜 틀렸는지: 나머지 연산의 답은 몫이 아니라 나누고 남는 수다. $10 = 3 \times 3 + 1$ 이므로 $10 \bmod 3 = 1$ 이 맞다.
잘못된 생각: 나머지가 나누는 수 $n$과 같거나 더 클 수도 있다고 생각한다. → 왜 틀렸는지: 나머지는 항상 $0$ 이상 $n$ 미만이어야 한다. 만약 계산 결과 나머지가 $n$ 이상이면 몫을 잘못 구한 것이다.
잘못된 생각: 두 데이터의 해시값 $h(x)$가 같으면 원래 데이터도 같다고 믿는다. → 왜 틀렸는지: 해시는 많은 입력을 적은 개수의 출력으로 압축하는 과정이므로, 서로 다른 데이터가 우연히 같은 해시값(충돌)을 가질 수 있다. 해시값이 같다고 원본이 같다는 보장은 없다.
확인 문제
$128 \bmod 6$의 값을 구하시오.
학생 37명을 번호 1번부터 37번까지 매긴 뒤 $h(x) = x \bmod 5$ 로 5개 조에 배정하려고 한다. 몇 번 학생과 몇 번 학생이 반드시 같은 조가 되는지 한 쌍을 찾고, 이런 일이 왜 항상 일어날 수밖에 없는지 입력 개수와 출력 개수를 비교해서 설명하시오.
$47 \times 53 \bmod 6$을 두 가지 방법(직접 곱한 뒤 나머지 구하기 / 각각 나머지를 구한 뒤 곱하고 다시 나머지 구하기)으로 계산해서 같은 값이 나오는지 확인하시오.
정답 보기
$128 = 21 \times 6 + 2$ 이므로 $128 \bmod 6 = 2$.
예를 들어 1번과 6번 학생은 둘 다 $h(x) = x \bmod 5 = 1$ 이 되어 같은 조가 된다. 학생은 37명(입력)인데 조는 5개(출력)뿐이므로, 비둘기집 원리에 의해 적어도 두 학생은 같은 조에 배정될 수밖에 없다 — 이것이 해시 충돌이 일어나는 이유다.
직접 계산: $47 \times 53 = 2491 = 415 \times 6 + 1$ 이므로 $1$. 나눠서 계산: $47 \bmod 6 = 5$, $53 \bmod 6 = 5$, $5 \times 5 = 25$, $25 \bmod 6 = 1$. 두 방법 모두 $1$로 같다.