[2026] 해시 테이블 | O(1) 탐색 자료구조 완벽 정리

· 20분 읽기 · 수정 중급 튜토리얼
[2026] 해시 테이블 | O(1) 탐색 자료구조 완벽 정리

이 글의 핵심

해시 테이블: O(1) 탐색 자료구조 해시 함수 (Hash Function)·Python dict 사용법.

🎯 이 글을 읽으면 (읽는 시간: 20분)

TL;DR: O(1) 탐색의 비밀, 해시 테이블을 완벽하게 마스터합니다. 배열의 O(n) 검색을 O(1)로 최적화하는 방법과 해시 충돌 해결 전략을 배웁니다. 이 글을 읽으면:

  • ✅ 해시 함수와 해시 테이블 동작 원리 완벽 이해
  • ✅ Python dict, C++ unordered_map 실전 활용
  • ✅ 해시 충돌 해결 전략 (Chaining, Open Addressing) 마스터 실무 활용:
  • 🔥 빠른 데이터 검색 (사용자 조회, 캐싱)
  • 🔥 중복 제거 및 빈도 계산
  • 🔥 Two Sum, Anagram 등 코딩 테스트 난이도: 중급 | 실습 문제: 8개 | Python + C++: 모두 포함

들어가며

해시 테이블이란?

해시 테이블(Hash Table)은 키(Key)-값(Value) 쌍을 저장하는 자료구조로, 평균 O(1)의 시간복잡도(입력이 커질 때 걸리는 시간이 얼마나 늘어나는지)로 검색/삽입/삭제가 가능합니다. 여기서 O(1)은 입력 크기와 거의 무관하게 일정한 시간에 가깝다는 뜻입니다. 다른 이름:

  • Hash Map
  • Dictionary (Python)
  • Associative Array
  • Map (C++, Java) 왜 빠른가? 배열은 인덱스로 O(1) 접근이 가능합니다. 해시 테이블은 해시 함수(키를 고정 길이의 숫자·슬롯 번호로 바꾸는 함수)로 키를 인덱스로 변환하여 배열처럼 빠르게 접근합니다. 아래 코드는 python를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
# 배열: 인덱스로 접근
arr = [10, 20, 30, 40, 50]
print(arr[2])  # 30 (O(1))
# 해시 테이블: 키로 접근
hash_table = {"apple": 100, "banana": 200}
print(hash_table[apple])  # 100 (O(1))
# 내부적으로: hash("apple") % size → 인덱스 → 값

시간 복잡도 비교:

자료구조검색삽입삭제
배열 (정렬 안 됨)O(n)O(1)O(n)
배열 (정렬됨)O(log n)O(n)O(n)
연결 리스트O(n)O(1)O(n)
해시 테이블O(1)O(1)O(1)

코딩 테스트 준비하며 깨달은 것

알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.

1. 해시 함수 (Hash Function)

해시 함수란?

해시 함수는 임의 크기의 데이터를 고정 크기의 값(해시값)으로 변환하는 함수입니다. 좋은 해시 함수의 조건:

  1. ✅ 결정적: 같은 입력 → 같은 출력
  2. ✅ 빠른 계산: O(1)
  3. ✅ 균등 분포: 해시값이 골고루 분산
  4. ✅ 충돌 최소화: 다른 입력 → 다른 출력 (이상적)

간단한 해시 함수 예제

해시 함수는 키를 받아 고정된 크기의 슬롯 번호(배열 인덱스)로 바꿉니다. 우편번호로 구역을 나누듯, “이 키는 몇 번 칸에 넣는다”를 한 번에 정해 주는 역할입니다. 같은 키는 항상 같은 칸으로 가야 하므로(결정적) 검색 시에도 같은 인덱스로 찾아갈 수 있습니다.

# 방법 1: Python 내장 hash() + 나머지 연산
def simple_hash(key, size):
    # hash(key): Python 내장 해시 함수
    #   - 문자열, 숫자, 튜플 등에 대해 정수 해시값 반환
    #   - 같은 값은 항상 같은 해시값 (결정적)
    # % size: 배열 크기로 나눈 나머지 (0 ~ size-1)
    #   - 해시값을 배열 인덱스 범위로 변환
    return hash(key) % size
