해시와 집합으로 빠른 조회 만들기

왜 필요한가: 매번 찾는 일은 생각보다 비싸다

배열에서 어떤 값이 있는지 확인하려면 보통 처음부터 끝까지 살펴본다. 원소가 10개라면 큰 문제가 아니지만, 100만 개라면 이야기가 달라진다.

예를 들어 다음 배열에서 7이 있는지 찾는다고 하자.

[4, 1, 9, 7, 2]

앞에서부터 보면 4, 1, 9를 지나서야 7을 찾는다. 운이 나쁘면 끝까지 봐야 한다. 배열에서 존재 여부를 확인하는 기본 방식은 보통 O(n)이다.

문제는 이런 조회를 반복문 안에서 계속 할 때 생긴다.

for x in A:
    if x가 B 안에 있는지 처음부터 끝까지 찾기:
        ...

A의 길이가 n이고 B의 길이도 n이라면, 매번 n개를 찾는 일이 n번 반복된다. 전체 시간 복잡도는 O(n²)이 된다.

해시는 이 상황을 바꾼다. 핵심은 간단하다.

값을 하나씩 뒤지지 말고, 찾기 쉬운 위치에 저장해 두자.

해시를 사용하면 어떤 값이 있는지 확인하는 작업을 평균적으로 O(1)에 가깝게 처리할 수 있다. 그래서 완전 탐색으로 매번 찾던 문제를 훨씬 빠르게 바꿀 수 있다.

AI 생성 이미지

해시 테이블: 값을 넣을 위치를 계산한다

해시를 처음 들으면 어렵게 느껴질 수 있다. 하지만 생각은 일상적이다.

도서관에서 책을 아무 곳에나 꽂아 두면 찾을 때 모든 책장을 뒤져야 한다. 반대로 책마다 분류 번호가 있고, 그 번호에 따라 꽂을 위치가 정해져 있다면 훨씬 빨리 찾을 수 있다.

해시 테이블도 비슷하다.

1. 저장할 값을 받는다.

2. 그 값을 어떤 숫자로 바꾼다.

3. 그 숫자를 이용해 저장할 위치를 정한다.

4. 나중에 같은 값을 찾을 때도 같은 계산을 해서 바로 그 위치로 간다.

여기서 값을 숫자로 바꾸는 규칙을 해시 함수라고 한다. 해시 함수가 계산한 값을 이용해 데이터를 저장하는 구조를 해시 테이블이라고 한다.

정확한 내부 구현은 언어마다 다르지만, 초보 단계에서는 다음 정도로 이해하면 충분하다.

값 → 해시 함수 → 저장 위치

예를 들어 apple이라는 단어를 넣으면 해시 함수가 어떤 위치를 계산한다. 나중에 apple이 있는지 확인할 때도 같은 계산을 하므로, 전체 배열을 처음부터 훑지 않아도 된다.

해시 테이블의 대표 연산은 다음과 같다.

여기서 중요한 표현은 평균적으로이다. 해시 테이블은 대부분의 실전 상황에서 매우 빠르지만, 항상 무조건 O(1)이라고 말하면 정확하지 않다. 이 부분은 뒤에서 해시 충돌을 설명할 때 다시 살펴본다.

집합: 존재 여부와 중복 제거에 강하다

집합은 중복을 허용하지 않는 자료구조다. 수학에서 말하는 집합과 비슷하다.

[3, 1, 3, 2, 1]

이 배열을 집합에 넣으면 다음처럼 중복이 사라진다.

{1, 2, 3}

집합은 값의 순서보다 있느냐 없느냐가 중요할 때 사용한다. 대표적인 상황은 다음과 같다.

• 이미 나온 숫자인지 확인하기

• 중복된 값을 제거하기

• 두 목록에 공통으로 들어 있는 값 찾기

• 한 목록에는 있고 다른 목록에는 없는 값 찾기

예시 1: 중복 제거하기

배열에서 중복을 제거한 값의 개수를 구한다고 하자.

numbers = [2, 5, 2, 3, 5, 7]

배열만 사용하면 이미 나온 값인지 매번 다시 찾아야 한다. 집합을 사용하면 간단하다.

seen = empty set

for x in numbers:
    add x to seen

answer = size of seen

2를 여러 번 넣어도 집합 안에는 하나만 남는다. 따라서 seen의 크기가 서로 다른 값의 개수가 된다.

예시 2: 두 목록의 공통 값 찾기

두 학생 명단이 있다고 하자.

clubA = ["민수", "지아", "현우"]
clubB = ["서연", "현우", "민수"]

두 동아리에 모두 들어 있는 학생을 찾고 싶다. 한 명씩 비교하면 모든 쌍을 확인해야 하므로 O(n²)이 될 수 있다. 집합을 쓰면 먼저 한쪽 명단을 저장해 두고, 다른 쪽을 보면서 존재 여부만 확인하면 된다.

setA = empty set

