알고리즘 공부 - 재귀함수 2편(하노이의 탑, 재귀 제거)

이번 포스팅에선 지난 재귀함수 1편에 이어서 공부해보겠습니다!

 

재귀함수를 제거하거나 비재귀적으로 표현하려면 어떻게 해야할까요? 

 

꼬리 재귀의 제거

메서드의 꼬리에서 재귀 호출하는 메서드 recur(n-2)라는 말은 '인자로 n-2를 전달하여 recur 메서드를 호출한다.' 는 의미 입니다. 따라서 이 호출은 다음과 같이 바꿀 수 있습니다.

n 의 값을 n - 2로 업데이트하고 메서드의 시작 지점으로 돌아갑니다.

static void recur(int n) {
	while (n > 0) {
    	recur(n - 1);
        System.out.println(n);
        n = n-2;
	}
}

이렇게 하면 메서드의 끝에서 실행하는 꼬리 재귀(tail recursion) 는 쉽게 제거할 수 있습니다. 

 

일반 재귀의 제거

그런데 꼬리 재귀와는 다르게 앞에서 호출한 재귀 메서드의 제거는 쉽지 않습니다. 왜냐하면 변수 n의 값을 출력하기 전에 recur(n-1)을 먼저 수행해야 하기 때문입니다. 예를 들어 n이 4인 경우 재귀 호출 recur(3)의 처리가 완료되지 않으면 n의 값인 '4' 를 저장해야 합니다. 그래서 재귀 호출 recur(n-1)을 아래처럼 바꿀 수 없습니다.

n의 값을 n-1 로 업데이트하고 메서드의 시작지점으로 돌아갑니다.
현재 n의 값을 '잠시' 저장합니다.
저장했던 n을 다시 꺼내 그값을 출력합니다.

이런 재귀 호출을 제거하려면 '잠시' 저장할 필요가 있습니다. 이를 잘 해결할 수 있는 자료구조가 Stack 입니다.

static void recur(int n) {
	IntStack s = new IntStack(n);
    
    while(true) {
    	if(n>0) {
        	s.push(n);
            n = n-1;
            continue;
        }
        if(s.isEmpty() != true) {
        	n = s.pop();
            System.out.println(n);
            n = n - 2;
            continue;
        }
        break;
    }
}

1. n 값 4를 스택에 푸시합니다.
2. n 값을 하나 줄여 3으로 만듭니다.
3. continue문에 의해 while문의 처음으로 돌아갑니다.
4. 스택에서 팝한 값 1 을 n에 꺼내 놓습니다. 
5. n 값 1을 출력합니다.
6. n 값을 2 줄여 -1로 만듭니다.
7. continue문에 의해 while문의 처음으로돌아갑니다.

 

 

하노이의 탑( Towers of Hanoi )

이번에는 쌓아 놓은 원반을 최소의 횟수로 옮기기 위한 알고리즘 '하노이의 탑'에 대해 공부해보겠습니다.

작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제입니다. 모든 원반은 크기가 다르고 처음에는 모든 원반이 이 규칙에 맞게 첫 번째 기둥에 쌓여 있습니다. 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기면 됩니다.

원반은 1개씩만 옮길 수 있고 큰 원반을 작은 원반위에 쌓을 수 없습니다.

 

원반 1을 첫 번째 기둥에서 세 번째 기둥으로 
원반 2를 첫 번째 기둥에서 두 번째 기둥으로 
원반 1을 세 번째 기둥에서 두 번째 기둥으로
원반 3을 첫 번째 기둥에서 세 번째 기둥으로
원반 1을 두 번째 기둥에서 첫 번째 기둥으로 
원반 2를 두 번째 기둥에서 세 번째 기둥으로 
원반 1을 첫 번째 기둥에서 세 번째 기둥으로 

class Hanoi {
	static void move(int no, int x, int y) {
    	if(no > 1) move(no-1, x, 6-x-y);
        
        System.out.println("원반 "+ no +" 를" + x + "기둥에서 "+ y + "기둥으로 옮김");
        
        if(no > 1) move(no-1, 6-x-y, y);
    }
    
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        System.out.print("원반의 갯수 : ");
        int n = sc.nextInt();
        
        move(n,1,3); // 1번 기둥의 n개의 원반을 3번기둥으로 옮김
    }
}

하노이의 탑 알고리즘을 코드로 표현해보자면 이러하다.

no 개의 원반이 주어진다.
move 메서드를 no 개의 원반과, 시작지점의 기둥 index, 목표지점의 기둥 index를 파라미터로 전달한다.
no 개의 원반이 1보다 크다면 재귀하면서 no - 1 하면서 , y값인 2번기둥으로 옮기고 재귀한다.
그 다음 다시 no - 1 만큼 원반을 소비하고, 6 - x (1) - y (2) = 3번 기둥으로 옮기고 다시 재귀한다.
이를 반복하면서 원반을 3번 기둥까지 모두 옮겨 no 개의 원반이 0이 될때까지 재귀하는 것이다.

 

8퀸 문제

8퀸 문제란 (8-Queen problem) 재귀 알고리즘에 대한 이해를 돕기 위한 예제로 자주 등장한다고 합니다.

문제는 서로 공격하여 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓으세요  입니다.

이문제의 해답은 92가지의 조합이 있는데 행과 열을 모두 어긋나게 하면서 대각선까지 신경써야합니다.

 

class Queen {
	// 각 열의 퀸의 위치
	static int[] pos = new int[8];
    
    // 각 열의 퀸의 위치를 출력합니다. 
    static void print() {
    	for(int i=0; i< 8; i++) {
        	System.out.printf("%2d", pos[i]); 
        }
        System.out.println();   
    }
    
    // i 열에 퀸을 놓습니다. 
    static void set(int i) {
    	for(int j=0; j<8; j++) {
        	// 퀸을 j행에 배치합니다.
        	pos[i] = j;
            // 모든열에 배치합니다.
            if(i == 7) print();
            // 다음열에 퀸을 배치합니다.
            else set(i+1);
        }
    }
    
    public static void main(String[] args) {
    	// 0열에 퀸을 배치합니다. 
    	set(0);
    }
}

 

이렇게 가지를 뻗으며 퀸을 배치하는 조합을 모두 나열했습니다. 이런 방법을 가지뻗기(branching) 라고 합니다.

하노이의 탑이나 8퀸 문제처럼 문제를 세분화하고 세분된 문제풀이를 결합해 전체 문제를 풀어가는 기법을 정복법(divide and conquer) 

라고 합니다.