[알고리즘 공부] 실전 알고리즘 12강-백트래킹
바킹독님이 올려주신 [실전 알고리즘] 영상을 보면서 공부한것을 기록
모든 사진은 바킹독님의 블로그에서 가져왔습니다.
https://blog.encrypted.gg/
알고리즘 설명
현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
백준 15649번
#include <bits/stdc++.h>
using namespace std;
int n,m;
int arr[10]; // 수열을 담을 배열
bool isused[10]; // 특정 수가 사용되었는지 나타내는 배열
void func(int k){ // 현재 k개까지 수를 택했음.
if(k == m){ // m개를 모두 택했으면
for(int i = 0; i < m; i++)
cout << arr[i] << ' '; // arr에 기록해둔 수를 출력
cout << '\n';
return;
}
for(int i = 1; i <= n; i++){ // 1부터 n까지의 수에 대해
if(!isused[i]){ // 아직 i가 사용되지 않았으면
arr[k] = i; // k번째 수를 i로 정함
isused[i] = 1; // i를 사용되었다고 표시
func(k+1); // 다음 수를 정하러 한 단계 더 들어감
isused[i] = 0; // k번째 수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 이제 사용되지않았다고 명시함.
}
}
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
func(0);
}
백준 9663번
#include <bits/stdc++.h>
using namespace std;
bool isused1[40]; // column을 차지하고 있는지
bool isused2[40]; // / 방향 대각선을 차지하고 있는지
bool isused3[40]; // \ 방향 대각선을 차지하고 있는지
int cnt = 0;
int n;
void func(int cur) { // cur번째 row에 말을 배치할 예정임
if (cur == n) { // N개를 놓는데 성공했다면
cnt++;
return;
}
for (int i = 0; i < n; i++) { // (cur, i)에 퀸을 놓을 예정
if (isused1[i] || isused2[i+cur] || isused3[cur-i+n-1]) // column이나 대각선 중에 문제가 있다면
continue;
isused1[i] = 1;
isused2[i+cur] = 1;
isused3[cur-i+n-1] = 1;
func(cur+1);
isused1[i] = 0;
isused2[i+cur] = 0;
isused3[cur-i+n-1] = 0;
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
func(0);
cout << cnt;
}
백준 1182번
#include <bits/stdc++.h>
using namespace std;
int n, s;
int arr[30];
int cnt = 0;
void func(int cur, int tot){
if(cur == n){
if(tot == s) cnt++;
return;
}
func(cur+1, tot);
func(cur+1, tot+arr[cur]);
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> s;
for(int i = 0; i < n; i++)
cin >> arr[i];
func(0, 0);
if(s == 0) cnt--;
cout << cnt;
}
STL next_permutation
순열과 조합을 해결할 수 있는 STL이다.
int a[3] = {1,2,3};
do{
for(int i=0;i<3;++i)
cout << a[i];
cout << '\n';
}while(next_permutation(a,a+3));
Author And Source
이 문제에 관하여([알고리즘 공부] 실전 알고리즘 12강-백트래킹), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kwkim95/알고리즘-공부-실전-알고리즘-12강-백트래킹저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)