for name in clubA:
    add name to setA

common = empty list

for name in clubB:
    if name in setA:
        append name to common

이 방식은 clubA를 한 번, clubB를 한 번 본다. 두 명단의 길이를 각각 n, m이라고 하면 평균 시간 복잡도는 O(n + m)이다.

두 수의 합 문제를 해시로 개선하기

앞에서 완전 탐색을 배울 때 두 수의 합 문제를 생각했다. 배열에서 서로 다른 두 수를 골라 목표값을 만들 수 있는지 확인하는 문제다.

numbers = [4, 1, 7, 3]
target = 10

완전 탐색은 모든 쌍을 확인한다.

4 + 1
4 + 7
4 + 3
1 + 7
1 + 3
7 + 3

이 방식은 O(n²)이다. 하지만 관점을 바꾸면 더 빠르게 풀 수 있다.

x를 보고 있을 때 필요한 값은 target - x다. 예를 들어 7을 보고 있다면 필요한 값은 3이다. 따라서 지금까지 본 값 중에 3이 있었는지만 빠르게 확인하면 된다.

seen = empty set

for x in numbers:
    need = target - x

    if need in seen:
        return true

    add x to seen

return false

작은 예시로 따라가 보자.

numbers = [4, 1, 7, 3]
target = 10

• x = 4, 필요한 값은 6이다. 아직 없다. 4를 저장한다.

• x = 1, 필요한 값은 9이다. 아직 없다. 1을 저장한다.

• x = 7, 필요한 값은 3이다. 아직 없다. 7을 저장한다.

• x = 3, 필요한 값은 7이다. 이미 있다. 답은 true다.

여기서 중요한 점은 확인한 뒤에 현재 값을 넣는 것이다. 그래야 같은 원소를 두 번 사용하는 실수를 막을 수 있다.

예를 들어 배열이 [5]이고 목표값이 10일 때, 5 하나만으로 5 + 5를 만들었다고 판단하면 안 된다. 먼저 필요한 값이 있는지 확인하고, 그다음 현재 값을 저장하면 이런 실수를 피할 수 있다.

딕셔너리: 값에 이름표를 붙여 저장한다

집합이 존재 여부를 저장한다면, 딕셔너리는 키와 값을 쌍으로 저장한다.

key → value

예를 들면 다음과 같다.

이름 → 점수
단어 → 등장 횟수
상품명 → 가격
문자 → 나온 횟수

딕셔너리는 언어에 따라 맵, 해시맵, 해시 테이블, 객체 등으로 불리기도 한다. 이름과 세부 구현은 조금씩 다르지만, 알고리즘 문제에서 자주 사용하는 핵심은 같다.

어떤 키를 주면 그 키에 연결된 값을 빠르게 찾는다.

예시 1: 문자 등장 횟수 세기

문자열에서 각 문자가 몇 번 나오는지 세어 보자.

word = "banana"

원하는 결과는 다음과 비슷하다.

b: 1
a: 3
n: 2

딕셔너리를 사용하면 문자를 키로, 등장 횟수를 값으로 저장할 수 있다.

count = empty dictionary

for ch in word:
    if ch not in count:
        count[ch] = 0

    count[ch] = count[ch] + 1

처음 보는 문자는 횟수를 0으로 만들고, 볼 때마다 1씩 더한다. 이 패턴은 매우 자주 나온다.

숫자 등장 횟수도 똑같이 처리할 수 있다.

count = empty dictionary

for x in numbers:
    if x not in count:
        count[x] = 0
    count[x] = count[x] + 1

예시 2: 이름별 점수 저장하기

학생 이름으로 점수를 빠르게 찾고 싶다면 딕셔너리가 적합하다.

scores = empty dictionary

scores["민수"] = 90
scores["지아"] = 85
scores["현우"] = 92

이후 지아의 점수가 필요하면 전체 학생 목록을 뒤질 필요 없이 scores["지아"]로 바로 접근할 수 있다.

배열로도 학생 정보를 저장할 수는 있다.

[("민수", 90), ("지아", 85), ("현우", 92)]

하지만 이 구조에서 지아를 찾으려면 앞에서부터 이름을 비교해야 한다. 반면 딕셔너리는 이름을 키로 사용하므로 조회가 평균 O(1)이다.

집합과 딕셔너리는 언제 고를까

집합과 딕셔너리는 알고리즘 문제에서 빠른 조회가 필요할 때 자주 함께 떠올리는 자료구조다. 특히 많은 언어에서 기본 집합과 딕셔너리는 해시를 바탕으로 구현되어 평균 O(1)에 가까운 조회를 제공한다. 차이는 저장하려는 정보에 있다.

판단 기준은 간단하다.

• "이 값이 있었나?"가 핵심이면 집합

• "이 키에 연결된 값이 무엇인가?"가 핵심이면 딕셔너리

예를 들어 출석 여부만 확인하면 집합이면 충분하다.

