완전탐색이란 가능한 모든 경우의 수를 모두 탐색하여 정답을 찾아내는 방법을 말한다.
예를 들어, 4자리 비밀번호 자물쇠가 있다고 가정해보자!
비밀번호를 잊어버렸을 때, 자물쇠를 풀기 위한 가장 확실한 방법은 0000부터 9999까지 모든 조합을 하나씩 확인해보는 것이다.
(최대 10,000번의 시도로 해결 가능)
이처럼 완전탐색은 모든 경우를 빠짐없이 확인하므로 정확한 답을 얻을 수 있다.
하지만 경우의 수가 많아질수록 제한 시간 내에 문제를 해결하기 어려워질 수도 있다.
완전탐색 기법
Brute-Force
단순히 반복문과 조건문을 통해 가능한 모든 경우를 탐색하며 답을 구하는 방법이다.
위의 4자리 비밀번호 자물쇠를 푸는 방법을 Brute-Force로 구현해보면 다음과 같다.
function bruteForce() {
for (let i = 0; i < 10000; i++) {
const password = String(i).padStart(4, "0");
console.log(password);
}
}
bruteForce();순열
n개의 값 중에서 r개의 숫자를 순서대로 뽑는 경우의 수를 순열이라고 한다.
예를 들어, [1, 2, 3] 배열에서 3개의 값 중에서 2개의 숫자를 순서대로 뽑는 경우는 다음과 같이
1, 2
1, 3
2, 1
2, 3
3, 1
3, 2총 6개의 순열이 있다.
순열을 공부할 때 풀기 좋은 문제는 LeetCode의 46. Permutations 문제를 추천한다.
재귀
재귀는 함수가 자기 자신을 호출하여 문제를 해결하는 방법이다. 반복적인 문제를 해결할 때 유용하게 사용되며, 종료 조건을 명확하게 설정하는 것이 중요하다.
예를 들어, 팩토리얼을 구하는 문제는 재귀를 통해 간단하게 해결할 수 있다.
function factorial(n) {
if (n === 0) return 1;
return n * factorial(n - 1);
}
console.log(factorial(5)); // 120비트마스크
비트마스크는 0과 1을 비트 연산을 통해 문제를 해결하는 기법으로, 원소가 포함되거나 포함되지 않는 두 가지 선택이 있는 경우에 유용하다.
BFS, DFS
BFS와 DFS는 그래프나 트리 구조에서 탐색을 할 때 사용하는 알고리즘이다. 두 알고리즘은 기본적으로 탐색 방식에서 차이가 있다.
BFS(Breadth-First Search)
BFS는 너비 우선 탐색으로, 시작 노드에서 가까운 노드부터 탐색을 시작하고 점차적으로 더 멀리 있는 노드로 탐색을 진행한다.
즉, 최단 경로를 찾을 때 유용하며 큐를 사용하여 구현할 수 있다.
DFS(Depth-First Search)
DFS는 깊이 우선 탐색으로, 한 방향으로 끝까지 탐색을 진행한 후, 더 이상 갈 곳이 없으면 되돌아가서 다른 경로를 탐색한다.
즉, 경로를 찾는데 유리하며, 그래프에서 모든 경로를 탐색해야 하는 문제에서 유용하다. 재귀 또는 스택을 사용하여 구현할 수 있다.
