[과제 10] 탐색 알고리즘(Search Algorithm)

1. 탐색 알고리즘이란?

1.1 탐색(Search)의 의미

탐색(Search)이란 여러 데이터 중에서 원하는 값을 찾는 작업을 의미한다.
예를 들어 리스트 안에서 특정 숫자를 찾거나, 전화번호부에서 이름을 검색하거나, 지도에서 목적지까지 가는 길을 찾는 것도 탐색에 해당한다.

컴퓨터 프로그램에서는 데이터가 많아질수록 원하는 정보를 빠르게 찾는 것이 중요하다. 이때 어떤 방법으로 데이터를 찾을지 정해 놓은 절차를 탐색 알고리즘이라고 한다.

1.2 탐색 알고리즘이 중요한 이유

탐색은 거의 모든 프로그램에서 사용된다. 데이터가 적을 때는 단순히 처음부터 끝까지 확인해도 괜찮지만, 데이터가 많아지면 탐색 방법에 따라 실행 속도가 크게 달라진다.

예를 들어 학생 10명 중 한 명을 찾는 것은 어렵지 않지만, 회원 100만 명 중 특정 사용자를 찾는다면 효율적인 탐색 방법이 필요하다. 따라서 탐색 알고리즘은 프로그램의 성능을 높이는 데 매우 중요한 역할을 한다.

1.3 실생활에서 사용되는 탐색 예시

• 연락처 앱에서 친구 이름 검색하기
• 쇼핑몰에서 상품명 검색하기
• 도서관에서 책 제목이나 저자명 찾기
• 지도 앱에서 목적지까지의 경로 찾기
• 게임에서 캐릭터가 이동할 수 있는 길 찾기
• 데이터베이스에서 특정 회원 정보 조회하기

---

2. 선형 탐색(Linear Search)

2.1 선형 탐색이란?

선형 탐색은 데이터를 처음부터 끝까지 하나씩 확인하면서 원하는 값을 찾는 탐색 방법이다.
가장 단순한 탐색 알고리즘이며, 데이터가 정렬되어 있지 않아도 사용할 수 있다.

2.2 동작 원리

1. 리스트의 첫 번째 요소부터 확인한다.
2. 현재 요소가 찾는 값과 같은지 비교한다.
3. 같으면 해당 위치를 반환한다.
4. 다르면 다음 요소로 이동한다.
5. 리스트 끝까지 찾지 못하면 값이 없다고 판단한다.

2.3 Python 구현

# linear_search

def linear_search(arr, value):
    for idx in range(len(arr)):
        if arr[idx] == value:
            return idx
    return -1

student_numbers = [202601, 202614, 202603, 202622, 202610]
target_number = 202622

result = linear_search(student_numbers, target_number)

if result != -1:
    print(f"{target_number}번 학생은 출석부 {result + 1}번째에 있습니다.")
else:
    print(f"{target_number}번 학생을 찾을 수 없습니다.")

실행 결과

202622번 학생은 출석부 4번째에 있습니다.

2.4 장점

• 구현이 매우 쉽다.
• 데이터가 정렬되어 있지 않아도 사용할 수 있다.
• 리스트, 배열 등 다양한 자료구조에 적용하기 쉽다.
• 데이터의 개수가 적을 때는 충분히 효율적이다.

2.5 단점

• 데이터가 많아질수록 탐색 시간이 오래 걸린다.
• 최악의 경우 모든 데이터를 확인해야 한다.
• 정렬된 데이터에서도 정렬 정보를 활용하지 못한다.

2.6 사용하는 상황

• 데이터 개수가 적을 때
• 데이터가 정렬되어 있지 않을 때
• 한 번만 간단히 탐색하면 될 때
• 구현을 빠르게 해야 할 때

2.7 시간 복잡도

경우	시간 복잡도	설명
최선	O(1)	첫 번째 요소가 찾는 값인 경우
평균	O(n)	중간 정도 위치에서 찾는 경우
최악	O(n)	마지막에 있거나 없는 경우

---

3. 이진 탐색(Binary Search)

3.1 이진 탐색이란?

