[Python] 탐색 알고리즘의 개념: 선형(Linear), 이진(Binary), 깊이 우선(DFS), 너비 우선(BFS)

탐색 알고리즘이란?

> 탐색(Search): "많은 데이터 중에서 원하는 값을 찾는 과정" 입니다.
> 탐색 방법(알고리즘) : 데이터가 어떻게 저장되어 있는지에 따라 탐색 알고리즘이 달라집니다.
 
이 글에서는 다음 네 가지 탐색 알고리즘을 다룹니다.

• 선형 탐색 (Linear Search)
• 이진 탐색 (Binary Search)
• 깊이 우선 탐색 (Depth-First Search, DFS)
• 너비 우선 탐색 (Breadth-First Search, BFS)
  

탐색 알고리즘은 크게 두 가지 축으로 나눌 수 있습니다.

1. 선형 구조 : 일차원(배열/리스트) 탐색
   • 선형 탐색: 정렬 여부 상관 없이 앞에서부터 쭉 검사.
   • 이진 탐색: 정렬된 배열에서 중간값 기준으로 범위를 반씩 줄이기.
     
2. 비선형 구조 : 그래프/트리 탐색
   • DFS: 스택(또는 재귀)을 사용해서 깊게 파고들기.
   • BFS: 큐를 사용해서 가까운 곳부터 넓게 훑기. (최단 경로에 강점)

위 표 내용을 상기하면서 각 알고리즘을 하나씩 자세하게 알아봅시다.

 

우선, 아래 표로 탐색 알고리즘의 특징을 비교하고, 트리/그래프의 개념 또한 다시 상기해봅시다.

탐색 알고리즘	자료구조	내부 자료구조	시간 복잡도	장점	단점	대표 사용 예시
선형 (Linear)	리스트 / 배열	없음 (단순 순회)	O(n)	매우 단순한 구현, 정렬 불필요(정렬 여부 무관)	대용량 데이터에서 느림	소규모 데이터, 임시 검사
이진 (Binary)	정렬된 리스트 / 배열	인덱스 기반 접근	O(log n)	정렬된 데이터 필수, 대용량 데이터에서도 매우 빠름	정렬 필요, 삽입/삭제 비용	정렬된 ID/점수/로그 검색
깊이 우선 (DFS)	*트리/그래프	스택(Stack) / 재귀	O(V+E)	모든 경로/경우 탐색에 강점 (한 우물만 깊게 파고들기)	최단 경로 보장 X, 깊이 문제	미로/퍼즐, 백트래킹, 사이클 탐지
너비 우선 (BFS)	*트리/그래프	큐(Queue)	O(V+E)	최단 거리/레벨 탐색에 강점 (가까운 곳부터 넓게 훑기)	큐 메모리 사용량 증가	최단 경로, 네트워크 전파, SNS 친구 단계

 

*트리, 그래프란?

• 트리와 그래프의 구조 예시

예) 트리			예) 그래프
         
     A (Root)			A ----- B ------D
    /     \			│    /  │    /  │
   B       C			│   /   │   /   │
 /   \    /  \			│  /    │  /    │
D     E  F    G			C ----- E ------F

	트리(Tree)	그래프(Graph)
