완전 탐색 (Brute Force Algorithm)

완전 탐색이란?

브루트-포스 알고리즘이라고 불리는데, 그냥 모든 경우를 탐색해보는 알고리즘이다.

정말 하나부터 열까지 모든 경우를 탐색하기 때문에 정확성 100%지만, 속도는 느리다는 단점이 있다.

그래서 데이터가 매우 적을 때만 사용 가능하다.

 

 

 

 

 

완전 탐색을 활용하는 방법

1. 반복/조건문 활용
2. 순열(Permutation) : n개의 원소 중 r개의 원소를 중복 허용 없이 나열
3. 재귀 호출
4. BFS, DFS 활용
5. 비트마스크 : 2진수 표현 기법 활용

 

 

 

 

 

완전 탐색 활용 - 단순 반복/조건문 활용

단순하게 모든 방법을 찾는 방법

(예) 자물쇠 암호를 찾는 경우 (모든 경우의 수 계산)

 

 

 

 

 

완전 탐색 활용 - 순열

순열은 임의의 수열이 있을 때, 그것을 다른 순서로 연산하는 방법이다. (순서가 중요)

같은 데이터지만, 그 순서에 따라 의미가 있다.

 

아래 문제는 순열을 사용하면 편하다.

https://daydream-sy.tistory.com/299

[프로그래머스 level 2] 피로도 - 87946 (Python)

 

위의 문제를 예시로 들어보자.

dungeons의 길이가 최대 8이기 때문에 데이터가 적어 완전 탐색을 활용하는 게 편하다.

그 중 순열을 사용하는 게 편하다. 왜냐하면, dungeon을 도는 순서에 따라 피로도가 바뀌고 도는 던전 숫자도 바뀌기 때문이다.

 

순열을 사용하면 시간 복잡도가 높기 때문에 문제에 주어진 데이터의 크기를 꼭 고려해야 한다.

 

python에서는 itertools 라이브러리에서 제공하는 permutations 메서드를 사용해서 순열을 구현할 수도 있다.

# 예시
from itertools import permutations

if __name__ == '__main__':
    iterator = [1, 2, 3, 4]
    for i in permutations(iterator, 2):
        print(i)

 

위의 코드는 간단한 예시이다. (출처: https://velog.io/@heehee/Python-itertools-%EB%9D%BC%EC%9D%B4%EB%B8%8C%EB%9F%AC%EB%A6%AC-%EC%82%AC%EC%9A%A9%EB%B2%95)

iterable에서 원소 개수가 r개인 순열을 뽑는 것이다.

 

itertools 관련된 문서를 읽어보면 더 도움이 될 것이다.

https://docs.python.org/ko/3.8/library/itertools.html

itertools — 효율적인 루핑을 위한 이터레이터를 만드는 함수 — Python 3.8.17 문서

 

 

 

 

 

 

완전 탐색 활용 - 재귀(Recursive)

재귀는 자기 자신을 호출한다는 의미이다.

이 함수를 활용한다면 자기 자신을 호출함으로써 전체 코드를 매우 짧게 줄일 수 있다. 주로 이러한 경우에 쓰인다.

 

재귀에서는 세 가지가 중요하다.

• 재귀를 탈출하기 위한 탈출 조건
• 현재 함수의 상태를 저장하는 parmeter가 필요
• return문 주의

 

완전 탐색의 재귀와 DP의 차이점이 있다.

DP는 작은 문제가 큰 문제와 동일한 구조를 가져 그대로 사용하여 수행 속도가 빠르다는 장점이 있다.

반면 완전 탐색은 크고 작은 문제의 구조가 다를 수 있고 반드시 기억하지 않으므로 해결방법을 모두 탐색한다.

 

 

 

 

 

완전탐색 활용 - BFS, DFS

그래프 자료 구조에서 모든 정점을 탐색하기 위한 방법이다.

(예) 길찾기 + 중간에 장애물 존재 => 완전 탐색과 BFS, DFS를 함께 사용할 수 있다.

 

 

 

 

 

완전 탐색 활용 - 비트 마스크

비트(bit) 연산을 통해 부분 집합을 표현하는 방법이다.

 

 

 

 

 

 

---

 

조금 더 공부하면 내용이 추가될 수 있다.

 

 

참고 : https://hongjw1938.tistory.com/78