브루트포스(완전탐색) 개념
문제를 해결하기 위한 솔루션을 모든 영역에서 탐색한다고 하여 완전탐색이다. 경우의 수를 모두 고려하는 방식이기 때문에 문제의 영역이 크다면 시간초과의 가능성이 있으므로, 조건을 잘 고려하여야 한다.
단순한 완전탐색 문제는 간단히 해결할 수 있고, DFS, BFS, 백트래킹 등의 알고리즘으로도 해결할 수 있다.
특정 문제들의 경우(N개 중에서 M개를 가지고 문제를 해결해야 할 때 등) 재귀적인 형태로 문제를 해결해나갈 수 있다.
주의할 점 - 백트래킹을 써야 하는지 알기 어렵다.
재귀를 이용한 탐색 방법이 여전히 익숙하지 않고 어색하다. 문제를 딱 봤을 때 어떤 알고리즘을 사용해야하는지 감을 잡기 어려운 경우가 종종 있는데, 그 중 하나가 백트래킹이다.
주어진 N 개 중 K개를 가지고 어떠한 솔루션을 만들어야하는 경우인지 파악할 필요가 있다.
또한, 무한 탐색을 하지 않도록 종료 조건을 잘 설계해야 한다.
백트래킹 예제 문제
백트래킹 문제 접근법
벡터, 배열 등등의 어떠한 자료구조에 재귀적으로 추출한 정보를 저장해야 한다. 또한 해당 함수가 종료되고 return 될 때 이전에 탐색한 정보를 삭제해야하는 과정을 포함하여야 한다.
위와 같이 문제를 해결해나가는 방식이 그래프를 그려나가는 과정과 같다(DFS, BFS).
특정 조건에 해당할 경우 return 할 수 있는 종료조건에 대한 설계와, 특정 조건에 해당하지 않는 경우 재귀적 탐색을 계속하는 설계로 해당 함수를 구성하면 된다. 기본적인 형태는 아래와 같다.
void Recursion(string& order_string, int course_num, int idx, int cnt){
// end condition
if(cnt == course_num){
ordermap[order_checker_str] ++;
return;
}
for(int i=idx; i<order_string.size(); i++){
order_checker_str += order_string[i];
Recursion(order_string, course_num, i+1, cnt+1);
order_checker_str.pop_back();
}
}프로그래머스 2021 KAKAO BLIND RECRUITMENT '메뉴 리뉴얼' 문제의 본인 풀이 일부이다.
재귀함수의 구성은 위에서 언급했던 것과 같이 1. 종료조건 2. 탐색 조건 으로 나뉘며, 탐색 시에는 탐색이 종료된 다음 다음 탐색을 위한 벡터/배열의 값 초기화가 필요하다(push_back & pop_back or erase....)
문제가 어렵게 출제된다면, 탐색에 대한 조건이 까다로울 것으로 예상한다.
유형 문제
1. https://www.acmicpc.net/problem/2580
2. https://school.programmers.co.kr/learn/courses/30/lessons/72411
3. https://www.acmicpc.net/problem/14888
참고 사이트
1. https://www.youtube.com/@codetreelecture5794
2. https://school.programmers.co.kr/learn/courses/30/lessons/72411