개념	> 계층 구조를 표현한 비순환 연결 그래프 → 트리는 특수한 그래프의 한 종류라고 볼 수 있다.	> 정점(Vertex)들과 간선(Edge)으로 이루어진 관계 구조 → 트리보다 훨씬 자유로운 구조로, 단순히 Vertex + Edge로 이루어진 구조일 뿐, 어느 Node가 위/아래인지 구분이 없다
특징	> Root(루트) : 트리의 최상단, 시작점, 1개 > Node(노드) : 데이터 저장 단위 → 부모 노드 1개, 자식 노드 여러 개 가능 → 순환(Cycle) 없음 > Edge(간선) : 부모–자식을 잇는 선 > Leaf(리프) : 자식이 없는 노드 > Depth/Level : 노드의 깊이 > 하나의 루트만 존재 : Root(루트) 개수 = 1 > Edge(간선) 개수 = Node(노드) 개수 - 1	> Vertex(정점) : 노드 > Edge(간선) : 정점 간 연결 → 부모와 자식 노드 모두 여러 개 가능 → 순환(Cycle) 허용, 자유로운 간선 수 > 루트라는 개념 자체가 없음. → 시작점이 정해져 있지 않기 때문에 방향이 없을 수 있음. > 서로 연결되지 않은 정점 존재 가능 (Disconnected) > 방향성(Directed) 유무 선택 가능 > 가중치(Weight) 존재할 수 있음
종류	> 이진 트리(Binary Tree) : 자식이 최대 2개 > 이진 탐색 트리(BST) : 왼쪽 < 루트 < 오른쪽 규칙 > 힙(Heap) :우선순위 큐 구현 (최대힙/최소힙) > 트라이(Trie) : 문자열 검색 트리 > Segment Tree : 구간 합/최댓값 등 계산	> 무방향 그래프(Undirected) : A—B 같은 양방향 관계 > 방향 그래프(Directed) : A → B 같은 일방향 > 가중치 그래프(Weighted) : 거리, 비용 등이 포함 > DAG(Directed Acyclic Graph) : DP에서 많이 쓰임 > 완전 그래프(Complete) : 모든 노드가 서로 연결됨 > 이분 그래프(Bipartite) : 두 그룹으로 나뉨
예시	> 조직도, 폴더 구조, 의사결정 트리	> 지도, SNS, 네트워크

 

---

1. 선형 탐색 (Linear Search)

 

1.1. 정의

 
: 선형 탐색은 데이터 집합의 처음부터 끝까지 순차적으로(Sequential) 값을 비교하면서 찾는 가장 직관적이고 단순한 탐색 알고리즘입니다. 

1.2. 동작 원리

1. 인덱스 0부터 시작해서, 각 원소를 차례대로 확인합니다.
2. data[i] = target 이 되는 순간, 인덱스 i 를 반환하고 종료합니다.
3. 끝까지 확인했는데도 못 찾으면 "없다"는 의미로 -1을 반환합니다.

예시)

data = [8, 4, 7, 3, 9, 0, 2, 5, 6, 1]

찾을 값 : target = 2

0번째 원소 8 → 2와 같은지?  아니요
1번째 원소 4 → 2와 같은지?  아니요
2번째 원소 7 → 2와 같은지?  아니요
3번째 원소 3 → 2와 같은지?  아니요
4번째 원소 9 → 2와 같은지?  아니요
5번째 원소 0 → 2와 같은지?  아니요
6번째 원소 2 → 2와 같은지?  예!  → 위치 6 (인덱스 6)

탐색 종료

 

1.3. 사용되는 자료구조

• 리스트(list), 배열(array) : 순차적으로 탐색할 수만 있으면 어떤 선형 자료구조에도 적용 가능합니다.
  
  

1.4. 장점 / 단점

• 장점 : 알고리즘이 매우 단순하고 구현이 쉽습니다. 중요한 것은 데이터가 정렬되어 있을 필요가 없습니다.
• 단점 : 데이터 개수 n 이 많아질수록, 최악의 경우 n번까지 비교해야 합니다. 대용량 데이터에는 비효율적입니다.
  
  

1.5. 시간 복잡도

• 최악, 평균: O(n)
• 최선: O(1) (첫 번째 원소가 정답인 경우)
  
  

---

2. 이진 탐색 (Binary Search)

 

2.1. 정의

 
: 이진 탐색은 오름차순(또는 내림차순)으로 정렬된 배열에서만 사용할 수 있는 고속 탐색 알고리즘으로, 탐색 범위를 매 단계마다 절반씩 줄여가며 값을 찾아가는 분할 정복(Divide and Conquer) 방식입니다.

2.2. 동작 원리

