[C++]완전탐색

1. 완전탐색이란?

제목에서도 알 수 있듯이 가능한 모든 경우의 수를 탐색하는 것을 의미한다. 

알고리즘 문제에서는 크게 6가지 유형 정도가 있다. 

1)Brute Force

진짜 말 그대로 가능한 모든 방법을 단순히 찾는 방법이다. 

흔히 패턴매칭 같은 곳에서 사용되는데 예를 들어 txt파일에서 abcd라는 패턴을 찾을 때 텍스트 파일의 첫 번째부터 찾다가 패턴이 매치가 안되는 순간 두 번째로 이동하여서 다시 비교하고 아니라면 세번째 문자부터 시작하여 다시 비교하는 무식한 알고리즘을 의미한다. 또한 4자리의 비밀번호를 푸는 문제에서 brute force알고리즘을 적용하게 되면 

가능한 모든 경우의 수는 10 * 10 * 10 * 10 = 10000번을 비교해야 풀리는 그런 방식이다. 

 

2) 백트래킹

백트래킹은 그래도 brute force보다는 영리한 방법으로 현재 상태에서 가능한 경우의 수를 파악한 후 그 경우의 수로만 이동하는 알고리즘을 의미한다. 앞서 패턴 매칭을 예시로 들었는데 패턴이 틀리면 무조건 바로 다음 문자로 이동 후 다시 비교하던 brute force와는 다르게 접두사의 정보를 저장해두었다가 패턴이 틀렸을 때 같은 접두사가 접미사에 존재하는 경우 중간은 건너뛰고 접두사와 같은 접미사에서 다시 패턴 비교를 시작하는 KMP알고리즘과 같은 경우에 사용된다. 

흔히 우리가 일상에서 볼 수 있는 상황은 베스킨 라빈스 31과 같은 게임을 예시로 둘 수 있는데 만일 28까지 온 경우 외칠 수 있는 경우의 수는 29, 아니면 {29,30}이다. brute force보다는 조금 더 똑똑한 방식이라고 할 수 있다. 

 

3) 순열

순열은 뭐 수학시간에 많이들 해서 익숙할텐데 순열을 쉽게 c++로 구현하는 방법은 <algorithm>라이브러리를 include한 후 next_permutation함수를 이용하는 방법이다. 

 

4)비트 마스크

컴퓨터가 어떠한 연산을 할 때 2진수로 처리하는 것을 이용한 방식이다. 0과 1 즉 두 가지 상태에 대한 포함 문제를 이 방식으로 풀 수 있다. 

 

출처:&nbsp;https://velog.io/@yesjjin99/Algorithm-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89

어떠한 집합에 포함되는지의 여부를 1과 0으로 나타낼 수 있다.