귀납적 사고

• func1(k)가 k k-1 k-2 … 1 을 출력하면, func1(k+1)은 k+1 k k-1 …. 1을 출력한다

void func1(int n){
    if(n == 0) return;
    cout << n << ' ' ;
    func1(n-1);
}

피보나치 수열

• dfs(k)가 1부터 k까지 합을 출력한다면, dfs(k-1)은 1부터 k-1의 합을 출력함
  • dfs(k) = dfs(k-1) + k

int dfs(int k){
    if(k == 1){
        return 1;
    }
    return k + dfs(k-1);
}

int main(){

	cout << dfs(3) << '\n';

}

a^b 를 m으로 나눈 나머지

• 백준 곱셈(1629번)

- k승의 결과를 토대로, 2k, 2k+1 승의 결과를 계산할 수 있음!

• a^n * a^n = a^2n 을 활용
• a^n을 m으로 나눈 나머지가 x 라면, a^2n을 m으로 나눈 나머지는 x^2
• (a mod n * b mod n) mod n = (a*b) mod n

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); // a^(2/b) mod m의 결과
    val = val * val % m ;  // a^b mod m은 val의 제곱에 m을 나눈 나머지
    if(b % 2 == 0){
        return val;
    }
    return val * a % m; // b가 홀수라면 val에 a를 곱해서 m으로 나눈 나머지
}

하노이탑의 이동 순서 (백준 11729)

• 이 문제 역시, 절차적 사고로 하면 답이 없음!
  • 1번 원판을 기둥2에 옮겨야할지, 3번에 옮겨야할지… 이런 생각을 하면 안됨!
• n-1개의 원판을 원하는 곳으로 옮길수 있다면 n개의 원판을 처리할 수 있음
  • 원판이 k개일 때 옮길 수 있으면, 원판이 k+1개일 때도 옮길 수 있다.
• 함수의 정의
  • void func(int n) 원판 n개를 기둥 1에서 기둥 3으로 옮기는 방법을 출력하는 함수
    • 그런데 여기서, 원판 n개를 기둥 1에서 기둥 3으로 옮기려면 원판 n-1개를 기둥 1에서 기둥 2로 옮겨야 함!
    • 그러면, func(n-1) 활용 불가
  • 그럼 어떤 함수로 정의해야하나?
    • 시작 기둥과 도착 기둥도 인자를 받아야 한다!
    • void func(int a, int b, int n)
• base condition
  • n = 1일 때 cout « a « ’ ‘ « b « ‘\n’;
• 재귀식
  • n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮긴다 => func(a, 6-a-b, n-1);
  • n번 원판을 기둥 a에서 기둥 b로 옮긴다 => cout << a << ' ' << b << '\n';
  • n-1개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다 => func(6-a-b, b, n-1);

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(){
    int k;
    cin >> k;
    cout << (1<<k) - 1 << '\n'; // 1을 k칸만큼 left shift => 2^k
    func(1, 3, k);
}