[코테 알고리즘] 프로그래머스 고득점 Kit - 완전탐색

완전탐색(Brute Force)이란?

- 무식하게 모든 경우를 탐색해보는 알고리즘이다.

- 정확성은100% 보장되나 속도가 최악이라는 단점이 있다.

- 문제에서 주어진 데이터가 맹루 적을때만 사용 가능하다.

- 완전 탐색은 딱히 알고리즘이라고 할 게 없지만, 완전탐색을 하기 위한 기법들은 여러 개가 있다.

---

1. 단순 브루트포스

- for 문과 if문 등으로 모든 케이스를 조사해보는 방법이다.

- 코테에 단독적으로 나오지 않는다. pass!!

---

2. 순열

- 완전 탐색의 대표적인 유형이다.

- 서로 다른 n개 중 r개를 중복없이 선택하여 나열하는 경우의 수이다.

- 순서가 상관이 있고 [1,2,3] 과 [3,2,1]은 다른 것이다.

---

 

순열

from itertools import permutations
list(permutations([1,2,3], 2)) # permutations(값, 몇개로 묶을지)
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

 

조합 

- 순서 상관 없다. [1,2] 나 [2,1] 은 같다고 봄.

from itertools import combinations
list(combinations([1,2,3], 2))
[(1, 2), (1, 3), (2, 3)]

 

중복순열

from itertools import combinations_with_replacement
list(combinations_with_replacement([1,2,3], 2))
[(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

---

3. 재귀

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

- 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지는 자기 자신을 호출해 실행한다. 

- 반복문을 줄일 수 있지만 스택 오버플로우가 잘 발생한다는 점에서 주의해야 한다.

- 한번 함수의 상태를 저장하는 파라미터와 재귀 탈출 조건이 반드시 필요하고, return 문을 명확하게정의해야 한다.

 

ex. 간단한 재귀함수 예시(팩토리얼)

def recursive_factorial(n):
    if n <= 1:
        return 1
    return n * recursive_factorial(n-1)
    
print(recursive_factorial(5))
120

** 재귀함수는 주로 BFS/DFS에서 사용된다.

---

4. 비트마스크

- 2진수를 사용하여 연산하는 방식이다.

- 각 원소가 포함 or 불포함으로 구성되는 경우에 사용된다.

 

ex. [1,2,3,4] 의 부분집합을 만들때 비트마스크를 사용하면

[1, 2, 3, 4]
 1  1  1  1
 1  1  1  0
 1  1  0  1
 1  1  0  0
 ...

- 리스트의 길이만큼 비트 리스트를 만든 후에 원소가 포함되면 1, 아니면 0으로 구분해서 간단하게 표기할 수 있다.

- 비트 연산은 (&,|,^,~,<<,>>)이 가능하다.

---

5. BFS/DFS

- 이건 나중에 따로 정리

---

6. 백그래킹

- 해를 찾는 도중에 막히면 더 이상 깊이 들어가지 않고 이전 단계로 되돌아가서 해를 찾아나가는 기법이다.

- 불필요한 부분을 쳐내고(가지치기) 최대한 올바른 방향으로 나아가려는 방식이다.

- 백트래킹을 사용하는 대표적인 알고리즘이 DFS인데, DFS는 재귀를 통해 가능한 경로 중 유망한 경로만 찾아서 탐색을 수행한 뒤 다시 돌아와 그 중 가장 최적의 경로를 반환하는 것이다. 

---

* 완전탐색 시간복잡도

비트마스크 > DFS/BFS > Brute-Force > 재귀함수 > 순열 > 백트래킹