1. 현재 탐색 구간의 중간 인덱스 mid 를 계산합니다.
2. data[mid] 와 target 을 비교합니다.
   • target > data[mid] → 왼쪽은 모두 버리고 오른쪽 절반만 남김
   • target < data[mid] → 오른쪽은 모두 버리고 왼쪽 절반만 남김
3. 한 원소만 남을 때까지 1~2를 반복합니다.
4. 같으면 mid 반환, 끝까지 못 찾으면 -1 반환.

예시)

data = [2, 4, 6, 8, 10, 12, 14]
#index: 0, 1, 2, 3,  4,  5,  6 

target = 10

------1 단계------
→ left_index = 0, right_index = 6
→ mid = (0 + 6)//2 = 3
→ arr[3] = 8
→ 10 > 8 이므로, 오른쪽 구간만(index 4 ~ 6) 남김.


남은 data = [10, 12, 14]
남은 index:   4,  5,  6 

------2 단계------
→ left_index = 4, right_index = 6
→ mid = (4 + 6)//2 = 5
→ arr[5] = 12
→ 10 < 12 이므로, 왼쪽 구간만 남김(index 4 ~ 4) 남김.


남은 data = [10]
남은 index:   4 

------3 단계------
→ left_index = 4, right_index = 4
→ mid = (4 + 4)//2 = 4
→ arr[4] = 10
→ 10 = 10 이므로, 일치!

→ 찾음.

 

2.3. 사용되는 자료구조

• 인덱스로 O(1) 접근 가능한 배열/리스트
• 반드시 정렬된 상태가 유지되어야 합니다.
  
  

2.4. 장점 / 단점

• 장점 : 시간 복잡도가 O(log n) 이라, 데이터가 수십만/수백만 이상이어도 다른 알고리즘에 비해 매우 빠릅니다.
• 단점 : 정렬된 데이터에서만 사용 가능하고, 삽입/삭제가 잦으면 정렬 상태를 유지하는 비용이 들 수 있습니다.
  
  

2.5. 시간 복잡도

• 평균, 최악: O(log n)
• 최선: O(1) (첫 중간값이 바로 정답인 경우)
  
  

---

3. 깊이 우선 탐색 (DFS, Depth-First Search)

 

3.1. 정의

 
: DFS는 그래프나 트리에서 한 방향으로 갈 수 있을 만큼 깊게 내려갔다가, 더 이상 갈 수 없으면 직전 분기점으로 되돌아와 다른 방향으로 다시 깊게 들어가는 방식의 탐색입니다.

3.2. 동작 원리

1. 현재 정점을 방문하고, 방문 표시를 합니다.
2. 인접한 정점들 중 아직 방문하지 않은 정점이 있으면 그 정점으로 이동합니다.
3. 더 이상 갈 수 없으면 직전 정점(스택(Stack)의 이전 요소) 으로 되돌아갑니다.
4. 모든 정점을 방문할 때까지 반복합니다.
5. 구현 시에는 재귀 호출 (call stack 사용) 또는 명시적인 스택 자료구조를 사용합니다.

스택을 사용해 DFS 과정을 따라가 보겠습니다. 재귀 호출로 구현해도 내부적으로는 호출 스택이 비슷한 역할을 합니다.

예시) 

      A
     / \
    B   C
   / \   \
  D   E   F

 

1. 시작 정점 A를 스택에 push
   • 스택: [A]
2. 스택에서 A를 꺼내면서(A 방문) : A의 자식 C, B 순으로 스택에 넣기
   • 방문 순서: A
   • 스택: [C, B] (나중에 넣은 B가 먼저 꺼내지도록 역순으로 push)
3. 스택에서 B를 꺼내면서(B 방문) : B의 자식 E, D 를 스택에 push
   • 방문 순서: A → B
   • 스택: [C, E, D]
4. 스택에서 D를 꺼내면서(D 방문) : D는 자식이 없으므로 스택만 갱신
   • 방문 순서: A → B → D
   • 스택: [C, E]
5. 스택에서 E를 꺼내면서(E 방문) : E도 자식이 없음
   • 방문 순서: A → B → D → E
   • 스택: [C]
