[Java/알고리즘] 완전 탐색(Exhaustive Search) 이해하기 -1 : 정의 및 종류

반응형

 
 

해당 글에서는 탐색 알고리즘 중에서 완전 탐색 알고리즘에 대해 이해하고 각각의 종류에 대해 이해 및 시간 복잡도에 대해 확인해 봅니다.

 
 

1) 완전 탐색(Exhaustive Search)

---

💡 완전 탐색(Exhaustive Search)이란?

- ‘모든 가능한 경우의 수를 탐색’하여 ‘최적의 결과를 찾는 방법’을 의미합니다.

- 모든 가능성을 고려하기 때문에 항상 최적의 해를 찾을 수 있지만 경우의 수가 매우 많은 경우 시간과 메모리의 부담이 커질 수 있습니다. 그렇기에 문제의 특성에 따라 다른 탐색 기법을 사용하는 것이 좋습니다.

 
 

2) 완전 탐색의 종류

---

 💡완전 탐색의 종류

- 탐색 알고리즘 중에서 '완전 탐색'에 대해 이해하고 각각의 탐색 종류에 대해서 이해합니다.

알고리즘 종류	설명	장점	단점
브루트 포스	‘모든 경우의 수를 탐색’하면서 원하는 결과를 얻는 알고리즘을 의미합니다.	가능한 모든 경우를 다 검사하기 때문에 예상된 결과를 얻을 수 있음	경우의 수가 많을 경우 시간이 오래 걸림
비트마스크	‘모든 경우의 수를 이진수로 표현‘하고 ‘비트 연산’을 통해 원하는 결과를 빠르게 얻는 알고리즘을 의미합니다.	이진수 연산을 이용하여 계산 속도가 빠름	경우의 수가 많아질수록 메모리 사용량이 늘어남
백트래킹	결과를 얻기 위해 진행하는 도중에 ‘막히게 되면’ 그 지점으로 다시 돌아가서 ‘다른 경로를 탐색’하는 방식을 의미합니다. 결국 모든 가능한 경우의 수를 탐색하여 해결책을 찾습니다.	경우의 수를 줄이면서도 모든 경우를 탐색할 수 있음	재귀 함수를 이용하기 때문에 스택 오버플로우가 발생할 가능성 있음
순열	‘순열을 이용하여 모든 경우의 수를 탐색‘하는 방법입니다. 순열은 서로 다른 n개 중에서 r개를 선택하여 나열하는 방법을 의미합니다	경우의 수가 적을 때 사용하면 유용함	경우의 수가 많을 경우 시간이 오래 걸림
재귀함수	‘자기 자신을 호출‘하여 모든 가능한 경우의 수를 체크하면서 최적의 해답을 얻는 방식을 의미합니다.	코드가 간결하며, 이해하기 쉽습니다.	스택 오버플로우가 발생할 가능성이 있음
DFS/BFS	깊이 우선 탐색(DFS: Depth-First Search) - 루트 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 의미합니다. 너비 우선 탐색(Breadth-First Search: BFS) - 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법을 의미합니다.	미로 찾기 등에 유용함	최악의 경우, 모든 노드를 다 방문해야 하므로 시간이 오래 걸림

 
 

💡 [참고] 탐색 알고리즘 중 ‘선형 탐색’과 ‘이진 탐색’에 대해서 궁금하시면 아래의 글을 참고하시면 크게 도움이 됩니다.

[Java/알고리즘] 선형 탐색(Linear Search) 이해하기

[Java/알고리즘] 이진/이분탐색(Binary Search) 이해하기

 
 
 

3) 완전 탐색의 시간 복잡도

---

💡 완전 탐색의 시간 복잡도

- 빅오 표기법으로 확인하는 시간 복잡도에 따른 효율적인 알고리즘 순서

- 비트마스크 > DFS/BFS > Brute-Force > 재귀함수 > 순열 > 백트래킹

알고리즘	시간 복잡도
브루트 포스	O(nm)
비트마스크	O(2^n * n)
백트래킹	최악의 경우, O(n!)
순열	O(n!)
재귀함수	O(n)
DFS/BFS	O(V+E)

 

 [ 더 알아보기 ]

💡 시간 복잡도(Time Complexity)란?

- 알고리즘이 실행될 때 필요한 ‘입력 값’과 ‘연산 수행 시간’에 따라 효율적인 알고리즘을 나타내는 척도를 의미합니다.

 

💡 [참고] 빅오 표기법에 대해 궁금하시면 아래의 글을 참고하시면 도움이 됩니다.

[Java/알고리즘] 시간 복잡도, 공간 복잡도, 빅오 표기법 이해하기

 
 
 
 

💡 해당 글은 다음 글에서 이어집니다.

[Java/알고리즘] 완전 탐색(Exhaustive Search) 이해하기 -2 : 종류 별 이해

 
 

💡 [참고] 좀 더 다양한 알고리즘에 대해 알고 싶으시면 아래의 글을 참고하시면 도움이 됩니다.

알고리즘 종류	설명	장점	단점
브루트 포스	‘모든 경우의 수를 탐색’하면서 원하는 결과를 얻는 알고리즘을 의미합니다.	가능한 모든 경우를 다 검사하기 때문에 예상된 결과를 얻을 수 있음	경우의 수가 많을 경우 시간이 오래 걸림
비트마스크	‘모든 경우의 수를 이진수로 표현‘하고 ‘비트 연산’을 통해 원하는 결과를 빠르게 얻는 알고리즘을 의미합니다.	이진수 연산을 이용하여 계산 속도가 빠름	경우의 수가 많아질수록 메모리 사용량이 늘어남
백트래킹	결과를 얻기 위해 진행하는 도중에 ‘막히게 되면’ 그 지점으로 다시 돌아가서 ‘다른 경로를 탐색’하는 방식을 의미합니다. 결국 모든 가능한 경우의 수를 탐색하여 해결책을 찾습니다.	경우의 수를 줄이면서도 모든 경우를 탐색할 수 있음	재귀 함수를 이용하기 때문에 스택 오버플로우가 발생할 가능성 있음
순열	‘순열을 이용하여 모든 경우의 수를 탐색‘하는 방법입니다. 순열은 서로 다른 n개 중에서 r개를 선택하여 나열하는 방법을 의미합니다	경우의 수가 적을 때 사용하면 유용함	경우의 수가 많을 경우 시간이 오래 걸림
재귀함수	‘자기 자신을 호출‘하여 모든 가능한 경우의 수를 체크하면서 최적의 해답을 얻는 방식을 의미합니다.	코드가 간결하며, 이해하기 쉽습니다.	스택 오버플로우가 발생할 가능성이 있음
DFS/BFS	깊이 우선 탐색(DFS: Depth-First Search) - 루트 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 의미합니다. 너비 우선 탐색(Breadth-First Search: BFS) - 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법을 의미합니다.	미로 찾기 등에 유용함	최악의 경우, 모든 노드를 다 방문해야 하므로 시간이 오래 걸림

 
 
 
 
 
오늘도 감사합니다. 😀