[바킹독 알고리즘]0x0B강 - 재귀

0x00 알고리즘 설명

 

수학에서의 재귀방정식 풀이와 같다

 

 

 

 

 

 

 

 

0x01 연습문제 1 - 거듭제곱

int를 사용하면 int overflow가 발생하기 때문에 long long 범위로 잡는다. 이것또한 범위를 넘어설 수도 있는데 그럴때는 _int128 이런걸 상요해야한다.(코테에서는 그리 크지않음)

 

 

 

 

 

BOJ 1629번: 곱셈

1629번: 곱셈

 

첫 번째는, 수의 범위이다.
제한사항을 보면 입력이 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번: 하노이 탑 이동 순서

 

 

하노이탑의 중요한 규칙 2가지

1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
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

 

 

 

 

다음 레벨의 사각형을 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);
}