6. 스택에서 C를 꺼내면서(C 방문) : C의 자식 F 를 스택에 push
   • 방문 순서: A → B → D → E → C
   • 스택: [F]
7. 스택에서 F를 꺼내면서(F 방문) : F는 자식이 없음 → 스택이 비면 탐색 종료
   • 방문 순서: A → B → D → E → C → F  ☜ 최종 탐색 순서(DFS)
   • 스택: []

즉, DFS는 "현재 정점에서 내려갈 수 있을 때까지 깊게 들어갔다가, 막히면 한 단계씩 위로 되돌아오는 방식"으로 탐색이 진행됩니다.
 

3.3. 사용되는 자료구조

• 그래프 표현: 인접 리스트(adjacent list)
• 내부적으로: 스택 또는 재귀 호출 스택
• 방문 여부 체크: set 또는 bool 배열
  
  

3.4. 장점 / 단점

• 장점 : 구현이 비교적 간단하고, 재귀와 잘 어울리며, 모든 경로/모든 경우의 수를 탐색하는 문제에 잘 맞습니다. (Backtracking)
• 단점 : 최단 경로(최소 간선 수)를 보장하지 않습니다. 그래프가 매우 깊을 때, 재귀 깊이 제한을 넘을 수 있습니다.
  
  

3.5. 시간 복잡도

• O(V + E),  V : 그래프의 정점(Vertex) 수, E : 간선(edge) 수
  
  

---

4. 너비 우선 탐색 (BFS, Breadth-First Search)

 

4.1. 정의

 
: BFS는 시작 정점에서 가까운 정점(1단계 이웃) 들부터 방문하고, 그 다음 2단계 이웃, 3단계 이웃… 순서로 계층(Level)별로 넓게 탐색하는 알고리즘입니다. 예로, 연못에 돌을 던졌을 때, 물결이 동심원 모양으로 퍼져 나가는 순서대로 방문하는 것과 유사하다.

4.2. 동작 원리

1. 시작 정점을 큐(Queue)에 넣고 방문 처리합니다.
2. 큐에서 하나씩 꺼내면서, 그 정점의 인접한 정점들을 큐의 뒤에 추가합니다.
3. 큐가 빌 때까지 2를 반복합니다.

이 과정에서, 먼저 큐에 들어간 정점(가까운 레벨)이 먼저 처리되므로, 최단 거리(간선 수)가 자동으로 보장됩니다.

예시)

      A
     / \
    B   C
   / \   \
  D   E   F

 

1. 시작 정점 A를 방문하고, 큐에 A를 넣음
   • 큐: [A]
2. 큐에서 A를 꺼내고(A 방문 완료), A와 인접한 정점 B, C를 큐에 차례대로 추가
   • 방문 순서: A
   • 큐: [B, C]
3. 큐에서 B를 꺼내고(B 방문 완료), B의 자식 D, E를 큐 뒤에 추가
   • 방문 순서: A → B
   • 큐: [C, D, E]
4. 큐에서 C를 꺼내고(C 방문 완료), C의 자식 F를 큐 뒤에 추가
   • 방문 순서: A → B → C
   • 큐: [D, E, F]
5. 큐에서 D를 꺼내고(D 방문 완료), D는 자식이 없으므로 큐만 갱신
   • 방문 순서: A → B → C → D
   • 큐: [E, F]
6. 큐에서 E를 꺼내고(E 방문 완료), E도 자식이 없음
   • 방문 순서: A → B → C → D → E
   • 큐: [F]
7. 큐에서 F를 꺼내고(F 방문 완료), F도 자식이 없음 → 큐가 비면 탐색 종료
   • 방문 순서: A → B → C → D → E → F  ☜  최종 탐색 순서(DFS)
   • 큐: []

즉, 시작점에서 가까운 레벨(1촌, 2촌…)을 차례대로 방문하는 것이 DFS와의 가장 큰 차이입니다.

 

4.3. 사용되는 자료구조

