[알고리즘]구현-완전탐색

완전탐색 알고리즘

완전탐색은 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 알고리즘이다. 이 방법은 무식하게 한다는 의미로 "Brute Force"라고도 부른다.
직관적이기 때문에 이해하기 쉽고 정확한 결과값을 얻어낼 수 있어서 가장 기초적인 방법이다.

효율성
Computer Science에서 문제 해결 알고리즘을 사용할 때는 2가지 규칙이 적용된다.
1. 사용된 알고리즘이 적절한가?
2. 효율적으로 동작하는가?

완전 탐색 알고리즘은 1번은 만족하지만 대부분의 경우 2번을 만족하지 못하기 때문에 제한이 따른다. 시간 복잡도를 생각하면 완전탐색 알고리즘을 사용할 경우 모든 문제에 대한 경우의 수가 적을 경우 적절하다.

완전 탐색 기법

• Brute Force
  단순히 for문과 if문과 같은 반복 / 조건문을 통해 가능한 모든 방법을 찾는 경우를 의미한다.

• 비트마스크
  비트연산(AND, OR, XOR, SHIFT, NOT)을 이용하는 방식이다.
  모든 경우의 수가 각각의 원소에 포함되거나 포함되지 않는 두가지 선택으로 구성되는 경우에 유용하게 사용이 가능하다. 숫자를 2진수로 변환하여 부분집합에 어떤 원소들을 포함하고 있는지 나타낼 수 있다.

  S = {1, 3, 4, 7, 10} 이 있는 경우 5자리 이진수를 이용하여 각 원소의 포함 여부를 체크할 수 있다.

  • 부분집합이 {4, 10}일 경우 3번째와 5번째 원소를 갖고 있으므로 5=101(2)
  • {1, 3, 4, 7, 10}일 경우는 1~5번째 원소를 모두 갖고 있으므로 31=11111(2)로 나타낼 수 있다.

• 순열
  임의의 수열이 주어졌을 때 그것을 다른 순서로 연산하는 방법이다. 서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N!이므로 완전 탐색을 이용하기 위해서는 N이 한자리 수 정도여야 한다.

• 재귀
  재귀는 자기 자신을 호출하는 것이다.

  중요

  • 자기 자신을 호출하기 때문에 빠져나오기 위한 탈출 조건이 필요
  • 현재 함수의 상태를 저장하는 전달인자가 필요
  • return문을 신경써야 한다.
    이전 결과에 추가 연산을 수행해야할 경우는 연산 결과를 반환해야하기 때문이다

  예시) 피보나치 수열

  def Fibo(n) :
  	if n<=1 :
    	return n
    else :
    	return fibo(n-1)+fibo(n-2)
  
  '''

• DFS, BFS(따로 다룰 예정)
  BFS/DFS 정리 링크
  그래프 자료 구조에서 모든 정점을 탐색하기 위한 방법이다.
  BFS: 너비 우선 탐색으로 현재 정점과 인접한 정점을 우선으로 탐색
  DFS: 깊이 우선 탐색으로 현재 정점과 인접한 정점을 탐색한 후 그 다음 인접한 정점을 탐색하여 끝까지 탐색하는 방식이다.

• 백트래킹
  해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법이다. 불필요한 부분을 쳐내고 최대한 유망한(promising) 방향으로 간다는 의미로 가지치기(pruning)라 한다.

  주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 될 수 없는 상황이 오면 탐색을 중지시킨 뒤, 이전으로 돌아가 다른 경우를 탐색하도록 구현한다.

[출처]
https://hongjw1938.tistory.com/78
https://chanhuiseok.github.io/posts/algo-23/