CS알고리즘

[알고리즘] 완전탐색 알고리즘 정리

BACK TRACKING, BFS, BRUTE FORCE, DFS, EXHAUSTIVE SEARCH, 완전탐색

* 19.09.19 작성중..

완전탐색 알고리즘 이란?

어떤 해답에 도달하기까지의 과정을 전부 하나하나씩 검사한다는 의미이다.

가장 이상적인 방법이지만 해결까지에 드는 자원 소모가 많은게 단점이다.

완전탐색 알고리즘의 사용처

  • 무작위의 변수를 비교/탐색해야 할 때
  • 최적화 문제(여러가지 경우를 만들 수 있을때, 가장 적합한 답을 구하는 문제)

완전탐색 알고리즘

완전탐색 알고리즘의 종류로는

  • Brute Force (무작위 대입)

  • DFS (깊이 우선 탐색)

  • BFS (너비 우선 탐색)

  • 백트래킹

    네종류가 있다.

1. Brute Force (무작위 대입) 방식

가장 흔히 사용하는, for문으로 배열의 시작값부터 끝값까지 전부 체크하는 방식이다.

1
2
3
4
5
6
checkStr = 'qwertyuiopasdfghjkl' # 원래값
pattern = 'asdf' # 찾을 값

for idx in range(0, len(checkStr)):
    if checkStr[idx:idx + 4] == pattern:
        print("checkStr에서 patter이 시작되는 index :", idx)

checkStr이 가진 qwertyuiopasdfghjkl 값을 q부터 4개씩 비교해가면서 무작위대입 방식으로 찾는다.

(위 예는 checkStr.find(pattern) 내장함수와 동일하다.)

아래로 가면서 모든 경우의 수를 전부 탐색하는 방법이다.
BF에 비해 구현방식이 간단하다. 트리 그래프는 많은곳에서 볼수있으니 딱히 그리지는 않겠다.
보통 재귀함수로 많이 구현한다.

DFS 재귀함수 구현조건

  1. 종료를 언제 할 것인가?
  2. 종료시에 어떤 값을 반환할 것인가?(T/F 두 가지 전부)
  3. 왼쪽 / 오른쪽 중 탐색할 방향의 결과값을 담는다
  4. 이전 단계에서 탐색하지 않은 방향으로 탐색하게 한다.
  5. 다시 원래지점으로 되돌아와서 반환한다.
공유하기