[알고리즘] 완전 탐색 (Exhaustive search)

완전탐색( Exhaustive search )

'무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 뜻한다.

• 완전 탐색은 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다.

완전 탐색 관련 개념

 다음과 같은 개념들이 완전탐색을 통한 문제풀이에 사용되며 문제의 조건과 방식에 따라 적절한 개념을 이용하여 문제 해결 시간을 향상 시킬 수 있다.

 

1. Brute Force : 가능한 모든 경우에 대해 모두 확인 하여 답을 찾는 방식

 

2. 비트마스크 : 컴퓨터의 언어인 이진수를 활용하여 정수를 이진수 형태로 표현하여 비트연산을 활용하는 방법

 

3. 순열 : 서로 다른 개의 원소 n개에서 r(r<=n)개를 뽑아 한 줄로 세우는 경우의 수 

 

4. DFS (Depth-First Search) : 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

   -관련 개념) 백트래킹 : 비선형으로 구성된 자료 구조를 깊이 우선으로 탐색할 때, 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하는 과정

 

5. BFS (Breadth-First Search) : 탐색트리의 루트노드부터 목표노드를 만날 때까지 단계별로 횡방향으로 탐색을 진행해 나가는 방식

 

6. 재귀함수 : 함수 내에서 자기 자신을 다시 호출하는 함수 // 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수

 

 

완전 탐색과 관련된 백준 의 알고리즘 문제 해결을 통해 완전 탐색에 대해 탐구해보겠다.

 

 

---

1. 2309번 일곱 난쟁이

 

일곱 난쟁이

2309번: 일곱 난쟁이

* 문제 풀이

https://hroad.tistory.com/27

[BAEKJOON 2309번] (C++) 일곱 난쟁이

---

2. 3085번 사탕 게임

 

사탕 게임

3085번: 사탕 게임

* 문제 풀이

https://hroad.tistory.com/29

[BAEKJOON 3085번] (C++) 사탕 게임

---

3. 2503번 숫자 야구

 

숫자 야구

2503번: 숫자 야구

* 문제풀이

https://hroad.tistory.com/28

[BAEKJOON 2503번] (C++) 숫자 야구

---

3. 1182번 부분수열의 합

 

 

부분수열의 합

1182번: 부분수열의 합

* 문제풀이

https://hroad.tistory.com/31

[BAEKJOON 1182번] (C++) 부분수열의 합

---