🔍 탐색(Search)이란?
- 많은 데이터 중에서 원하는 정보를 찾는 과정
- 탐색 방식에 따라 내부 탐색과 외부 탐색으로 나뉨
- 내부 탐색: 컴퓨터 메모리(RAM)에서 빠르게 검색
- 외부 탐색: 보조 저장 장치(HDD, SSD)에서 검색 → 상대적으로 느림
🔎 탐색의 종류
1️⃣ 기본적인 탐색 방법
선형 탐색 (O(N))
- 처음부터 끝까지 차례로 비교하며 찾기
- 단순하지만 데이터가 많으면 속도가 느림
이분 탐색 (O(logN))
- 데이터를 절반씩 줄여가며 탐색
- 정렬된 데이터에서만 사용 가능 → 훨씬 빠름
보간 탐색
- 찾을 값이 어디에 있을지 예측해서 검색하는 방식
2️⃣ 효율적인 탐색 방법
블록 탐색
- 데이터를 그룹(블록)으로 나눠서 탐색 속도 향상
이진 트리 탐색
- 데이터를 트리 구조로 만들어 탐색
해싱 탐색 (O(1))
- 특정한 해시 함수를 사용해 데이터를 바로 찾아감
- 가장 빠르지만, 충돌이 발생할 수 있음
⏳ 복잡도 (연산량 측정)
1️⃣ 공간 복잡도
- 탐색 과정에서 메모리를 얼마나 차지하는지를 의미
- 일반적으로 시간 복잡도보다 영향이 적음
- 빅데이터 처리 시에는 신경 써야 함
2️⃣ 시간 복잡도
- 탐색 과정에서 연산이 몇 번 수행되는지를 의미
- 실행 환경(하드웨어, 운영체제)에 따라 속도 차이가 있을 수 있음
- 보통 최악의 경우를 기준으로 측정함
- "입력 데이터가 늘어날 때 작업 시간이 얼마나 늘어나는지"를 나타내는 척도
⏱ 빅 O 표기법 (시간 복잡도 비교)
예를 들어, 도서관에서 책을 찾는 상황
|
시간 복잡도
|
쉬운 설명
|
실생활 예시
|
효율성
|
|
O(1)
|
입력 크기와 상관없이 항상 같은 시간
|
도서관에서 책 위치를 정확히 알고 바로 찾기
|
매우 빠름 ⚡️
|
|
O(logN)
|
입력이 2배가 되어도 한 단계만 더 필요
|
두꺼운 사전에서 단어 찾기 (반씩 나눠가며 찾음)
|
빠름 ✨
|
|
O(N)
|
입력이 2배가 되면 시간도 2배
|
책장 한 줄을 처음부터 끝까지 찾기
|
적당함 👍
|
|
O(NlogN)
|
입력이 2배가 되면 시간은 2배보다 조금 더
|
여러 책장의 책들을 알파벳 순으로 정리하기
|
약간 느림 🚶
|
|
O(N²)
|
입력이 2배가 되면 시간은 4배
|
모든 책과 다른 모든 책을 한 번씩 비교하기
|
느림 🐌
|
|
O(2ᴺ)
|
입력이 1개 늘면 시간이 2배
|
도서관의 모든 책으로 만들 수 있는 조합 찾기
|
매우 느림 🐢
|
|
O(N!)
|
입력이 1개 늘면 시간이 폭발적으로 증가
|
도서관 책을 배열하는 모든 가능한 순서 찾기
|
극도로 느림 ⚠️
|
🔍 탐색의 종류
1️⃣ 선형 탐색 (Linear Search)
🔹 가장 기본적인 탐색 방법
🔹 처음부터 끝까지 하나씩 순서대로 확인하는 방식
🔹 예시: 도서관에서 책을 찾을 때 첫 번째 칸부터 하나씩 확인하는 것 📚
✅ 장점: 구현이 매우 쉽고, 정렬되지 않은 데이터에서도 사용 가능
❌ 단점: 데이터가 많으면 매우 느림
🔢 시간 복잡도: O(N)
📌 데이터가 10개면 최대 10번, 100개면 최대 100번 확인해야 함
2️⃣ 이진(=이분) 탐색 (Binary Search)
🔹 정렬된 데이터에서 반씩 줄여가며 탐색 ✂️
🔹 예시: 전화번호부에서 이름 찾기 ☎️
🔹 찾고 싶은 값이 중간보다 크면 오른쪽, 작으면 왼쪽 탐색
✅ 장점: 속도가 매우 빠름
❌ 단점: 반드시 정렬된 상태여야 함
🔢 시간 복잡도: O(logN)
[19, 33, 34, 37, 44, 45, 52, 56, 59, 61, 74, 75, 85, 91, 92] // 85를 찾는 경우
1단계: 중간값 56 확인 → 85가 더 크므로 오른쪽 탐색
2단계: 오른쪽 부분의 중간값 75 확인 → 85가 더 크므로 다시 오른쪽 탐색
3단계: 85 발견! → 탐색 종료3️⃣ 블록 탐색 (Block Search)
🔹 데이터를 일정 크기의 블록으로 나눠서 탐색 📦
🔹 각 블록의 최댓값을 먼저 확인 후, 적절한 블록을 선택하여 선형 탐색 진행
✅ 장점: 선형 탐색보다 빠르고, 이진 탐색보다 구현이 쉬움
❌ 단점: 데이터가 정렬되어 있어야 효율적
🔢 시간 복잡도: O(√N)
전체 데이터 15개 중 60을 찾는 경우
3개의 블록으로 나누어 검색
각 블록의 첫 값: 36, 64, 86
순차적으로 블록을 찾아가며 검색4️⃣ 보간 탐색 (Interpolation Search)
🔹 이진 탐색을 개선한 방식
🔹 찾고자 하는 값이 어디 있을지 예측하여 탐색 🎯
🔹 예시: 전화번호부에서 'ㅎ'으로 시작하는 이름을 찾을 때 맨 뒤쪽을 먼저 확인하는 방식
✅ 장점: 데이터가 균일하게 분포된 경우 이진 탐색보다 더 빠름
❌ 단점: 데이터가 불균일하면 오히려 느려질 수 있음
🔢 시간 복잡도: O(log(logN))
5️⃣ 이진 트리 탐색 (Binary Tree Search) 🌳
🔹 데이터를 트리 구조로 정리하여 탐색
🔹 각 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽에 배치
🔹 예시: 스무고개 게임처럼 질문을 통해 범위를 좁혀가는 방식 🎤
✅ 장점: 데이터 추가/삭제가 잦을 때 유리함
❌ 단점: 트리 구성과 관리가 어려움
🔢 시간 복잡도: O(logN)
6️⃣ 해시 탐색(Hash Search)란?
🔹 데이터를 빠르게 찾기 위한 방법
🔹 특별한 해시 함수(Hash Function)를 사용해 데이터를 저장하고 검색
🔹 도서관에서 책을 찾는 방식과 비슷 📚
🔹 시간 복잡도: O(1) → 매우 빠름 ⚡
주요 구성 요소 🏗
🔹 홈 주소 (Home Address): 데이터가 저장될 위치
🔹 키 (Key): 찾고자 하는 데이터의 고유값
🔹 버킷 (Bucket): 실제 데이터가 저장되는 공간
🔹 슬롯 (Slot): 각 데이터가 저장되는 개별 공간
🔹 해시 테이블 (Hash Table): 전체 저장 공간
👉 도서관에서 책 분류번호(해시값) 를 통해 해당 책이 있는 위치(버킷) 로 바로 이동하는 것과 같음
해시 충돌(Hash Collision)과 해결 방법 🚧
🔹 충돌 (Collision): 서로 다른 키가 같은 주소를 가지는 문제
해결 방법
✅ 체이닝 (Chaining): 같은 주소에 여러 데이터를 연결 리스트로 저장 🔗
✅ 프로빙 (Probing): 충돌이 발생하면 다른 비어있는 공간을 찾아 저장 🔍
👉 체이닝 = 같은 주소에 여러 개의 책을 서로 연결해서 보관 📖
👉 프로빙 = 책이 원래 자리(해시 주소)에 없으면 근처 빈 칸을 찾아 배치 📚
해시 함수(Hash Function)의 종류 🔢
🔹 제산법: 키를 특정 수로 나눈 나머지 값을 주소로 사용
🔹 폴딩법: 키를 여러 부분으로 나눠서 합친 후 주소 결정
🔹 제곱법: 키를 제곱한 후, 중간 부분 값을 주소로 사용
🔹 숫자 분석법: 키의 특정 부분만 사용하여 주소 결정
🔹 기수 변환법: 키의 진법을 변환하여 사용
🔹 무작위법: 난수를 활용하여 주소 결정 🎲
5️⃣ 좋은 해시 함수의 조건 ✅
✅ 충돌을 최소화해야 함
✅ 연산 속도가 빠르고 간단해야 함
✅ 해시 값이 골고루 분포되어야 함