재귀 정리 (c++)

바킹독알고리즘 블로그를 보고 정리한 내용입니다.

출처 : https://blog.encrypted.gg/943

[실전 알고리즘] 0x0B강 - 재귀

 

재귀 정의 

하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

 

1부터 N까지 출력하는 재귀함수

void func(int n) {
	if(n==0) retrun;
    cout << n << " ";
    func(n-1);
}

 

재귀를 순차적으로 생각하지말고, 귀납적인 방법으로 풀자.

(순차적으로 생각하다가 혼자서 자멸..했던 기억이 떠오름..)

 

* 도미노가 k개 쓰러지는 모습을 생각해보자.

1. 1번 도미노가 쓰러진다

2. k번 도미노가 쓰러지면 k+1 도미노도 쓰러진다

-> 따라서, 모든 도미노가 쓰러진다

 

* 1부터 N까지 출력하는 재귀함수도 귀납적으로 생각해보자.

1. func(1)이 1을 출력한다.

2. func(k)가 k, k-1,  k-2, ... , 1을 출력하면 func(k+1)도 k+1, k, k-1, ... , 1을 출력한다.

-> 따라서 func1은 n부터 1까지 차례로 출력한다.

 

재귀 함수의 조건

1. 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다. (Base condition이 필요하다)

2. 모든 입력은 Base condition으로 수렴해야 한다.

 

재귀에 대한 정보

1. 함수의 인자가 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 함 -> 명확한 함수 정의

2. 모든 재귀는 반복문으로도 동일한 동작을 만들 수 있다

3. 재귀는 반복문으로 구현했을 때 코드가 간결해지지만, 메모리/시간 측면에서는 손해를 본다.

4. 한 함수가 자기 자신을 여러번 호출하게 되면 비효율적일 수 있다 (피보나치 수열처럼 여러번 호출하여 같은 값을 여러번 호출할 경우, 시간복잡도가 말도 안되게 커져버린다. 이럴때 다이나믹 프로그래밍 쓴다)

5. 재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적된다. (스택 메모리 제한이 걸려있는걸 확인하자)

 

재귀로 풀이할 때 순서

1. 함수를 정의한다.

2. base condition을 정한다.

3. 재귀식을 작성한다

 

거듭제곱

BOJ 1629 곱셈

int의 범위가 훨씬 넘는 곱셈의 나머지 구하기

 

a^n * a^n = a^2n

 

12^58 mod 67 = 4

12^116 mod 67 = 4

 

이게 모듈러 연산이라 하던거였나.. 하튼 그냥 수학식 알면 된다

 

재귀적으로 생각하기

1. 1승을 계산할 수있다

2. k승을 계산했으면 2k승과 2k+1승도 O(1)에 계산할 수 있다.

덧붙이자면..

2의7승이라고 할때, 2의3승 * 2의3승 * 2 로 이루어짐. 홀수, 짝수 다르게 처리해야 함. 

 

풀이

1. 함수를 정의한다.

ll fun(ll a, ll b, ll m) {
	val = val * val % m;
	if(b%2 == 0) return val;
    return val*a%m;
}

2. base condition을 정한다.

if(b==1) return a%m;

3. 재귀식을 작성한다

ll val = fun(a, b/2, m);

4. 최종 풀이

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

ll fun(ll a, ll b, ll m) {
	if(b == 1) return a % m;
    ll val = fun (a, b/2, m);
    val = val * val % m;
    if(b % 2 == 0) return val;
    return val * a % m;
}

int main() {
	ll a, b, m;
	cin >> a >> b >> m;
    cout << func(a, b, m);
}

 

하노이탑

BOJ 11729 하노이탑

 

재귀적으로 생각하는게 제일 도움이 많이 된 듯한 문제다.

 

원판이 n개일 때, 모든 원판을 3번으로 이동하기를 생각해보자

1. 1~n-1번의 원판을 2번으로 옮긴다.

2. n번 원판을 3번으로 옮긴다.

3. 1~n-1번의 원판을 3번으로 옮긴다.

 

재귀적으로 생각하기

1. 원판이 1개일 때 원판을 내가 원하는 곳으로 옮길 수 있다.

2. 원판이 k개일 때 옮길 수 있으면 원판이 k+1개일 때에도 옮길 수 있다.

그냥 이렇게 느끼삼

 

풀이

1. 함수를 정의한다.

a기둥에서 b기둥으로 n개의 원판을 옮기는 방법을 출력한다

void fun(int a, int b, int n)

2. base condition을 정한다.

if(n == 1) cout << a << ' ' << b << "\n";

3. 재귀식을 작성한다

fun(a, 6-a-b, n-1);
cout << a << " " << b << "\n"'
fun(6-a-b, b, n-1);

4. 최종풀이

 

#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';
  func(1, 3, k);
 }

 

Z

BOJ 1074 Z

해당 좌표를 Z모양을 그리는 순서대로 방문했을 때, 몇번째로 방문하는지 알아내는 문제

힌트를 보니까 쉽게 풀었다

한변이 2^3일 때, 구역을 4군데로 나눌 수 있다.

1번구역 -> (0~4, 0~4) -> 0 + 좌표위치

2번구역 -> (5~8, 0~4) -> 4*4 + 좌표위치

3번구역 -> (0~4, 5~8) -> 4*4*2 + 좌표위치

4번구역 -> (5~8, 5~8) -> 4*4*3+ 좌표위치

 

Z모양 자체가 구역 순서대로므로 풀이 순서대로 구현하면 된다.

 

풀이

1. 함수를 정의한다.

행, 열, 배열의 크기를 받아서 위치를 넘기는 함수

int fun(int r, int c, int n)

2. base condition을 정한다.

if(n == 0) return 0;

3. 재귀식을 작성한다

int half = 1 << (n-1);
if(r < half && c < half) return fun(r, c, n-1);
if(r < half && c >= half) return half*half + fun(r, c-half, n-1);
if(r >= half && c < half) return half*half*2 + fun(r-half, c, n-1);
return half*half*3 + fun(r-half, c-half, n-1);

4. 최종풀이

#include <bits/stdc++.h>
using namespace std;

int func(int r, int c, int n){
  if(n == 0) return 0;
  int half = 1<<(n-1);
  if(r < half && c < half) return func(r, c, n-1);
  if(r < half && c >= half) return half*half + func(r, c-half, n-1);
  if(r >= half && c < half) return 2*half*half + func(r-half, c, n-1);
  return 3*half*half + func(r-half, c-half, n-1);
}

int main(void){
  int n, r, c;
  cin >> n >> r >> c;
  cout << func(r, c, n);
}

 

음.. 어렵군