[kakao x goorm] 선형 탐색(Linear Search), 이진 탐색(Binary Search) 과 해시법(Hashing)

오늘은 자료를 효율적으로 탐색하는  가지 알고리즘인 선형 탐색(Linear Search) , 이진 탐색(Binary Search) 그리고 해시법(Hashing) 에 대해 학습했다.
두 방식은 모두 탐색 속도를 획기적으로 줄여주는 핵심적인 도구이며, 정렬 상태나 저장 방식에 따라 적용 방식이 다르다는 점이 흥미로웠다.

선형 탐색 (Linear Search)

개념 정리

선형 탐색은 가장 단순한 탐색 알고리즘으로, 배열의 처음부터 끝까지 차례로 값을 비교하며 원하는 값을 찾는다.
정렬 여부와 관계없이 사용할 수 있다는 점에서 범용적으로 활용된다.

• 전제 조건: 정렬되지 않아도 됨
• 동작 방식: 배열의 첫 번째 원소부터 마지막 원소까지 순서대로 비교
• 시간 복잡도:
  • 평균 및 최악의 경우: O(n)
  • 최선의 경우(첫 번째 값이 정답일 때): O(1)

Python 코드 예시

from typing import Any, Sequence

def linear_search(arr: Sequence, target: Any) -> int:
    for index, value in enumerate(arr):
        if value == target:
            return index
    return -1

이진 탐색 (Binary Search)

개념 정리

이진 탐색은 정렬된 배열에서 중간값을 기준으로 탐색 범위를 반씩 좁혀가며 탐색하는 알고리즘이다.

• 전제 조건: 배열이 오름차순 등으로 정렬되어 있어야 한다.
• 동작 방식:
  1. 중간 인덱스의 값과 찾는 값을 비교
  2. 찾는 값이 더 크면 오른쪽 반쪽만 탐색
  3. 찾는 값이 더 작으면 왼쪽 반쪽만 탐색
  4. 값을 찾거나 범위가 사라질 때까지 반복
• 시간 복잡도:
  O(log n) — 탐색 대상이 절반씩 줄어들기 때문에 매우 빠르다.

Python 코드 예시

from typing import Any, Sequence

def bin_search(a: Sequence, key: Any) -> int:
    pl = 0
    pr = len(a) - 1

    while True:
        pc = (pl + pr) // 2
        if a[pc] == key:
            return pc  # 탐색 성공
        elif a[pc] < key:
            pl = pc + 1  # 오른쪽 절반 탐색
        else:
            pr = pc - 1  # 왼쪽 절반 탐색
        if pl > pr:
            break
    return -1  # 탐색 실패

 

해시법 (Hashing)

개념 정리

해시법은 키 값을 해시 함수로 특정 인덱스로 변환해 저장하고 탐색하는 방법이다.
이진 탐색과는 다르게 정렬이 필요 없고, 평균적으로 매우 빠른 성능을 자랑한다.

• 핵심 요소:
  • 해시 함수: key를 배열 인덱스로 바꾸는 함수
  • 해시 테이블: 해시 값을 인덱스로 사용하는 배열
  • 충돌 처리: 동일 인덱스에 여러 데이터가 맵핑될 경우 처리 방식

체인법 (Chaining)

충돌이 발생했을 때 같은 인덱스의 값을 연결 리스트로 관리하는 이며, 오프 해시법 (open hashing) 이라고도 부른다.

배열의 각 버킷 (해시 테이블)에 저장하는 것은 인덱스를 해시값으로 연결하는 연결리스트의 앞쪽 노트 (head node)를 참조한다.

주요 연산 함수 예시

1. 탐색 함수 (get)

 def get(self, key: str) -> int | None:
        # 탐색한 뒤 key가 존재하면 value를 반환
        for k, v in self.table[self.hash(key)]:
            if k == key:
                return v
        # key가 존재하지 않으면 None을 반환
        return -1

2. 추가 함수 (put)

def put(self, key: str, value: int) -> None:
        # 탐색한 뒤 key가 존재하면 value를 업데이트
        for i, (k, v) in enumerate(self.table[self.hash(key)]):
            if k == key:
                self.table[self.hash(key)][i] = (key, value)
                return
        # key가 존재하지 않으면 새로운 엔트리를 추가
        self.table[self.hash(key)].append((key, value))

3. 삭제 함수 (remove)

 def remove(self, key: str) -> None:
        # 탐색한 뒤 key가 존재하면 삭제
        for i, (k, v) in enumerate(self.table[self.hash(key)]):
            if k == key:
                del self.table[self.hash(key)][i]
                return
        # key가 존재하지 않으면 -1 반환
        return -1

 

복잡도 비교

알고리즘 시간 복잡도 조건

알고리즘	시간 복잡도	조건
선형 탐색	O(n)	정렬 불필요
이진 탐색	O(log n)	배열 정렬 필수
해시법	평균 O(1), 최악 O(n)	해시 함수 품질 및 충돌 처리 방식에 따라 다름

