재귀

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

 

절차지향적 사고 / 귀납적 사고

 

절차지향적 사고

: 1번째 도미노가 쓰러진다 -> 2번째 도미노가 쓰러진다 -> ... -> K번째 도미노가 쓰러진다

 

귀납적 사고

: 1번째 도미노가 쓰러지면 2번째 도미노가 쓰러진다

= K번째 도미노가 쓰러지면 K+1번째 도미노가 쓰러진다

 

재귀 함수의 조건

자기 자신을 호출하지 않고 종료되는 특정 조건이 있어야 함 Base Condition

모든 입력은 base condition으로 수렴해야함

 

재귀 함수에 대해

1. 함수의 인자로 받을 것과 어디까지 연산한 후에 자기 자신에게 넘겨줄 지 명확히 정해야함

2. 모든 재귀함수는 반복문으로 동일한 동작을 하는 함수를 만들어 낼 수 있음

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

(함수를 호출하는 게 꽤 비용이 큰 연산이기 때문)

 

재귀 함수가 자기 자신을 부를 때 스택 영역에 함수에 대한 정보가 누적 됨

스택영역에는 지역변수도 들어감

 

---

https://www.acmicpc.net/problem/1629

1629번: 곱셈

// 단순 반복문으로 작성하면 시간초과 발생
#include <iostream>
#include <math.h>

using namespace std;
using ll = long long;

ll pow(ll a, ll b, ll m) {
	// base condition
    // b == 0 일 때로 설정해도 무방
	if (b == 1) return a % m;
    
	ll val = pow(a, b / 2, m);
	val = val * val % m;
	
    // b가 짝수면 val을 return 
    // b가 홀수면 val * a % m (추가로 연산을 한번 더 해서 return)
	if (b % 2 == 0) return val;
	return val * a % m;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	long long a, b, c;
	cin >> a >> b >> c;
	cout << pow(a, b, c);

}

재귀 함수를 잘 짜려면 귀납적인 사고, 즉 base condition을 잘 잡아뒀고 k승의 결과를 토대로 2k, 2k+1승의 결과를 계산할 수 있으니 마치 도미노를 쓰러트리는 것 처럼 모든 결과가 잘 계산될 것이다로 함수를 이해할 필요가 있다.

 

위의 함수의 시간복잡도는 b가 계속 절반씩 깎이기 때문에 O(log b)

 

2023/04/13 처음 문제 풀 때 틀렸어서 다시 품

#include <iostream>
#include <math.h>

using namespace std;

long long a, b, c;

long long solve(long long a, long long b, long long c) {
	if (b == 1) return a % c;
	long long val = solve(a, b / 2, c);
	val = val * val % c;
	if (b % 2 == 0) return val;
	else return val * a % c;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> a >> b >> c;

	cout << solve(a, b, c);

	return 0;
}

b가 짝수일 때 홀수일 때를 구분하는 이유가 좀 모호했는데

아래와 같음 ! 

---

https://www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

a도 b도 아닌 기둥이 6-a-b 기둥 ( 1 + 2 + 3 = 6 이기 때문에 ) 

 

#include <iostream>
#include <math.h>

using namespace std;

void func(int a, int b, int n) {
	// base condition
	if (n == 1) { cout << a << " " << b << "\n"; return; }
	// 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);
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	// 이동 횟수 
	// ( 1 << n ) 은 left shift 연산으로 2^n 이 됨
	// 원판 n 개를 옮길 때 A 번의 이동이 필요하다면
	// 원판 n+1 개를 옮길 때는
	// n 개의 원판을 빈 곳으로 옮길 때 A 번 
	// + n+1 번째 원판을 목적지로 옮길 떄 1 번
	// + 빈 곳에 있는 n 개의 원판을 목적지로 옮길 때 A 번
	// 해서 n+1개의 원판을 옮기기 위해서는 2A+1 번의 이동이 필요하다
	// n 일 때 A , n+1 일 때 2A+1 이고 초항이 1이기 때문에
	// 수열의 일반항은 2^n -1 이 됨
	cout << (1 << n) - 1 << "\n";
	
	func(1, 3, n);
}

