완전탐색 Brute-Force (브루트 포스) 이란?
- 문제를 해결하기 위해 확인해야 하는 모든 경우를 전부 탐색하는 방법
- 그 중에서도 백트래킹을 통해야 하는 상황을 해결하기
- 모든 코테 문제에서 기본적으로 접근해 봐야 한다. 많은 연습 필요
- 부분점수를 얻기 좋다
- 전부 탐색하기에 시간 복잡도가 일반적으로 높다
완전 탐색 알고리즘 종류
단순 Brute-Force
- 단순히 반복문(for)과 조건문(if)으로 모든 경우(case)를 만들어 답을 구하는 방법
- 이 방법만을 사용하는 문제는 거의 나오지 않음
비트마스크(Bitmask)
- 나올 수 있는 모든 경우의 수가 각각의 원소를 포함하거나, 포함하지 않는 두가지 선택으로 구성되는 경우 유용하게 사용
- ex) '원소가 n개인 집합의 모든 부분 집합'을 구한다면, 각 원소가 포함되는 경우와, 포함되지 않는 경우를 0과 1로 구분함
재귀함수
- 비트마스크와 마찬가지로 각 원소가 두가지 선택지를 가질 때 유용하게 사용
- 포함이 되면 해당 원소를 넣어 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출하는 등의 식
- ex) 위 부분집합 문제를 예로, 만들고자 하는 부분집합을 S'라고 할 때, S' = { } 부터 시작해서
각 원소에 대해서 해당 원소가 포함이 되면 S'에 넣고 재귀 함수를 돌려주고,
포함이 되지 않으면 S'를 그대로 재귀 함수에 넣어주는 방식이다. - ex) 피보나치 수열
- 시간복잡도 O(N)
여기서 중요한 점!
(1) 재귀를 탈출하기 위한 탈출 조건이 필요!
(2) 현재 함수의 상태를 저장하는 Parameter 필요!
- cnt 통해 몇 개를 선택했는지 전달.이것이 없다면 현재 함수의 상태를 저장할 수 없어 재귀 탈출 조건을 만들 수 없게 되거나 잘못된 결과 출력!
(3) Return문 신경 쓸 것!- 재귀를 통해 이후의 연산 결과를 반환 후 이전 결과에 추가 연산을 수행하는 경우도 있을 수 있다
순열
- 오나전 탐색의 대표적인 유형
- 순열은 서로 다른 N개의 원소를 일렬로 나열하는 경우의 수를 말함
- 순열의 경우의 수는 N!으로 완전 탐색을 이용하기 위해서는 N이 한자리 수는 되어야 함.
- 순서가 중요함! 만약, 수열에서 숫자 [1, 2, 3]이 있다면, 이것을 [1, 2, 3]으로 보는 순서와 [3, 2, 1]로 보는 순서가 차이가 있음이 중요한 경우를 의미한다.
- 순열에 원소를 하나씩 채워가는 방식
- 재귀 함수 이용
- 시간복잡도 O(N!)
너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)
- 약간의 난이도 있는 문제, 완전 탐색 + BFS/DFS 문제 많이 나옴
- 너비 우선 탐색(Breadth-First Search, BFS)는 하나의 요소를 방문하고, 그 요소에 인접한 모든 요소를 우선 방문하는 방식
- 깊이 우선 탐색(Depth-First Search, DFS)는 트리의 한 노드와 다른 레벨의 자식 노드를 따라가는 방햑으로 탐색하는 방식
- 길 찾기 등에 주로 쓰이는 알고리즘
: 단순 길찾기에는 BFS/DFS만 써도 무방하지만,
장애물이 존재하는 등 추가적 연산이 필요할 때 완전탐색과 병용하기도 함 - ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현하고, A와 B사이에 존재하는 경로 찾을 때
- DFS : 모든 친구 관계를 다 살펴야 한다.
- BFS : A와 가까운 관계부터 탐색한다
추천 문제
★ BOJ 14502 연구소
★ BOJ 9663 N-Queen
★ BOJ 15686 치킨 배달
★ BOJ 1062 가르침
★ BOJ 10819 차이를 최대로
★ 2309번: 일곱 난쟁이
★ 2231번: 분해합
★ 3085번: 사탕 게임
★ 10448번: 유레카 이론
★ 2503번: 숫자 야구
★ 1018번: 체스판 다시 칠하기
★ 1182번: 부분집합의 합 (★)
참고
https://rebro.kr/59
https://hongjw1938.tistory.com/88
https://hongjw1938.tistory.com/78