데일리 미션

이번 포스팅부터는 매일 과제로 나왔던 문제도 포함시킬 예정이다.

문제 1. 선형 탐색 구현

설명
주어진 정수 배열에서 특정 값을 선형 탐색 방식으로 찾는 함수를 작성하시오.

• 입력: 정수 배열 arr, 정수 target
• 출력: target이 존재하면 인덱스, 존재하지 않으면 -1

def linear_search(arr: list[int], target: int) -> int:
    for index, value in enumerate(arr):
        if value == target:
            return index
    return -1

target = int(input("찾고자 하는 숫자를 입력하세요: "))
arr = list(map(int, input("정수 리스트를 입력하세요: ").split()))

print("입력된 리스트:", arr)
print("찾고자 하는 숫자:", target)

result = linear_search(arr, target)
if result != -1:
    print(f"숫자 {target}은(는) 인덱스 {result}에 있습니다.")
else:
    print(f"숫자 {target}은(는) 리스트에 없습니다.")

 

문제 2. 이진 탐색 구현

설명
정렬된 배열에서 이진 탐색을 구현하시오.

• 입력: 오름차순 정렬된 정수 배열 arr, 정수 target
• 출력: target의 인덱스, 없으면 -1

def binary_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


target = int(input("찾고자 하는 숫자를 입력하세요: "))
arr2 = list(map(int, input("정수 리스트를 입력하세요: ").split()))

arr2.sort()  # 이진 탐색은 정렬이 필요

print("입력된 리스트:", arr2)
print("찾고자 하는 숫자:", target)

result = binary_search(arr2, target)
if result != -1:
    print(f"숫자 {target}은(는) 인덱스 {result}에 있습니다.")
else:
    print(f"숫자 {target}은(는) 리스트에 없습니다.")

 

문제 3. 체이닝 해시맵 구현 (기초 버전)

설명
해시 충돌을 체이닝 방식으로 처리하는 해시맵을 구현하시오.

• 기능: put, get, remove

