[자료구조] 재귀 알고리즘

[5장. 재귀 알고리즘]

1. 재귀의 기본

• 재귀란? 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라 한다. 재귀를 효과적으로 사용하면 프로그램도 간결하게 표현할 수 있다.

 

• 팩토리얼 구하기
  • 음이 아닌 정수의 팩토리얼을 구하는 방법은 재귀적으로 정의할 수 있다. 
  • TODO  재귀 호출 소스코드
  • 직접 재귀(direct) : 자기 자신과 같은 메서드를 호출하면 직접 재귀이다.
  • 간접 재귀(indirect) : 메서드 a가 메소드 b를 호출하고, 다시 메소드 b가 메소드a를 호출하는 구조이다.

int factorial(int n)
{
    if (n == 1)      
        return 1;    // 1을 반환하고 재귀호출을 끝냄

    return n * factorial(n - 1);    // n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함
}

• 유클리드 호제법
  • 최대공약수를 구하는 알고리즘 중 하나이다.
  • 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 의미한다.

int gcd_modulus(int m, int n)
{
	int t;
	while(n){
		t = m%n;
		m = n;
		n = t;
	}
	return m;
}

int gcd_recursion(int u, int v)
{
	if(v==0)
		return u;
	else
		return gcd_recursion(v, u%v);
}

• 피보나치 메소드

int fibonacci(int n){
	if(n<2)
		return n;
	else
		return fibonacci(n-1) + fibonacci(n-2);
}

 

2. 재귀 알고리즘 분석

• 재귀 알고리즘의 분석 
• 하향식 분석(top-down analysis) : 가장 위쪽에 위치한 메소드 호출부터 시작해 계단식으로 자세히 조사하는 분석 기법
• 상향식 분석(bottom-up analysis) : 아래쪽부터 쌓아 올리며 분석하는 방법 

• 재귀 알고리즘의 비재귀적 표현 : 재귀 호출을 사용하지 않고 recusive메서드를 구현해보자.
• 꼬리 재귀의 제거 : 인자를 감소한 후 메서드의 시작 지점으로 돌아가기
• 재귀의 제거 : 재귀 호출을 제거하기 위해서는 변수의 값을 잠시 저장해야 한다. 이런 문제를 잘 해결할 수 있는 데이터 구조가 스택이다.  

꼬리 재귀를 제거

vois recur(int n)
{
	while(n>0)
	{
		recur(n-1);
		std::cout << n << std:endl;
		n = n -2;
    }
}

 

 

3. 8퀸 문제

• 8퀸 문제란? 서로 공격하여 잡을 수 없도록 8개의 퀸을 8 X 8 체스판에 놓기.
• 퀸 배치하기
  • 각 열에 퀸을 1개만 배치한다.
  • 각 행에 퀸을 1개만 배치한다.
• 가지 뻗기
  • 가지를 뻗으며 모든 조합을 나열하며 문제를 푸는 방법이다.
  • 분할정복법(divide and conquer) : 하노이의 탑이나 8퀸 문제처럼 문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법을 의미한다. 
  • 문제를 세분할 때는 작은 문제의 풀이에서 원래 문제의 풀이가 쉽게 도출될 수 있게 설계해야 한다.
  • 퀵 정렬과 병합 정렬도 분할 정복 알고리즘에 해당한다.
• 분기 한정법(branching and bounding method)
  • 가지뻗기를 통해 배치 조합은 나열할 수 있지만 정답을 찾을 수 없다. 
  • 한정 조작(bounding) : 필요하지 않은 분기를 없애 불필요한 조합을 줄이는 방법이다.
  • 가지뻗기와 한정 조작을 조합하여 문제를 풀어가는 방법을 분기 한정법이라 한다.
• 8퀸 문제를 푸는 프로그램

#include <iostream>
#include <cmath>

#define MAX_SIZE 8
// 최대 MAX_SIZE queen 문제까지 해결할 수 있다.

using namespace std;

int board[MAX_SIZE];
// board[i]는 i번째 행에 퀸이 몇번째 열에 있는지 의미하는 변수이다. (행열은 서로 바뀌어도 된다.)
// 즉 board[0] = 3일때, (1,4) 혹은 (4,1) 위치에 퀸이 있다는 뜻이다.
int n;
int cnt;

void path(int y) {
	// y는 현재 몇개의 퀸이 배치되었는지를 의미하는 변수다.
	int ko;
	if( y == n ) {
		// n개의 퀸이 배치가 되었다면 이 경우는 답이다.
		cnt++;
		return;
	}
	for( int i=0; i<n; i++ ) {
		// ko는 퀸이 배치될 수 있는지를 저장하는 플래그다.
		ko = 1;
		for( int j=0; j<y; j++ ) {
			// 이미 배치가 끝난 퀸을 참고해서 i번째 칸에 퀸을 설치할 수 있는지를 확인한다.
			if( board[j] == i || abs(y-j) == abs(i-board[j]) ) {
				// j번째 줄에 있는 퀸과 같은 칸에 있거나, 대각선에 같은 곳에 있다면, i번째 칸에 대한 탐색을 중단한다.
				ko = 0;
				break;
			}
		}
		if( ko ) {
			// 여기까지 왔다면 y번째 줄에 i번째 칸에 퀸을 놔두는 것이 가능하다.
			board[y] = i;
			path(y+1);
		}
	}
}

int main() {
	int k;
	cin >> k;

	while( k-- ) {
		cin >> n;
		cnt = 0;
		path(0);

		cout << cnt << '\n';
	}

	return 0;
}

 

---

https://ko.wikipedia.org/wiki/%EC%97%AC%EB%8D%9F_%ED%80%B8_%EB%AC%B8%EC%A0%9C

여덟 퀸 문제 - 위키백과, 우리 모두의 백과사전