print(simple_hash("apple", 10))   # 8 (인덱스 8에 저장)
print(simple_hash("banana", 10))  # 3 (인덱스 3에 저장)
print(simple_hash("cherry", 10))  # 6 (인덱스 6에 저장)
# 방법 2: 문자열 해시 (직접 구현)
def string_hash(s, size):
    hash_value = 0
    for char in s:
        # ord(char): 문자의 ASCII/유니코드 값
        # 31: 소수(prime number) 사용 (충돌 감소)
        # 각 문자를 31배씩 누적하여 해시값 계산
        hash_value = (hash_value * 31 + ord(char)) % size
    return hash_value
# 예: "abc"의 해시 계산 과정
# 1. hash_value = 0
# 2. 'a': (0 * 31 + 97) % 10 = 97 % 10 = 7
# 3. 'b': (7 * 31 + 98) % 10 = 315 % 10 = 5
# 4. 'c': (5 * 31 + 99) % 10 = 254 % 10 = 4
# 결과: 4
print(string_hash("apple", 10))  # 특정 값
# Python 내장 hash() 함수
print(hash("apple"))   # -6076896708304529682 (예시)
# 실행마다 다를 수 있음 (Python 3.3+는 보안상 랜덤 시드 사용)
print(hash(42))        # 42 (정수는 자기 자신)
print(hash((1, 2)))    # 3713081631934410656 (튜플 해시)
# ❌ 가변 객체는 해시 불가
# print(hash([1, 2]))  # TypeError: unhashable type: 'list'
# 이유: 리스트는 내용이 변할 수 있어 해시값이 달라질 수 있음
# dict의 키는 불변(immutable) 타입만 가능

해시 함수의 역할: 다음은 python를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 해시 테이블 내부 동작 (개념적)
class SimpleHashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [None] * size  # 배열 생성
    
    def _hash(self, key):
        # 키를 인덱스로 변환
        return hash(key) % self.size
    
    def put(self, key, value):
        index = self._hash(key)  # 해시 함수로 인덱스 계산
        self.table[index] = value  # 배열에 저장
    
    def get(self, key):
        index = self._hash(key)  # 같은 해시 함수로 인덱스 계산
        return self.table[index]  # O(1) 접근
# 사용
ht = SimpleHashTable()
ht.put("apple", 100)   # hash("apple") % 10 = 8 → table[8] = 100
ht.put("banana", 200)  # hash("banana") % 10 = 3 → table[3] = 200
print(ht.get("apple"))  # table[8] 접근 → 100

해시 충돌 (Hash Collision)

충돌은 서로 다른 키가 같은 해시값을 가질 때 발생합니다. 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

# 충돌 예시
def bad_hash(key, size):
    return len(key) % size  # 길이만 사용 (나쁜 해시 함수)
print(bad_hash("apple", 10))   # 5
print(bad_hash("grape", 10))   # 5 (충돌!)
print(bad_hash("peach", 10))   # 5 (충돌!)

2. Python dict 사용법

언어 차원에서 dict·set 문법과 함께 다루려면 Python 자료형 (리스트, 딕셔너리, 튜플, 세트)를 참고하면 좋습니다.

기본 연산

다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 생성
hash_table = {}
hash_table = dict()
# 삽입 O(1)
hash_table[apple] = 100
hash_table[banana] = 200
hash_table[cherry] = 300
# 검색 O(1)
print(hash_table[apple])  # 100
print(hash_table.get("grape", 0))  # 0 (기본값)
# 수정 O(1)
hash_table[apple] = 150
print(hash_table[apple])  # 150
# 삭제 O(1)
del hash_table[apple]
print("apple" in hash_table)  # False
# 존재 확인 O(1)
if "banana" in hash_table:
    print("있음")
# 순회 O(n)
for key in hash_table:
    print(key, hash_table[key])
for key, value in hash_table.items():
    print(f"{key}: {value}")
# 키/값 리스트
keys = list(hash_table.keys())
values = list(hash_table.values())
print(keys)    # ['banana', 'cherry']
print(values)  # [200, 300]

dict 고급 기능

다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# setdefault(): 키가 없을 때만 추가
hash_table = {"a": 1}
hash_table.setdefault("b", 2)  # 추가
hash_table.setdefault("a", 100)  # 이미 있으므로 무시
print(hash_table)  # {'a': 1, 'b': 2}
# update(): 병합
hash_table.update({"c": 3, "d": 4})
print(hash_table)  # {'a': 1, 'b': 2, 'c': 3, 'd': 4}
# pop(): 제거 및 반환
value = hash_table.pop("a")
print(value)  # 1
print(hash_table)  # {'b': 2, 'c': 3, 'd': 4}
# popitem(): 마지막 키-값 제거 (Python 3.7+)
last = hash_table.popitem()
print(last)  # ('d', 4)
# clear(): 전체 삭제
hash_table.clear()
print(hash_table)  # {}

