백트래킹이란 무엇인가?
-현재상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
(ex. 게임에서 현재상태에서 가능한 모든 선택지를 다 플레이 해보는 방법)
문제풀이에서 백트래킹의 활용방식은?
-각 상태별로 여러가지 경우의수가 생기고 일일이 확인할 필요가 있을때
-분기점에 다시 되돌아올 마킹을 남겨야 할때
Code
int n,m;
int arr[10];
bool isused[10];
void func(int k){
if(k == m){
for(int i=0; i<m; i++)
cout << arr[i] << ' ';
cout << '\n';
return;
}
for(int i=1; i<=n; i++){
if(!isused[i]){
arr[k] = i;
isused[i] = 1;
func(k+1);
isused[i] = 0;
}
}
}
int main(void){
ios:: sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
func(0);
}
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));
/*
123
132
213
231
312
321 순열
*/
int a[4] = {0,0,1,1};
do{
for(int i=0; i<4; i++){
if(a[i] == 0)
cout << i+1;
}
cout << '\n';
}while(next_permutation(a, a+4));
/*
12
13
14
23
24
34 조합
*/
'CS > 자료구조와 알고리즘' 카테고리의 다른 글
유니온 파인드 알고리즘 (0) | 2024.03.07 |
---|---|
재귀 (0) | 2023.02.18 |
DFS (0) | 2023.02.12 |
BFS (0) | 2023.02.10 |
덱(Deque) (0) | 2023.02.09 |