목차
- 완전탐색 알고리즘
- 브루트포스
- 백트래킹
- 구현 기법
1. 완전탐색 알고리즘
가능한 경우의 수를 전부 확인하는 알고리즘
비밀번호의 조합같은 것으로 예시를 들 수 있습니다.
만약 비밀번호의 조건이 '4자리 숫자의 조합'일 경우
'0000'~'9999'까지 가능한 모든 경우의 수를 시도해보는 것이 완전탐색 알고리즘입니다.
시간적으로 비효율적이라 생각할 수 있으나 반드시 정답을 알수 있다는 것이 장점입니다.
2. 브루트포스
가장 기초적인 완전탐색 알고리즘입니다.
앞서 설명했던 비밀번호의 예시처럼 반복문(for)만을 사용해서 모든 경우의 수를 확인하는 방식입니다.
이때 중요한 점은 반복문을 진행하면서 확인여부를 거치지 않는 것입니다.
그렇기 때문에 부르트포스 알고리즘을 사용하기 위해서는 모든 경우의 수를 배열과 같이 형태로 표현할 수 있어야 합니다.
3. 백트래킹
'퇴각 검색'이라는 표현을 사용하기도 한다.
앞서 설명했던 모든 조건을 검사하는 것은 비슷하나 브루트포스와는 다르게 한정 조건에 대한 확인 여부를 거칩니다.
위에서 보여드렸던 예시에서 조건을 하나 추가해 보도록 하겠습니다.
'각 자리수의 숫자는 중복되어선 않된다.'
이런식으로 각 자릿수를 정할 시에 그 숫자를 이미 사용한 숫자인지 검사하는 과정이 추가됩니다.
4. 구현 기법
4-1. for
앞서 설명에서 나타난 것 처럼 모든 경우의 수를 순차적으로 확인해야 하는 상황에서 주로 사용됩니다.
4-2. 비트 마스크
이것 역시 주로 배열과 함께 사용됩니다.
하지만 순차적인 과정이 아니라 여러 개의 양자택일(Yes, No) 혹은 이진수로 나타내는 것이 필요한 과정에서 사용됩니다.
4-3. 재귀 함수
백트래킹 예시에서도 보여드렸듯이 N자릿 수를 정한 후 N+1자릿 수로 넘어가는 등, 지난 과정의 결과들이 이후 과정에 영향을 끼칠 때 주로 사용됩니다.
백트래킹의 제한조건을 설정할 때 매우 유용합니다.
4-4. 순열
'N개의 숫자 중 R개를 중복없이 골라 나열하는 방법의 수'라는 수학적 용어로 순열 자체를 구현하는 데에는 재귀함수가 쓰이며 같은 것으로 보일 수 있으나, 순열이라는 수학적 개념 자체가 백트래킹 구현에 큰 도움이 됩니다.
4-5. DFS
깊이 우선 탐색입니다.
아래의 그림은 wiki에서 그려진 백트래킹의 설명 그림입니다.
이런 식으로 나타낼 경우 각 leaf node를 하나의 경우의 수라고 생각할 수 있으며 DFS를 사용하면 각각의 경우의 수를 우선적으로 확인할 수 있습니다.
이런 개념은 재귀함수로 표현하기 용이하기 때문에 DFS는 재귀함수와 자주 사용됩니다.
