[Algorithm] 완전탐색 (Exhaustive Search)

완전탐색

 

모든 경우의 수를 고려하는 탐색 알고리즘.

 

완전탐색의 종류

• 브루트 포스 : for문을 이용하여 처음부터 끝까지 탐색하는 방법
• 비트 마스크 : 이진수 표현을 자료구조로 쓰는 기법 (AND, OR, XOR, SHIFT, NOT)
• 백트래킹 : 분할정복을 이용한 기법, 재귀함수를 이용, 해를 찾아가는 도중에 해가 될 것 같지 않은 경로가 있다면 더 이상 가지 않고 되돌아간다.
• 재귀함수 : 함수 내에서 함수 자기 자신을 계속해서 호출하는 것
• 순열 : 서로 다른 n개의 원소에서 r개의 중복을 허용하지 않고 순서대로 늘어 놓은 수
• BFS(너비 우선 탐색)
• DFS(깊이 우선 탐색)

 

관련 문제

완전탐색(재귀 + 순열) : 프로그래머스 소수 찾기 (programmers.co.kr/learn/courses/30/lessons/42839)

순열(permutation)을 통해 수를 만들 수 있는 모든 경우를 고려해주어야 하는 문제

- 중복을 제거해야하므로 보통 Set과 함께 사용한다.

- swap 사용하여 순열 구현하기

출처: https://siyoon210.tistory.com/76

1. 0번째 인덱스 원소를, 0번째 부터 n-1번째까지 위치를 바꾼다.
2. 1번 과정을 진행해서 나온 경우들을, 1번째 인덱스 원소를, 1번째 부터 n-1번째까지 위치를 바꾼다.