class ChainedHashMap:
    def __init__(self, size: int = 10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def hash(self, key: str) -> int:
        # 문자열 key를 정수 인덱스로 변환하는 간단한 해시 함수
        return sum(ord(c) for c in key) % self.size

    def put(self, key: str, value: int) -> None:
        # 탐색한 뒤 key가 존재하면 value를 업데이트
        for i, (k, v) in enumerate(self.table[self.hash(key)]):
            if k == key:
                self.table[self.hash(key)][i] = (key, value)
                return
        # key가 존재하지 않으면 새로운 엔트리를 추가
        self.table[self.hash(key)].append((key, value))

    def get(self, key: str) -> int | None:
        # 탐색한 뒤 key가 존재하면 value를 반환
        for k, v in self.table[self.hash(key)]:
            if k == key:
                return v
        # key가 존재하지 않으면 None을 반환
        return -1
    
    def remove(self, key: str) -> None:
        # 탐색한 뒤 key가 존재하면 삭제
        for i, (k, v) in enumerate(self.table[self.hash(key)]):
            if k == key:
                del self.table[self.hash(key)][i]
                return
        # key가 존재하지 않으면 -1 반환
        return -1



hashmap = ChainedHashMap(size=10)

print("Chained HashMap")
print("---------------")
print("1. 추가")
print("2. 조회")
print("3. 삭제")
print("4. 종료")
print("---------------")

while True:
    choice = int(input("원하는 작업을 선택하세요: "))

    if choice == 1:
        print("추가")
        key = input("키를 입력하세요: ")
        value = int(input("값을 입력하세요: "))
        hashmap.put(key, value)
        print(f"{key} : {value} 추가 완료")

    elif choice == 2:
        print("조회")
        key = input("조회할 키를 입력하세요: ")
        value = hashmap.get(key)
        if value != -1:
            print(f"{key} : {value}")
        else:
            print(f"{key}는(은) 존재하지 않습니다.")

    elif choice == 3:
        print("삭제")
        key = input("삭제할 키를 입력하세요: ")
        value = hashmap.remove(key)
        if value != -1:
            print(f"{key} 삭제 완료")
        else:
            print(f"{key}는(은) 존재하지 않습니다.")

    elif choice == 4:
        print("종료.")
        break

    else:
        print("잘못된 선택.")

 

문제 4. 해시 충돌 시나리오 실습

설명
같은 해시값이 나오도록 size=1인 해시맵을 생성하고 충돌 상황을 관찰하시오.

# hash collision, set hash size 1

class ChainedHashMap:
    def __init__(self, size: int = 10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def hash(self, key: str) -> int:
        return sum(ord(c) for c in key) % self.size

    def put(self, key: str, value: int) -> None:
        # 탐색한 뒤 key가 존재하면 value를 업데이트
        for i, (k, v) in enumerate(self.table[self.hash(key)]):
            if k == key:
                self.table[self.hash(key)][i] = (key, value)
                return
        # key가 존재하지 않으면 새로운 엔트리를 추가
        self.table[self.hash(key)].append((key, value))

    def get(self, key: str) -> int | None:
        # 탐색한 뒤 key가 존재하면 value를 반환
        for k, v in self.table[self.hash(key)]:
            if k == key:
                return v
        # key가 존재하지 않으면 None을 반환
        return -1
    
    def remove(self, key: str) -> None:
        # 탐색한 뒤 key가 존재하면 삭제
        for i, (k, v) in enumerate(self.table[self.hash(key)]):
            if k == key:
                del self.table[self.hash(key)][i]
                return
        # key가 존재하지 않으면 -1 반환
        return -1
    

hashmap = ChainedHashMap(size=1)

print("Chained HashMap")
print("---------------")
print("1. 추가")
print("2. 조회")
print("3. 삭제")
print("4. 종료")
print("5. 전체 조회")
print("---------------")

while True:
    choice = int(input("원하는 작업을 선택하세요: "))

    if choice == 1:
        print("추가")
        key = input("키를 입력하세요: ")
        value = int(input("값을 입력하세요: "))
        hashmap.put(key, value)
        print(f"{key} : {value} 추가 완료")

    elif choice == 2:
        print("조회")
        key = input("조회할 키를 입력하세요: ")
        value = hashmap.get(key)
        if value != -1:
            print(f"{key} : {value}")
        else:
            print(f"{key}는(은) 존재하지 않습니다.")

    elif choice == 3:
        print("삭제")
        key = input("삭제할 키를 입력하세요: ")
        value = hashmap.remove(key)
        if value != -1:
            print(f"{key} 삭제 완료")
        else:
            print(f"{key}는(은) 존재하지 않습니다.")

    elif choice == 4:
        print("종료.")
        break

    # 전체 조회
    elif choice == 5:
        print("전체 조회")
        for i, bucket in enumerate(hashmap.table):
            print(f"버킷 {i}: {bucket}")
    else:
        print("잘못된 선택.")

 

문제 5. 탐색 알고리즘 비교 실험

설명
랜덤 숫자 배열을 만들고 선형 탐색과 이진 탐색의 수행 시간을 비교하시오.

import time
import random

def linear_search(arr: list[int], target: int) -> int:
    for index, value in enumerate(arr):
        if value == target:
            return index
    return -1

def binary_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1


random_list = list(range(100000000))  # 1,000,000개의 정수로 이루어진 리스트
target = random.choice(random_list)  # 리스트에서 무작위로 숫자 선택

print("무작위 리스트:", random_list[:10], "...")  # 처음 10개만 출력
print("찾고자 하는 숫자:", target)

# 선형 탐색
start_time = time.time()
result = linear_search(random_list, target)
end_time = time.time()
print(f"선형 탐색의 인덱스 위치: {result}")
print(f"선형 탐색 시간: {end_time - start_time:.6f}초")

# 이진 탐색

start_time = time.time()
result = binary_search(random_list, target)
end_time = time.time()
print(f"이진 탐색의 인덱스 위치: {result}")
print(f"이진 탐색 시간: {end_time - start_time:.6f}초")

 

문제 6. 체인드 해시의 시간복잡도 분석

설명
각 연산에 대한 평균 및 최악의 경우 시간 복잡도를 분석하시오.

# 평균 시간복잡도:
# put: O(1), get: O(1), remove: O(1)

# 최악 시간복잡도:
# put: O(n), get: O(n), remove: O(n)
# (n은 버킷 충돌로 인해 하나의 리스트에 저장된 원소 수)

 

보너스 과제

1. 해시맵에 학생 이름과 점수를 저장하고 이름으로 탐색 및 삭제 기능을 구현하시오.

hashmap = ChainedHashMap()
hashmap.put("홍길동", 95)
hashmap.put("김철수", 88)
print(hashmap.get("홍길동"))  # 95
hashmap.remove("홍길동")
print(hashmap.get("홍길동"))  # -1

2. 정렬되지 않은 배열에서 이진 탐색을 사용할 경우 어떤 문제가 발생하는지 설명하시오.

정답
정렬되지 않은 배열에서는 이진 탐색이 제대로 동작하지 않는다.
이진 탐색은 배열의 중간값을 기준으로 탐색 방향을 결정하는데, 정렬되지 않은 배열에서는 이 기준이 무의미해지기 때문이다. 따라서 오답이 반환되거나 무한 루프에 빠질 수 있다.

오늘의 회고

선형 탐색, 이진 탐색과 해시법은 각각의 상황에 맞게 사용할 수 있는 강력한 탐색 알고리즘이다.
특히 해시법은 충돌을 어떻게 처리하느냐에 따라 성능 차이가 큰데, 체인법을 통해 이를 효율적으로 관리할 수 있었다.
직접 구현하며 해시 함수, 연결 리스트 구조, 충돌 처리의 중요성을 체감할 수 있었고, 단순한 개념을 넘어 구조적 사고를 기를 수 있었다.