Exhaustive Search(완전 탐색)

완전 탐색

모든 경우의 수를 다 체크해서 정답을 찾는 방법

 

Brute force

• 단순히 반복문과 조건문으로 모든 경우를 만들어 답을 구하는 방법

 

Bitmask

• 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우 유용하게 사용
• ex) '원소가 n개인 집합의 모든 부분 집합'을 구한다면, 각 원소가 포함되는지 포함되지 않는 지를 0, 1로 구분하여 배열에 저장해둘 수 있음.

 

재귀 함수

• 비트마스크와 마찬가지로 각 원소가 두 가지 선택지를 가질 때 유용하게 사용
• 포함이 되면 해당 원소를 넣어 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출하는 등의 식
• ex) 피보나치 수열

 

순열

• 서로 다른 N개를 일렬로 나열하는 방법(경우의 수)를 말함.
• 순열의 경우의 수는 N!으로, 완전 탐색을 이용하기 위해서는 N이 한자리 수는 되어야 함.
• 순열에 원소를 하나 씩 채워가는 방식
• 재귀 함수 이용 or C++의 next_permutation() 함수 이용

 

BFS / DFS

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

하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문하는 방식

• 루트 노드 또는 임의 노드에서 인접한 노드부터 먼저 탐색하는 방법
• 최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합
• 큐를 통해 구현
• 시간 복잡도
  • V는 접점, E는 간선
  • 인접 행렬: $O(V^2)$
  • 인접 리스트: $O(V+E)$

 

깊이 우선 탐색(Depth-First Search, DFS)

트리의 한 요소(노드)와 다음 수준(level)의 자식 노드를 따라가는 방향으로 탐색하는 방식

• 스택 or 재귀함수를 통해 구현
• 시간 복잡도
  • V는 접점, E는 간선
  • 인접 행렬: O(V^2)
  • 인접 리스트: O(V+E)
• 길 찾기 등에 주로 쓰이는 알고리즘
  • 단순 길 찾기에는 BFS/DFS만 써도 무방하지만, 장애물이 존재하는 등 추가적 연산이 필요할 때 완전 탐색을 병행하기도 함.

 

📍 ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현하고 A와 B 사이에 존재하는 경로 찾을 때

• DFS: 모든 친구 관계를 다 살펴야 한다.
• BFS: A와 가까운 관계부터 탐색한다.