완전탐색(브루트 포스), 백트랙킹

완전탐색, 브루트 포스란 무엇인가?

🎈 완전탐색 알고리즘은 무식하게 전부 확인하겠다는 뜻이다.

• 즉 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다.
• 전체를 탐색한다는 의미에서 완전탐색이라고 부름

브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다고 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다.

브루트 포스의 장점

• 알고리즘을 설계하고 구현하기 매우 쉽다.
• 복잡한 알고리즘 없이 빠르게 구현할 수 있다.

브루트 포스의 단점

• 알고리즘의 실행 시간이 매우 오래 걸린다.
• 메모리 효율면에서 매우 비효율적이다.

브루트 포스의 종류

😀 브루트 포스는 크게 선형구조와 비선형 구조로 나뉜다.

선형구조 : 순차 탐색
비선형구조 : 백트랙킹, DFS/BFS

백트랙킹과 DFS/BFS에 대해서 이제 따로 다룰 것.

• 지금은 순차탐색에 대해 공부!

문제 해결 방법

1. 주어진 문제를 선형 구조로 구조화
2. 구조화된 문제공간을 적절한 방법으로 구성할 때까지 탐색
3. 구성된 해를 정리

😎 문제풀 때 마인드 !

👻 완전탐색 문제의 경우, 코드는 단순할 수 있지만 어떻게 완전탐색 풀이가 나올 수 있는지 판단하는 것이 제일 중요!!
👻 백트래킹 문제의 경우, 재귀함수의 탈출 조건과 선택지의 회복을 고려하면서 코드를 설계하고, 작성