Machineboy空
완전탐색(브루트포스), 백트래킹(back tracking) - 조합 재귀함수 구현코드, 원상복구 본문
완전탐색은 모든 경우의 수를 탐색하는 것이고, 백트래킹은 완전 탐색을 기반으로 하되, 불필요한 연산을 좀 줄이는 것.
경우의 수는 순열과 조합 + 로직으로 풀린다. 이를 재귀 또는 반복문으로 구현할 수 있다.
원상복구 타이밍 잘 처리하기! 상태값이 그 다음 경우의 수에 영향미치지 않게 처리해주는 것
완전 탐색 (brute force, exhaustive key search)
모든 경우의 수를 탐색하는 알고리즘
순열or 조합 + 로직
보통 1억 미만까지는 컴퓨터를 믿고 넘겨라.
예제)
https://machineboy0.tistory.com/183
벽을 세우는 경우의 수를 모두 탐색해야함.
다만 순서가 있다면 순열, 없다면 조합 요정도 수준.
완전탐색 구현 1 : 반복문을 활용한 완전탐색 (for, while)
//단순한 선형적 반복도 완전탐색
int main(){
vector<int> v = {1,2,3,4,5};
for(int i = 0; i < v.size(); i++){
if(v[i]==5){
cout << "야호\n";
}
}
}
예제)
https://machineboy0.tistory.com/176
666 부터 int_max까지 하나씩 돌리며 수를 찾는 것이므로 완전 탐색
완전탐색 구현 2 : 재귀함수
반목문이 가능하면 무조건 반복문으로.
그 외에 너무 복잡하거나, 어떠한 행위를 반복하는데 매개변수만 수정해서 넘기면 될 것 같다? 그러면 재귀함수로
- 조합 or 순열 + DFS, BFS 등의 알고리즘
- 경우의 수 마다 생각해야하는 로직도 나온다.
예를 들어,
nC1,nC2,nC3 등 경우의 수를 생각해야한다면 재귀함수로 하는 것이 낫다. (비트마스킹은 추후에 배울 것)
예제 1)
승철이는 도쿄 상공의 구름 위에 올라가 있다. 이 구름은 그대로 내버려두면 땅으로 떨어져 100만명의 사상자가 발생한다.
구름을 멈추는 방법은 구름의 특정 위치에 합이 소수가 되는 n개의 요석을 꽂으면 된다.
총 몇 개의 경우의 수가 있는지.
입력)
10
24 35 38 40 49 59 60 67 83 98
예제 2)
N개의 자연수가 주어질 때
여기서 몇 개의 숫자를 골라 합을 mod11 했을 때 나오는 가장 큰 수를 구하라.
#include <bits/stdc++.h>
using namespace std;
int n,temp, ret;
vector<int> v;
const int mod = 11;
int cnt = 0;
void go(int idx, int sum){
if(idx == n){ //재귀함수는 기저사례가 중요
ret = max(ret, sum %mod);
cnt++;
return;
}
go(idx +1, sum + v[idx]);
go(idx + 1, sum);
}
int main(){
cin >> n;
for(int i = 0; i < n; i++){
cin >> temp;
v.push_back(temp);
}
go(0,0);
cout << ret << "\n";
cout << cnt << "\n";
}
백트래킹 (back tracking)
완전 탐색을 하되, 할 필요 없는 것들은 가지치기
최대한 불필요한 탐색을 피하는 것.
위의 문제에서 불필요한 연산을 좀 줄여보자.
예제 2)
N개의 자연수가 주어질 때
여기서 몇 개의 숫자를 골라 합을 mod11 했을 때 나오는 가장 큰 수를 구하라.
#include <bits/stdc++.h>
using namespace std;
int n,temp, ret;
vector<int> v;
const int mod = 11;
int cnt = 0;
void go(int idx, int sum){
// 최대는 10이므로 10에 이미 충족했다면 나머지연산은 불필요
if(ret == 10) return;
if(idx == n){ //재귀함수는 기저사례가 중요
ret = max(ret, sum %mod);
cnt++;
return;
}
go(idx +1, sum + v[idx]);
go(idx + 1, sum);
}
int main(){
cin >> n;
for(int i = 0; i < n; i++){
cin >> temp;
v.push_back(temp);
}
go(0,0);
cout << ret << "\n";
cout << cnt << "\n";
}
완전탐색과 원상복구
완전탐색하며 변화를 주고 원상복구를 해야하는 경우,
즉, 상태값이 그 다음 경우의 수에 반영되지 않도록 원상 복구를 해야하는 경우
https://machineboy0.tistory.com/183
예제 1)
아래와 같이 노드가 이어저 있을 때, 탐색한 정점이 3개이면 출력하라.
#include <bits/stdc++.h>
using namespace std;
int n, visited[4];
vector<int> v;
vector<int> adj[4];
void print(){
for(int i : v) cout << char(i + 'A') << " ";
cout <<'\n';
}
void go(int idx){
if(v.size() ==3){
print();
return;
}
for(int there : adj[idx]){
if(visited[there]) continue;
visited[there] = 1; //색칠했다가
v.push_back(there); //넣었다가
go(there);
visited[there] = 0; //다시 초기화해줄래.
v.pop_back(); //빼자
}
}
int main(){
adj[0].push_back(1);
adj[1].push_back(0);
adj[1].push_back(2);
adj[2].push_back(1);
adj[1].push_back(3);
adj[3].push_back(1);
visited[0] = 1;
v.push_back(0);
go(0);
return 0;
}
원복의 기본꼴
go(int here){
visited[there] = 1; // 방문 처리
go(there);
visited[there] = 0; // 방문 처리 지우기
}
예제 2)
홍철이는 각 칸마다 코인이 있는 3*3맵 위에 서있고, (0,0) 지점에서, (2,2)로 가면서 코인을 얻으려고 한다.
홍철이는 상하좌우로 이동할 수 있다. 각 칸에 있는 코인의 수는 아래와 같다.
코인을 모으는 모든 경우의 수를 출력하여라.
{10,20,21}
{70,90,12}
{80,110,120}
#include <bits/stdc++.h>
using namespace std;
const int n = 3;
int a[3][3] = {
{10,20,21},
{70,90,12},
{80,110,120}
};
int visited[3][3];
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
vector<int> v;
void print(){
for(int i : v) cout << i <<" ";
cout <<'\n';
}
void go(int y, int x){
if(y==n-1 && x == n-1){
print();
return;
}
for(int i = 0; i <4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny <0||nx<0||ny>=n|| nx>=n) continue;
if(visited[ny][nx]) continue;
visited[ny][nx] = 1; //방문 처리
v.push_back(a[ny][nx]); // 넣고
go(ny,nx); // 원하는 거 실행하고
visited[ny][nx]= 0; // 방문 처리 취소
v.pop_back(); // 빼고
}
}
int main(){
visited[0][0] = 1;
v.push_back(a[0][0]);
go(0,0);
return 0;
}
딱 바꿔준 것만 교체하는 그런 로직 생각해야함.
'Computer > 알고리즘' 카테고리의 다른 글
모듈러 연산과 유클리드 호제법 (0) | 2024.06.17 |
---|---|
비트연산자 활용법 - 비트 bool 배열 확인 (0) | 2024.04.05 |
트리 순회 (Tree traversal) - 후위 순회, 전위 순회, 중위 순회 (0) | 2024.02.08 |
깊이우선탐색(DFS) vs 너비우선탐색(BFS) (1) | 2024.02.08 |
연결된 컴포넌트 (connected compoonent), Flood Fill (0) | 2024.02.07 |