#include <bits/stdc++.h>
using namespace std;
int n, m;
int num[10];
int arr[10];
bool check[10];
void func(int cnt){ // 이전 수열의 마지막항과 새로 추가할 값이 같으면 중복된 수열이다.
if(cnt == m){
for(int i = 0; i < m; i++){
cout << num[i]<< ' ';
}
cout << '\n';
return;
}
int prev_num = -1;
for(int i = 0; i < n; i++){ // 선택하여 출력할 수를 num에 저장
if(!check[i] && prev_num != arr[i]){
check[i] = true;
num[cnt] = arr[i]; // cnt 번째 숫자를 i로 정한다.
prev_num = arr[i]; // 방금 선택한 수를 기억해둔다.
func(cnt+1); // 다음 숫자 탐색 시작
check[i] = false;
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i <n; i++){
cin >> arr[i]; // 주어진 수를 arr에 저장
}
sort(arr, arr+n); // 정렬. 사전순으로 출력해야하기 때문.
func(0); // 0번째 수를 선택하는 것으로 시작한다
return 0;
}
리뷰
백트래킹에 익숙해지기 위한 문제 중 하나다. 수열이 [ 9, 7, 9, 1] 이 주어져도 (1, 9)를 두 번 출력하면 안된다. 하지만 (9, 9)는 출력해야 한다.
일단 수열을 입력받자마자 정렬한다. 이전 선택 값이 현재 선택 값과는 달라야 한다. 그래서 prev_num 변수를 쓴다.
처음에 prev_num 변수를 전역변수로 사용해서 틀렸다. for문 내부의 함수의 재귀호출이 끝나면 check배열을 false로 돌려놓고, 다음 i번째 숫자를 검사하게 된다. 따라서 방금 종료된 재귀 호출에서 변경된 prev_num이 그대로 적용된다는 문제가 있다. 그래서 동일한 순서(cnt)의 숫자를 선택할 때는 prev_num을 똑같이 바라봐야 한다. 따라서 지역변수로 prev_num을 써야 한다.
코드를 읽어 보면 재귀적으로 구현됬다. 이 모양은 백트래킹의 전형적인 구조니까 주석을 읽고 잘 익혀두자.
선택한 숫자를 저장하는 int arr 배열 1부터 n까지의 숫자 중에서 '선택 여부'를 저장하는 bool isused 배열 현재 몇 개의 숫자를 선택했는지 인자를 넘기는 재귀 함수 void func(int k ) 재귀 함수의 종료 조건(base condition)은 k가 m개를 모두 선택했을 때 이다.
// http://boj.kr/f36567ec0c9f44b4b460b5b29683c27b
#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);
}
func함수의 for문이 핵심이다.
1부터 n까지의 수에 대해 아직 i가 사용되지 않았으면 다음 수를 정하러 한 단계 더 들어간다.
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를 이제 사용되지않았다고 명시함.
}
}
재귀로 다음 수를 정하러 함수를 호출하고 나서 종료되면, 현재 선택했던 수를 사용하지 않았다고 표시한다.
즉, 이전 단계로 돌아오는 것이다.
단 현재 값이 i인 arr[k]는 굳이 0과 같은 값으로 변경할 필요가 없다. 어차피 자연스럽게 다른 값으로 덮힐 예정이기 때문이다.
잘 모르겠다면 함수의 중간 중간 arr, isused, k를 출력한다던가 하는 방식으로 확인하고, (영상으로도 확인)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll A, B, C;
ll rec(ll a, ll b, ll c){
if(b == 1) return a % c; // a가 c보다 클 수 있기 때문에 a % c를 반환.
ll val = rec(a, b/2, c);
val = val * val % c;
if(b%2 == 0) return val;
return val * a % c; // b가 홀수라면 *a %c 를 한 번 더 수행.
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> A >> B >> C;
cout << rec(A, B, C);
return 0;
}
리뷰
재귀를 공부하면서 푼 문제다. 곱셈을 하면 int의 범위를 넘어서기 때문에 long long 을 써야 한다. 단, b승을 알려면 b/2승을 제곱하면 된다는 것을 기반으로 코드를 짜야 한다.
12의 58승을 67로 나눈 나머지가 4라면, 12의 116승을 67로 나눈 나머지는 (4의 제곱) 즉, 16이 된다.
-> 58승을 계산할 수 있으면 116승을 계산할 수 있다.
-> k승을 계산할 수 있으면 2k승과 2k+1승도 O(1)에 계산할 수 있다.
이 두 문장은 참이다. 따라서 a의 임의의 지수승을 귀납적으로 계산할 수 있다.
귀납법의 일부를 코드로 바꿔보자.
func(a, b, c)는 func(a, b/2, c)를 기반으로 구할 수 있다.
using ll = long long;
ll func(ll a, ll b, ll c){
val = func(a, b/2, c);
val = val * a % c; // a를 곱하고 c로 나눈 나머지
}
// func(a, b, c)는 func(a, b/2, c)를 기반으로 구할 수 있다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll A, B, C;
ll rec(ll a, ll b, ll c){
if(b == 1) return a % c; // a가 c보다 클 수 있기 때문에 a % c를 반환.
ll val = rec(a, b/2, c);
val = val * val % c;
if(b%2 == 0) return val;
return val * a % c; // b가 홀수라면 *a %c 를 한 번 더 수행.
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> A >> B >> C;
cout << rec(A, B, C);
return 0;
}
// http://boj.kr/9c320eecca4b4958bd54977f83371a36
이 함수의 시간 복잡도는 b가 계속 절반씩 깎이니까 O(log b)이다.
그래서 문제의 시간 제한을 넉넉히 지킬 수 있다.
0x02 연습문제2 - 하노이 탑
두 번째 문제는 재귀 문제 중에 스테디셀러인 하노이탑 문제다.
온라인 게임으로 원판 3, 4, 5개일 때를 깨고 오자. 하노이탑 문제가 뭔지 감이 올 것이다.
//바킹독님코드 http://boj.kr/f2440915dca04aaa9aec759080516973
#include <bits/stdc++.h>
using namespace std;
void func(int a, int b, int n){
if(n == 1){
cout << a << ' ' << b << '\n';
return;
}
func(a, 6-a-b, n-1);
cout << a << ' ' << b << '\n';
func(6-a-b, b, n-1);
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
int k;
cin >> k;
cout << (1<<k) - 1 << '\n'; // (1<<k)는 2의 k승이다.
func(1, 3, k);
}
0x03 연습문제3 - Z
하노이탑이 아리송하지만. 백준 1074번 Z문제를 읽어 보면 '또 뭔가..' 싶을 것이다.
꾹 참고 5분만 재귀 관점으로 고민해보자.
방문 순서가 어떤 식으로 매겨지냐면, 배열을 4등분 한 후에, 1,2,3,4 순으로 진행된다.
아래 그림에서 N=3일 때, 16x16 배열을 그려놓고. 4등분 해서 영역 1,2,3,4로 나눠놨다.
r=2, c=2 칸은 '영역1'에서' 12번째로 방문한다.
'영역1' 내부를 4등분으로 나누면, 영역 1, 2, 3에 포함된 0칸~11칸을 전부 방문하고, 12번째로 방문한 셈이다.
r=6, c=2 칸은 '영역3'에서 44번째로 방문한다.
'영역3'에 오기 전에는 이미 '영역1, 영역2'를 방문한다. '영역3'내부의 0칸~11칸을 전부 방문하고, 12번째로 방문한 셈이다.
뭔가 이전에 방문한 순서를 기반으로 다음 것을 구할 때 써먹을 수 있을 것 같다는 느낌이 조금 온다. (그저 느낌뿐..)
구현을 위해 단계적으로 생각해보자.
1. 함수의 정의
직관적으로 보이는 모양 대로 정의하면 된다. 2의 N승 배열에서, (r,c)를 방문하는 순서를 반환하는 함수.
이 값이 Int범위에 들어오는지 신경써줄 필요가 있는데, n은 15이하니까 int범위를 초과하지 않는다.
int func(int n, int r, int c)
2. base condition
n=0일 때 0을 반환하도록 하자.
n=0 일 때, return 0;
3. 재귀 식
각 상황에 따른 반환 값은 아래와 같다.
여기서 half는 한 변 길이의 절반, 즉 2의 n-1승이다.
(r,c)가 1번 영역일 때, return func(n-1, r, c);
(r,c)가 2번 영역일 때, return half*half + func(n-1, r, c-half);
(r,c)가 3번 영역일 때, return 2* half*half + func(n-1, r-half, c);
(r,c)가 4번 영역일 때, return 3* half*half + func(n-1, r-half, c-half);
아까 그림을 보며 확인한 12번째 방문한다는 것의 의미를 다시 보자.
12번째 방문한다는 것은0칸~11칸을 전부 방문하고, 12번째로 방문하는 것이다.
2의 2승 을 4등분한 영역에서, 2의 1승(2의 n-1승) 영역의 1,2,3영역을 모두 방문한 다음에 4영역을 방문하고 있는 것이다.