3. 해시 충돌 해결 방법

충돌이란?

서로 다른 키가 같은 해시값(인덱스)을 가질 때 충돌(Collision)이 발생합니다. 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

# 충돌 시뮬레이션
def hash_func(key, size):
    return sum(ord(c) for c in key) % size
# 크기 10인 테이블
size = 10
print(hash_func("abc", size))  # 4
print(hash_func("bca", size))  # 4 (충돌!)
print(hash_func("cab", size))  # 4 (충돌!)

방법 1: Chaining (체이닝)

연결 리스트로 같은 인덱스의 값들을 저장합니다. 시각화: 아래 코드는 code를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

Index 0: []
Index 1: []
Index 2: [("apple", 100), ("grape", 150)]  ← 충돌 발생
Index 3: [("banana", 200)]
Index 4: []
...

구현: 다음은 python를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

class HashTableChaining:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]  # 각 인덱스는 리스트
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        idx = self._hash(key)
        
        # 기존 키가 있으면 업데이트
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        
        # 없으면 추가
        self.table[idx].append((key, value))
    
    def get(self, key):
        idx = self._hash(key)
        
        # 연결 리스트 순회
        for k, v in self.table[idx]:
            if k == key:
                return v
        
        return None
    
    def delete(self, key):
        idx = self._hash(key)
        
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                del self.table[idx][i]
                return True
        
        return False
    
    def __str__(self):
        result = []
        for i, bucket in enumerate(self.table):
            if bucket:
                result.append(f"Index {i}: {bucket}")
        return "\n".join(result) if result else "Empty"
# 테스트
ht = HashTableChaining(size=5)
ht.insert("apple", 100)
ht.insert("banana", 200)
ht.insert("cherry", 300)
ht.insert("grape", 150)  # 충돌 가능
print(ht)
print(f"\napple: {ht.get('apple')}")  # 100
print(f"banana: {ht.get('banana')}")  # 200
ht.delete("apple")
print(f"\napple 삭제 후: {ht.get('apple')}")  # None

Chaining 시간 복잡도:

  • 평균: O(1) (충돌이 적을 때)
  • 최악: O(n) (모든 키가 같은 인덱스에 충돌)

방법 2: Open Addressing (개방 주소법)

충돌 시 다른 빈 공간을 찾습니다.

2-1. Linear Probing (선형 탐사)

충돌 시 다음 인덱스를 순차적으로 탐색합니다. 다음은 python를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

class HashTableLinearProbing:
    def __init__(self, size=10):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        idx = self._hash(key)
        
        # 빈 공간 찾기
        while self.keys[idx] is not None:
            if self.keys[idx] == key:  # 기존 키 업데이트
                self.values[idx] = value
                return
            idx = (idx + 1) % self.size  # 다음 인덱스
        
        self.keys[idx] = key
        self.values[idx] = value
    
    def get(self, key):
        idx = self._hash(key)
        
        # 키 찾기
        while self.keys[idx] is not None:
            if self.keys[idx] == key:
                return self.values[idx]
            idx = (idx + 1) % self.size
        
        return None
    
    def delete(self, key):
        idx = self._hash(key)
        
        while self.keys[idx] is not None:
            if self.keys[idx] == key:
                self.keys[idx] = None
                self.values[idx] = None
                return True
            idx = (idx + 1) % self.size
        
        return False
    
    def __str__(self):
        result = []
        for i in range(self.size):
            if self.keys[i] is not None:
                result.append(f"[{i}] {self.keys[i]}: {self.values[i]}")
        return "\n".join(result) if result else "Empty"
# 테스트
ht = HashTableLinearProbing(size=5)
ht.insert("apple", 100)
ht.insert("banana", 200)
ht.insert("cherry", 300)
print(ht)
print(f"\napple: {ht.get('apple')}")  # 100

Linear Probing 문제점:

  • 클러스터링(Clustering): 연속된 공간이 채워지면 탐색 시간 증가

2-2. Quadratic Probing (이차 탐사)

충돌 시 제곱수만큼 이동합니다 (1, 4, 9, 16, …).

def _probe_quadratic(self, key, i):
    """i번째 충돌 시 이동할 인덱스"""
    return (hash(key) + i * i) % self.size

2-3. Double Hashing (이중 해싱)

두 번째 해시 함수를 사용하여 이동 간격을 결정합니다. 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

def _hash1(self, key):
    return hash(key) % self.size
def _hash2(self, key):
    return 7 - (hash(key) % 7)  # 7은 소수
