[알고리즘] 완전탐색 | Brute Force, Permutation, Recursive, Bitmask, DFS / BFS

나윤빈·2024년 1월 10일

자료구조와 알고리즘

목록 보기

5/11

1. 완전탐색이란?

완전 탐색은 가능한 모든 경우의 수를 고려하는 탐색 알고리즘이다.

완전탐색은 무식하게 푼다는 의미로 "Brute Force" 라고도 부르며 직관적이기 때문에 이해하기 쉽고 정확한 결과값을 얻을 수 있는 가장 확실하고 기초적인 방법이지만, 경우의 수가 많이지면 그만큼 많은 시간이 걸린다는 단점이 있다.

예를 들면, 4자리의 암호로 구성된 자물쇠를 풀고자 할 때, 가장 확실한 방법은 0000부터 9999까지 가능한 모든 경우의 수를 시도해보는 것이다. 이러한 방법으로 암호를 풀 땐 최대 10,000번의 시도로 해결할 수 있다.

2. 완전 탐색의 종류

완전탐색 알고리즘의 종류는 다음과 같다.

브루트 포스 (Brute Force)
순열 (Permutation)
재귀 (Recursive)
비트마스크 (Bitmask)
깊이 / 너비 우선 탐색 (DFS / BFS)

1) 브루트 포스 (Brute Force)

브루트 포스는 반복문(for문)과 조건문(if문)을 사용하여 가능한 모든 방식을 단순하게 찾는 방법이다.

예시) 주어진 배열에서 두 수의 합이 특정한 값이 되는 두 수의 인덱스 찾기

function findSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [];
}

const numbers = [2, 7, 11, 15];
const targetSum = 9;

console.log(findSum(numbers, targetSum)); // [ 0, 1 ]

2) 순열 (Permutation)

순열은 요소들의 순서를 고려하여 가능한 모든 순서를 생성하는 방식이다.

순열에서 순서를 고려한다는 것은 [1, 2, 3]과 [3, 2, 1]은 같은 요소를 가진 배열이지만, 그 순서가 다르기 때문에 두 배열은 다른 것으로 본다는 것이다.

예시) 주어진 숫자로 모든 순열 생성하기

function permute(arr) {
  const result = [];

  // 재귀 함수 정의
  function generatePermutations(current, remaining) {
    // 만약 남은 요소가 없다면, 현재 순열을 결과에 추가하고 종료
    if (remaining.length === 0) {
      result.push(current.slice());
      return;
    }

    // 남은 요소에 대해 반복
    for (let i = 0; i < remaining.length; i++) {
      // 현재 순열에 다음 요소를 추가한 배열 생성
      const next = current.concat(remaining[i]);
      // 다음 순열에 대해 재귀 함수 호출하여, 현재 처리한 요소를 제외한 배열 생성
      const rest = remaining.slice(0, i).concat(remaining.slice(i + 1));
      // 재귀 호출을 통해 모든 가능한 순열 찾기
      generatePermutations(next, rest);
    }
  }

  // 초기 호출은 빈 배열과, 주어진 배열로 시작
  generatePermutations([], arr);

  // 최종적으로 모든 순열이 담긴 배열을 반환
  return result;
}

const array = [1, 2, 3];
const permutations = permute(array);

console.log(permutations); // [[ 1, 2, 3 ], [ 1, 3, 2 ], [ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ]]

concat() 메서드는 두 개 이상의 배열을 병합하는 데 사용되며, 이 메서드는 기존 배열을 변경하지 않고 새 배열을 반환한다.
slice() 메서드는 어떤 배열의 begin 부터 end 까지(end 미포함)에 대한 얕은 복사본을 새로운 배열 객체로 반환하며 원본 배열은 바뀌지 않는다.
begin 이 음수일 경우 배열의 끝에서부터의 길이를 나타내므로 slice(-2) 는 배열에서 마지막 두 개의 엘리먼트를 추출한다. 또한 begin이 undefined인 경우에는 0번 인덱스부터 slice 하고, begin이 배열의 길이보다 큰 경우에는 빈 배열을 반환한다.
end 가 음수일 경우 배열의 끝에서부터의 길이를 나타내므로 slice(2,-1) 는 세번째부터 끝에서 두번째 요소까지 추출한다. 또한 end가 생략되면 slice()는 배열의 끝까지(arr.length) 추출하고, end 값이 배열의 길이보다 크다면 slice()는 배열의 끝까지(arr.length) 추출한다.

3) 재귀 (Recursive)

재귀는 함수가 자기 자신을 호출하여 해결책을 찾아내는 방식이다.

재귀는 문제를 더 작은 부분으로 나누어 해결할 수 있다. 다만, 재귀를 종료하기 위한 종료 조건이 필요하며 스택 오버플로우에 주의해야 한다.

예시) 피보나치 수열

function fibonacci(n) {
    // 종료 조건: n이 0 또는 1일 때, n을 반환
    if (n === 0 || n === 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

const result = fibonacci(6);
console.log(result); // 8

피보나치 수열의 첫 번째 항은 0, 두 번째 항은 1 이며, 그 이후의 모든 항은 이전 두 항의 합으로 계산된다. ( 0,1,1,2,3,5,8,13,21,… )

4) 비트마스크 (Bitmask)

비트마스크는 이진수를 사용하여 집합의 부분집합을 나타내는 방식이다.

각 비트가 원소를 나타내며, 비트 연산을 통해 부분집합을 생성한다. 이는 모든 부분집합을 생성하거나 검사할 때 유용하다. 어떤 집합의 부분집합은 집합의 각 원소가 해당 부분집합에 포함되거나, 포함되지 않은 두 가지 경구만 존재하기 때문이다.

예시) 부분집합 구하기

function getSubsets(nums) {
  let arr = [1, 2, 3];
  let subsets = [];
  
  for (let i = 1; i < 1 << arr.length; i++) {
    subsets.push([]);
    for (let j = 0; j < arr.length; j++) {
      if (i & (1 << j)) subsets[i - 1].push(arr[j]);
    }
  }

  return subsets;
}

const numbers = [1, 2, 3];
const allSubsets = getSubsets(numbers);

console.log(allSubsets); // [ [ 1 ], [ 2 ], [ 1, 2 ], [ 3 ], [ 1, 3 ], [ 2, 3 ], [ 1, 2, 3 ] ]

<< : 왼쪽으로 시프트 하는 연산자로 1 << n 은 2의 n승을 나타낸다.
>> : 오른쪽으로 시프트 하는 연산자로 x >> n 은 x를 2의 n승으로 나눈 효과를 가지고 있다.