ALGORITHMS · CHAPTER 03
중급 · 48분트리와 해시
빠른 탐색을 만드는 두 전략
정렬 기반 탐색과 해싱 기반 탐색의 차이를 비교한다.
CONCEPTS
개념을 문장으로 설명하기
이진 탐색 트리
각 노드의 왼쪽에는 더 작은 값, 오른쪽에는 더 큰 값을 두는 트리입니다.
예시
균형이 잡히면 탐색 경로가 높이만큼이라 O(log n)을 기대합니다.
CHECK한쪽으로 치우치면 O(n)이 될 수 있다.
해시 함수
키를 배열의 위치로 바꾸는 함수입니다.
예시
학번을 해시해 버킷에 넣으면 평균적으로 빠르게 찾을 수 있습니다.
CHECK서로 다른 키가 같은 버킷을 가리킬 수 있다.
충돌 처리
같은 해시 값이 나왔을 때도 모든 키를 저장·검색하도록 하는 방법입니다.
예시
체이닝은 한 버킷에 리스트를 두고, 개방 주소법은 다른 빈 칸을 찾습니다.
CHECK해시의 O(1)은 평균적 기대값이다.
GUIDED PRACTICE
전화번호부 선택
10만 명의 학번으로 학생을 빠르게 찾으려 합니다.
- 순서 없이 배열을 훑으면 최악 O(n)입니다.
- 정렬된 데이터라면 이진 탐색으로 O(log n)입니다.
- 키-값 조회가 중심이고 좋은 해시 함수가 있다면 해시 테이블의 평균 O(1)을 기대합니다.
결론
범위 조회·정렬 순서가 필요하면 트리, 단일 키 조회가 많으면 해시를 우선 검토합니다.
ACTIVE RECALL · 4 STEPS
가리고, 말하고, 확인하기
읽기만 하지 말고 답을 떠올린 뒤 펼쳐 보세요.
01 · 정의 회상
“이진 탐색 트리”을(를) 보지 않고 한 문장으로 정의해 보세요.
02 · 비교 설명
“해시 함수”이(가) 필요한 상황을 예시와 함께 설명해 보세요.
03 · 핵심 점검
해시의 O(1)은 평균적 기대값이다.
04 · 풀이 재현
“전화번호부 선택”의 결론을 보기 전에 풀이 순서를 3단계로 다시 적어 보세요.
WORKBOOK · STEP BY STEP
개념 확인 문제
정답을 고르고 해설로 사고 과정을 확인하세요.
01
균형 잡힌 이진 탐색 트리의 탐색 시간은 보통?
02
해시 충돌이란?
03
정렬 순서대로 범위 조회가 중요한 경우 더 자연스러운 선택은?
SPEAK IT OUT
면접 1분 답변 연습
해시 테이블이 평균 O(1)인데도 항상 최고의 선택이 아닌 이유를 설명해 보세요.
답변할 때는 정의 → 이유 → 짧은 예시 순서로 말해 보세요.공식·표준 자료로 더 읽기
Java SE · HashMap원문 열기 ↗표준 해시 맵의 동작과 주의점을 읽어 볼 수 있습니다.