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