완전 탐색 Brute Force
Brute : 무식한, Force : 힘
발생 가능한 모든 경우의 수를 전부 탐색하면서 조건에 맞는 답을 찾아내는 방법입니다.
모든 경우의 수를 확인하기때문에 100% 정답을 출력하지만 시간이 오래걸립니다.
종류
브루트 포스 Brute Force
반복문과 조건문을 사용하여 가능한 모든 방법을 단순하게 찾는 기법을 말합니다.
예를 들어 3자리로 구성된 자물쇠를 풀어야 한다면 000부터 999까지 모든 경우의 수를 입력하는 기법입니다.
비트 마스크 Bit Mask
비트 마스크는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하는 기법입니다.
2진수를 활용하기 때문에 문제에서 확인해야 하는 경우가 A 또는 B와 같이
두 가지 선택으로 구성되는 경우 유용한 방법입니다.백트래킹 Backtracking
백트래킹은 답을 찾는 과정에서 이 경로가 답이 아니라고 판단되면 버리고 다른 경로를 탐색하는 기법입니다.
가지치기(Pruning)라고도 표현하는데 불필요한 가지를 처내면서 답을 찾아내서 붙은 이름입니다.
보통 반복문의 횟수를 줄일 수 있어 효율적이지만 최악의 경우에는 여전히 완전 탐색을 하기 때문에
경로를 찾아 가지치는 방법이 효율성을 결정하게 됩니다.순열 Permutation
순열은 완전 탐색의 대표적인 유형으로 서로 다른 n개의 원소에서 r개를 중복 없이 골라 순서대로 나열하는 것입니다.
예를 들어, ABC가 주어지면 ABC, ACB, BAC, BCA, CBA, CAB가 모든 경우의 수 입니다.
재귀 함수, Recursion Function
재귀 함수는 자기 자신을 답을 찾을 때까지 반복적으로 참조하는 함수를 의미합니다.
직관적이고 간단하다는 장점이 있지만 자기 자신을 반복적으로 호출하는 과정에서 종료조건이 포함되거나 만족하지 못하면 무한루프에 빠질 수 있다는 위험성이 있으므로 종료조건을 고려해서 작성해야 합니다.
깊이우선탐색 DFS
먼저 깊이 우선 탐색( DFS, Depth-First Search )은 최대한 깊게 내려간 뒤, 더 이상 내려갈 곳이 없을 경우 옆으로 이동하는 방식입니다. 스택 또는 재귀함수로 구현합니다.
너비우선탐색 BFS
너비 우선 탐색 ( BFS, Breadth-First Search )은 최대한 넓게 이동한 다음, 더 이상 이동할 곳이 없을 때 아래로 이동하는 방식입니다. 큐를 이용해서 구현합니다.
정리
우선 지금은 완전 탐색에 대해 간단하게 알아보았고 추가적인 내용은 백준과 프로그래머스를 풀어가며 천천히 수준을 올린 후에 정리할 예정입니다.