탐색 알고리즘 (Search Algorithm)

탐색 알고리즘이란?

탐색 알고리즘의 의미

탐색 또는 검색이란 주어진 데이터 집합에서 원하는 데이터를 찾는 과정을 말한다. 탐색은 데이터베이스 검색, 네트워크 경로 탐색, 정보 검색 등 다양한 분야에서 필수적으로 활용된다. 탐색 알고리즘이란 이러한 탐색 작업을 효율적으로 수행할 수 있도록 설계된 알고리즘이다. 탐색 알고리즘은 매커니즘에 따라 선형(Linear), 이진(Binary), 해싱(Hashing)으로 구분된다.

탐색 알고리즘의 중요성

• 데이터 처리 효율성 극대화 : 무작위로 데이터를 찾는 선형 탐색보다 정렬된 데이터를 반씩 쪼개어 찾는 이진 탐색이 훨씬 빠르다. 데이터양이 증가할수록 탐색 속도의 차이가 시스템 전체 성능을 좌우한다.
• 복잡한 문제 해결의 근간 : 인공지능, 내비게이션 최적 경로 탐색, 로봇 자율주행 등은 초기 상태에서 목표 상태로 도달하는 최적의 경로를 찾는 탐색 과정을 거친다.
• 다양한 분야로의 응용 : 체스나 바둑과 같은 게임 AI부터 웹 검색 엔진 크롤링까지, 논리적인 문제 해결 과정을 컴퓨터가 수행할 수 있도록 돕는 범용적인 기반 기술이다.

선형 탐색 (Linear Search)

선형 탐색의 동작 원리

가장 단순하고 직관적인 방법으로, 데이터의 첫 번째 요소부터 마지막 요소까지 순서대로 하나씩 원하는 값과 비교하며 찾는 방식이다.

선형 탐색의 장단점

장점

• 데이터가 정렬되어 있지 않아도 사용할 수 있다.
• 알고리즘이 매우 단순하여 구현하기 쉽다.

단점

• 데이터의 양이 많아질수록 탐색 시간이 정비례하게 늘어난다. 시간 복잡도 O(n)
• 최악의 경우 모든 데이터를 다 확인해야 하므로 비효율적이다.

선형 탐색을 사용하는 상황

• 데이터의 양이 적을 때
• 데이터가 정렬되어 있지 않고, 정렬하는 비용이 더 클 때

선형 탐색의 코드 구현

def linear_search(list, target):
    for i in range(len(list)):
        if list[i] == target:
            return i
    return -1

이진 탐색

이진 탐색의 동작 원리

데이터의 중간값(Mid)을 선택한 뒤, 찾고자 하는 값과 비교한다. 대소 관계에 따라 탐색 범위를 절반씩 줄여나가며 값을 찾는 방식이다.

이진 탐색에서 정렬이 필요한 이유

이진 탐색은 "중간값보다 크면 오른쪽에 있고, 작으면 왼쪽에 있다"라는 규칙을 전제로 탐색을 진행하게 된다. 이때 데이터가 무작위로 섞여 있다면 이 규칙이 성립하지 않으므로, 반드시 데이터가 오름차순이나 내림차순으로 정렬되어 있어야한다.

이진 탐색의 장단점

장점

• 탐색 범위를 매번 절반씩 깎아내기 때문에 속도가 빠르다.

단점

• 반드시 정렬된 데이터여야만 사용할 수 있다.
• 데이터가 자주 추가되거나 삭제되는 환경에서는 정렬을 유지하는 비용이 더 클 수 있다.

이진 탐색의 코드 구현

def binary_search(list, target):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2

        if list[mid] == target:
            return mid
        elif list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

선형 탐색과 이진 탐색의 차이

분류	선형 탐색	이진 탐색
동작 원리	데이터를 처음부터 끝까지 순차적으로 검색	정렬된 배열에서 중간값을 기준으로 탐색
탐색 방법	한 개씩 순차 비교	중간값 기준 분할 탐색
속도	느림	매우 빠름
시간 복잡도	O(n)	O(logn)
정렬 필요 여부	필요 없음 (무작위 데이터도 가능)	무조건 정렬이 필요함
사용하기 좋은 상황	데이터의 양이 적거나 정렬되지 않았을 때	데이터의 양이 많고 이미 정렬되어 있을 때

깊이 우선 탐색 (DFS)

DFS란 무엇인가?

Depth-First Search의 약자로, 루트 노드(혹은 다른 임시의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 의미한다.

• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
• 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 방법이다.
• 사용하는 경우 : 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
• 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.

DFS의 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
• 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.
• 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검새햐아 한다는 것이다. 검사하지 않을 경우 무한루프에 빠질 수 있다.

DFS의 과정

1. 시작 노드를 방문하고 방문 처리를 한다.

2. 방문하지 않은 인접 노드가 있다면 그 방향으로 끝까지 내려간다.

3. 끝까지 내려갔다면 가장 최근의 갈림길로 돌아와서 다른 방향의 끝까지 내려간다.

스택(Stack)과의 관계

DFS는 '가장 최근의 갈림길'로 돌아가야 하므로, LIFO(후입선출) 구조인 스택(Stack) 자료구조를 사용한다.

DFS가 사용되는 곳

• 미로 찾기
• 경로의 특징을 저장해야 할 때
• 그래프의 사이클 검사
• 백트래킹 문제
• 순열, 조합 탐색
• 모든 경우의 수 조합

너비 우선 탐색 (BFS)

BFS란 무엇인가?

Breadth-First Search의 약자로, 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법이다
• 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 방법이다.
• 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
• 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.

BFS의 특징

• 직관적이지 않은 면이 있다.
  • BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
• BFS는 재귀적으로 동작하지 않는다.
• 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 수 있다.
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
  • 선입선출(FIFO) 원칙으로 탐색
  • 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.

BFS의 과정

1. 시작 노드를 방문 처리하고 저장소(큐)에 넣는다.

2. 저장소에서 노드를 하나 꺼내어 그 노드의 모든 이웃(인접) 노드를 확인하고 방문하지 않았다면 저장소에 차례로 넣는다.

3. 저장소가 빌 때까지 이 과정을 반복한다.

큐(Queue)와의 관계

먼저 발견한 이웃 노드들을 순서대로 먼저 방문해야 하므로, FIFO(선입선출) 구조인 큐(Queue) 자료구조를 사용한다.

BFS가 사용되는 곳

• 최단 경로 찾기
• 최소 횟수 구하기
• 소셜 네트워크 서비스 (SNS)

DFS vs BFS

비교 항목	깊이 우선 탐색 (DFS)	너비 우선 탐색 (BFS)
탐색 방식	한쪽 방향으로 끝까지 깊게 탐색	가로로 한 층 한 층 탐색
사용하는 자료구조	스택(Stack) / 재귀 함수 (Call Stack)	큐 (Queue)
특징	깊은 경로를 먼저 확인	같은 거리의 노드를 먼저 확인
장점	경로 탐색에 적합함	최단 거리 탐색에
단점	최단 경로를 보장하지 않음	메모리 공간의 소모가 심함
사용 예시	미로 찾기, 백트래킹 등	최단 경로 찾기, SNS