Solving Skill ] 완전 탐색

---

 

완전 탐색

[코테에서의 시뮬레이션, 구현, 완탐은 서로 비슷한 점이 多]

 

+  가능한 모든 경우의 수를 탐색하고, 확인하는 방법입니다.

      (예) 문제 : '1 ~ 100'까지 모든 수의 합을 구하시오.

              풀이 : 1 ~ 100까지 모든 수를 더한다. (for문 이용 등)

 

     따라서 Brute Force라고 불리거나 Generate & Test라고 불리기도 합니다.

 

+  일반적으로 탐색해야 할 데이터 개수가 100만개 이하일 때 사용하면 적절합니다.

    즉 검색해봐야 할 모든 경우의 수가 적을 때 적절합니다.

---

 🍇 완전 탐색 기법 종류

        Brute Force

           :  단순히 for과 if를 이용해 문제를 풀어가는 방법

 

        비트마스크

           :  AND, OR, XOR, SHIFT, NOT인 이진수 표현을 자료구조로 사용

              모든 경우의 수가 각각의 원소에 포함되거나 포함되지 않는 두 가지 선택으로 구성되는 경우 용이합니다.

 

          ❓ 비트마스크로 무엇을 할 수 있는가

          * 정수로 집합을 나타낼 수 있다.

          * {1, 3, 4, 5, 9} = 570 = 2^1 + 2^3 + 2^4 + 2^5 + 2^9

          * 굳이 비트마스크를 쓰는 이유는? 공간적인 이유 + 정수 하나로 배열을 대체할 수 있기 때문에

 

        백트래킹

           : 재귀함수를 설계할 때 고려해야 할 아주 중요한 개념입니다.

             해를 찾아가는 도중에 해가 될 것 같지 않은 경로가 있다면 더 이상 가지 않고 back을 하는 개념입니다.

      

          🔸 백트래킹 예시와 효율성

         if(sum >= 20) return; 한 줄짜리 코드의 효율성은 엄청나다. 

         00000 ~ 99999 까지 10만개를 모두 검사하지 않고, 중간에 더 진행하더라도 결코 답이 될 수 없는 숫자 는 배제시킨다.

 

        재귀

 

        순열  

           : 완전 탐색을 이용하기 위해서는 N이 한자리 수 정도는 되어야 한다.

             C++의 경우 STL - Algorithm 에 존재하는 next_permutation 과 prev_permutation을 활용하자.

           : 순회 외판원 문제가 대표적인 순열 문제이다.

완탐中 ] 순열과 조합

 

        BFS & DFS

Solving Skill ] 탐색

        

---

 🌷 문제

   프로그래머스

        Level 1 - 모의고사

             >   단순 구현, 주어진 배열의 반복을 파악하면 빠르게 풀 수 있는 문제

        Level 2 - 소수 찾기

        Level 2 - 카펫

 

 

 

---

SWEA 강의 학습

https://dkanxmstmdgml.tistory.com/694

 

---

reference

완전 탐색 (Brute-Force Search / Exhaustive Search) 알고리즘

Problem Solving - 문제 풀이 팁 정리 (완전 탐색 - Brute Force)