[알고리즘강의] Recursion

do_large·2021년 1월 25일

강의 알고리즘

알고리즘강의

목록 보기

1/2

알고리즘 강의를 보고 정리한 내용입니다.

재귀함수

자기자신을 호출하는 함수

무한루프에 빠지지 않으려면
1. 종료조건을 줘야한다. 적어도 무한루프에 빠지지 않는 하나이상의 경우가 존재해야 한다. (base case)
2. 무한루프를 반복하다 보면 결국 base case로 수렴해야 한다.

피보나치, 팩토리얼
최대공약수(gcd), 최소공배수

수학함수뿐 아니라 다른 많은 문제들을 해결할 수 있다.

문자열의 길이를 계산하는 방법

이런 개념?이 신기하다....
이렇게 되돌아가는 방식으로 접근해보자..!

코드로 구현하면 이렇게 할 수 있다.

문자열을 하나씩 줄여가면서 ("")에 가까워지는 방식!

모든 순환함수는 반복문으로 변경가능하다.
그 역도 성립한다. 모든 반복문은 recursion으로 표현가능하다.
순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는것을 가능하게 한다.
하지만 함수호출에 따른 오버헤드가 발생할 수 있다.

recursion 설계

적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함
무한루프에 빠지지 않는지 확인해야함
모든 case는 결국 base case로 수렴해야함!!!!!!
암시적 매개변수를 명시적 매개변수로 바꿔라!~!!!

back-tracking

길을 가다가 막다른 길을 만나면 다시 돌아간다.
내가 가장 최근에 내렸던 결정을 번복하고 다른 선택지를 찾는다.

상태공간 트리를 보자.

상태공간 트리의 모든 노드를 탐색해야하는것은 아니다.
내가 선택한 길이 잘못된 길이라는 것을 알게되면 뒤로 돌아가서 다른 선택지를 선택하는것이다.

백트래킹은 깊이우선탐색 방식으로 탐색해서 해를 찾는 알고리즘을 말한다.

백트래킹 예시

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

문제설명
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 M개를 고른 수열

같은 수를 여러 번 골라도 된다.

고른 수열은 비내림차순이어야 한다

풀이방법

main함수에서 n과 m을 입력받는다.
per(permutation)이라는 배열에 순열을 구성할 값들을 저장한다.
go라는 함수가 재귀호출을 통해 순열을 구성한다.
- go 함수에서 cnt가 m과 같은경우가 탈출할 수 있는 조건이다.
go 함수를 호출할 때마다 cnt값을 1 씩 증가시키므로, 무한루프에 빠지지 않게 해준다.
- go함수에서 for문을 보면 재귀호출이 발생한다.
- go함수의 매개변수를 보면 첫번째 매개변수인 cnt는 현재 몇개의 값을 구성했는지 알려준다.(동적으로 구성한 순열의 길이 또는 per배열에 들어간 값들의 개수)
- go함수의 두번째 매개변수인 cur는 for문에서 ★i의 초기값★이 된다.
- 현재 per배열의 cnt번째에 i에 1을 더한값을 넣는다. (왜냐하면 배열의 index는 0부터 시작하지만 순열에는 1부터 N사이의 값이 들어가야 하기 때문이다.)
- 그리고 똑같은 값을 순열에 포함시킬 수 있으므로 재귀함수를 호출할 때는 go(cnt+1, i)를 호출한다. 만약 똑같은 값을 순열에 포함할 수 없을때는 go(cnt+1, i+1)을 호출하면 된다.
- 이부분이 이해되지 않는다면, 코드가 작동하는 방식을 손으로 그려보면 도움이 된다.

#include <iostream>

using namespace std;

void go(int cnt, int cur);
int n, m;
int per[8] = { 0, };

int main(void) {
	cin >> n; // 전체수
	cin >> m; // 순열 개수

	go(0, 0);
	return 0;
}


void go(int cnt, int cur) {
	if (cnt == m) {
		for (int i = 0; i < m; i++) {
			cout << per[i] << " ";
		}
		cout << "\n";
		return;
	}

	for (int i = cur; i < n; i++) {
		per[cnt] = i + 1;
		go(cnt + 1, i);
	}
}

위 문제를 이해하기 쉽게 그림으로 구성해 봤는데

1. 레벨 1에서 1이 선택되고, 그다음 레벨 2에서 우선 1이 선택된다.
2. 총 선택된 값의 개수인 2가 m과 동일하기 때문에 레벨2에서 다시 레벨1로 올라간다.(백트래킹)
3. 레벨2단계의 값 중 1은 이미 사용?되었으므로 그다음 값인 2를 선택하게 된다.
4. 위의 2번째 과정이 반복된다.
5. 레벨 2단계의 숫자 3을 선택하는 과정도 같다.
6. 위의 2번째 과정이 반복된다.
7. [1, 1], [1, 2], [1, 3]이 출력되었다. 그래서 레벨1의 선택값이 2가되고, 2에서 선택할 수 있는 레벨2의 값들도 위의 과정과 동일하게 진행되어 [2, 2], [2, 3]이 출력된다.
8. 나머지 과정은 알아서 추론하시길..!

do_large

다음 포스트

[알고리즘강의] Recursion