🪡 완전탐색
가능한 경우의 수를 모두 나열하면서 원하는 답을 찾는 방법
Brute-Force 라고도 함(무차별 대입해 억지로 문제를 풀기 때문)
i.e) 10개의 서로 다른 정수 중 두 개를 택해 그 합이 최대가 되는 경우
🧺 완전 탐색 기법
단순 Brute-Force
특별한 방법 대신 단순히 반복문과 조건문으로 모든 경우를 따지는 경우
이 방법만을 이용한 문제는 거의 나오지 않음
비트마스크(Bitmask)
각 원소가 A이거나 B인, 즉 두 가지 상태만을 가질 수 있을 때 사용할 수 있음
i.e) '원소가 n개인 집합의 모든 부분 집합'을 구한다면 각 원소가 포함되는지 포함되지 않는지를 0, 1로 구분하여 배열에 저장해둘 수 있음
재귀함수
비트마스크와 마찬가지로 각 원소가 두 가지 선택지를 가질 때 사용하면 좋음
포함이 되면 해당 원소를 넣고 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출하는 등의 식임
순열(permutaion)
서로 다른 n개를 일렬로 나열하는 방법(경우의 수)
재귀함수를 이용하거나 C++ next_permutation() 함수를 이용할 수 있음
너비우선탐색(BFS),깊이우선탐색(DFS)
- 너비우선탐색(Breadth-first search, BFS)은 하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문하는 방식
- 깊이우선탐색(depth-first search, DFS)은 트리의 한 요소(노드)와 다음 수준의 자식 노드를 따라가는 방향으로 탐색하는 방식
이들은 길 찾기 등에 주로 쓰이는 알고리즘으로, 단순 길찾기에는 BFS/DFS만 써도 무방하나 장애물이 존재하는 등 추가적 연산이 필요할 때 완전탐색을 병용하기도 함
⚡️ 완전탐색을 풀 때는 주로 입력의 개수 (n)이 작을 때가 좋다. 시간복잡도가 O(2^N) 혹은 O(N!)이기 때문에 N의 크기가 증가할수록 복잡도는 폭발적으로 증가함
완전 탐색 이용 예시
- 입력으로 주어지는 데이터(N)의 크기가 매우 작음
- 답의 범위가 작고, 임의의 답을 하나 선택했을 때 문제 조건을 만족하는지 역추적할 수 있음
- 여러 문제 조건 중 한 조건을 고정시키면 문제 풀이가 간단해짐
Hi