초보자를 위한 탐색 알고리즘 가이드: 선형, 이진, DFS와 BFS - 코드카인 티스토리

안녕하세요😊 코드카인 여러분!

오늘은 탐색 알고리즘에 대해 이야기해볼게요. 컴퓨터 과학에서 탐색 알고리즘은 마치 숨바꼭질에서 친구를 찾는 방법을 정리한 규칙 같아요. 여러분이 미로에서 출구를 찾거나, 사전에서 단어를 찾는 일을 컴퓨터가 수행한다면, 어떤 방법으로 가장 효율적으로 찾아낼 수 있을까요? 😊

---

탐색 알고리즘의 핵심, 어디에 쓰일까요?

탐색 알고리즘은 컴퓨터 과학의 기본 중 기본이에요.

• 일상 비유: 마트에서 물건을 찾는다고 생각해보세요. 상품의 위치를 아예 모른다면 무작위로 걸어다니며 찾아야 하지만, 섹션이 구분되어 있다면 단서를 활용해 빠르게 찾아낼 수 있겠죠?
• 활용 사례: 데이터베이스에서 정보를 검색하거나, 네트워크에서 최단 경로를 찾는 데 사용돼요.

---

대표적인 탐색 알고리즘

1. 선형 탐색(Linear Search)

• 어떻게 작동할까요? 리스트의 첫 번째 요소부터 마지막 요소까지 하나씩 확인해요.
  마치 마트에서 모든 선반을 처음부터 끝까지 살피는 것과 같아요.

• 코드 예제:

  def linear_search(arr, target):
      for i in range(len(arr)):
          if arr[i] == target:
              return i
      return -1
  
  # 예제
  numbers = [10, 20, 30, 40, 50]
  print(linear_search(numbers, 30))  # 결과: 2

• 장단점:

  • 장점: 구현이 쉽고 작은 데이터셋에 적합.
  • 단점: 데이터가 많아질수록 비효율적.

---

2. 이진 탐색(Binary Search)

• 어떻게 작동할까요? 정렬된 리스트에서 중간값을 기준으로 왼쪽 또는 오른쪽으로 탐색 범위를 줄여나가는 방식이에요.
  예를 들어, 사전에서 "apple"을 찾을 때 중간에서 시작해 반씩 줄이는 느낌이죠.

• 코드 예제:

  def binary_search(arr, target):
      left, right = 0, len(arr) - 1
      while left <= right:
          mid = (left + right) // 2
          if arr[mid] == target:
              return mid
          elif arr[mid] < target:
              left = mid + 1
          else:
              right = mid - 1
      return -1
  
  # 예제
  numbers = [10, 20, 30, 40, 50]
  print(binary_search(numbers, 30))  # 결과: 2

• 장단점:

  • 장점: 큰 데이터셋에서도 빠름. 시간 복잡도 O(log⁡n)O(\log n)O(logn).
  • 단점: 정렬된 리스트가 필요.

---

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

• 어떻게 작동할까요? 그래프 구조에서 한 노드를 끝까지 탐색하고, 막히면 다른 경로를 탐색해요.
  마치 미로에서 한쪽 방향으로 계속 가다가 막히면 돌아오는 방법과 비슷해요.

• 코드 예제:

  def dfs(graph, start, visited=None):
      if visited is None:
          visited = set()
      visited.add(start)
      for neighbor in graph[start]:
          if neighbor not in visited:
              dfs(graph, neighbor, visited)
      return visited
  
  # 예제
  graph = {
      'A': ['B', 'C'],
      'B': ['A', 'D', 'E'],
      'C': ['A', 'F'],
      'D': ['B'],
      'E': ['B', 'F'],
      'F': ['C', 'E']
  }
  print(dfs(graph, 'A'))  # 결과: {'A', 'B', 'C', 'D', 'E', 'F'}

---

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

• 어떻게 작동할까요? DFS와 달리 한 레벨씩 차근차근 탐색해요.
  미로에서 출발점에서 가까운 길부터 확인하는 방법과 같아요.

• 코드 예제:

  from collections import deque
  
  def bfs(graph, start):
      visited = set()
      queue = deque([start])
      visited.add(start)
      while queue:
          vertex = queue.popleft()
          for neighbor in graph[vertex]:
              if neighbor not in visited:
                  visited.add(neighbor)
                  queue.append(neighbor)
      return visited
  
  # 예제
  graph = {
      'A': ['B', 'C'],
      'B': ['A', 'D', 'E'],
      'C': ['A', 'F'],
      'D': ['B'],
      'E': ['B', 'F'],
      'F': ['C', 'E']
  }
  print(bfs(graph, 'A'))  # 결과: {'A', 'B', 'C', 'D', 'E', 'F'}

---

언제, 어떤 탐색 알고리즘을 선택할까요?

• 빠른 탐색이 필요하고 DATA가 정렬되어 있다면? → 이진 탐색
• 구조화된 DATA를 탐색해야 한다면? → DFS 또는 BFS
• 작은 DATA를 다룬다면? → 선형 탐색

---

😊 마무리하며..

탐색 알고리즘은 DATA 구조와 함께 사용되며, 효율적인 DATA 처리를 위해 필수적인 기술이에요. 오늘 배운 내용을 바탕으로 여러분도 직접 코드를 작성해보세요! 여러분의 코딩 여정을 항상 응원합니다. 🚀