탐색 알고리즘(Search Algorithm)

1. 탐색 알고리즘이란?

우리는 종종 수백, 수천 개, 더 나아가 수십만 개의 데이터 중에서 특정 값을 찾아야 할 때가 있다. 예를 들어 휴대폰에서 특정 연락처를 찾거나, 수많은 정보 속에서 원하는 데이터를 검색해야 하는 상황이 그렇다.

이때 중요한 역할을 하는 것이 바로 탐색 알고리즘(Search Algorithm) 이다.

 

만약 탐색 알고리즘이 없다면, 원하는 데이터를 찾기 위해 모든 데이터를 하나씩 직접 확인해야 한다. 데이터의 양이 많아질수록 이러한 방식은 시간이 오래 걸리고 비효율적일 수 있다.

 

탐색 알고리즘은 컴퓨터 사이언스에서 여러 데이터(컬렉션 자료형) 안에서 원하는 값을 더 효율적으로 찾기 위해 사용되는 알고리즘 이다.

대표적인 탐색 알고리즘으로는 선형 탐색(Linear Search) 과 이진 탐색(Binary Search) 이 있다.

---

2. 선형 탐색(Linear Search)

2.1 선형 탐색의 동작 원리

선형 탐색은 탐색 알고리즘 중 가장 간단한 방식이다.
선형 탐색에서는 먼저 우리가 찾고자 하는 값을 지정한다.

이후 배열의 첫 번째 요소부터 시작해서, 원하는 값을 찾을 때까지 요소를 하나씩 순서대로 비교하며 탐색한다.

만약 원하는 값을 찾거나 배열의 끝까지 도달하면 그 때의 인덱스 값을 반환하고, 탐색이 종료된다.
하지만, 배열을 끝까지 순회했지만, 원하는 값을 결구 찾지 못했다면 -1를 반환한다.

---

2.2 선형 탐색의 장단점

장점

• 선형 탐색은 구현 방식이 비교적 단순하고 이해하기 쉬운 편이다.
• 정렬되지 않은 배열에서도 사용할 수 있다.
• 배열 안의 데이터 타입이 통일되지 않아도 찾고자 하는 값을 찾을 수 있다.

단점

• 데이터를 하나씩 직접 비교해야 하기 때문에 데이터의 개수가 많아질수록 탐색 시간이 오래 걸릴 수 있다. 👉 시간 복잡도 : O(n)

 

💻 구현

def linear_search(arr, key):
  for i in range(len(arr)): # arr를 처음부터 순회하면서
    if arr[i] == key : # key값과 동일한 arr[i]를 찾으면 
      return i # i를 return 

  ## 배열을 끝까지 탐색했지만 key값과 동일한 값을 찾지 못했을 때 
  return -1  # -1을 return 


unsorted_arr= [60,10,30,20,50,40]

print(linear_search(unsorted_arr,40))
print(linear_search(unsorted_arr,100))

실행결과

5
-1

---

3. 이진 탐색(Binary Search)

3.1 이진 탐색의 동작 원리

이진 탐색(Binary Search)은 정렬된 배열에서 사용할 수 있는 탐색 알고리즘이다.

 

배열의 처음부터 하나씩 확인하는 선형 탐색과 달리, 이진 탐색은 먼저 배열의 중간 요소와 찾고자 하는 값 key를 비교한다.

 

만약 중간 요소와 key 값이 같다면, 해당 중간 인덱스를 반환하고 탐색을 종료한다.

 

하지만 값이 같지 않다면, 중간 요소를 기준으로 탐색 범위를 절반으로 줄인다.

 

key 값이 중간 요소보다 작으면 배열의 왼쪽 절반을 다시 탐색하고, key 값이 중간 요소보다 크면 배열의 오른쪽 절반을 다시 탐색한다.

 

이 과정을 원하는 값을 찾거나, 더 이상 탐색할 범위가 없을 때까지 반복한다.

왜 정렬이 필요할까?

이진 탐색은 중간값을 기준으로 왼쪽과 오른쪽을 탐색할 지 결정한다.

그런데 배열이 정렬되어 있지 않으면, 중간값보다 작은 값들이 왼쪽에 있고, 큰 값이 오른쪽에 있다는 보장이 없다.

 

따라서 이진 탐색은 반드시 정렬된 배열에서 사용해야 한다.

---

3.2 이진 탐색의 장단점

장점

• 선형 탐색보다 훨씬 빠르다.
• 탐색할 때마다 범위가 절반씩 줄어들기 때문에 시간복잡도는 O(logN)이다.

단점

• 배열이 정렬되어 있어야 사용할 수 있다.
• 정렬되지 않은 배열이라면, 먼저 정렬을 해야 하므로, 상황에 따라 정렬 비용이 추가될 수 있다.

---

3.3 💻 구현

def binary_search(arr,left,right,key): 

  mid = (left + right) // 2 # 중간 인덱스 

  if left > right : return -1 

  elif arr[mid] == key : return mid  # 만약 중간값이 key값과 동일하면 mid 반환

  elif key > arr[mid]: # 찾고자 하는 값이 중간값보다 크면 
    return binary_search(arr, mid+1,right, key) # 재귀적으로 mid+1 부터 right까지 다시 비교를 진행 


  else : # key < arr[mid] # 중간값보다 작으면 
    return binary_search(arr, left, mid - 1, key) # 재귀적으로 left 부터 mid-1까지 다시 비교를 진행 
## 실행
unsorted_arr= [60,10,30,20,50,40]
arr_len = len(unsorted_arr)
sorted_arr = sorted(unsorted_arr)

