[Algorithm] 01.알고리즘 완전탐색

완전탐색이란?

완전탐색이란, 모든 경우의 수를 통한 해결 방법입니다. 기본적으로는 브루트 포스(Brute Force)라고도 합니다. 상대적으로 간단한 방법이지만 경우의 수가 많으면 많아질수록 시간이 오래 걸린다는 단점이 있습니다. 그래도 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻을 수 있는 기초적인 방법입니다.

 

* 경우의 수에 따라서 실행 시간이 비례할 수 있기 때문에 입력 값의 범위가 작은 경우에 유용하게 사용됩니다.

완전탐색 기법 - 코딩 테스트

1. 가능한 모든 경우의 수, 방법을 고려해야 합니다.
2. 해결할 문제의 가능한 만큼 경우의 수를 계산해 봅니다.
3. 실제로 답을 구할 수 있는지 적용해 봅니다.

완전탐색 종류

탐색 알고리즘에는 선형 탐색, 이진 탐색, 완전 탐색 총 3가지 큰 분류로 나눌 수 있습니다.

그중에 완전 탐색 알고리즘이 어떤 종류로 존재하는지 알아보겠습니다.

1. 브루트 포스(Brute Force)
   • 단순하게 반복문과 조건문으로 모든 경우의 수를 확인해서 해결합니다.
   • 이 방법으로는 해결할 수 있는 문제가 많지 않으며, 문제의 일부분을 해결할 경우에 사용됩니다.
   • 경우의 수가 많을 경우에 시간이 오래 걸린다는 단점이 있습니다.
2. 비트마스크(Bitmask)
   
   • 모든 경우의 수를 이진수로 표현하고 비트 연산을 통해서 원하는 결과를 빠르게 얻는 알고리즘입니다.
   • 나올 수 있는 모든 경우의 수가 각각의 원소를 포함하거나, 포함하지 않는 두 가지 선택으로 나뉠 경우에 사용합니다.
   • 이진수 연산을 이용하기 때문에 계산 속도가 빠르나, 경우의 수가 많아질수록 메모리 사용량이 늘어납니다.
3. BFS(너비 우선 탐색)/DFS(깊이 우선 탐색) 
   1. BFS(Breadth-First Search, 너비 우선 탐색)
      • 하나의 노드를 방문 후에 인접한 모든 노드에 우선 방문합니다.
      • 그래프 탐색의 경우에는 어떤 노드를 방문했었는지를 반드시 검사하고, 검사하지 않았다면 무한 루프됩니다.
      • BFS는 방문한 노드들을 차례로 저장하고 꺼낼 수 있는 큐를 사용해서 구현합니다.
      • 두 노드 사이의 최단 경로 및 임의의 경로를 찾고 있을 때 사용합니다.
      • 최악의 경우, 모든 노드를 방문해야 하기 때문에 시간이 오래 걸립니다.
      • 재귀함수를 사용하지 않습니다.
   2. DFS(Depth-First Search, 깊이 우선 탐색)
      • 그래프 탐색의 경우에는 어떤 노드를 방문했었는지를 반드시 검사하고, 검사하지 않았다면 무한 루프됩니다.
      • 하나의 노드를 방문 후에 그 노드의 모든 자식(level) 노드를 우선 방문합니다.
      • 모든 노드를 방문할 때 사용합니다.
      • BFS보다 간단하게 구현할 수 있지만 검색 속도가 느립니다.
      • 최악의 경우, 모든 노드를 방문해야 하기 때문에 시간이 오래 걸립니다.
      • 재귀함수를 사용해서 구현합니다.
4. 순열(Permutation)
   
   • 순열은 서로 다른 N개의 원소를 일렬로 나열하는 방법입니다.
   • 시간 복잡도가 높은 편( O(N!) )이어서 n이 한 자릿수 경우일 때 고려합니다.
   • 경우의 수가 적을 때 사용하면 유용하나, 많은 경우 시간이 오래 걸립니다.
5. 재귀함수
   • 재귀함수는 자기 자신을 호출하는 함수입니다.
   • 호출된 함수 스택에 저장, 호출 완료 시 스택에서 삭제됩니다.
   • for, while과 같은 반복 코드를 간결하게 구현할 수 있습니다.
   • 재귀 탈출 조건이 없는 경우에 재귀함수는 계속해서 자기 자신을 호출하는 무한 루프에 갇혀 스택 오버 플로우가 발생합니다.
   • 재귀 탈출 조건을 적어주거나 재귀 발생 횟수를 정한 후 사용해야 합니다.
   • 스택 오버플로우가 발생할 가능성이 있습니다.
6. 백트래킹(Backtracking)
   • 결과를 얻기 위해 진행하는 도중에 '막히게 되면' 그 지점으로 돌아가서 '다른 경로를 탐색'하는 방식입니다.
   • 경우의 수를 줄이면서도 모든 경우를 탐색할 수 있습니다.
   • 재귀 함수를 이용하기 때문에 스택 오버플로우가 발생할 수 있습니다.

브루트 포스란 (Brute Force)?

브루트 포스란, 사전적 정의로 Brute : 난폭한, Force : 힘 으로 난폭한(무식한) 힘이라고 합니다.

즉, 완전 탐색 알고리즘에서 모든 경우의 수를 모두 탐색하면서 요구조건에 충족하는 결과만을 조회할 수 있습니다. 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS), 너비 우선탐색(BFS), 백트래킹이 가장 기본적입니다.

어떤 방법으로 해도 전체 탐색 알고리즘은 브루트 포스 알고리즘으로 해결했다고 봐도 무방합니다.

 

모든 경우의 수를 전부 탐색하기 때문에 문제 해결은 정확하지만, 전부 탐색하기 때문에 높은 시간 복잡도를 가지게 됩니다.

 

완전탐색과 브루트 포스는 같은 의미로 볼 수 있지만, 완전 탐색 알고리즘은 모든 경우의 수를 전부 탐색하는 알고리즘으로 결과보단 과정에 중점을 둡니다. 하지만 브루트 포스 알고리즘은 문제를 해결하기 위해 모든 경우의 수를 전부 탐색하고 답을 찾는 결과에 중점을 둡니다.

브루트 포스의 장·단점

• 장점
  • 알고리즘을 설계하고 구현하기가 매우 쉽습니다.
  • 복잡한 알고리즘 없이 빠르게 구현할 수 있습니다.
• 단점
  • 알고리즘의 실행 시간이 매우 오래 걸립니다.
  • 메모리 효율성이 매우 비효율적입니다.

완전 탐색의 시간 복잡도

다음은 빅오 표기법을 통해 시간 복잡도가 효율적인 알고리즘 표입니다.

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

Ref.

https://adjh54.tistory.com/196

https://hawaiian-pizza-it.tistory.com/39