0x0C 백트래킹
0x00 알고리즘 설명
백트래킹 : 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
0x01 연습문제1 - N과 M
BOJ 15649번 : N과 M (1)
자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 프로그램
#include <bits/stdc++.h>
using namespace std;
int n,m;
int arr[10]; // 0-indexed
bool isused[10]; // 1-indexed
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() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
func(0);
}
0x02 연습문제2 - N-Queen
BOJ 9663번 : N-Queen
크기가 N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제
- isused1 : 같은 열에 Queen이 있는지 저장하는 배열
- isused2 : 대각선(x+y값이 같다)에 같은 Queen이 있는지 저장하는 배열
- isused3 : 대각선(x-y값이 같다)에 같은 Queen이 있는지 저장하는 배열
#include <bits/stdc++.h>
using namespace std;
int n, cnt = 0;
bool isused1[40];
bool isused2[40];
bool isused3[40];
void func(int cur) {
if(cur == n) {
cnt++;
return;
}
for(int i = 0; i < n; i++) { // (cur, i)에 Queen을 둘 수 있는지
if(!isused1[i] && !isused2[cur + i] && !isused3[cur - i + n -1]){
isused1[i]= 1;
isused2[cur + i]= 1;
isused3[cur - i + n -1]= 1;
func(cur+1);
isused1[i]= 0;
isused2[cur + i]= 0;
isused3[cur - i + n -1]= 0;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
func(0);
cout << cnt << "\n";
}시간복잡도 가늠이 힘들다. A1에 퀸을 놓으면 바로 B1, B2에 퀸을 놓는 경우는 해볼 필요가 없어지는 것과 같은 상황을 가지치기라고 부르는데, 때문에 문제를 보고 시간복잡도가 가늠이 잘 안간다.
따라서 가장 큰 N일 경우의 케이스를 직접 돌려봐서 시간 초과가 나는지 안나는지를 보면된다. 시간을 로컬에서 측정할 때에는 반드시 Release모드로 실행을 해야한다. 서버가 로컬보다 빠르다.
Release 모드 : 코드 최적화를 하여 컴파일된 어셈블리어의 라인 수를 획기적으로 줄여서 속도가 빨라진다.
- Release vs Debug : Debug 모드는 컴파일 시 코드의 안정성을 위해 여러 가지 장치를 추가해서 컴파일했을 때 Debug 모드가 Release 모드보다 파일크기가 크다. 또한 사용되는 런타임 라이브러리가 다르고, 증분 링크 사용 여부가 다르다.
Debug모드에서는 정상적으로 작동하는데 Release모드에서는 정상적으로 작동하지 않는 코드들이 있다. 따라서 Debug로 작업을 진행하다가도 중간중간 Release모드로도 꼭 테스트를 진행해야 한다.
0x03 연습문제3 - 부분수열의 합
BOJ 1182번 : 부분수열의 합
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수(>0)인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램
#include <bits/stdc++.h>
using namespace std;
int n, s, cnt = 0;
int arr[30];
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() {
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 << "\n";
}0x04 STL next_permutation
현재의 수열을 사전 순으로 생각했을 때의 다음 수열로 만들고 true를 반환하는 함수. 현재 수열이 사전 순으로 제일 마지막이어서 다음 수열이 존재하지 않는다면 false를 반환한다.
조합이 필요할 경우에는 0과 1을 이용해서 next_permutation을 돌리는 방법으로 해결한다.
예를 들어 5개에서 3개를 뽑는 문제라면 배열 a = 1로 두면 된다.
문제 풀이
이번 강의에 해당하는 문제는 총 20개였다.
연습문제는 강의를 들으면서 잠시 멈춰놓고 해결하였고, 나머지 체크표시있는 기본문제, 응용문제를 풀어보면서 백트래킹이 익숙해지도록 연습하려고 한다.
기본문제는 다 문제없이 고민하면서 천천히 해결할 수 있었다.
하지만 응용문제로 넘어간 뒤 이제 이전에 배웠던 것을 응용해 백트래킹을 구현해야해서 머리가 아팠다.
Note_ 1941번 소문난 칠공주 : '상하좌우' 단어를 보자마자 BFS를 떠올렸다. 머리로는 조금 구상이 되었으나 막상 풀려고하니 잘 되지 않아서 헤맸던 문제다. 나중에는 답지를 참고하여 구현을 하였다.
16987번 계란으로 계란치기 : 문제를 읽으면서도 헷갈리고 어지러웠다. 집중력이 흐트러진 탓인지 문제 이해하고 생각하는데 상당히 오래걸렸고 구현력도 조금 부족했다.
if(s[k] <= 0 || cnt == n-1) {
func(k+1);
return;
} // k번째 계란이 깨져있거나 다른 모든 계란이 깨져있으면 패스return을 써서 조건에서는 백트래킹을 실행하지않고 패스하는 부분을 생각해내지 못해서 노트한다.
리뷰
백트래킹에 대해서는 정말 처음 들어보는 알고리즘이다.
그래서 처음에 많이 두렵기도 했고 아직 많이 어렵지만, 연습문제를 많이 풀어보면서 숙달할 예정이다.
점점 배운내용이 쌓이다보니 하루정도 복습을 하고 진행해야 할 것 같다.
다음은 0X0D 시뮬레이션으로 돌아오겠다.
출처: 바킹독님의 실전알고리즘 강의