def _probe_double(self, key, i):
    return (self._hash1(key) + i * self._hash2(key)) % self.size

Chaining vs Open Addressing 비교

특징ChainingOpen Addressing
충돌 해결연결 리스트다른 빈 공간
메모리추가 메모리 (포인터)고정 크기 배열
캐시 효율낮음높음
삭제쉬움복잡 (재배치 필요)
부하율> 1 가능< 1 필수
사용Python dictJava HashMap
부하율(Load Factor) = 저장된 항목 수 / 테이블 크기
  • Chaining: 1.0 이상 가능
  • Open Addressing: 0.7 이하 권장

4. 실전 문제 풀이

문제 1: 두 수의 합 (Two Sum)

문제: 배열에서 합이 target인 두 수의 인덱스를 반환하세요. 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

def two_sum(arr, target):
    """
    합이 target인 두 수의 인덱스
    [2, 7, 11, 15], target=9 → [0, 1]
    
    시간: O(n), 공간: O(n)
    """
    seen = {}  # 값: 인덱스
    
    for i, num in enumerate(arr):
        complement = target - num
        
        if complement in seen:
            return [seen[complement], i]
        
        seen[num] = i
    
    return []
# 테스트
arr = [2, 7, 11, 15]
print(two_sum(arr, 9))  # [0, 1]
print(two_sum(arr, 13))  # [0, 2]
print(two_sum(arr, 100))  # []

동작 과정: 아래 코드는 code를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

arr = [2, 7, 11, 15], target = 9
i=0, num=2:
  complement = 9 - 2 = 7
  7 not in seen
  seen = {2: 0}
i=1, num=7:
  complement = 9 - 7 = 2
  2 in seen! → return [0, 1]

왜 해시 테이블?

  • 브루트포스: O(n²) - 모든 쌍 확인
  • 해시 테이블: O(n) - 한 번만 순회

문제 2: 완주하지 못한 선수 (프로그래머스)

문제: 마라톤에 참가한 선수 중 완주하지 못한 선수 1명을 찾으세요. (동명이인 가능) 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

def solution(participant, completion):
    """
    완주하지 못한 선수 1명 찾기
    시간: O(n), 공간: O(n)
    """
    hash_table = {}
    
    # 참가자 카운트
    for name in participant:
        hash_table[name] = hash_table.get(name, 0) + 1
    
    # 완주자 감소
    for name in completion:
        hash_table[name] -= 1
    
    # 카운트가 1인 사람 찾기
    for name, count in hash_table.items():
        if count == 1:
            return name
# 테스트
participant = ["leo", "kiki", "eden"]
completion = ["eden", "kiki"]
print(solution(participant, completion))  # "leo"
# 동명이인 케이스
participant = ["marina", "josipa", "nikola", "vinko", "marina"]
completion = ["josipa", "nikola", "marina", "marina"]
print(solution(participant, completion))  # "vinko"

동작 과정: 아래 코드는 code를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

participant = ["leo", "kiki", "eden"]
completion = ["eden", "kiki"]
1단계: 참가자 카운트
  hash_table = {"leo": 1, "kiki": 1, "eden": 1}
2단계: 완주자 감소
  "eden" → hash_table = {"leo": 1, "kiki": 1, "eden": 0}
  "kiki" → hash_table = {"leo": 1, "kiki": 0, "eden": 0}
3단계: 카운트 1인 사람
  "leo" → return "leo"

다른 풀이: Counter 사용: 아래 코드는 python를 사용한 구현 예제입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

from collections import Counter
def solution(participant, completion):
    counter = Counter(participant) - Counter(completion)
    return list(counter.keys())[0]
# 테스트
print(solution(["leo", "kiki", "eden"], ["eden", "kiki"]))  # "leo"

문제 3: 베스트앨범 (프로그래머스)

문제: 장르별로 가장 많이 재생된 노래를 2개씩 선택하세요. 조건:

  1. 장르별 총 재생 횟수가 많은 순서대로
  2. 장르 내에서 재생 횟수가 많은 순서대로
  3. 재생 횟수가 같으면 고유 번호가 낮은 순서대로 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
