고고
알고리즘 - 탐색 (선형, 이진, DFS, BFS) 본문
탐색 알고리즘
탐색 알고리즘이란
탐색이란 주어진 데이터에서 원하는 데이터를 찾는 과정이다.
이 과정을 효율적으로 수행할 수 있도록 설계된 알고리즘을 탐색 알고리즘이라 한다.
탐색 알고리즘이 중요한 이유
주어진 데이터를 찾는데 얼마나 걸리는가를 결정한다. 컴퓨터의 메모리를 얼마나 잡아먹는지 탐색까지 얼마나 시간이 걸리는지가 중요하므로 효율적인 탐색을 위해서는 탐색 알고리즘이 중요하다. 뿐만 아니라 데이터처리, 문제해결, 경로 탐색 등 다양한 분야에서 성능을 확보할 수 있다.
따라서 여러 개의 탐색 알고리즘 중, 경우에 따라 최적화된 알고리즘을 선택하는 것도 중요하다.
실생활에서 사용되는 예시
- 내비게이션의 빠른 길 찾기 : 이동 비용이 적은 최적의 경로를 찾기 위해 BFS 알고리즘을 사용
- 포털 사이트 검색엔진 : 사용자가 입력한 단어와 가장 연관성 높은 결과부터 보여주기 위해 트리 탐색 사용
- 사전 찾기 : 검색된 단어의 순서에 따라 절반을 버리고 다시 범위를 좁혀나가는 식으로 이분탐색 사용
탐색 알고리즘의 종류
- 선형 탐색
- 이진 탐색
- 깊이 우선 탐색(DFS)
- 너비 우선 탐색(BFS)
선형 탐색 알고리즘(Linear Search)
- 주어진 데이터 집합에서 처음부터 끝까지 순차적으로 비교하며 데이터를 찾는 방법
- 순차탐색이라고도 한다.
- 시간 복잡도
- O(n) : 찾는 데이터가 가장 끝에 있는 경우 (또는 찾는 데이터가 배열에 없을 경우)
- 장점: 구현이 쉽고, 데이터가 정렬되어 있지 않아도 사용가능하다.
- 단점: 최악의 경우 배열의 처음부터 끝까지 다 탐색해야 하므로 많은 시간이 소요된다.(비효율적)
동작 원리
- 첫번째 데이터부터 차례대로 비교한다.
- 찾고자 하는 값이 있으면 해당 위치를 반환하고
- 끝까지 탐색해도 없으면 탐색 실패한다.
다음과 같은 데이터 집합이 있다면
[8, 1, 5, 9, 11]
5를 찾는다.
첫 번째 데이터인 8과 5를 비교 => 같지 않으므로 두 번째 데이터로 넘어감
두 번째 데이터인 1과 비교 => 같이 않으므로 세 번째 데이터로 넘어감
세 번째 데이터인 5와 비교 => 값이 일치하므로 탐색 성공
인덱스 2 반환
파이썬으로 구현하면 다음과 같다.
def linear_search(arr, target): # 배열 arr과 원하는 데이터를 담는 변수 target
for i in range(len(arr)): # 배열의 길이만큼 반복 (즉, 배열의 처음부터 끝까지)
if arr[i] == target: # 만약 찾는 값(target)과 배열의 값이 일치하면
return i # 해당 인덱스 반환
return -1 # 배열의 끝까지 찾지 못했다면 -1 반환
data = [10, 3, 154, 51, 13, 29]
print(linear_search(data, 51))
만약 찾는 값이 배열에 없다면
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1 # 배열의 끝까지 찾지 못했다면 -1 반환
data = [10, 3, 154, 51, 13, 29]
print(linear_search(data, 25)) # 배열에 없는 값 25를 탐색
-1을 반환했다
어떤 상황에서 사용하나?
- 크기가 작은 데이터 집합에서 유용하다.
- 정렬이 필요하지 않은 일회성 조회에 사용한다.
- 탐색하는 동안 조건식을 만족하는 요소가 처음/마지막으로 나타나는 곳을 찾을 때에도 사용할 수 있다.
- 자주 사용되는 항목을 앞에 배치함으로써 선형 탐색의 효율을 개선할 수 있다. (3가지 방법)
- 전진이동법 : 탐색된 요소를 데이터의 맨 앞으로 옮긴다.
- 전위법: 탐색된 요소를 바로 이전 항목과 교환한다.
- 계수법: 데이터의 각 요소가 탐색된 횟수를 임의의 공간에 저장해 두고, 탐색된 횟수가 높은 순으로 데이터를 재구성한다.
이진탐색 알고리즘(Binary Search)
- 정렬된 데이터 집합에서 중간 값을 기준으로 범위를 절반씩 줄여가며 찾는 방법
- 이분탐색이라고도 한다.
- 시간 복잡도
- O( log N ) : 배열의 크기가 n일때 중간 값을 반복적으로 계산한다.
- 장점: 선형탐색보다 시간이 매우 빠르고 효율적이다.
- 단점: 반드시 데이터가 정렬되어 있어야 사용할 수 있다.
동작 원리
- 배열의 중간 요소를 선택한다,
- 찾는 값과 비교하여
- 같으면 탐색 성공
- 중간 요소가 찾는 값보다 작으면 왼쪽 절반을 탐색한다.
- 중간 요소가 찾는 값보다 크면 오른쪽 절반을 탐색한다.
- 탐색 범위가 없을때까지 1~5를 반복한다.
다음과 같이 정렬된 데이터 집합이 있다면
[1, 5, 9, 12, 18, 23, 35]
찾는 값: 35
중간값 : 12
12와 35을 비교하여 찾는 값이 더 크므로 => 오른쪽 절반 탐색
오른쪽 절반에서 중간 값: 23
23과 35를 비교하여 찾는 값이 더 크므로 => 오른쪽 절반 탐색
오른쪽 절반에서 중간 값: 35
중간 값과 찾는 값이 같으므로
탐색 성공
파이썬으로 구현하면 다음과 같다.
def binary_search(arr, target): # 배열 arr과 찾는 데이터를 담는 변수 target
left, right = 0, len(arr) -1 # left는 0번째 인덱스를, right는 배열의 마지막 인덱스를 가리킨다.
while left <= right: # right가 가리키는 인덱스의 값이 left가 가리키는 인덱스의 값보다 클 동안
mid = (left+right) // 2 # 배열의 중간 인덱스를 계산
if arr[mid] == target: # 만약 중간 값이 찾는 값과 같다면
return mid # mid(인덱스 위치) 반환
elif arr[mid] > target: # 만약 중간 값이 찾는 값보다 크다면
right = mid - 1
else: # 중간 값이 찾는 값보다 작다면
left = mid + 1
return -1 # 배열 안에서 찾지 못했다면 -1 반환
data = [2, 4, 6, 7, 11, 14, 20, 28, 35] # 편의상 정렬된 데이터로
print(binary_search(data, 4))
찾는 값 4는 1번째 인덱스에 있으니 1을 반환한다. ( 찾는 값이 배열에 없다면 -1 반환 ).
만약 정렬되지 않은 데이터가 있다면 정렬하는 것이 우선이다.
밑의 코드는 정렬되지 않은 데이터를 정렬한 후, 이진탐색하는 코드이다.
def binary_search(arr, target): # 배열 arr과 찾는 데이터를 담는 변수 target
arr.sort() # 받은 데이터를 오름차순 한다.
print("데이터를 먼저 정렬합니다")
print("정렬된 데이터: ", arr)
left, right = 0, len(arr) -1
while left <= right:
mid = (left+right) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1
data = [1, 98, 12, 52, 30, 18, 22, 2, 4, 46] # 순서가 뒤죽박죽
print(binary_search(data, 4))
데이터를 오름차순 후, 이진탐색을 진행한다.
반복문으로 구현했는데 재귀함수로도 구현할 수 있다.
선형 탐색 vs 이진 탐색 비교
| 선형탐색 | 이진탐색 | |
| 데이터 정렬 | 안해도 됨 | 반드시 해야함 |
| 속도 | 비교적 느림 | 비교적 빠름 |
| 탐색 방식 | 앞에서부터 순차적으로 탐색 | 중간부터 절반씩 탐색 |
| 사용하기 좋은 상황 | 규모가 작고 비정렬 | 규모가 크고 정렬 |
깊이 우선 탐색 (DFS)
- 깊이 우선 탐색 (Depth-First Search)
- 그래프에서 깊은 부분을 우선적으로 탐색하는 방식
- 깊이 우선 탐색 시 스택을 이용하는데
- 방문한 노드를 스택에 저장한다.
- 가장 마지막으로 기록된 노드에 대해 탐색을 수행한다.
- 더 이상 탐색이 불가능한 경우 노드를 스택에서 제거하며 이전 노드로 돌아간다.
동작방식
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 스택에 삽입 후 방문 처리
- 2번의 과정을 더 수행할 수 없을 때까지 반복
시작 노드인 0번 노드를 스택에 담는다.
0번 노드를 꺼내 출력하고
인접 노드인 1번 노드를 스택에 담는다.
1번 노드를 꺼내 출력하고
인접 노드인 2와 3 노드를 스택에 담는다.
스택에 가장 마지막에 있던 3번 노드를 출력하고
인접 노드인 4와 5 노드를 스택에 담는다. (2번 노드도 3번 노드와 인접 노드지만 스택에 이미 있으므로 다시 추가하지 않는다.)
순서대로 5, 4, 2를 꺼내면서 출력한다.
(5를 출력하면서 인접노드를 다시 스택에 넣어야하는데 인접 노드가 없으므로 순서대로 출력한다.)
어떤 상황에서 사용하나?
- 미로 찾기 게임에서 가장 빠른 탈출구 검색
- 파일 시스템 검색 (하위 디렉터리를 포함한 모든 내용을 처리한 후 다음 디렉터리로 이동)
너비 우선 탐색 (BFS)
- 너비 우선 탐색 (Breadth-First Search)
- 그래프에서 가까운 노드부터 탐색하는 방식
- 너비 우선 탐색 시 큐를 이용하는데
동작방식
- 탐색 시작 노드를 큐에 삽입하고 방문처리
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 큐에 삽입하고 방문 처리
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
시작 노드인 0을 큐에 담는다.
0번 노드를 꺼내 출력하고
인접 노드인 1번 노드를 큐에 담는다.
1번 노드를 꺼내고
인접 노드인 2번, 3번 노드를 큐에 담는다
2번 노드를 꺼내고
인접 노드인 4번 노드를 큐에 담는다.
3번 노드를 꺼내고 인접 노드인 5번 노드를 큐에 담는다
4번 노드를 꺼내고 인접 노드가 없으니 큐에는 아무것도 담기지 않는다.
5번 노드를 꺼내고 인접 노드가 없으니 큐에는 아무것도 담기지 않는다.
어떤 상황에서 사용하나?
- 내비게이션 및 지도 애플리케이션의 최단 경로 안내
- SNS에서 가까운 친구 찾기
- 최소 단계의 수를 찾을 때 주로 사용
DFS와 BFS 비교
| 깊이 우선 탐색(DFS) | 너비 우선 탐색(BFS) | |
| 탐색 방식 | 깊이를 우선적으로 탐색 | 가까운 곳부터 탐색 |
| 사용하는 자료구조 | 스택 | 큐 |
| 특징 | 경로의 특징을 저장할 때 유용하다. | 최단 거리를 구할 때 유용하다. |
| 장점 | 메모리 사용이 상대적으로 적다 | 최단 경로를 보장한다. |
| 단점 | 최단 경로를 보장하지 않는다. (가장 먼저 발견한 해답이 최단거리가 아닐 수 있음) |
메모리 사용이 상대적으로 많다. (방문한 모든 노드를 큐에 저장) |
| 사용예시 | 미로찾기, 백트래킹, 트리 순회 | 최단 거리, 레벨 탐색 |
'과제' 카테고리의 다른 글
| 알고리즘 - 다익스트라 알고리즘 (0) | 2026.06.23 |
|---|---|
| 알고리즘 - 그리디 알고리즘 (0) | 2026.06.22 |
| 알고리즘 - 병합정렬, 퀵 정렬 + 재귀함수 (0) | 2026.06.11 |
| 알고리즘 - 기본정렬 (0) | 2026.06.11 |
| 자료구조 - 힙 (0) | 2026.06.09 |
