[알고리즘] 완전탐색기법

✅ 완전탐색 알고리즘 (Brute Force Algorithm)

❕ 기본 개념 

- 가능한 모든 경우를 모두 확인하여 정답을 찾아내는 방식

- 운이 좋다면 빠르게 답을 도출할 수 있지만, 운이 나쁘면 가장 마지막으로 확인하는 경우가 답이 될 수도 있음

- 따라서 효율적인 문제 해결에는 적합하지 않은 탐색 알고리즘임

 

 

❕ 완전탐색 기법 

1. Brute Force 기법              : 반복 / 조건문을 활용하여 모든 가능한 경우를 전부 다 확인
2. Permutation (순열)          : 서로 다른 n개의 원소 중 r개를 선택하여 나열 (순서 상관 O, 중복 허용 X)
3. Recursive (재귀 호출)
4. Bitmasking (비트마스크)  : 2진수 표현 기법 활용
5. BFS, DFS

 

 

❓ Brute Force 기법 

- 반복 / 조건문을 통해 가능한 모든 경우를 단순 무식하게 찾는 방법

 

ex. 4자리 자물쇠를 풀기 위해 0000 ~ 9999까지 모두 시도하기 / 분해합

 

 

❓ Permutation (순열) 

- 순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미함

- 순서가 상관 있기 때문에 [1, 2, 3]과 [3, 2, 1]은 다른 경우로 취급함

- N개의 서로 다른 데이터를 순열로 나타낸다면 순열의 전체 가짓수는 N!개가 됨

- 시간복잡도는 O(N x (N - 1)!) = O(N!)

 

ex. n명의 학생 중 3명이 차례로 발표하는 경우 / 수들의 합

 

* 순열 구하는 코드 (JS)

const getPermutations = function (arr, selectNumber) {
  const results = [];
  if (selectNumber === 1)
	return arr.map((value) => [value]);  // 1개씩 택할 때, 바로 모든 배열의 원소 return

  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];  // 해당하는 fixed를 제외한 나머지 배열
    const permutations = getPermutations(rest, selectNumber - 1);  // 나머지에 대해 순열을 구한다.
    const attached = permutations.map((permutation) => [fixed, ...permutation]);
    // 돌아온 순열에 대해 떼 놓은(fixed) 값 붙이기
    results.push(...attached);  // 배열 spread syntax 로 모두다 push
  });

  return results;  // 결과 담긴 results return
};

const arr = [1, 2, 3, 4];
const result = getPermutations(arr, 3);
console.log(result);
// => [
//   [ 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 ]
// ]

 

 

❓ Recursive (재귀) 

 

- 자기 자신을 호출한다는 의미

- 재귀 함수를 활용한다면 자기 자신을 호출함으로써 반복문을 줄일 수 있음

- 이때 주의할 점은

   ① 현재 함수의 상태를 저장하는 parameter와 재귀를 탈출하기 위한 탈출 조건이 반드시 필요함

   ② return문을 명확하게 정의해야함

 

ex. 이진수 변환, 피보나치 수열

 

* 이진수 변환하기 (Python)

def convertBinary(n):
    if (n == 1 or n == 0):
        return str(n)
    return convertBinary(n // 2) + str(n % 2)

def main():
    n = int(input())
    print(convertBinary(n))

if __name__ == "__main__":
    main()

 

 

❓ Bitmasking (비트마스크) 

- 집합의 요소들의 구성 여부를 표현하는 방법 (= 부분집합을 표현하는 방법)

- 비트(bit)란 컴퓨터에서 사용되는 최소 단위 (0 or 1 ☞ 2진법)

 

- 비트마스크를 사용하는 이유

   ① 배열 활용만으로 해결할 수 없는 문제를 해결할 수 있음

   ② 적은 메모리와 빠른 수행시간으로 문제 해결 가능 (but 원소의 수가 많지 않아야 한다는 전제조건)

       ☞ N개의 boolean 원소를 갖는 배열을 선언하는 대신 비트마스크를 이용하면 정수 하나로 표현이 가능 (메모리 ⬇)

   ③ 집합을 배열의 인덱스로 표현할 수 있음

   ④ 코드가 간결해짐

 

- 비트 연산

• AND ( & )  : 두 비트가 모두 1일 때 1 반환
• OR ( | )  : 두 비트 중 모두 1이거나 하나라도 1일 때 1 반환
• XOR ( ^ )  : 두 비트가 서로 다를 때 1 반환, 서로 같으면 0 반환
• NOT ( ~ )  : 비트 값 반전해서 반환
• SHIFT ( >>, << )  : 왼쪽 혹은 오른쪽으로 비트 옮겨 반환 (A << B 는 A를 좌측으로 B 비트만큼 옮긴다는 뜻)

 

ex. 집합 요소 중 임의로 몇 개를 골라서(부분집합) 확인을 해야하는 문제, 막대기, 엘리베이터 장난

 

 

❓ BFS, DFS 

- 그래프 자료구조에서 모든 노드를 탐색하기 위한 방법

- BFS는 너비 우선 탐색으로, 최대한 넓게 이동한 뒤 더 이상 갈 수 없을 때 아래로 이동하여 탐색함

- DFS는 깊이 우선 탐색으로, 최대한 깊이 내려간 뒤 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동하여 탐색함

☞ [알고리즘] BFS & DFS

 

ex. 경로의 특징을 저장해둬야 하는 문제, 최단거리를 구해야 하는 문제

 

 

 

참고자료

완전탐색 알고리즘

순열 자료1, 순열 자료2

Recursive Algorithm

비트마스크 자료1, 비트마스크 자료2

BFS/DFS