def solution(genres, plays):
    """
    장르별 재생 횟수 많은 노래 2개씩
    시간: O(n log n), 공간: O(n)
    """
    genre_play = {}  # 장르: 총 재생 횟수
    genre_songs = {}  # 장르: [(재생, 인덱스), ...]
    
    # 1단계: 데이터 수집
    for i, (genre, play) in enumerate(zip(genres, plays)):
        genre_play[genre] = genre_play.get(genre, 0) + play
        
        if genre not in genre_songs:
            genre_songs[genre] = []
        genre_songs[genre].append((play, i))
    
    # 2단계: 장르를 총 재생 횟수 내림차순 정렬
    sorted_genres = sorted(genre_play.items(), key=lambda x: x[1], reverse=True)
    
    result = []
    # 3단계: 각 장르에서 상위 2곡 선택
    for genre, _ in sorted_genres:
        # 재생 횟수 내림차순, 인덱스 오름차순
        songs = sorted(genre_songs[genre], key=lambda x: (-x[0], x[1]))
        result.extend([idx for _, idx in songs[:2]])  # 최대 2곡
    
    return result
# 테스트
genres = ["classic", "pop", "classic", "classic", "pop"]
plays = [500, 600, 150, 800, 2500]
print(solution(genres, plays))  # [4, 1, 3, 0]

동작 과정:

genres = ["classic", "pop", "classic", "classic", "pop"]
plays =  [500,       600,   150,       800,       2500]
index =  [0,         1,     2,         3,         4]
1단계: 데이터 수집
  genre_play = {"classic": 1450, "pop": 3100}
  genre_songs = {
    "classic": [(500, 0), (150, 2), (800, 3)],
    "pop": [(600, 1), (2500, 4)]
  }
2단계: 장르 정렬 (총 재생 횟수 내림차순)
  sorted_genres = [("pop", 3100), ("classic", 1450)]
3단계: 각 장르에서 상위 2곡
  pop: [(2500, 4), (600, 1)] → 인덱스 [4, 1]
  classic: [(800, 3), (500, 0), (150, 2)] → 인덱스 [3, 0]
결과: [4, 1, 3, 0]

defaultdict 버전: 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

from collections import defaultdict
def solution(genres, plays):
    genre_play = defaultdict(int)
    genre_songs = defaultdict(list)
    
    for i, (genre, play) in enumerate(zip(genres, plays)):
        genre_play[genre] += play
        genre_songs[genre].append((play, i))
    
    sorted_genres = sorted(genre_play.items(), key=lambda x: x[1], reverse=True)
    
    result = []
    for genre, _ in sorted_genres:
        songs = sorted(genre_songs[genre], key=lambda x: (-x[0], x[1]))
        result.extend([idx for _, idx in songs[:2]])
    
    return result

문제 4: 그룹 애너그램 (Group Anagrams)

문제: 애너그램끼리 그룹화하세요. 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

def group_anagrams(strs):
    """
    애너그램 그룹화
    ["eat", "tea", "tan", "ate", "nat", "bat"]
    → [["eat", "tea", "ate"], ["tan", "nat"], [bat]]
    
    시간: O(n * k log k), 공간: O(n * k)
    n = 문자열 개수, k = 문자열 평균 길이
    """
    anagrams = {}
    
    for word in strs:
        # 정렬된 문자열을 키로 사용
        key = '.join(sorted(word))
        
        if key not in anagrams:
            anagrams[key] = []
        anagrams[key].append(word)
    
    return list(anagrams.values())
# 테스트
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(strs))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

동작 과정:

strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
"eat" → sorted: "aet" → anagrams = {"aet": [eat]}
"tea" → sorted: "aet" → anagrams = {"aet": ["eat", "tea"]}
"tan" → sorted: "ant" → anagrams = {"aet": ["eat", "tea"], "ant": [tan]}
"ate" → sorted: "aet" → anagrams = {"aet": ["eat", "tea", "ate"], "ant": [tan]}
"nat" → sorted: "ant" → anagrams = {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"]}
"bat" → sorted: "abt" → anagrams = {"aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": [bat]}
결과: [["eat", "tea", "ate"], ["tan", "nat"], [bat]]

defaultdict 버전: 아래 코드는 python를 사용한 구현 예제입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

from collections import defaultdict
def group_anagrams(strs):
    anagrams = defaultdict(list)
    
    for word in strs:
        key = '.join(sorted(word))
        anagrams[key].append(word)
    
    return list(anagrams.values())

문제 5: 중복 문자 없는 가장 긴 부분 문자열

문제: 중복 문자가 없는 가장 긴 부분 문자열의 길이를 구하세요. 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

def length_of_longest_substring(s):
    """
    "abcabcbb" → 3 ("abc")
    "bbbbb" → 1 ("b")
    "pwwkew" → 3 ("wke")
    
    시간: O(n), 공간: O(min(n, m)) (m = 문자 종류)
    """
    char_index = {}  # 문자: 마지막 인덱스
    max_length = 0
    start = 0
    
    for i, char in enumerate(s):
        # 중복 문자 발견 시 시작점 이동
        if char in char_index and char_index[char] >= start:
            start = char_index[char] + 1
        
        char_index[char] = i
        max_length = max(max_length, i - start + 1)
    
    return max_length
# 테스트
print(length_of_longest_substring("abcabcbb"))  # 3
print(length_of_longest_substring("bbbbb"))     # 1
print(length_of_longest_substring("pwwkew"))    # 3
print(length_of_longest_substring(""))          # 0

동작 과정:

s = "abcabcbb"
i=0, char='a': char_index={'a': 0}, start=0, max_length=1
i=1, char='b': char_index={'a': 0, 'b': 1}, start=0, max_length=2
i=2, char='c': char_index={'a': 0, 'b': 1, 'c': 2}, start=0, max_length=3
i=3, char='a': 중복! start=1, char_index={'a': 3, 'b': 1, 'c': 2}, max_length=3
i=4, char='b': 중복! start=2, char_index={'a': 3, 'b': 4, 'c': 2}, max_length=3
i=5, char='c': 중복! start=3, char_index={'a': 3, 'b': 4, 'c': 5}, max_length=3
i=6, char='b': 중복! start=5, char_index={'a': 3, 'b': 6, 'c': 5}, max_length=3
i=7, char='b': 중복! start=7, char_index={'a': 3, 'b': 7, 'c': 5}, max_length=3
결과: 3

5. Python collections 모듈

Counter 상세

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

from collections import Counter
# 생성
counter = Counter([1, 2, 2, 3, 3, 3])
print(counter)  # Counter({3: 3, 2: 2, 1: 1})
# 문자열 카운트
text = "hello world"
counter = Counter(text)
print(counter)  # Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})
# most_common(): 가장 빈번한 요소
print(counter.most_common(3))  # [('l', 3), ('o', 2), ('h', 1)]
# 연산
c1 = Counter(['a', 'b', 'c', 'a'])
c2 = Counter(['a', 'b', 'b'])
print(c1 + c2)  # Counter({'a': 3, 'b': 3, 'c': 1})
print(c1 - c2)  # Counter({'a': 1, 'c': 1})
print(c1 & c2)  # Counter({'a': 1, 'b': 1}) (교집합, 최소값)
print(c1 | c2)  # Counter({'a': 2, 'b': 2, 'c': 1}) (합집합, 최대값)
# elements(): 요소 반복
c = Counter(a=3, b=1)
print(list(c.elements()))  # ['a', 'a', 'a', 'b']

defaultdict 상세

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

from collections import defaultdict
# int 기본값 (0)
word_count = defaultdict(int)
for word in ["apple", "banana", "apple"]:
    word_count[word] += 1
print(dict(word_count))  # {'apple': 2, 'banana': 1}
# list 기본값 ([])
groups = defaultdict(list)
for name, grade in [("Alice", "A"), ("Bob", "B"), ("Charlie", "A")]:
    groups[grade].append(name)
print(dict(groups))  # {'A': ['Alice', 'Charlie'], 'B': ['Bob']}
# set 기본값 (set())
tags = defaultdict(set)
tags[python].add("programming")
tags[python].add("tutorial")
print(dict(tags))  # {'python': {'programming', 'tutorial'}}
# lambda 기본값
counter = defaultdict(lambda: 0)
counter[a] += 1
print(dict(counter))  # {'a': 1}

OrderedDict (순서 유지)

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

from collections import OrderedDict
# Python 3.7+ 이전에는 dict가 순서를 보장하지 않았음
# 현재는 dict도 순서 유지, OrderedDict는 추가 기능 제공
od = OrderedDict()
od[a] = 1
od[b] = 2
od[c] = 3
# move_to_end(): 요소를 끝으로 이동
od.move_to_end("a")
print(list(od.keys()))  # ['b', 'c', 'a']
# popitem(last=True): 마지막 요소 제거
od.popitem(last=True)
print(list(od.keys()))  # ['b', 'c']
# popitem(last=False): 첫 요소 제거
od.popitem(last=False)
print(list(od.keys()))  # ['c']

LRU Cache 구현 (OrderedDict 활용)

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity
    
    def get(self, key):
        if key not in self.cache:
            return -1
        
        # 최근 사용으로 이동
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        
        self.cache[key] = value
        
        # 용량 초과 시 가장 오래된 항목 제거
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)
    
    def __str__(self):
        return str(dict(self.cache))
