탐색 알고리즘 (브루트포스, DFS, BFS, 백트래킹)

 

 

탐색

• 데이터 구조 내에서 가능한 경우의 수를 탐색해 최적의 결과를 찾는 방법
• 선형 탐색 알고리즘
  • 순차적 탐색
  • 이진 탐색
• 비선형 탐색 알고리즘
  • 트리나 그래프 같이 복잡한 형태에 사용
  • dfs / bfs

 

 

1. 브루트 포스

• 완전 탐색
• 모든 경우의 수 탐색
• 단순하지만 경우의 수가 많아서 비효율적일 수 있다

 

2. DFS

출처 위키피디아

 

• 깊이 우선 탐색
• 그래프 또는 트리에서 모든 경로 탐색
• 한 방향으로 깊숙이 노드 탐색 후 더이상 갈 곳이 없으면 다른 방향 탐색
• 스택 / 재귀 함수 사용

 

3. 백트래킹

• DFS의 확장 개념
• 해결 가능성 없는 경로일 경우 탐색 중지하고 되돌아가 다른 경로 탐색

 

4. BFS

출처 위키피디아

 

• 너비 우선 탐색
• 시작 노드에서 가까운 노드부터 탐색
• 같은 깊이 층의 노드들 모두 탐색 후 층 내려가면서 탐색
• 큐 함수 사용
• 최단 경로 문제

 

알고리즘 선택 가이드

 

▣ 경로의 특징을 저장하는 문제 

• 예시: a부터 b까지 가는 경로를 구하는데, 경로에 같은 숫자가 있으면 안 되는 경우
• 알고리즘 ▶ DFS
  

▣ 최단 거리 문제

• 예시: 미로에서 출구까지의 최단 경로 찾기
• 알고리즘 ▶ BFS
  
  

▣ 조건에 만족하는 해결책을 찾아야 하는 문제

• 예시: N-Queens 문제, 조합이나 순열에서 특정 조건을 만족하는 경우를 찾는 문제
• 알고리즘 ▶ 백트래킹
  
  

▣ 모든 경우의 수를 검토해야 하는 문제

• 예시: 비밀번호 크래킹, 작은 규모의 데이터에서 모든 조합을 검토해 최적의 해를 찾는 경우
• 알고리즘 ▶  브루트포스

 

 

시간 복잡도

DFS	O(V+E)
BFS	O(V+E)
백트래킹	O(2ⁿ)
브루트포스	다양

 

 

 

 

 

*** 계속해서 업데이트 중입니다 ***