완전 탐색 #Brute Force #브루트 포스 [ 수정 내역 ] [ 수정 ]

최근 수정: 4년 전

1. 개요

영어로는 Brute Force. 가능한 모든 경우에 대해 완전히 탐색하는 것을 의미한다.

2. 상세

가능한 모든 경우에 대해 해보기 때문에 구현은 상대적으로 쉬우나 시간 효율이 매우 좋지 못하다. 가능한 모든 경우는 대략 조합이나 순열 형태이므로 시간복잡도가 기하급수적으로 증가한다. 하지만, 간단한 문제의 경우 완전 탐색이 굉장히 편하다.

3. 구현

여러가지 구현이 있을 수 있다. 재귀 함수(DFS)로 모든 경우를 다 해볼 수 있고 BFS로도 탐색이 가능한데, 주로 최단 거리 등을 찾는 경우는 BFS를 많이 사용한다.

4. 여담

삼성, 네이버, 카카오 등 IT/개발 회사 입사 코딩테스트 문제로 상당히 많이 출제되니 완전 탐색 정도는 마스터 해야 취업할 때 편할 것이다.