재귀함수

• 재귀함수는 정의단계에서 자신을 재참조하는 함수
• 전달되는 상태인 매개변수가 달라질 뿐 똑같은 일을 하는 함수
• 큰 문제를 작은 부분문제로 나눠서 풀 때 사용한다.

주의사항

• 반드시 기저사례를 써야 한다. (종료조건)
• 사이클이 있다면 쓰면 안 된다. ex) f(a)가 f(b)를 호출한 뒤 f(b)가 다시 f(a)를 호출
• 반복문으로 될 것 같으면 반복문으로 하는 것이 좋음 (함수 호출에 대한 코스트가 강함)

int fact(int n){
	if(n == 1 || n == 0 ) return 1;
	return n * fact(n - 1);
}

n - 1 즉 n이 점점 작아지다가, n이 0과 1일 때가 기저사례가 되는 것임(종료조건)

문제를 풀 때 무조건 점화식을 만들어서 푸는 것은 아니다.
하지만 어떤 문제를 봤을 때 아 이게 이런 동작이 반복되고 있구나 를 파악해야 한다.

또한 함수간에 정점과 간선을 대충 상상할 줄 알아야한다.

순열

순서와 상관 있게 뽑는다면 >> 순열
순서와 상관 없게 뽑는다면 >> 조합

문제에서

순서를 재배치하여...
~한 순서의 경우 max값을... 이런 경우 보통 순열이다.

C++에서는 next permutation 이라는 간단한 함수를 제공한다.
next_permutation(시작지점, 끝 지점)
[시작지점, 끝지점)

마지막은 포함하지 않기 때문에 vector면 그냥 begin(), end() .
오름차순을 기준으로 순열 생성.

내림차순을 기준으로 만드는 것은 prev_permutation이 있다.

int main(){
	vector<int> a = {1, 2, 3};
    do{
    	for(int i : a ) cout << i << " ";
        cout << '\n';
    }while(next_permutation(a.begin(), a.end());

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

그런데 오름차순을 기준으로 다음 순열을 생성하기 때문에, sort()를 먼저 해주고 해야 한다.

만약 여기서 두 개씩 뽑고 싶다. 하면 간단하게

int main(){
	vector<int> a = {1, 2, 3};
    do{
    	for(int i = 0; i < 2; i++){
        	cout << a[i] << " ";
        }
        cout << '\n';
    }while(next_permutation(a.begin(), a.end());

이렇게 응용이 가능하다.

재귀함수를 이용한 순열

전통적으로는 재귀함수를 이용해 순열을 구현할 수 있다.

void makePermutation(int n, int r, int depth){
	cout << n << " : " << r << " : " << depth << '\n';
	if(r == depth){
    	printV(v);
        return;
    }
    for(int i = depth; i  < n; i++){
    	swap(v[i], v[depth]);
        makePermutation(n, r, depth + 1);
        swap(v[i], v[depth]);
    }
    return;
}

n개 중에 r개를 뽑는다고 할 때이다.

근데 거의 대부분 do while next_permutation <- 무적이다.

조합

조합은 순서따위 상관없음
구현 방법은 두 가지가 있는데, 3개 이하 뽑는거는 중첩 for문이 좋고, 4개 이상은 재귀가 좋다.

1. 재귀

void combi(int start, vector<int> b){
	if(b.size() == k){
    	/* logic */
        return;
    }
    for(int i = start + 1 ; i < n; i++){
    	b.push_back(i);
        combi(i, b);
        b.pop_back();
    }
    return;
}

vector<int> b;
combi(-1, b);

이건 그냥 외우는 걸 추천. 강사와의 약속 ㅎㅎ
"인덱스" 를 기반으로 뽑는 것임. 0 1 2 같은 경우 0번, 1번, 2번 인덱스를 뽑는다는거.

2. for문

3개를 뽑는다

for(int i = 0 ; i < n; i++){
	for(int j = = + 1 ; j < n; j++){
    	for(int k = j + 1; k < n; k++){
        	cout << i << " : " << j << " : " << k << '\n';
       	}
    }
}

아주 이지!!! 꼭 외우기!!