// 주석 정리

문제에서는 총 옮긴 횟수도 같이 물어보고 있는데 원판 k개를 옮기기 위해 A번 이동이 필요했다고 하겠다. 그러면 원판 k+1개를 옮길 때는 k개의 원판을 빈 곳으로 옮길 때 A번, k+1번 원판을 옮길 때 1번, k개의 원판을 다시 빈 곳에서 목적지로 옮길 때 A번이 필요하니 2A+1번 이동이 필요함을 알 수 있다.

 

2023/04/13

다시 풀어봄 !

위 문제와 마찬가지로 로직은 이해해서 바로 짰으나

총 횟수를 구하는 일반항을 도출하지 못함

#include <iostream>
#include <math.h>

using namespace std;

int N, K =0;

// a => b로 n개의 원판을 옮길 때 걸리는 횟수를 return 
// 과정도 출력
void hanoi(int a, int b, int n) {
	if (n == 1) {
		cout << a << " " << b << "\n";
		K++;
		return;
	}
	hanoi(a, 6 - a - b, n - 1);
	hanoi(a, b, 1);
	hanoi(6 - a - b, b, n - 1);
}

int main(void) {
	cin >> N;

	cout << (1 << N) - 1 << "\n";
	hanoi(1, 3, N);

	return 0;
}

일반항 도출 과정

---

https://www.acmicpc.net/problem/1074

1074번: Z

#include <iostream>
#include <math.h>

using namespace std;

// 2^n * 2^n 배열에서 (r,c)를 방문하는 순서를 반환하는 함수
int func(int n, int r, int c) {
	if (n == 0)	return 0;
	int half = 1 << (n - 1);
	// 2 ^ (n-1) 하면 안됨 ! 왜 ?
	if (r < half && c < half) {
		return func(n - 1, r, c);
	}
	else if (r < half && c >= half) {
		return half * half + func(n - 1, r, c - half);
	}
	else if (r >= half && c < half) {
		return 2 * half * half + func(n - 1, r - half, c);
	}
	else {
		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);
}

 

2023/04/13

다시 풀었는데 틀렸엉 ,,, 

 

재귀 부분을 아래와 같이 짰는데

// 전역 변수로 두고 계속 범위 비교 하려했음
int N, r, c;

int Z(int x, int y, int n) {
   // base condition
   if (n == 1) { if (x == c && y == r) return cnt; }

   if (r >= 0 && r < n / 2) {
      if (c >= 0 && c < n / 2) {
         // 1구역
         Z(x, y, n / 2);
      }
      else {
         // 2구역
         cnt += (n / 2) * (n / 2);
         Z(x + n / 2, y , n / 2);
      }
   }
   else {
      if (c >= 0 && c < n / 2) {
         // 3구역
         cnt += 2 * (n / 2) * (n / 2);
         Z(x, y + n / 2, n / 2);
      }
      else {
         // 4구역
         cnt += 3 * (n / 2) * (n / 2);
         Z(x + n / 2, y + n / 2, n / 2);
      }
   }
}

이처럼 코드상에서 n은 계속 줄어드는데 구역을 체크하는 r,c의 값은 바뀌지 않으니

구역이 두 번 이상 나눠지는 경우 오류가 발생함

 

n을 반으로 쪼개며 구역을 체크한 뒤에는

횟수를 카운트 하는 변수에 해당 구역의 첫 칸에 도달하기 위한 횟수를 더해준 뒤

r, c의 값도 그에 맞게 조정을 해주어야 함

 

해당 칸이 2구역의 칸이라면 (n/2)*(n/2)를 더해준 뒤

다시 칸을 세기 시작하는 기준점은 (n/2 ,0) 이 되기 때문에

y 값에 해당하는 r은 두고 x 값에 해당하는 c에 -(n/2) 연산을 해서 옮겨진 기준점에 대한 처리를 해줘야함 !