# 해시와 나머지 연산 분야: CS·데이터사이언스 학교급: 중등 정식 URL: https://pi.devxdev.xyz/wiki/math/%ED%95%B4%EC%8B%9C%EC%99%80_%EB%82%98%EB%A8%B8%EC%A7%80_%EC%97%B0%EC%82%B0 --- ## 정의 **나머지 연산**은 자연수 $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번까지, 즉 정해진 개수로만 있으면 된다. ## 성질 나머지 연산에는 다음과 같은 유용한 성질이 있다 (단, $a, b, n$은 자연수). $$(a+b) \bmod n = \big((a \bmod n) + (b \bmod n)\big) \bmod n$$ $$(a \times b) \bmod n = \big((a \bmod n) \times (b \bmod n)\big) \bmod n$$ 즉 먼저 나머지를 구한 뒤에 더하거나 곱하고 다시 나머지를 구해도 결과가 같다. 큰 수를 직접 계산하지 않고도 나머지를 구할 수 있어 편리하다. 해시 함수는 다음 두 성질을 갖는다. - **같은 입력 → 항상 같은 출력**: $x$ 값이 같으면 $h(x)$도 항상 같다. - **서로 다른 입력이 같은 출력을 가질 수 있음**: 입력의 개수가 출력 범위보다 많으면 반드시 겹치는 값이 생기는데, 이를 **해시 충돌**이라 한다. ## 예시 - $253 \bmod 7$: $253 = 36 \times 7 + 1$ 이므로 $253 \bmod 7 = 1$. - 곱셈에서 성질 활용: $18 \times 23 \bmod 5$는 $18 \bmod 5 = 3$, $23 \bmod 5 = 3$ 이므로 $3 \times 3 = 9$, 다시 $9 \bmod 5 = 4$. 실제로 $18 \times 23 = 414 = 82 \times 5 + 4$ 이므로 일치한다. - 학번 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)$가 같으면 원래 데이터도 같다고 믿는다. → **왜 틀렸는지**: 해시는 많은 입력을 적은 개수의 출력으로 압축하는 과정이므로, 서로 다른 데이터가 우연히 같은 해시값(충돌)을 가질 수 있다. 해시값이 같다고 원본이 같다는 보장은 없다. ## 확인 문제 1. $128 \bmod 6$의 값을 구하시오. 2. 학생 37명을 번호 1번부터 37번까지 매긴 뒤 $h(x) = x \bmod 5$ 로 5개 조에 배정하려고 한다. 몇 번 학생과 몇 번 학생이 반드시 같은 조가 되는지 한 쌍을 찾고, 이런 일이 왜 항상 일어날 수밖에 없는지 입력 개수와 출력 개수를 비교해서 설명하시오. 3. $47 \times 53 \bmod 6$을 두 가지 방법(직접 곱한 뒤 나머지 구하기 / 각각 나머지를 구한 뒤 곱하고 다시 나머지 구하기)으로 계산해서 같은 값이 나오는지 확인하시오. 정답 보기: 1. $128 = 21 \times 6 + 2$ 이므로 $128 \bmod 6 = 2$. 2. 예를 들어 1번과 6번 학생은 둘 다 $h(x) = x \bmod 5 = 1$ 이 되어 같은 조가 된다. 학생은 37명(입력)인데 조는 5개(출력)뿐이므로, 비둘기집 원리에 의해 적어도 두 학생은 같은 조에 배정될 수밖에 없다 — 이것이 해시 충돌이 일어나는 이유다. 3. 직접 계산: $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$로 같다. ## 관련 개념 - 나눗셈 - 자연수 - 약수와 배수 - 해시 충돌과 생일 문제 - 블룸 필터 --- 관련 개념: - 나눗셈 (/wiki/math/%EB%82%98%EB%88%97%EC%85%88) - 자연수 (/wiki/math/%EC%9E%90%EC%97%B0%EC%88%98) - 약수와 배수 (/wiki/math/%EC%95%BD%EC%88%98%EC%99%80_%EB%B0%B0%EC%88%98) - 해시 충돌과 생일 문제 (/wiki/math/%ED%95%B4%EC%8B%9C_%EC%B6%A9%EB%8F%8C%EA%B3%BC_%EC%83%9D%EC%9D%BC_%EB%AC%B8%EC%A0%9C) - 블룸 필터 (/wiki/math/%EB%B8%94%EB%A3%B8_%ED%95%84%ED%84%B0)