• 그래프 표현: 인접 리스트
• 탐색 구조: 큐(Queue) (collections.deque 활용)
• 방문 여부 체크: set 또는 bool 배열
  
  

4.4. 장점 / 단점

• 장점 : 가중치가 없는 그래프에서 최단 거리(최소 간선 수)를 보장합니다. 특히 레벨(Level) 별로 데이터를 처리하기 좋아서, 계층 구조 분석에 적합합니다.
• 단점 : 한 레벨의 노드 수가 많으면, 큐에 많은 노드가 동시에 쌓여 메모리 사용량이 증가합니다.
  
  

4.5. 시간 복잡도

• O(V + E),  V :그래프의 정점 수,E: 간선 수
  
  

---

5. 탐색 알고리즘의 시간 복잡도 비교

 

아래 그래프는 4가지 탐색 알고리즘들의 시간 복잡도를 이론 함수로 비교해본 것 입니다. (그래프의 가로, 세로 축들 모두 logscale입니다.) 이 그래프를 보면, 이진탐색(Binary Search, (O(log n))의 증가 정도가 다른 알고리즘들의 증가 경향성(선형)과 비교하여 훨씬 완만한 것을 바로 알 수 있습니다.  

 

즉, 입력 크기 n 이 커질수록, 선형 탐색 O(n)과의 격차가 크게 벌어지는 것을 확인할 수 있습니다. DFS와 BFS는 이론적으로 O(V+E) 이지만, 노드(V)와 간선(E)의 비율이 적당한 어떤 그래프에서는 선형 탐색과 비슷한 기울기를 가질 수 있습니다.

---

6. 요약

 

정리하면, "언제 어떤 탐색 알고리즘을 선택할 것인가?" 라는 의문에 다음과 같은 기준을 적용할 수 있습니다. 

1. 데이터가 작거나 정렬되지 않았다.
 → 구현이 가장 쉬운 선형 탐색(Linear Search) 도 충분히 실용적입니다.

2. 데이터가 크고 정렬된 상태로 유지되고 있다.
 → 이진 탐색(Binary Search) 을 사용해서 압도적인 속도 향상을 얻을 수 있습니다.

3. 그래프/트리에서 모든 경로를 탐색하거나 가능한 경우를 다 보고 싶다.
 → DFS 가 적합합니다. (Backtracking, 퍼즐, 사이클 탐지 등)

4. 최단 거리, 최소 단계, 레벨 구조가 중요하다.
 → BFS 가 적합입니다. (미로 최단 경로, SNS 친구 단계, 네트워크 전파 등)


데이터의 조건과 문제의 목적을 정확히 파악하면 가장 효율적인 탐색 알고리즘을 선택할 수 있습니다. 작은 규모이거나 정렬되지 않은 데이터라면 구현이 간단한 선형 탐색이 충분하며, 큰 데이터가 정렬되어 있다면 이진 탐색이 압도적으로 유리하다는 사실을 이해할 수 있습니다. 또한 그래프나 트리에서 모든 경로를 확인해야 할 때는 DFS가 적합하고, 최단 거리나 레벨 구조가 중요할 때는 BFS가 적합하다는 것을 알 수 있습니다. 결국 핵심은 문제 해결에 가장 잘 부합하는 탐색 방식(들)을 선택하여 적용하는 것이 중요합니다. 그러면 불필요한 연산을 줄이고 계산 효율을 크게 높일 수 있을 것 입니다. 

 

알고리즘을 공부하는 것은 곧 "동등한 결과를 얻을 대, 가장 적은 에너지와 시간을 소비하는 방식을 선택해야 하는 이유를" 이해하고 효율성을 극대화하기 위입니다.
 

---

 

※ [코드] 탐색 알고리즘의 시간 복잡도 

import os                      # 운영체제 관련 기능(폴더 생성, 경로 조작 등)을 위한 모듈
import numpy as np             # 수치 계산과 배열 연산을 위한 라이브러리
import matplotlib.pyplot as plt  # 그래프(시각화)를 그리기 위한 라이브러리

#--------------------------------------
#네 가지 탐색 알고리즘의 시간 복잡도를 log-log 스케일 그래프로 그리고,
#결과 이미지를 Google Drive에 저장하기.
#--------------------------
def plot_complexity():

    # 1. 출력 결과 그림 저장 경로 지정 -----------
    save_dir = "/content/gdrive/MyDrive/figures"
    os.makedirs(save_dir, exist_ok=True)
    save_path = os.path.join(save_dir, "search_time_complexity_loglog.png")

    # 2. 입력 크기 n 정의 -------------------------------------------------------
    #   - logscale에서 보기 좋은 샘플 포인트 생성
    #   - 10^1(=10) 부터 10^5(=100000)까지 로그 스케일로 50개 점 생성
    #   - 즉, n이 10, 12.7, 16, …, 100000 처럼 로그 간격으로 증가
    n = np.logspace(1, 5, num=50)

    # 3. 각 알고리즘의 이론적 시간 복잡도 함수 --------------------------------
    #   - y값은 "연산 횟수" 또는 "복잡도"를 나타내는 가상의 값
    #   - Big-O에서 상수는 중요하지 않지만, 그래프에서 선이 겹치지 않도록
    #     DFS/BFS에는 서로 다른 상수배(0.5, 2.0)를 곱해줌

    y_linear = n              # 선형 탐색: O(n)
    y_binary = np.log2(n)     # 이진 탐색: O(log n)
    y_dfs = 0.5 * n           # DFS:   O(V+E) ≈ O(n) (상수 0.5 곱함)
    y_bfs = 2.0 * n           # BFS:   O(V+E) ≈ O(n) (상수 2.0 곱함)

    # 4. 그래프 기본 설정 -------------------------------------------------------
    #   - figure(figsize=(가로, 세로)) : 그림 크기 (단위: 인치)
    plt.figure(figsize=(10, 6))

    # 각 알고리즘별로 선을 하나씩 그림
    # label: 범례에 표시될 이름
    # linewidth: 선 굵기
    # linestyle: 실선/점선 등 스타일 ("--"는 점선)
    plt.plot(n, y_linear, label="Linear Search O(n)", linewidth=2)
    plt.plot(n, y_binary, label="Binary Search O(log n)", linewidth=2)
    plt.plot(n, y_dfs, label="DFS O(V+E) ≈ O(n)", linestyle="--")
    plt.plot(n, y_bfs, label="BFS O(V+E) ≈ O(n)", linestyle="--")

    # 5. 축을 log scale로 설정 --------------------------------------------------
    # - x축: 입력 크기 n
    # - y축: 시간 복잡도(연산 횟수)
    # - log 스케일을 사용하면 O(log n), O(n) 같은 곡선을 직선처럼 볼 수 있어
    #   서로의 기울기를 비교하기 쉬워짐
    plt.xscale("log")
    plt.yscale("log")

    # 6. 제목, 축 라벨, 격자, 범례 등 설정 ----------------------------------------
    plt.title("Time Complexity Comparison of Search Algorithms (log-log plot)")
    plt.xlabel("Input size n (log scale)")
    plt.ylabel("Number of operations / complexity (log scale)")
    plt.grid(True, which="both", alpha=0.3, linestyle="--", linewidth=0.5)

    # legend(): 위에서 label로 지정한 이름들을 모아 범례 생성
    plt.legend()
    plt.tight_layout()

    # 7. 이미지 파일로 저장 ------------------------------------------------------
    # savefig(경로, dpi=해상도)
    # - dpi가 높을수록 그림이 선명해짐
    plt.savefig(save_path, dpi=300)

    # 8. 화면에 결과 표시 --------------------------------------------------------
    plt.show()

    # 9. 어느 위치에 저장되었는지 경로 출력 ------------------------------------
    print("저장 경로:", save_path)

# 함수 호출: 위에서 정의한 plot_complexity() 함수를 실제로 실행
plot_complexity()

 
 
즐거운 파이썬~ 즐 파이씽~
 
[주의] 내용에 오류가 있을 수 있습니다.