[Definition] 완전탐색

완전탐색

정의

Brute force, 즉 ‘무식하게 푼다’라는 의미를 가지고있는 알고리즘이다.

 

모든 경우를 체크하여 풀이하는 방식으로, 쉽고 확실하게 답을 찾을 수 있지만 시간이 많이 든다.

 

 

완전탐색의 종류

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

 

관련 문제

BOJ 2309번: 일곱난쟁이

BOJ 2231번: 분해합

BOJ 3085번: 사탕 게임

BOJ 10448번: 유레카 이론

BOJ 2503번: 숫자 야구

BOJ 1018번: 체스판 다시 칠하기

BOJ 10974번: 모든 순열

BOJ 1182번: 부분집합의 합