[바킹독 알고리즘]0x0B강 - 재귀
0x00 알고리즘 설명
0x01 연습문제 1 - 거듭제곱
BOJ 1629번: 곱셈
1629번: 곱셈
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
www.acmicpc.net
첫 번째는, 수의 범위이다.
제한사항을 보면 입력이 2,147,483,647까지다.
입력부터 20억이 넘어가기 때문에 20억^20억
long long int 자료형을 아득히 넘어간다.
그렇기 때문에 지수를 한 번에 곱해서 구해서는 안된다.
자료형을 넘지 않도록 지수를 분할하여 곱하여야 한다.
두 번째는 시간복잡도이다.
그럼 한 번씩 곱할 때마다 나머지를 구하면 되지 않을까?
이러면 시간복잡도가 O(n)이 되는데,
해당 문제의 시간제한이 0.5초로 시간초과가 뜬다. 그래서 다른 방법을 사용해야 한다.
결론적으로 이 문제는 분할정복을 사용하여 자료형을 넘지 않도록 하고
O(logN)의 시간복잡도로 실행되게 한다.
이 문제는 지수(B)의 짝수일 때와 홀수일 때를 구분해야 한다.
예를 들어, 2^10 같은 짝수일 경우, (2^5)*(2^5)로 분할할 수 있다.
하지만 2^11 같은 홀수일 경우에는, 분할을 하면 정확히 반으로 나눠지지 않기 때문에
2를 하나 밖으로 빼두어 (2^5)*(2^5)*2 이런 식으로 형식을 맞춰준다.
2^5는 또한 반으로 나눌 수 있다.
(2^2)*(2^2)*2.. 이런 식으로 계속해서 재귀적으로 반으로 나눠갈 수 있다.
결국 이 문제는 b의 홀짝을 잘 구분해서
재귀호출을 해주면 되는 문제이다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll POW(ll a, ll b, ll m){
if(b==1) return a % m;
ll val = POW(a, b/2 ,m);
val = val * val % m;
if(b%2==0) return val;
return val * a % m;
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
ll a, b, c;
cin >> a >> b >> c;
cout << POW( a, b, c);
}
0x02 연습 문제 2 - 하노이 탑
BOJ 11729: 하노이 탑 이동 순서
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
하노이탑의 중요한 규칙 2가지
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
하노이탑의 문제 해결법은 " k층일때 k-1층부터 꼭대기까지 모두를 한 곳에 몰아넣고 k층을 목표지점으로 둔다. 이후 맨 아래층인 k-1층부터 똑같이 반복한다" 이다.
하노이탑의 이동 횟수는 pow(2,k)-1 이다.
#include <bits/stdc++.h>
using namespace std;
void Hanoi(int a, int b, int n){
if(n==1) {
cout << a << ' ' << b << '\n';
return;
}
Hanoi( a, 6-a-b, n-1);
cout << a <<' ' << b << '\n';
Hanoi( 6-a-b, b, n-1);
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
cout << (1<<n)-1 <<'\n';
Hanoi(1,3,n);
}
0x03 연습 문제 3 - Z
BOJ 1074번: Z
1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을
www.acmicpc.net
다음 레벨의 사각형을 4등분으로 구역을 나누고 1, 2, 3, 4 순으로 진행된다.
위 예시를 보면 3번 사각형을 방문하기 전에 이미 32개의 칸을 방문했을 것이고, 3번 사각형 내에서 빨칸 칸은 12번째로 방문되니 최종적으로 32 + 12 = 44번째라는것을 알 수 있게된다.
#include <bits/stdc++.h>
using namespace std;
int func(int n, int r, int c){
if(n == 0) return 0;
int half = pow(2,n-1);
if( r < half && c < half) return func(n-1,r,c);
if( r < half && c >= half) return half*half + func(n-1,r, c-half);
if( r >= half && c < half) return 2*half*half + func(n-1,r-half,c);
return 3*half*half + func(n-1,r-half,c-half);
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
int N, r, c;
cin >> N >> r >> c;
cout << func(N,r,c);
}