개발기록장

재귀

3 min read

용어 정의

재귀 함수 : 자기 자신을 호출하는 작업이 포함된 함수. 반환하는 조건이 없으면 계속 호출만 하니 주의

예시

피보나치 수열

피보나치 수열 f에서 f(i)는 f(i-1) + f(i-2)이다. 이때, f(0) = 0, f(1) = 1이다.

int Fibo(int n){
	if(n == 0 || n == 1) return n;
	return Fibo(n-1) + Fibo(n-2);
}

유클리드 호제법

두 정수 m, n의 최대 공약수를 구하는 방법 m을 n으로 나눈 나머지 r이 있을 때, GCD(m, n) == GCD(n, r)

참고 : GCD = 최대 공약수, LCM = 최소 공배수 (LCD = (m * n) / GCD(m, n));

int GCD(int m, int n){
	if(m % n == 0) return n;
	return GCD(n, m%n);
}

메모이제이션

메모이제이션 : 재귀의 결과를 저장해서 불필요한 연산을 줄이는 방법

예시

피보나치 수열

피보나치 수열을 저장하는 배열을 만들고 거기서 연산함

vector<int> fibo(n, 0);
fibo[0] = 0; fibo[1] = 1;
for(int i = 2; i < n; i++) fibo[n] = fibo[n-1] + fibo[n-2];

부분합

부분합 문제를 쪼개서 생각하면 다음의 2가지 방법이 나옴

  1. 앞에서부터 N-1개의 수를 써서 원하는 합인 W를 만들 수 있음
  2. 앞에서부터 N-1개의 수를 써서 원하는 합인 W - an-1을 만들 수 있음 (마지막에 더하면 되니까)
// i : 앞에서부터 원소 갯수, w : 목표하는 합, a : 원소 배열
bool ItCanBeW(int i, int w, const vector<int> &a){
	if(i == 0){
		if(w == 0) return true;
		return false;
	}
	if(ItCanBeW(i-1, w, a)) return true;
	if(ItCanBeW(i-1, w - a[i], a)) return true;
	return false;
}

참고자료

문제 해결력을 높이는 알고리즘과 자료 구조

그래프 뷰