[2021 하계 모각코] 3차시

브루트포스 알고리즘

 

brute: 무식한, force: 힘

무식한 힘

완전 탐색 알고리즘으로 가능한 모든 경우의 수를 탐색하면서 조건에 맞는 결과만을 선택한다.

컴퓨터에게 계산을 맡김으로써 무조건 결과를 얻는 강력한 방법이다.

 

---

브루트 포스 문제를 해결하기 위해선 어떤 구조에서도 모든 자료 탐색이 가능해야하기 때문에 구조에 따라 방식이 나뉜다.

선형 구조의 경우 모두 탐색하기 위해서 가장 간단한 방식인 순차탐색이 가능하다.

비선형 구조의 경우 모두 탐색하기 위해선 깊이 우선 탐색과 너비 우선 탐색이 있다.

 

---

순차 탐색

 

 

순차탐색으로 문제를 해결하는 방법은 다음과 같다.

​

1. 주어진 문제를 선형 구조로 구조화한다.

2. 구조화된 자료를 구조에 맞는 방식으로 해를 구할 때까지 탐색한다.

3. 탐색된 해를 정리하여 출력한다.

 

---

모든 순열 문제

​

https://github.com/miraekwak/BOJ/blob/main/10974.py

GitHub - miraekwak/BOJ