이진 탐색은 정렬된 데이터에서 가운데 값을 기준으로 탐색 범위를 절반씩 줄여 가며 원하는 값을 찾는 탐색 방법이다.

선형 탐색은 앞에서부터 하나씩 확인하지만, 이진 탐색은 한 번 비교할 때마다 탐색할 데이터의 절반을 버릴 수 있다. 그래서 데이터가 많을수록 선형 탐색보다 훨씬 빠르다.

3.2 동작 원리

1. 데이터의 시작 인덱스와 끝 인덱스를 정한다.
2. 가운데 인덱스를 구한다.
3. 가운데 값이 찾는 값과 같으면 탐색을 종료한다.
4. 찾는 값이 가운데 값보다 작으면 왼쪽 범위만 다시 탐색한다.
5. 찾는 값이 가운데 값보다 크면 오른쪽 범위만 다시 탐색한다.
6. 탐색 범위가 없어질 때까지 반복한다.

왜 정렬이 필요한가?

이진 탐색은 가운데 값을 기준으로 왼쪽 또는 오른쪽 중 한쪽을 버리면서 탐색한다.
이때 데이터가 정렬되어 있어야만 찾는 값이 어느 쪽에 있는지 판단할 수 있다.

예를 들어 오름차순 정렬된 데이터에서 찾는 값이 가운데 값보다 작다면, 찾는 값은 반드시 왼쪽에 있다. 하지만 데이터가 정렬되어 있지 않다면 왼쪽에 있는지 오른쪽에 있는지 알 수 없기 때문에 이진 탐색을 사용할 수 없다.

3.3 Python 구현

# binary_search.py

def binary_search(arr, value):
    left = 0
    right = len(arr) - 1
    
    while(left <= right):
        middle = (left + right) // 2
        if(arr[middle] == value):
            return middle
        elif(arr[middle] > value):
            right = middle - 1
        else:
            left = middle + 1
    return -1
    
    
# binary_search 는 정렬된 배열에서만 사용가능
product_numbers = [1001, 1010, 1024, 1040, 1055, 1072, 1100, 1135]
target_product = 1072

result = binary_search(product_numbers, target_product)

if result != -1:
    print(f"{target_product}번 상품은 {result}번 인덱스에 있습니다.")
else:
    print(f"{target_product}번 상품을 찾을 수 없습니다.")

실행 결과

1072번 상품은 5번 인덱스에 있습니다.

3.4 장점

• 데이터가 많을 때 매우 빠르다.
• 한 번 비교할 때마다 탐색 범위가 절반으로 줄어든다.
• 정렬된 데이터에서 효율적으로 사용할 수 있다.

3.5 단점

• 반드시 데이터가 정렬되어 있어야 한다.
• 정렬되지 않은 데이터라면 먼저 정렬해야 하므로 추가 시간이 필요하다.
• 연결 리스트처럼 중간 위치에 바로 접근하기 어려운 자료구조에는 적합하지 않다.

3.6 선형 탐색과의 차이점

선형 탐색은 처음부터 끝까지 하나씩 확인하지만, 이진 탐색은 가운데 값을 기준으로 탐색 범위를 계속 절반씩 줄인다.
따라서 데이터가 적을 때는 큰 차이가 없을 수 있지만, 데이터가 많아질수록 이진 탐색이 훨씬 빠르다.

3.7 시간 복잡도

경우	시간 복잡도	설명
최선	O(1)	가운데 값이 찾는 값인 경우
평균	O(log n)	탐색 범위를 절반씩 줄이는 경우
최악	O(log n)	끝까지 범위를 줄여야 하는 경우

---

4. 선형 탐색 vs 이진 탐색 비교

비교 항목	선형 탐색(Linear Search)	이진 탐색(Binary Search)
탐색 방식	처음부터 끝까지 순서대로 확인	가운데 값을 기준으로 범위를 절반씩 줄임
속도 차이	데이터가 많으면 느림	데이터가 많을수록 빠름
시간 복잡도	O(n)	O(log n)
정렬 필요 여부	필요 없음	반드시 필요
구현 난이도	쉬움	선형 탐색보다 약간 복잡함
사용하기 좋은 상황	데이터가 적거나 정렬되어 있지 않은 경우	데이터가 정렬되어 있고 개수가 많은 경우
예시	작은 리스트에서 값 찾기	정렬된 회원 번호, 상품 번호 검색