print(binary_search(sorted_arr ,0,arr_len-1,40))
print(binary_search(sorted_arr ,0,arr_len-1,-10))

실행 결과

3
-1

---

4. 선형 탐색 vs 이진 탐색

비교	선형 탐색	이진 탐색
탐색 방식	순차 탐색(Sequential Search)	분할 정복(Divide and Conquer)
속도 차이	느리다 O(N)	빠르다 O(logN)
정렬 필요 여부	❌	⭕
사용하기 좋은 상황	데이터 수가 적거나 정렬되지 않았을 때	데이터가 많고 이미 정렬되어 있을 때

 

---

5. 깊이 우선 탐색(DFS) & 너비 우선 탐색(BFS) 가볍게 살펴보기

깊이 우선 탐색과 너비 우선 탐색은 그래프를 순회하는 알고리즘을 말한다.

---

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

DFS(깊이 우선탐색)는 트리에서는 루트 노드(root node), 그래프에서는 임의의 정점(vertex) 에서 시작한다. 이후 한 경로를 따라 가능한 깊게 탐색한 뒤, 더 이상 방문할 정점이 없으면 이전 정점으로 돌아가(backtracking) 다시 탐색을 이어가는 방식이다. 

DFS의 동작방식

DFS 방법은 스택이나 재귀 호출로 다음 방문할 정점(Vertex)를 얻는다.
또, 같은 정점을 재방문하는 것을 막기 위해 Boolean 타입의 방문 배열을 사용한다.

 

1. 시작 노드를 스택에 push 하고 방문 여부를 True로 변경한다.
   👉 같은 노드를 여러 번 방문하는 것을 방지하기 위해서
2. 스택의 top 노드를 pop 하여 출력한다.
   👉 DFS는 가장 나중에 들어간 노드를 먼저 꺼내는 스택구조를 사용한다.
3. 현재 노드와 연결된 인접 노드(neighbor)를 확인한다.
   👉 아직 방문하지 않은 노드만 스택에 push하고 방문 배열을 True로 변경한다.
4. 더 이상 방문할 노드가 없을 때까지 위 과정을 반복한다.
   👉 갈 수 있는 곳이 없다면 이전 경로로 되돌아가며(backtracking) 탐색이 이어진다.

---

DFS는 어디에서 사용될까?

1️⃣ 그래프 내 사이클(cycle) 탐지

DFS를 통해 그래프를 순회하는 과정에서 이미 방문했던 정점으로 다시 돌아가는 간선(back edge)이 발견된다면 해당 그래프에는 사이클이 존재한다고 볼 수 있다.

2️⃣ 경로 탐색

DFS는 두 정점 사이의 경로(Path)를 찾을 때 활용될 수 있다.

예를 들어 정점 u에서 목적지 z까지 가는 경로를 찾는다고 하자.

1. 시작 정점 u를 기준으로 DFS(G,u)를 호출한다.
2. 탐색 과정에서 스택을 사용해 시작 정점부터 현재 정점까지의 경로를 저장한다.
3. 만약 목적지인 정점 z를 발견하면, 스택에 저장된 경로를 반환하면 된다.

👉 DFS는 한 방향으로 끝까지 깊게 탐색하기 때문에 어떤 경로로 도착했는지 를 추적하는 데 유용하다.

---

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

BFS(Breadth First Search, 너비 우선 탐색) 는 그래프나 트리의 노드를 탐색하는 방법 중 하나이다.

이 알고리즘은 현재 깊이(level)에 있는 노드들을 먼저 모두 방문한 뒤, 다음 깊이의 노드로 이동하는 방식으로 탐색을 진행한다.

쉽게 말해, 가까이 있는 노드부터 차례대로 방문하면서 점점 범위를 넓혀가는 탐색 방식이라고 보면 된다. 

---

BFS의 동작 방식

 

BFS의 동작 과정은 다음과 같다.

1. 시작 노드를 큐에 enqueue 하고 방문 여부를 True로 변경한다.
   👉 같은 노드가 여러 번 큐에 들어가는 것을 방지하기 위함이다.
2. 큐의 front 노드를 dequeue 하여 출력한다.
   👉 BFS는 먼저 들어온 노드를 먼저 꺼내 탐색한다.
3. 현재 노드와 연결된 인접 노드(neighbor)를 확인한다.
   👉 아직 방문하지 않은 노드라면 큐에 enqueue 하고, 그 순간 바로 방문 배열을 True로 변경한다.
4. 큐가 빌 때까지 위 과정을 반복한다.
   👉가까운 노드부터 순서대로 탐색하면서 점점 범위를 넓혀간다.

---

BFS는 어디에서 사용될까?

1️⃣ 최단 경로 탐색(Shortest Path Problems)

가중치가 없는 그래프(unweighted graph)에서는 BFS를 이용해 두 노드 사이의 최단 경로를 찾을 수 있다.
즉 , 시작 노드에서 가까운 곳부터 차례대로 탐색하기 때문에 가장 먼저 도착한 경로가 최단 경로가 되는 특징이 있다.
이러한 특징 덕분에 BFS는 GPS 네비게이션 시스템, SNS(두 사용자 사이의 가장 짧은 연결 관계-친구관계) 등에서 활용된다.

2️⃣ 웹 크롤러

검색 엔진은 웹 페이지를 수집하고 인덱싱하기 위해 BFS 방식을 활용한다.
처음 시작 페이제(seed page)부터 출발해서 연결된 링크들을 가까운 순서대로 탐색하면서, 많은 웹 페이지를 효율적으로 수집할 수 있도록 돕는다.