완전탐색(Brute-Force) 기법

완전탐색?

Brute(단순히,순전히)Force(힘): 순전히 힘으로 밀어붙이는 문제 해결 기법. 컴퓨터의 빠른 계산 능력을 사용하여 모든 경우의 수를 다 계산하는 것을 의미한다. ex) 4자리 비밀번호 풀기 -> 0000~9999까지 모두 대입해본다.

*효율성

완전탐색으로 문제를 해결할 수 있다는 것은 직관적으로 알 수 있지만, 그것이 효율적인 성능을 갖는다고는 보장할 수 없다. 그래서 문제를 풀 때 이 부분을 연습을 통해 판단하는 과정이 필요하다. 기본적으로 완전탐색은 N의 크기가 작은 문제를 해결할 때 사용한다.

완전탐색 기법에 활용되는 알고리즘

1. 단순 Brute-force 알고리즘
2. 비트마스크
3. 순열
4. 재귀
5. DFS, BFS

1. 단순 Brute-Force

반복문(for,while)을 이용하는 방법이다.

2. 순열

어떤 집합에서 원소를 뽑아 순서에 상관 있게 조합할 때 사용한다.
ex) 1,2,3,4에서 숫자 두개를 이용하여 만들 수 있는 수 중 가장 큰 수는? ->43

3. 비트마스킹

어떤 집합에서 어떤 원소가 존재하는지 판단하기 위해 정수를 이진수로 표현해 연산하는 것이다. 이진수에서 하나의 비트는 하나의 원소이다.
ex) {1,2,3,4,5}에서 {1,4} = 10010 / {1,2,3,4,5}에서 {2,5} = 01001

3-1. 비트연산자

주의할점
1. 비트연산자는 비교연산자보다 우선순위 낮기 때문에 () 꼭 사용하기
2. 시프트 연산(<<,>> 사용 시 오버플로우 생각하기

4. 재귀

어떤 집합에서 원소들을 탐색할 때, 특정 조건에 맞는 원소들을 뽑아낼 때 사용한다. n이 커서 반복문을 이용하면 시간을 초과해버리는 문제에서 사용할 수 있다.
주의할 점: 재귀함수 안에서 return을 이용한 탈출조건을 걸어주는 것이 중요하다

5. DFS/BFS

그래프 탐색을 통해 모든 원소를 탐색할 수 있다.