# 테스트
cache = LRUCache(3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)
print(cache)  # {'a': 1, 'b': 2, 'c': 3}
cache.get("a")  # 'a' 사용
cache.put("d", 4)  # 용량 초과, 'b' 제거
print(cache)  # {'c': 3, 'a': 1, 'd': 4}

6. 해시 테이블 실전 활용 패턴

패턴 1: 빈도수 세기

아래 코드는 python를 사용한 구현 예제입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 문자 빈도
def char_frequency(s):
    freq = {}
    for char in s:
        freq[char] = freq.get(char, 0) + 1
    return freq
print(char_frequency("hello"))  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}
# Counter 사용
from collections import Counter
print(dict(Counter("hello")))  # {'h': 1, 'e': 1, 'l': 2, 'o': 1}

패턴 2: 그룹화

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 길이별 그룹화
words = ["apple", "pie", "banana", "cat", "dog", "cherry"]
groups = {}
for word in words:
    length = len(word)
    if length not in groups:
        groups[length] = []
    groups[length].append(word)
print(groups)
# {5: ['apple'], 3: ['pie', 'cat', 'dog'], 6: ['banana', 'cherry']}
# defaultdict 사용
from collections import defaultdict
groups = defaultdict(list)
for word in words:
    groups[len(word)].append(word)
print(dict(groups))

패턴 3: 캐싱 (Memoization)

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 피보나치 (캐싱 없음) - 느림
def fib_slow(n):
    if n <= 1:
        return n
    return fib_slow(n-1) + fib_slow(n-2)
# 피보나치 (캐싱) - 빠름
def fib_fast(n, cache={}):
    if n in cache:
        return cache[n]
    
    if n <= 1:
        return n
    
    cache[n] = fib_fast(n-1, cache) + fib_fast(n-2, cache)
    return cache[n]
# 테스트
print(fib_fast(30))  # 832040 (빠름)
# print(fib_slow(30))  # 832040 (매우 느림)
# functools.lru_cache 사용 (권장)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
print(fib(30))  # 832040 (매우 빠름)

패턴 4: 인덱스 매핑

아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 배열 요소의 인덱스 저장
def find_indices(arr, target):
    """target 값의 모든 인덱스 찾기"""
    index_map = {}
    
    for i, num in enumerate(arr):
        if num not in index_map:
            index_map[num] = []
        index_map[num].append(i)
    
    return index_map.get(target, [])
arr = [1, 2, 3, 2, 4, 2, 5]
print(find_indices(arr, 2))  # [1, 3, 5]

패턴 5: 집합 연산

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 두 배열의 교집합
def intersection(arr1, arr2):
    """
    [1, 2, 2, 1], [2, 2] → [2, 2]
    시간: O(n + m), 공간: O(min(n, m))
    """
    count1 = Counter(arr1)
    result = []
    
    for num in arr2:
        if count1[num] > 0:
            result.append(num)
            count1[num] -= 1
    
    return result
print(intersection([1, 2, 2, 1], [2, 2]))  # [2, 2]
# Counter 사용
from collections import Counter
def intersection(arr1, arr2):
    c1 = Counter(arr1)
    c2 = Counter(arr2)
    common = c1 & c2  # 교집합
    
    result = []
    for num, count in common.items():
        result.extend([num] * count)
    return result

7. 해시 테이블 성능 최적화

부하율 (Load Factor) 관리

다음은 python를 활용한 상세한 구현 코드입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

class DynamicHashTable:
    def __init__(self, initial_size=8):
        self.size = initial_size
        self.count = 0
        self.table = [[] for _ in range(self.size)]
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def _load_factor(self):
        return self.count / self.size
    
    def _resize(self):
        """부하율이 0.7 초과 시 크기 2배 증가"""
        old_table = self.table
        self.size *= 2
        self.table = [[] for _ in range(self.size)]
        self.count = 0
        
        # 모든 항목 재삽입
        for bucket in old_table:
            for key, value in bucket:
                self.insert(key, value)
    
    def insert(self, key, value):
        # 부하율 체크
        if self._load_factor() > 0.7:
            self._resize()
        
        idx = self._hash(key)
        
        for i, (k, v) in enumerate(self.table[idx]):
            if k == key:
                self.table[idx][i] = (key, value)
                return
        
        self.table[idx].append((key, value))
        self.count += 1
    
    def get(self, key):
        idx = self._hash(key)
        for k, v in self.table[idx]:
            if k == key:
                return v
        return None
