TIL91.완전탐색

조연정·2021년 12월 14일

완전탐색 알고리즘에 대해 공부해보자.

완전탐색

모든 경우의 수를 탐색하여 결과를 찾아내는 방법이다.
모두 탐색하기 때문에 정답을 100% 찾아낼 수 있지만, 경우의 수에 따라 실행시간이 비례된다. 즉, 탐색 범위가 넓다면 그만큼 찾아내는 일을 해야하기 때문에 효율적이지 못할 수 있다.

완전탐색 알고리즘 종류

Brute-force
비트 마스크
순열
백트래킹
DFS, BFS
Brute force
단순히 for문과 if문을 사용하여 모든 case들을 만들어 답을 구하는 방법이다.

function sequentialSearch (arr,x) {
  for (let i = 0; i < arr.length; i++) { 
    if(arr[i] === x) {
      return i;
    }
 }
  return -1;
}  
  sequentialSearch([1,2,4,8,18,27,37],2);

*조합

순열과 함께 자주 나오는 개념으로, 서로 다른 n개 중 순서를 생각하지 않고 r개를 택할 때, 이것은 n개에서 r개를 택하는 조합이라 한다. 선택 순서는 상관없다(ex)[1,2] =[2,1])

❓ n(4)개 중에 2개 뽑는 경우를 구해보자.

-접근법
'1' 고정하고 -> 나머지 [2, 3, 4] 중에서 2개 조합
[1, 2, 3][1, 2, 4] [1, 3, 4]
'2' 고정하고 -> 나머지 [3, 4] 중에서 2개 조합
[2, 3, 4]
'3' 고정하고 -> 나머지 [4] 중에서 2개 조합
[]
'4' 고정하고 -> 나머지 [] 중에서 2개 조합
[]

'인셉션' 같다...

-코드

const getCombinations = (arr, selectNum) => {
  const result = [];
  if(selectNum === 1) {
    return arr.map((el) => [el])
  };
  arr.forEach((fixed, idx, origin) => {
    const rest = origin.slice(idx + 1);
    // arr 배열에서 해당 fixed를 제외한 나머지 값  
   
   const combinations = getCombinations(rest, selectNum - 1);
  // 현재 fixed를 제외한 나머지 숫자들을 재귀함수로 돌려 조합을 구한다.
    
    const attached = combinations.map((combination) => [fixed,...combination]);
      //  돌아온 조합에 떼어 놓은(fixed) 값 합치기

    result.push(...attached);
  })
  return result;
}

getCombinations([1,2,3,4],3);

// output
[
  [ 1, 2, 3 ],
  [ 1, 2, 4 ],
  [ 1, 3, 4 ],
  [ 2, 3, 4 ]
]

순열
순열은 서로 다른 n개에서 r개를 선택해서 정렬하는 가짓수이고, 순열의 수를 기호로 nPr로 나타낸다.선택 순서가 결과에 영향을 미친다.(ex)[1,2] ≠ [2,1])

1.fixed을 이용한 순열

❓ n개 중에 2개 뽑는 경우 구하기
-코드

const getPermutations = (arr, selectNum) => {
 const result = [];
 if(selectNum === 1) {
  return arr.map((el)=> [el]);
 }
 
 arr.forEach((fixed, idx, origin) => {
   const rest = [...origin.slice(0,idx), ...origin.slice(idx + 1)];
   const permutations = getPermutations(rest,selectNum - 1 );
   const attached = permutations.map((el) => [fixed,...el])
   result.push(...attached);
 })  
 return result;
}

getPermutations([1,2,3,4], 3);
// output
[
 [ 1, 2, 3 ], [ 1, 2, 4 ],
 [ 1, 3, 2 ], [ 1, 3, 4 ],
 [ 1, 4, 2 ], [ 1, 4, 3 ],
 [ 2, 1, 3 ], [ 2, 1, 4 ],
 [ 2, 3, 1 ], [ 2, 3, 4 ],
 [ 2, 4, 1 ], [ 2, 4, 3 ],
 [ 3, 1, 2 ], [ 3, 1, 4 ],
 [ 3, 2, 1 ], [ 3, 2, 4 ],
 [ 3, 4, 1 ], [ 3, 4, 2 ],
 [ 4, 1, 2 ], [ 4, 1, 3 ],
 [ 4, 2, 1 ], [ 4, 2, 3 ],
 [ 4, 3, 1 ], [ 4, 3, 2 ]
]

차이점

조합코드와 거의 똑같고, rest부분만 다르다.

     |--- 현재 index보다 작으면 잘라낸다면, 조합
rest |     fixed:1 => [2,3,4] => fixed:2 => [3,4] => ...
     |     fixed:2 => [3,4] => fixed:1 => [4] => ...
     |--- 현재 index보다 작아도 존재해야한다면, 순열
     	   fixed:1 => [2,3,4] => fixed:2 => [3,4] => ...
           fixed:2 => [1,3,4] => fixed:1 => [3,4] => ...

2.swap을 이용한 순열

❓ 나올 수 있는 전체 경우 구하기

const getPermutations = (arr) => {
  const result = []; //(4) result = [[1,2]]
  //(6) [1,2] => [2,1]
  const swap = (arrToSwap, idxA, idxB) => {
    const temp = arrToSwap[idxA];
    arrToSwap[idxA] = arrToSwap[idxB];
    arrToSwap[idxB] = temp;
  };
  
  const generate = (n , array) => {
    //(3) n = 1이 되었기때문에, result에 담아줌 
    //(8) result에 [2,1] push
    if(n === 1){
       result.push([…array]);
      return;
    }
    generate( n-1, array); //(2)  n = 2, -> generate(1,[1,2])
    
    //(5) 다시 g(2, [1,2])케이스로 돌아와서 for문을 탄다. n이 짝수이기 때문에 swap([1,2],0,1)
    for(let i = 0; i < n - 1; i++) {
      if(n % 2 === 0) {
        swap(array, i, n - 1);
      }else {
        swap(array, 0, n - 1 );
      }
      generate( n - 1, array); //(7) generate(1, [2,1])
    }
  }
  generate(arr.length, arr.slice()); //(1) generate 함수 호출 (2,[1,2])
  return result;
}

getPermutations([1,2,3]);