탐색 알고리즘

탐색 알고리즘

특정 데이터를 많이 가지고 있을 때, 원하는 데이터를 찾는 방식

 

난이도별 종류

 

이외 많은 탐색 알고리즘이 존재

난이도	알고리즘
초급	선형 탐색, 이진 탐색, DFS, BFS
중급	이분 탐색 트리, 다익스트라 알고리즘, A* 알고리즘
고급	유전 알고리즘, 몬테 카를로 트리 탐색

 

 

기초 탐색 알고리즘 한눈에 보기

 

탐색 알고리즘	시간 복잡도 [최고 평균 최악]	장점	단점
선형탐색	O(1)/O(n)/O(n)	• 구현이 간단 • 정렬되지 않은 데이터에서도 사용 가능 • 데이터의 순서에 영향을 받지 않고 동작	• 큰 데이터 세트에서 성능이 저하 • 다른 탐색 알고리즘에 비해 느린 속도
이진탐색	O(1)/O(log n)/O(log n)	• 빠른 속도와 메모리 효율적인 알고리즘 • 정렬된 데이터에서 원하는 값을 빠르게 찾을 수 있음	• 데이터 수정이 빈번할 때 사용하기 어려움 • 데이터가 정렬되어 있지 않은 경우에는 사용할 수 없음
DFS	*노드 수 (V)와 간선 수 (E)에 비례 인접 리스트 : O(1)/O(V + E)/O(V + E) 인접 행렬 : O(V^2)/O(V^2)/O(V^2)	• 적은 메모리 사용	• 최단 경로를 보장하지 않음 • 트리의 깊이가 깊을 수록 성능 저하 • 완전 탐색의 경우 BFS보다 성능이 떨어짐
BFS	인접 리스트 : O(1)/O(V + E)/O(V + E) 인접 행렬 : O(V + E)/ O(V + E)/O(V^2)	• 최단 경로를 보장	• DFS보다 많은 메모리 소요
이진 탐색 트리	O(log n)/O(log n)/O(n)	• 탐색, 삽입, 삭제 연산이 빠름 • 데이터가 정렬된 구조로 저장되어 있어 범위 검색이 용이	• 트리가 편향되는 경우 성능 저하
해시 탐색	O(1)/O(1)/O(n)	• 빠른 검색 속도를 제공 • 데이터를 효율적으로 저장하고 관리 가능	• 충돌이 자주 발생하는 경우 성능 저하가 발생

 

---

 

선형 탐색과 이진 탐색

선형 자료구조(배열, 리스트)에 사용한다.
기초적인 데이터 검색 알고리즘으로 프로그래밍을 시작하거나 기초 알고리즘을 이해하는데 중요하다.

 

알고리즘	장점	단점
선형 탐색	정렬되지 않은 리스트에 사용가능	데이터량이 많을수록 비효율적
이진 탐색	로그복잡도를 보장, 효율적	정렬되지 않은 리스트에 사용 불가

 

선형 탐색(Linear Search)

• 맨 앞이나, 맨 뒤부터 순서대로 하나하나 찾아보는 알고리즘이다.
• 가장 단순하고 간단한 탐색 알고리즘이다.
• 시간 복잡도 : O(n)

 

동작
1. 맨 끝부터 하나하나 원하는 값을 찾아본다.
2. 원하는 값을 찾으면, 탐색을 종료한다.

 

장점

• 단순하여 구현이 굉장히 쉬움,
• 정렬되지 않은 리스트에서도 사용 가능

 

단점

• 검색할 리스트의 길이가 길면 길수록 비효율적

 

 

---

이진 탐색(Binary Search)

• 중간지점을 기준으로 데이터를 반씩 나눠서 탐색하는 알고리즘이다.
• 시간복잡도 : O(log n)

 

동작
1. 먼저 배열의 중간 값이 찾는 값과 일치하는지 확인한다.
2. 일치하지 않을 경우 내가 찾으려는 값과 중간 값의 대소를 비교한다.
3. 만약 내가 찾으려는 값이 중간값보다 크면 해당 배열의 왼쪽 반만 취한다.
4. 취한 배열을 가지고 다시 1번부터 값을 찾을 때까지 반복한다.

 

장점

• 데이터 집합의 크기에 비례하지 않고 로그 시간에 탐색을 수행해 매우 효율적

 

단점

• 데이터가 정렬되어 있어야 하므로, 정렬되지 않은 데이터에 대해서는 추가 작업이 필요
• 데이터 집합이 크거나 빈번한 삽입 및 삭제 작업이 있는 경우에는 비효율적

 

---

 

DFS와 BFS

비선형 자료구조(그래프, 트리)에 사용한다.
그래프 탐색의 기초 알고리즘이다.

• 그래프 혹은 트리에서 모든 노드를 한 번씩 탐색한다.
• 완전 탐색(모든 경우의 수를 시도하는 방법)을 수행하는 알고리즘이다.

 

알고리즘	검색 목적	장점	단점
DFS	목표 노드 찾기	적은 메모리 사용	최적 해라는 보장 없음
BFS	최단 경로 찾기	항상 최적 해임을 보장	노드 수가 많을 수록 메모리 사용 증가

깊이 우선 탐색(DFS)

• 스택 자료구조나 재귀함수를 사용해 구현한다.
• 시간 복잡도 : O(V + E)(V는 노드 수, E는 간선 수)

 

동작
1. 시작 노드에서 출발하여, 해당 노드의 자식 노드를 순차적으로 탐색
2. 탐색 중 방문한 노드는 스택(Stack)에 저장하거나 재귀 호출을 통해 처리
3. 현재 노드에서 더 이상 자식 노드를 탐색할 수 없을 때, 되돌아와서 이전 노드의 다른 자식 노드를 탐색
4. 스택이 비거나 모든 노드를 방문할 때까지 반복

 

 