# 테스트
ht = DynamicHashTable(initial_size=4)
for i in range(10):
    ht.insert(f"key{i}", i)
    print(f"삽입 후 크기: {ht.size}, 부하율: {ht._load_factor():.2f}")

해시 함수 선택

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 좋은 해시 함수 예제
def good_hash(s, size):
    """문자열 해시 (균등 분포)"""
    hash_value = 0
    prime = 31  # 소수 사용
    
    for char in s:
        hash_value = (hash_value * prime + ord(char)) % size
    
    return hash_value
# 나쁜 해시 함수 예제
def bad_hash(s, size):
    """길이만 사용 (충돌 많음)"""
    return len(s) % size
# 비교
words = ["apple", "grape", "peach", "melon", "berry"]
size = 10
print("좋은 해시 함수:")
for word in words:
    print(f"{word}: {good_hash(word, size)}")
print("\n나쁜 해시 함수:")
for word in words:
    print(f"{word}: {bad_hash(word, size)}")

8. 자주 하는 실수와 해결법

실수 1: 가변 객체를 키로 사용

아래 코드는 python를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

# ❌ 잘못된 방법
# hash_table = {[1, 2]: "value"}  # TypeError: unhashable type: 'list'
# ✅ 올바른 방법
hash_table = {(1, 2): "value"}  # 튜플 사용
print(hash_table[(1, 2)])  # value

실수 2: KeyError 처리 누락

아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ❌ 잘못된 방법
hash_table = {"a": 1}
# print(hash_table[b])  # KeyError: 'b'
# ✅ 올바른 방법 1: get() 사용
value = hash_table.get("b", 0)
print(value)  # 0
# ✅ 올바른 방법 2: in 체크
if "b" in hash_table:
    print(hash_table[b])
else:
    print("키가 없습니다")

실수 3: 순회 중 수정

다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ❌ 잘못된 방법
hash_table = {"a": 1, "b": 2, "c": 3}
# for key in hash_table:
#     if hash_table[key] == 2:
#         del hash_table[key]  # RuntimeError: dictionary changed size during iteration
# ✅ 올바른 방법 1: 리스트로 변환
hash_table = {"a": 1, "b": 2, "c": 3}
for key in list(hash_table.keys()):
    if hash_table[key] == 2:
        del hash_table[key]
print(hash_table)  # {'a': 1, 'c': 3}
# ✅ 올바른 방법 2: 딕셔너리 컴프리헨션
hash_table = {"a": 1, "b": 2, "c": 3}
hash_table = {k: v for k, v in hash_table.items() if v != 2}
print(hash_table)  # {'a': 1, 'c': 3}

9. 실전 팁

코딩 테스트 해시 테이블 사용 시점

아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# ✅ 해시 테이블 사용
# - 빠른 검색 (O(1))
# - 빈도수 세기
# - 중복 확인
# - 그룹화
# - 캐싱
# ❌ 해시 테이블 부적합
# - 순서가 중요 (정렬된 순서) → 이진 탐색 트리
# - 범위 검색 (k1 ≤ key ≤ k2) → 이진 탐색 트리
# - 최소/최대값 빠른 접근 → 힙(Heap)

시간 복잡도 개선 패턴

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# Before: O(n²) - 중첩 루프
def has_duplicate_slow(arr):
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False
# After: O(n) - 해시 테이블
def has_duplicate_fast(arr):
    seen = set()
    for num in arr:
        if num in seen:
            return True
        seen.add(num)
    return False
# 또는 더 간단하게
def has_duplicate(arr):
    return len(arr) != len(set(arr))

정리

핵심 요약

  1. 해시 테이블: 키-값 저장, 평균 O(1) 검색/삽입/삭제
  2. 해시 함수: 키를 인덱스로 변환, 균등 분포 중요
  3. 충돌 해결:
    • Chaining: 연결 리스트로 저장
    • Open Addressing: 다른 빈 공간 찾기 (Linear/Quadratic/Double Hashing)
  4. Python 도구:
    • dict: 기본 해시 테이블
    • Counter: 빈도수 세기
    • defaultdict: 기본값 자동 생성
    • OrderedDict: 순서 유지 + 추가 기능

언제 사용하나?

상황자료구조시간 복잡도
빠른 검색해시 테이블O(1)
빈도수 세기CounterO(n)
중복 확인setO(n)
그룹화defaultdictO(n)
캐싱dict / LRU CacheO(1)

추천 문제

백준:

다음 단계

관련 글

... 996 lines not shown ... Token usage: 63706/1000000; 936294 remaining Start-Sleep -Seconds 3