attended = {"민수", "지아", "현우"}

하지만 출석 시간까지 저장해야 한다면 딕셔너리가 필요하다.

attendedTime["민수"] = "09:01"
attendedTime["지아"] = "09:03"

자료구조를 고를 때는 "무엇을 저장해야 하는가"를 먼저 묻는 것이 좋다.

해시 충돌: 서로 다른 값이 같은 위치로 갈 수 있다

해시 테이블은 값을 저장할 위치를 계산한다고 했다. 그런데 서로 다른 두 값이 같은 위치로 계산될 수 있다. 이것을 해시 충돌이라고 한다.

예를 들어 사물함 번호를 정하는 규칙이 "이름 글자 수"라고 해 보자.

민수 → 2번 사물함
지아 → 2번 사물함
현우 → 2번 사물함

모두 이름 길이가 2라서 같은 사물함으로 가게 된다. 이런 규칙은 좋은 해시 함수가 아니다.

실제 해시 테이블은 충돌이 생겼을 때 처리하는 방법을 갖고 있다. 예를 들어 같은 위치에 여러 값을 묶어서 저장하거나, 다른 빈 위치를 찾아 저장한다. 그래서 충돌이 조금 생겨도 정상적으로 동작한다.

다만 충돌이 너무 많이 생기면 한 위치에 값이 몰린다. 그러면 결국 그 안에서 다시 여러 값을 찾아야 하므로 조회 시간이 느려질 수 있다. 최악의 경우에는 O(n)에 가까워질 수 있다.

그래서 해시 연산의 시간 복잡도는 보통 이렇게 말한다.

평균: O(1)
최악: O(n)

실전 알고리즘 문제에서는 특별히 해시 충돌을 직접 다루라고 하지 않는 한, 집합과 딕셔너리의 조회·삽입·삭제를 평균 O(1)로 보고 풀이를 설계하는 경우가 많다.

자주 틀리는 부분

1. 집합은 중복 개수를 기억하지 않는다

집합은 중복을 제거한다. 따라서 값이 몇 번 나왔는지 알아야 하는 문제에 집합만 쓰면 정보가 사라진다.

[1, 1, 1, 2]

집합으로 바꾸면 {1, 2}만 남는다. 1이 세 번 나왔다는 사실은 알 수 없다. 등장 횟수가 필요하면 딕셔너리를 사용해야 한다.

2. 순서가 중요한 문제에 무심코 집합을 쓰면 안 된다

집합은 기본적으로 존재 여부를 위한 자료구조다. 어떤 언어에서는 입력 순서를 유지하는 집합도 있지만, 알고리즘을 설계할 때는 문제에서 순서 보장이 명확하지 않다면 집합의 출력 순서에 의존하지 않는 것이 안전하다.

정렬된 결과가 필요하면 마지막에 정렬을 따로 해야 한다.

unique = set(numbers)
answer = sort(unique)

3. 조회 전에 저장할지, 저장 후에 조회할지 구분해야 한다

두 수의 합 문제처럼 같은 원소를 두 번 쓰면 안 되는 문제에서는 현재 값을 저장하기 전에 필요한 값이 이미 있었는지 확인해야 한다.

반대로 "현재 값까지 포함한 빈도"가 필요하다면 먼저 개수를 증가시킨 뒤 판단해야 할 수도 있다. 순서 하나가 답을 바꿀 수 있으므로 작은 예시로 꼭 확인해야 한다.

4. 평균 O(1)이라도 메모리는 더 쓴다

해시는 빠른 조회를 위해 값을 따로 저장해 둔다. 따라서 보통 O(n)의 추가 공간이 필요하다.

완전 탐색은 느리지만 추가 메모리를 거의 쓰지 않을 수 있다. 해시는 빠르지만 메모리를 더 쓴다. 알고리즘에서는 이런 선택이 자주 나온다.

시간을 줄이기 위해 공간을 더 사용한다.

이 문장은 해시를 이해하는 중요한 기준이다.

정리

해시는 반복문으로 매번 찾던 값을 빠르게 찾기 위한 도구다. 해시 함수로 저장 위치를 계산하고, 그 위치를 이용해 조회·삽입·삭제를 평균 O(1)에 가깝게 처리한다.

집합은 존재 여부와 중복 제거에 강하다. "이 값이 있었나?"라는 질문이 나오면 집합을 떠올릴 수 있다.

딕셔너리는 키와 값을 연결해 저장한다. "이 이름의 점수는?", "이 단어는 몇 번 나왔나?"처럼 어떤 대상에 정보를 붙여야 할 때 사용한다.

해시는 실전 문제에서 완전 탐색을 줄이는 강력한 방법이다. 먼저 배열을 모두 비교하는 풀이를 생각한 뒤, 그중 "찾기"가 반복되는 부분이 보이면 집합이나 딕셔너리로 바꿀 수 있는지 확인해 보자.