장점

• 간단하고 직관적인 구조로 구현이 쉬움
• 재귀함수를 활용하면 코드가 간결해짐
• 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용

 

단점

• 모든 경로를 탐색하기 때문에 그래프가 순환 구조일 경우 무한 루프에 빠질 수 있음
• 목표에 이르는 경로가 다수인 경우, DFS는 해에 도착하면 탐색을 종료하기에 얻어진 해가 최단 경로라는 보장이 없음.

 

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

• 가까운 노드부터 순차적으로 탐색하는 방식으로 동작한다.
• 큐 자료구조를 사용해 구현한다.
• 시간 복잡도 : O(V + E)

 

동작
1. 시작 노드에서 출발하여, 해당 노드와 인접한 모든 노드를 우선 탐색
2. 탐색 중 방문한 노드는 큐(Queue)에 저장
3. 큐에서 하나의 노드를 꺼내어 해당 노드와 인접한 노드를 탐색
4. 모든 인접 노드를 탐색한 후, 큐에서 다음 노드를 꺼내어 반복
5. 큐가 비거나 모든 노드를 방문할 때까지 반복

장점

• 답이 되는 경로가 여러 개인 경우에도 최단 경로를 보장

 

단점

• DFS에 비해 구현이 다소 복잡
• 노드의 수가 많을수록 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간(메모리)을 필요로 하게 됨.

 

---

+다익스트라 알고리즘과 BFS

공통점

• 최단 경로를 찾기 위해 사용

 

차이점

• BFS는 간선의 비용이 동일할 때 최단 거리 문제를 해결하기 위해 사용
• 다익스트라는 간선의 비용이 서로 다를 수 있을 때 사용

 

---

다익스트라 알고리즘

• 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다.
• 주로 가중치가 있는 그래프에서 사용한다.
• 특정 노드에 대하여 최단 거리값이 갱신될 수 있다.
• 선형 탐색이나 우선순위 큐로 구현한다.

 

장점

• 최단 경로를 찾는 데 효과적
• 양의 가중치만 다루는 경우에 사용

 

단점

• 음의 가중치를 가진 그래프에는 사용할 수 없음, 이 경우 벨만-포드 알고리즘을 고려
• 그래프가 크고 밀집된 경우 성능 저하가 발생

 

---

이진 탐색 트리, 해시 탐색

검색 알고리즘을 더 빠르고 더 효율적으로 만들기 위해 구성된 데이터베이스를 사용

이진 탐색 트리(BST / Binary Search Tree)

• 이진트리 자료구조를 이용
• 시간 복잡도: 최선 O(log n), 최악 O(n) 

 

• 다음과 같은 조건을 만족해야 함

1. 각 노드는 최대 두 개의 하위 노드(왼쪽 서브 트리 및 오른쪽 서브 트리)를 가짐
2. 각 노드의 왼쪽 서브 트리의 모든 요소는 해당 노드의 값보다 작음
3. 각 노드의 오른쪽 서브 트리의 모든 요소는 해당 노드의 값보다 큼
4. 중복 요소가 허용되지 않음

동작
1. 루트노드를 기준으로 시작
2. 원하는 값보다 노드 값이 작으면 오른쪽 서브트리로 이동
3. 원하는 값보다 노드 값이 크면 왼쪽 서브트리로 이동
4. 2-3 과정 반복, 원하는 값과 노드 값이 같으면 종료

 

장점

• 평균 시간 복잡도가 O(log n)으로 매우 효율적인 탐색 작업을 제공
• 데이터의 삽입 및 삭제가 빠르고 간단
• 정렬된 데이터를 유지하며 데이터를 추가하거나 삭제할 수 있음
• 트리 구조를 이용한 다양한 연산 및 탐색이 가능

 

단점

• 트리가 불균형하게 성장하는 경우, 최악의 경우 시간 복잡도가 O(n)
• 최소 또는 최댓값을 찾는 연산이 O(n)의 시간이 걸릴 수 있음

 

 

해시 탐색(Hash Search) or 해시 테이블(Hash Table)

• 데이터를 효율적으로 저장하고 검색하기 위한 자료구조 중 하나
• 해시 탐색은 해시 함수를 사용하여 데이터를 키와 연결시키고, 해당 키를 이용하여 데이터에 빠르게 접근하는 방식으로 동작
• 시간 복잡도 : 최선 O(1) , 최악 O(n)

 

동작
1. 데이터를 해시 함수를 사용하여 고유한 키(해시 값)로 매핑
2. 해시 값을 이용하여 데이터를 저장하거나 검색

• 해시 함수는 데이터의 내용으로부터 해시 값을 생성하는데, 같은 데이터에 대해 항상 동일한 해시 값을 반환해야 함

장점

• 매우 빠른 검색 속도를 제공
• 해시 함수를 통해 데이터에 상수 시간 안에 접근할 수 있음
• 키와 데이터가 일대일 대응 관계를 가지므로 중복 키가 허용되지 않음
• 데이터의 삽입, 삭제, 검색이 빠르고 효율적

 

단점

• 서로 다른 데이터가 동일한 해시 값에 매핑될 경우 충돌이 발생
• 부적절한 해시 함수 선택은 성능 저하를 야기
• 해시 테이블은 메모리 공간을 많이 차지

 

---

참고자료

[알고리즘] 탐색 알고리즘 (선형, 이분, 해시, BST)
알고리즘 기초(선형탐색)
이진 탐색 (Binary Search)
[Python] DFS & BFS
[자료구조] 해시테이블(HashTable)이란?