탐색 알고리즘

탐색(Searching) 알고리즘

자료구조 내에서 원하는 데이터를 찾는 방법을 정의

자료의 저장 방식, 정렬 여부, 자료 구조의 종류(배열, 리스트, 트리, 그래프 등)에 따라 다양한 탐색 알고리즘이 사용

----🐢

선형 탐색(Linear Search)

배열이나 리스트의 처음부터 끝까지 순차적으로 원하는 값을 찾는 방법

자료가 정렬되어 있지 않거나 자료의 순서를 고려하지 않아도 되는 경우에 사용

시간 복잡도 O(n); 최악의 경우 모든 요소를 확인

코드 예시

def linear_search(arr, target):
    """
    arr: 검색할 리스트
    target: 찾으려는 값
    반환: target의 인덱스 (없으면 -1)
    """
    for index, value in enumerate(arr):
        if value == target:
            return index
    return -1

# 사용 예시
data = [3, 5, 2, 9, 1, 8]
print("타겟 9의 인덱스:", linear_search(data, 9))  # 출력: 타겟 9의 인덱스: 3
print("타겟 7의 인덱스:", linear_search(data, 7))  # 출력: 타겟 7의 인덱스: -1

---🐢-

이진 탐색(Binary Search)

정렬된 배열에서 사용되는 탐색 알고리즘

배열의 중간 원소와 찾으려는 값을 비교하여,

 만약 중간 원소가 찾는 값보다 크다면 왼쪽 절반에서,

 작다면 오른쪽 절반에서 다시 이진 탐색을 반복하는 방식

분할 정복(Divide and Conquer) 사용

시간 복잡도 O(log n); 매 단계마다 검색 범위를 절반으로

코드 예시

# while문
def binary_search(arr, target):
    """
    arr: 정렬된 리스트
    target: 찾으려는 값
    반환: target의 인덱스 (없으면 -1)
    """
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# 사용 예시
sorted_data = [1, 2, 3, 5, 7, 9, 12]
print("타겟 7의 인덱스:", binary_search(sorted_data, 7))  # 출력: 4
print("타겟 4의 인덱스:", binary_search(sorted_data, 4))  # 출력: -1

# 재귀
def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)

# 사용 예시
print("타겟 7의 인덱스:", binary_search_recursive(sorted_data, 7, 0, len(sorted_data)-1))

--🐢--

그래프/ 트리 탐색

자료구조가 트리나 그래프인 경우, 탐색 알고리즘으로 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)가 많이 사용

 

깊이 우선 탐색(DFS: Depth-First Search)

한 경로를 가능한 깊게 탐색하다가 더 이상 진행할 수 없으면, 이전 분기점으로 돌아와 다른 경로를 탐색하는 방식

재귀 또는 스택을 사용하여 구현

코드 예시

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

# 방향 또는 무방향 그래프 (인접 리스트)
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print("DFS 탐색 결과:")
dfs(graph, 'A')  # 출력 예: A B D E F C (경로는 그래프에 따라 달라짐)

 

너비 우선 탐색(BFS: Breadth-First Search)

시작 정점에서 같은 레벨 정점들을 먼저 방문한 후, 점차 멀리 있는 정점으로 확장하는 방식

큐(Queue)를 사용하여 구현

코드 예시

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

print("\nBFS 탐색 결과:")
bfs(graph, 'A')  # 출력 예: A B C D E F (경로는 그래프에 따라 달라짐)

-🐢---

보간 탐색(Interpolation Search)

정렬된 배열에서 키의 분포를 이용해 탐색 범위를 추정하는 알고리즘

배열의 값이 균등하게 분포되어 있다는 가정 하에, 이진 탐색처럼 중간 인덱스가 아닌,
target과 현재 범위의 값들을 고려하여 대략적인 위치를 추정

 

계산식

코드 예시

def interpolation_search(arr, target):
    low = 0
    high = len(arr) - 1

    # target이 arr[low]와 arr[high] 사이에 있어야 탐색 진행
    while low <= high and target >= arr[low] and target <= arr[high]:
        # 만약 low와 high가 같다면 하나의 원소만 남은 것이므로 직접 비교
        if low == high:
            return low if arr[low] == target else -1

        # target의 위치를 예측하여 pos 계산
        pos = low + int(((target - arr[low]) * (high - low)) / (arr[high] - arr[low]))

        # 해당 위치의 값이 target과 일치하면 반환
        if arr[pos] == target:
            return pos
        # target이 더 크면, 왼쪽 범위를 줄임
        if arr[pos] < target:
            low = pos + 1
        else: # target이 더 작으면, 오른쪽 범위를 줄임
            high = pos - 1

    return -1

# 사용 예시
if __name__ == "__main__":
    sorted_arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
    target = 70
    index = interpolation_search(sorted_arr, target)
    print(f"인터폴레이션 탐색: {target}은(는) 인덱스 {index}에 있음")

 

장단점

장점

데이터가 균등하게 분포되어 있다면, 평균 시간 복잡도가 O(log⁡ log⁡ n)

중간 인덱스를 단순히 (low+high)//2로 계산하는 이진 탐색보다, target의 위치를 보다 정확하게 예측

단점

데이터가 균등하게 분포되어 있지 않거나, 극단적인 값들이 존재하면 성능이 O(n)

🐢----

점프 탐색(Jump Search)

정렬된 배열에서, 일정한 간격(step size) 으로 배열을 "점프"하며 target이 포함될 가능성이 있는 블록(block)을 먼저 찾은 후, 그 블록 안에서 선형 탐색(Linear Search)을 수행하는 방법

일반적으로 최적의 점프 간격 m =​ √n

 

동작 방식

배열을 점프 간격 m만큼 이동하면서, 각 점에서 target과 비교

만약 현재 점의 값이 target보다 크다면, 이전 점부터 현재 점 사이에 target이 있을 수 있으므로 그 구간을 선형 탐색

배열의 끝까지 도달하면 target이 없다고 판단

 

코드 예시

import math

def jump_search(arr, target):
    n = len(arr)
    # 최적 점프 간격: sqrt(n)
    step = int(math.sqrt(n))
    prev = 0

    # target이 포함될 블록을 찾음
    while prev < n and arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1

    # 이전 블록(인덱스 prev부터 min(step, n)-1까지)에서 선형 탐색
    for i in range(prev, min(step, n)):
        if arr[i] == target:
            return i

    return -1

# 사용 예시
if __name__ == "__main__":
    sorted_arr = [3, 5, 8, 12, 16, 23, 38, 56, 72, 91]
    target = 23
    index = jump_search(sorted_arr, target)
    print(f"점프 탐색: {target}은(는) 인덱스 {index}에 있음")

 

장단점

장점

시간 복잡도 O(√n)

이진 탐색처럼 중간 계산이 필요 없음

단점

점프 간격 m의 선택이 중요하며, 최적의 m이 아닐 경우 성능이 떨어짐