알고리즘 설명
현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
연습문제1 - N과 M
BOJ_15649번: N과 M(1)
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
예제 출력 1
풀이
#include <bits/stdc++.h>
using namespace std;
int N,M;
bool isUsed[12];
int arr[12];
void func(int idx){
if(idx == M){
for(int i = 0; i < M; i++) cout << arr[i] << " ";
cout << "\n";
return;
}
for(int i = 1; i <= N; i++){
if(isUsed[i]) continue;
isUsed[i] = true;
arr[idx] = i;
func(idx + 1);
isUsed[i] = false;
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin >> N >> M;
func(0);
return 0;
}팁
상태 트리로 구현할 수 있다.
다만, 상태를 전역에서 다룰 때는 위의 코드처럼 구현한다.
재귀함수의 매개변수로 상태 트리의 레벨이 들어간다.
상태를 노드에서 다룰 때는 call by reference로 전달하자.
recur(vector<int>& v, int level);
또한 요소의 중복체크도 마찬가지로 전역에서 관리할 수있고 노드에서 관리할 수 있다.
BFS 방문 배열처럼 이는 전역에서 관리하는게 더 쉽다.
BOJ_15663번: N과 M(9)
N과 M (9) 성공
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 512 MB 57935 29427 22482 49.708%
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
N개의 자연수 중에서 M개를 고른 수열
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
4 4 2
예제 출력 1
2
4
풀이
#include <bits/stdc++.h>
using namespace std;
int N, M;
array<int, 8> board;
bool isUsed[12];
void recur(vector<int>& v, int h){
if(h == M){
for(auto e : v) cout << e << " ";
cout << "\n";
return;
}
int temp = -1; // 범위 밖
for(int i = 0; i < N; i++){
if(isUsed[i]) continue;
if(temp == board[i]) continue;
temp = board[i];
isUsed[i] = true;
v.push_back(board[i]);
recur(v, h+1);
v.pop_back();
isUsed[i] = false;
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin >> N >> M;
for(int i = 0; i < N; i++) cin >> board[i];
sort(board.begin(), board.begin()+N);
vector<int> v;
recur(v, 0);
return 0;
}팁
중복을 제거하기 위해서는 보통 unique를 사용한다.
unique의 사용 전제 조건이 "정렬" 이다.
모든 값을 다 구한 다음에 unique를 사용해서 중복을 제거해도 되지만 이 경우 백트래킹이라고 보기 힘들다.
아닐 경우에는 탐색을 중지를 해야하는데 아닌걸 알면서도 나중에 걸러질꺼라 생각하고 탐색을 진행하기 때문이다.
트리를 그려보면 같은 레벨에서 중복이 이루어지지 않으면 된다는 걸 알 수 있다.
그렇다면 레벨 단위에서 중복을 제거하기 위해 unique를 써야할까?
그렇게 해도 되지만 unique를 쓰기위해 컨테이너를 준비 / 할당 / 제거...비용이 든다.
unique의 작동원리를 차용해서 직접 필터링을 진행한다.
정렬이 되어있으므로 이전 값과 현재 값이 같다면 "중복"임을 알 수 있다.
BOJ_15664번: N과 M(10)
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
N개의 자연수 중에서 M개를 고른 수열
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
4 4 2
예제 출력 1
2
4
풀이
#include <bits/stdc++.h>
using namespace std;
int N, M;
array<int, 8> board;
void recur(vector<int>& v, int h, int idx){
if(h == M){
for(auto e : v) cout << e << " ";
cout << "\n";
return;
}
int temp = -1;
for(int i = idx; i < N; i++){
if(temp == board[i]) continue;
temp = board[i];
v.push_back(board[i]);
recur(v, h+1, i+1);
v.pop_back();
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin >> N >> M;
for(int i = 0; i < N; i++) cin >> board[i];
sort(board.begin(), board.begin()+N);
vector<int> v;
recur(v, 0, 0);
return 0;
}팁
자식 노드 모두에게 같은 값을 적용할 때는 레벨 변수를 이용하면 되고 자식들 사이에 다른 값을 적용할 때는 새로운 변수를 추가해야 한다.
위의 풀이에서는 세 번째 매개변수를 이용했다.
연습문제2 - N-Queen
BOJ_9663번: N-Queen
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
예제 입력 1
8
예제 출력 1
92
풀이
#include <bits/stdc++.h>
using namespace std;
int cnt = 0;
int N;
bool isUsed1[15];
map<int, bool> isUsed2;
map<int, bool> isUsed3;
void recur(int r){
if(r == N){
cnt++;
return;
}
for(int i = 0; i < N; i++){
if(isUsed1[i] || isUsed2[r+i] || isUsed3[r-i]) continue;
isUsed1[i] = true;
isUsed2[r+i] = true;
isUsed3[r-i] = true;
recur(r+1);
isUsed1[i] = false;
isUsed2[r+i] = false;
isUsed3[r-i] = false;
}
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin >> N;
recur(0);
cout << cnt;
return 0;
}팁
행렬 내에서
- 같은 열 : c
- 같은 대각선(좌상우하) : r-c
- 같은 대각선(우상좌하) : r+c
로 판단할 수 있다.
다만 좌상우하 인 경우 음수가 나올 수 있으므로 최대 음수만큼 배열을 더 할당하여 양수쪽으로 선형이동하면 된다.
또는 N이 최대 15이므로 map 컨테이너를 이용해도 된다.
map 컨테이너는 O(logN)이지만 N이 15밖에 안되므로 O(1)으로 생각해도 무방하다.
연습문제3 - 부분수열의 합
BOJ_1182번: 부분수열의 합
문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
예제 입력 1
5 0
-7 -3 -2 5 8
예제 출력 1
1
풀이
#include <bits/stdc++.h>
using namespace std;
int N, S;
array<int, 24> arr;
int cnt;
void recur(vector<int>& v, int h){
if(h == N){
if(v.empty()) return;
if(accumulate(v.begin(), v.end(), 0) == S) cnt++;
return;
}
recur(v, h+1);
v.push_back(arr[h]);
recur(v, h+1);
v.pop_back();
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
cin >> N >> S;
for(int i = 0; i < N; i++) cin >> arr[i];
vector<int> v;
recur(v, 0);
cout << cnt;
return 0;
}팁
부분수열은 각 원소가 "있냐/없냐" 로 구분될 수 있다.
상태 트리의 레벨이 각 원소를 의미하고
상태 트리 노드에 추가하면 있다는 의미, 추가하지 않으면 없다는 의미가 된다.
마지막에 공집합도 나오게 되므로 공집합은 따로 빼두는 코드가 필요하다.
STL next_permutation
순열
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int arr[] = {1, 7, 5};
sort(arr, arr+3);
do{
for(int i = 0; i < 3; i++) cout << arr[i] << " ";
cout << endl;
}while(next_permutation(arr, arr+3));
return 0;
}기본적으로 next_permutation을 사용하기위해서는 오름차순 정렬이 되어있어야 한다.
조합
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int arr[] = {1, 3, 5, 6, 7};
bool temp[] = {0, 0, 0, 1, 1};
do{
for(int i = 0; i < 5; i++){
if(temp[i] == 0) cout << arr[i] << " ";
}
cout << endl;
}while(next_permutation(temp, temp+5));
return 0;
}5C3 조합을 사용하려면 임시로 {0, 0, 0, 1, 1} 배열을 만들어서 값이 0인 인덱스만을 사용하여 arr에 접근하면 된다.
{0, 0, 0, 1, 1}인 이유는 오름차순 정렬이 되어야 하기 때문이다.
