완전탐색

 

완전탐색: 말 그대로 가능한 모든 경우들을 탐색하는 방법.

 

완전탐색 기법

 

 - 단순 Brute-Force

 - 비트마스크(Bitmask)

 - 재귀 함수

 - 순열 (Permutation)

 - BFS / DFS

 

 1. 단순 Brute-Force

어느 기법을 사용하지 않고 단순히 for문과 if문 등으로 모든 case들을 만들어 답을 구하는 방법이다. 이는 아주 기초적인 문제에서 주로 이용되거나, 전체 풀이의 일부분으로 이용하며, 따라서 당연히 대회나 코테에서는 이 방법만을 이용한 문제는 거의 나오지 않는다. 

 

2. 비트마스크(Bitmask)

2진수를 이용하는 컴퓨터의 연산을 이용하는 방식이다. 완전 탐색에서 비트마스크는 문제에서 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용이 가능하다. 

 

간단한 예시로 원소가 5개인 집합의 모든 부분집합을 구하는 경우를 생각해보자. 

어떤 집합의 부분집합은 집합의 각 원소가 해당 부분집합에 포함되거나, 포함되지 않는 두 가지 경우만 존재한다. 

 따라서 5자리 이진수 (0 ~ 31)를 이용하여 각 원소의 포함 여부를 체크할 수 있다. 

 

function findAllSubsets(arr) {
  const subSets = [];
  for (let i = 0; i < 32; i++) {
    const subSet = [];
    for (let j = 0; j < arr.length; j++) {
      if (i.toString(2).padStart(5, "0")[j] === "1") subSet.push(arr[j]);
    }
    subSets.push(subSet);
  }
  return subSets;
}

console.log(findAllSubsets([1, 2, 3, 4, 5]));
/* [
  [],             [ 5 ],
  [ 4 ],          [ 4, 5 ],
  [ 3 ],          [ 3, 5 ],
  [ 3, 4 ],       [ 3, 4, 5 ],
  [ 2 ],          [ 2, 5 ],
  [ 2, 4 ],       [ 2, 4, 5 ],
  [ 2, 3 ],       [ 2, 3, 5 ],
  [ 2, 3, 4 ],    [ 2, 3, 4, 5 ],
  [ 1 ],          [ 1, 5 ],
  [ 1, 4 ],       [ 1, 4, 5 ],
  [ 1, 3 ],       [ 1, 3, 5 ],
  [ 1, 3, 4 ],    [ 1, 3, 4, 5 ],
  [ 1, 2 ],       [ 1, 2, 5 ],
  [ 1, 2, 4 ],    [ 1, 2, 4, 5 ],
  [ 1, 2, 3 ],    [ 1, 2, 3, 5 ],
  [ 1, 2, 3, 4 ], [ 1, 2, 3, 4, 5 ]
]*/

 

3. 재귀 함수 

재귀 함수를 통해서 문제를 만족하는 경우들을 만들어가는 방식이다.

위에서 언급한 부분집합 문제를 예로 들면, 만들고자 하는 부분집합을 S'라고 할 때, S' = { } 부터 시작해서 각 원소에 대해서 해당 원소가 포함이 되면 S'에 넣고 재귀 함수를 돌려주고, 포함이 되지 않으면 S'를 그대로 재귀 함수에 넣어주는 방식이다. 

비트마스크와 마찬가지로 주로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택을 가질 때 이용된다. 

 

4. 순열

완전 탐색의 대표적인 유형이다. 서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N! 이므로 완전 탐색을 이용하기 위해서는 N이 한자리 수 정도는 되어야 한다. 

function getPermutations(arr, n) {
  const result = [];

  function permute(current, remaining) {
    if (current.length === n) {
      result.push(current);
      return;
    }

    for (let i = 0; i < remaining.length; i++) {
      const next = current.concat([remaining[i]]);
      const newArray = remaining.slice();
      newArray.splice(i, 1);
      console.log(next, newArray);
      permute(next, newArray);
    }
  }

  permute([], arr);
  return result;
}

console.log(getPermutations([1, 2, 3, 4, 5], 2));
/*[
  [ 1, 2 ], [ 1, 3 ], [ 1, 4 ],
  [ 1, 5 ], [ 2, 1 ], [ 2, 3 ],
  [ 2, 4 ], [ 2, 5 ], [ 3, 1 ],
  [ 3, 2 ], [ 3, 4 ], [ 3, 5 ],
  [ 4, 1 ], [ 4, 2 ], [ 4, 3 ],
  [ 4, 5 ], [ 5, 1 ], [ 5, 2 ],
  [ 5, 3 ], [ 5, 4 ]
]*/

 

5. BFS / DFS

약간의 난이도가 있는 문제로 완전 탐색 + BFS/DFS 문제가 많이 나온다. 대표적인 유형으로 길 찾기 문제가 있다. 단순히 길을 찾는 문제라면 BFS/DFS만 이용해도 충분하지만, 주어진 도로에 장애물을 설치하거나, 목적지를 추가하는 등의 추가적인 작업이 필요한 경우에 이를 완전 탐색으로 해결하고 나서, BFS/DFS를 이용하는 방식이다. 

 

프로그래머스: 최소직사각형

문제 보기

function solution(sizes) {
    let arr = sizes.map(x => x.sort((a,b) => a-b)).reduce((a, b) => {
        if(a[0] < b[0]) a[0] = b[0]
        if(a[1] < b[1]) a[1] = b[1]
        return a;
    }, [0, 0])
    return arr[0] * arr[1];
}

 

프로그래머스: 모의고사

문제 보기

function solution(answers) {
    const arr = [[1,2,3,4,5],
    [2,1,2,3,2,4,2,5],
    [3,3,1,1,2,2,4,4,5,5]]
    var answer = [];
    let result = []
    
    for(let i=0; i<3; i++){
    answer.push(answers.reduce((a,b,idx) => {            
            if(b === arr[i][idx % arr[i].length]) a++
            return a
        }, 0))}
    let max = Math.max(...answer)

    answer.forEach((v,i) => {
        if(v === max) result.push(i+1)
    })
    return result
}

---

참고자료

https://rebro.kr/59