5. 깊이 우선 탐색(DFS)

5.1 DFS란 무엇인가?

DFS(Depth First Search)는 그래프나 트리에서 한 방향으로 갈 수 있는 곳까지 깊게 탐색한 뒤, 더 이상 갈 곳이 없으면 이전 위치로 돌아와 다른 경로를 탐색하는 방법이다.

DFS는 이름 그대로 깊이를 우선으로 탐색한다.

5.2 DFS 동작 방식

1. 시작 노드를 방문한다.
2. 현재 노드와 연결된 노드 중 방문하지 않은 노드로 이동한다.
3. 더 이상 이동할 수 없을 때까지 깊게 들어간다.
4. 갈 곳이 없으면 이전 노드로 돌아간다.
5. 방문하지 않은 다른 노드를 탐색한다.
6. 모든 노드를 방문할 때까지 반복한다.

스택(Stack)과의 관계

DFS는 가장 나중에 발견한 노드를 먼저 탐색하는 방식이다.
이 특징은 후입선출(LIFO, Last In First Out) 구조인 스택과 잘 맞는다.

DFS는 직접 스택을 사용해서 구현할 수도 있고, 재귀 함수를 사용해서 구현할 수도 있다. 재귀 함수는 내부적으로 함수 호출 스택을 사용하기 때문에 DFS와 잘 어울린다.

스택 구조 그림

스택은 데이터를 위에 쌓고, 가장 위에 있는 데이터부터 꺼내는 구조이다.

push A        push B        push C

  ┌───┐         ┌───┐         ┌───┐
  │ A │         │ B │         │ C │  ← 가장 나중에 들어온 C가 먼저 나감
  └───┘         ├───┤         ├───┤
                │ A │         │ B │
                └───┘         ├───┤
                              │ A │
                              └───┘

pop 순서: C → B → A

DFS는 한 경로를 깊게 들어가다가 더 이상 갈 곳이 없으면 이전 위치로 돌아온다.
이때 최근에 방문한 노드부터 되돌아가므로 스택 구조와 잘 맞는다.

5.3 Python 구현

# DFS(Depth First Search)

def DFS(graph, start, visited = None):
    if visited is None:
        visited = []
    visited.append(start)
    
    for node in graph[start]:
        if node not in visited:
            DFS(graph, node, visited)     
    
    return visited



graph = dict()
 
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

visited = []
visited = DFS(graph, 'A', visited)
print(visited)

실행 결과

['A', 'B', 'D', 'E', 'F', 'C', 'G', 'H', 'I', 'J']

5.4 DFS가 사용되는 곳

• 미로 찾기
• 경로 존재 여부 확인
• 그래프의 모든 노드 방문
• 백트래킹 문제
• 순열, 조합 탐색
• 게임에서 가능한 모든 경우 탐색

5.5 DFS 장점

• 구현이 비교적 간단하다.
• 재귀 함수와 함께 사용하기 좋다.
• 한 경로를 끝까지 탐색해야 하는 문제에 적합하다.
• 메모리를 비교적 적게 사용할 수 있다.

5.6 DFS 단점

• 최단 경로를 보장하지 않는다.
• 깊이가 너무 깊으면 재귀 호출 오류가 발생할 수 있다.
• 잘못 구현하면 무한 탐색에 빠질 수 있다.

---

6. 너비 우선 탐색(BFS)

6.1 BFS란 무엇인가?

BFS(Breadth First Search)는 그래프나 트리에서 시작 노드와 가까운 노드부터 차례대로 탐색하는 방법이다.

DFS가 한 방향으로 깊게 들어가는 방식이라면, BFS는 현재 위치에서 가까운 노드들을 먼저 모두 확인한 뒤 다음 단계로 이동한다.

6.2 BFS 동작 방식

