c++/ 자료구조&알고리즘 개념 복습하기 - 12 / 재귀, 비트 연산자

재귀

---

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

• 재귀를 사용한다는 것은 곧, 귀납적인 방식으로 풀이를 하는 것!

• 사이클이 존재하면 안된다

---

< Base Condition >

• 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다
  (Base Condition)
• 모든 입력은 Base Condition으로 수렴해야 함

---

< 재귀에 대한 정보 >

• 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 한다
• 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다
• 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간에서는 손해를 봄
  -> 반복적인 함수 호출 때문

• 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있다
  ex> 피보나치 수열을 재귀로 구현
• 재귀함수가 자기 자신을 호출할 때 스택 영역에 계속 누적이 됨

---

< 예제1 >

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

• a^n * a^n = a^2n
• 모듈러 연산 활용!
• https://sskl660.tistory.com/75 참고!!

---

< 예제2 >

• 하노이 탑
  
  

현재 n개의 원판이 있는 경우

• n-1개의 원판을 기둥1에서 기둥2로 옮긴다
• n번 원판을 기둥1에서 기둥3으로 옮긴다
• n-1개의 원판을 기둥2에서 기둥3으로 옮긴다

-> 원판이 n-1개일 때 옮길 수 있으면 원판이 n개일 때에도 옮길 수 있다

위를 함수로 나타내보자

• func(int a, int b, int n)
  -> 원판 n개를 a번 기둥에서 b번 기둥으로 옮기는 과정을 출력하는 함수

기둥은 1, 2, 3 세개가 있다
a, b, 6-a-b가 존재!!

-> n-1 개를 우선 기둥 a에서 기둥 6-a-b로 옮겨야 한다
-> n번 원판을 a에서 b로 옮긴다(출력)
-> n-1 개를 6-a-b에서 b로 옮긴다

• 하노이탑 이동횟수 = 2^k - 1

원판 k개를 이동시키는데 A번이 필요하다 하면
k+1개를 이동하려면 k개의 원판을 빈곳으로 이동하는데 A번, k+1번째 원판을 옮기는 1번, 다시 k개의 원판을 k+1 위에 옮기는데 A번이 소요된다
-> 2A+1 번 필요, 초항도 1이므로 일반항은 2^k-1

#include <iostream>
#include <string>
#include <vector>

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'; // 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'; // = 2^k - 1
	func(1, 3, k);
}

비트 연산자

• 참고 https://boycoding.tistory.com/163
• << = left shift
• (1<<k) : 1을 비트 기준으로 k칸 민다 -> 2^k 가 된다!!!

---