1. 시작 노드를 방문한다.
2. 시작 노드와 연결된 노드들을 큐에 넣는다.
3. 큐에서 노드를 하나 꺼내 방문한다.
4. 꺼낸 노드와 연결된 방문하지 않은 노드들을 다시 큐에 넣는다.
5. 큐가 빌 때까지 반복한다.

큐(Queue)와의 관계

BFS는 먼저 발견한 노드를 먼저 탐색한다.
이 특징은 선입선출(FIFO, First In First Out) 구조인 큐와 잘 맞는다.

따라서 BFS를 구현할 때는 보통 큐를 사용한다. 파이썬에서는 collections.deque를 사용하면 큐를 효율적으로 구현할 수 있다.

큐 구조 그림

큐는 한쪽으로 데이터를 넣고, 먼저 들어온 데이터부터 꺼내는 구조이다.

enqueue A      enqueue B      enqueue C

앞(front)                         뒤(rear)
  ↓                                  ↓
┌───┐          ┌───┬───┐          ┌───┬───┬───┐
│ A │          │ A │ B │          │ A │ B │ C │
└───┘          └───┴───┘          └───┴───┴───┘

dequeue 순서: A → B → C

BFS는 시작점에서 가까운 노드부터 차례대로 탐색한다.
먼저 발견한 노드를 먼저 처리해야 하므로 큐 구조와 잘 맞는다.

6.3 Python 구현

# BFS(Breadth First Search)
from collections import deque

def BFS(graph, start, visited = None):
    visited = []
    queue = deque([start])
    visited.append(start)
    while queue:
        node = queue.popleft()
        for next_node in graph[node]:
            if next_node not in visited:
                visited.append(next_node)
                queue.append(next_node)
    
    return visited
                

graph = dict()
 
graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']


result = BFS(graph, "A")
print(result)

실행 결과

['A', 'B', 'C', 'D', 'G', 'H', 'I', 'E', 'F', 'J']

6.4 BFS가 사용되는 곳

• 최단 경로 탐색
• 가까운 친구 추천
• 네트워크 단계별 탐색
• 웹 크롤링
• 지도에서 최소 이동 횟수 찾기
• 게임에서 가장 적은 이동으로 목표에 도달하는 문제

6.5 BFS 장점

• 시작점에서 가까운 노드부터 탐색한다.
• 가중치가 없는 그래프에서 최단 경로를 찾을 수 있다.
• 단계별 탐색이 필요한 문제에 적합하다.

6.6 BFS 단점

• 큐에 많은 노드를 저장해야 하므로 메모리를 많이 사용할 수 있다.
• 모든 인접 노드를 저장하면서 진행하기 때문에 DFS보다 메모리 부담이 클 수 있다.
• 단순히 한 경로를 깊게 확인하는 문제에는 DFS보다 비효율적일 수 있다.

---

7. DFS와 BFS 비교

비교 항목	DFS	BFS
탐색 방식	한 방향으로 갈 수 있는 곳까지 깊게 탐색	가까운 노드부터 넓게 탐색
사용하는 자료구조	스택 또는 재귀 함수	큐
자료구조 특징	후입선출(LIFO)	선입선출(FIFO)
특징	깊은 경로를 먼저 확인	같은 거리의 노드를 먼저 확인
장점	구현이 간단하고 경로 탐색에 적합	최단 거리 탐색에 적합
단점	최단 경로를 보장하지 않음	메모리를 많이 사용할 수 있음
사용 예시	미로의 모든 경로 탐색, 백트래킹	최단 경로, 최소 이동 횟수

---

8. 정리

탐색 알고리즘은 여러 데이터 중 원하는 값을 찾기 위한 방법이다.
선형 탐색은 단순하고 정렬이 필요 없지만 데이터가 많으면 느리다. 이진 탐색은 정렬된 데이터에서 매우 빠르게 동작하지만, 반드시 정렬이 필요하다.

DFS와 BFS는 리스트에서 값을 찾는 탐색과 달리 그래프나 트리 구조를 탐색할 때 많이 사용된다. DFS는 깊게 탐색하고, BFS는 가까운 곳부터 넓게 탐색한다. 문제의 목적이 전체 경로 탐색인지, 최단 거리 탐색인지에 따라 적절한 알고리즘을 선택해야 한다.