4장의 스택과 큐의 경우 이전에 따로 포스팅한적이 있기 때문에 (중복되는 내용밖에 없어서....) 과감히 생략하고(혼자 공부하고) 5장의 재귀 알고리즘을 정리한다.
재귀란?
어떤 사건이 자기 자신을 포함하고 다시 자기자신을 사용하여 정의될 때, 재귀적이라고한다.
(*참고: 뒤에서 배울 '병합정렬', '퀵 정렬', '이진 검색 트리' 등에 사용된다)
재귀 호출(recursive call): 재귀적으로 호출된다는 말 그대로의 의미이고, 직접 재귀와 간접 재귀로 나뉜다.
직접 재귀 VS 간접 재귀
직접 재귀란 어떤 메서드 내부에서 자기 자신(메서드)을 직접 호출하는 것이고, 간접 재귀는 메서드 a가 메서드 b를 호출하고, 다시 메서드 b가 메서드 a를 호출하는 구조로 이루어진다.
유클리드 호제법
두 정수의 최대공약수(GCD)를 재귀적으로 구하는 방법을 알아보자. 두 정수를 직사각형의 두 변의 길이라고 생각하면 두 정수의 최대공약수를 구하는 문제는 다음처럼 바꿀 수 있다.
public class EuclidGCD {
// 정수 x,y의 최대공약수를 구하여 반환한다.
static int gcd(int x, int y) {
if (y == 0) {
return x;
} else {
return gcd(y, x % y);
}
}
}이 방식은 '직사각형을 정사각형으로 완전히 채웠을 때, 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하라'는 문제와 착안점이 같다.
재귀 알고리즘 분석
재귀 알고리즘을 분석하는 두가지 방법인 하향식(top down) 분석과 상향식(bottom up) 분석을 살펴보자.
먼저 아래의 코드를 살펴보자
package problem.algorithm.chap5;
// 재귀 함수 이해하기
import java.util.Scanner;
public class Recur {
// 재귀 함수
static void recur(int n) {
if (n > 0) {
recur(n - 1);
System.out.println(n);
recur(n-2);
}
}
public static void main(String[] args) {
Scanner stdIn = new Scanner(System.in);
System.out.print("정수를 입력하세요: ");
int x = stdIn.nextInt();
recur(x);
}
}
위 프로그램의 재귀 메서드인 recur 메서드를 통해 재귀에 대해 좀 더 자세히 알아보자.
recur 메서드는 factorial 메서드나 gcd 메서드와 달리 메서드 안에서 재귀 호출을 2회 실행한다. 이처럼 재귀 호출을 여러번 실행하는 메서드를 순수하게 재귀적이라하며, 실제 동작은 매우 복잡하다. 이런 복잡한 구조를 가진 재귀 메서드는 좀 더 전략적으로 분석해야 한다. 여기서는 recur 메서드를 하향식과 상향식의 두 방법으로 분석한다.
하향식 분석
매개변수 n으로 4를 전달하면 recur 메서드는 아래 과정을 순서대로 실행한다.
|
(1) recur(3)을 실행한다. (2) 4를 출력한다. (3) recur(2)를 실행한다. |
물론 (2)에서 4를 출력하는 것은 (1)의 recur(3) 실행이 완료된 다음이다. 따라서 recur(3)을 먼저 조사해야 한다.
(1) recur(3)을 실행한다.
(1)-1. recur(2)를 실행한다.
(1)-2. 3을 출력한다.
(1)-3. recur(1)를 실행한다.
(2) 4를 출력한다.
(3) recur(2)를 실행한다.
(3)-1. recur(1)를 실행한다.
(3)-2. 2을 출력한다.
(3)-3. recur(0)를 실행한다.
이런식으로 처리과정을 더 세부적으로 확장해나갈 수 있다. (recur(3)을 한번 호출하고, 다시 recur(3)을 호출한 상자로 돌아가기 위해서는 많은 단계를 거쳐야 함을 알 수 있다)
이처럼 가장 위쪽에 위치한 상자의 메서드 호출부터 시작해 계단식으로 자세히 조사하는 분석 기법을 하향식 분석(top-down analysis)이라고 한다. 그런데 이 코드에서는 recur(1), recur(2)의 호출이 여러 번 있다(같은 호출이 여러번 있다) 꼭대기(top)부터 분석하면 이렇게 같은 메서드의 호출이 여러 번 나올 수 있기 때문에 하향식 분석이 마냥 효율석이라고 할 수 없다.
상향식 분석
하향식 분석과는 대조적으로 아래쪽부터 쌓아 올리며 분석하는 방법이 상향식 분석(bottom-up analysis)이다. recur 메서드는 n이 양수일 때만 실행하므로 먼저 recur(1)을 생각해보자. recur(1)이 수행하는 작업은 아래와 같다.
|
(1). recur(0)을 실행한다. (2). 1을 출력한다. (3). recur(-1)을 실행한다. |
여기서 (1)과 (3)의 recur(0)과 recur(-1)은 출력할 내용이 없다. 따라서 (2)의 1만 출력한다. 그럼 recur(2)에 대해 생각해보자
|
(1). recur(1)을 실행한다. (2). 2를 출력한다. (3). recur(0)을 실행한다. |
(1)의 recur(1)은 1을 출력하고 (3)의 recur(0)은 출력할 내용이 없다. 전체 과정을 거치면 1과 2가 출력된다. 이 작업을 recur(4)까지 쌓아올려 설명한 내용이 아래의 그림이다.
recur(-1) : 아무것도 하지 않음
recur(0) : 아무것도 하지 않음
recur(1) : recur(0) 1 recur(-1) → 1
recur(2) : recur(1) 2 recur(0) → 1 2
recur(3) : recur(2) 3 recur(1) → 1 2 3 1
recur(4) : recur(3) 4 recur(2) → 1 2 3 1 4 1 2
재귀 알고리즘의 비재귀적 표현
recur 메서드를 재귀 호출을 사용하지 않고 구현하는 방법에 대해 살펴본다.
꼬리 재귀의 제거
메서드의 꼬리에서 재귀 호출하는 메서드 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'를 저장해야 한다)
n의 값을 n - 1로 업데이트하고 메서드의 시작 지점으로 돌아간다. (왜냐하면 다음과 같은 처리를 미리 해야하기 때문이다)
현재 n의 값을 '잠시' 저장한다. (또 recur(n-1)의 처리가 완료된 다음에 n의 값을 출력할 때는 다음 과정을 따르게 된다)
저장했던 n을 다시 꺼내 그 값을 출력한다.
이런 재귀 호출을 제거하기 위해서는 변수 n의 값을 '잠시' 저장해야 한다는 사실을 알았다. 이때 이런 문제를 잘 해결할 수 있는 데이터 구조가 스택(stack)이다. 다음은 스택을 사용하여 비재귀적으로 구현한 recur 메서드이다.
static void recur(int n) {
IntStack s = new IntStack(n);
while (true) {
if (n > 0) {
s.push(n); // n의 값을 푸시
n = n - 1;
continue;
}
if (s.isEmpty() != true) { // 스택이 비어 있지 않다면
n = s.pop(); // 저장하고 있던 스택의 값을 팝
System.out.println(n);
n = n - 2;
continue;
}
break;
}
}위의 프로그램에서 recur(4)를 호출한 다음의 과정을 살펴본다. 매개변수로 전달받은 값 '4'는 0보다 크므로 맨 앞의 if문에 의해 다음과 같은 과정이 진행된다.
|
(1). n 값 4를 스택에 푸시한다. (2). n 값을 하나 줄여 3으로 만든다. (3) continue문에 의해 while문의 처음으로 돌아간다. |
n 값 3은 0보다 크므로 첫 번째 if문이 실행된다. 그 결과 위의 과정이 반복되고, 스택에는 4, 3, 2, 1이 쌓이게 된다. 마지막으로 스택에 1을 쌓은 다음 0이 되고 while문의 처음으로 돌아간다. 그러면 n값이 0이 되므로 첫 번째 if문은 그냥 지나가고 다음의 if문에 의해 다음과 같은 과정이 진행된다.
|
(4). 스택에서 팝한 값 1을 n에 꺼내놓는다. (5). n 값 1을 출력한다 (6). n 값을 2 줄여 -1로 만든다. (7). continue문에 의해 while문의 처음으로 돌아간다. |
n 값이 -1 이므로 다시 뒤쪽의 if문이 실행되고 스택에서 2가 팝된다. 그 이후의 순서는 생략한다.....
하노이의 탑
쌓아 놓은 원반을 최소의 횟수로 옮기기 위한 알고리즘인 '하노이의 탑'에 대해 살펴본다.
하노이의 탑(Tower of Hanoi)은 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제이다. 모든 원반은 크기가 다르고 처음에는 모든 원반이 이 규칙에 맞게 첫 번째 기둥에 쌓여있다. 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮기면 된다. 원반은 1개씩만 옮길 수 있고, 큰 원반을 작은 원반 위에 쌓을 수는 없다. 코드로 구현하면 아래와 같다.
public 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);
}
}
}
이 프로그램은 기둥 번호를 정수 1, 2, 3으로 나타낸다. 기둥 번호의 합이 6이므로 시작기둥, 목표 기둥이 어느 기둥이더라도 중간 기둥은 6 - x - y로 구할 수 있다. 원반은 no개이므로 move 메서드는 아래와 같은 과정을 거친다.
|
1. 바닥 원반을 제외한 그룹(원반[1] ~ 원반[no - 1])을 시작 기둥에서 중간 기둥으로 옮긴다. 2. 바닥 원반 no를 시작 기둥에서 목표 기둥으로 옮겼음을 출력한다. 3. 바닥 원반을 제외한 그룹(원반[1] ~ 원반[no - 1])을 중간 기둥에서 목표 기둥으로 옮긴다. |
8퀸 문제
이번에는 8퀸 문제에 대해 알아본다. 이 문제는 하노이의 탑과 마찬가지로 작은 문제로 세분하여 해결한다. 8퀸 문제(8-Queen problem)은 재귀 알고리즘에 대한 이해를 돕기 위한 예제로 자주 등장한다. (뿐만 아니라 19세기의 유명한 수학자 가우스(C. F. Gauss)가 잘못된 해답을 낸 사실로 잘 알려진 문제다) 문제는 아래와 같다.
| 서로 공격하여 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓으세요. |
(퀸은 서 있는 지점에서 체스판의 어떤 지점으로든 여덟방향으로 직선 이동이 가능하다)
이 문제의 정답은 92가지의 조합이다.
체스판의 가로줄을 행, 세로 줄을 열이라 하고 배열 인덱스에 맞추어 행과 열에 0 ~ 7의 번호를 부여한다.
퀸 배치하기
8개의 퀸을 배치하는 조합은 모두 몇 가지인지 알아보자. 체스판은 64간이므로 처음에 퀸을 1개 배치할 때는 64칸 중 아무 곳이나 선택할 수 있다. 다음 퀸은 63칸에서 임으로 선택한다.. 이런식으로
| 64 X 63 X 62 X 61 X 60 X 59 X 58 X 57 = 178,462,987,637,760 |
가지의 조합이 만들어진다. 하지만 이 조합을 모두 나열하면서 8퀸 문제의 조건을 만족하는지 조사하는 것은 비효율적이다.(실질적으로 불가능하다...!) 퀸은 자신과 같은 열에 있는 다른 퀸을 공격할 수 있으므로 아래와 같은 규칙을 세울 수 있다.
| [규칙1] 각 열에 퀸을 1개만 배치한다. |
이렇게 하면 퀸을 배치하는 조합의 수는 많이 줄어들었지만 여전히 그 수는
| 8 x 8 x 8 x 8 x 8 x 8 x 8 x 8 = 16,777,216 |
가지로 엄청나게 많다. 이 경우에는 자신과 같은 행에 있는 다른 퀸을 공격할 수 있는 경우의 수를 고려하지 않은 경우입니다.
| [규칙2] 각 행에 퀸을 1개만 배치한다. |
이렇게 하면 조합의 개수는 더 줄어든다.
이런 방식으로 이 조합을 나열하는 알고리즘은 다양하게 만들 수 있다.
가지 뻗기 (규칙 X)
public class QueenB {
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++) {
pos[i] = j; // 퀸을 j행에 배치한다.
if (i == 7) { // 모든 열에 배치한다.
print();
} else {
set(i + 1); // 다음 열에 퀸을 배치한다.
}
}
}
}
분기 한정법 (규칙2만 적용)
public class QueenBB {
static boolean[] flag = new boolean[8]; // 각 행에 퀸을 배치했는지 체크
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++) {
if (flag[j] == false) { // j행에는 퀸을 아직 배치하지 않았다면
pos[i] = j; // 퀸을 j행에 배치한다.
if (i == 7) { // 모든 열에 배치한 경우
print();
} else {
flag[j] = true;
set(i + 1);
flag[j] = false;
}
}
}
}
}
8퀸 문제 풀이(모든 규칙 적용)
public class EightQueen {
static boolean[] flag_a = new boolean[8]; //각 행에 퀸을 배치했는지 체크
static boolean[] flag_b = new boolean[16]; // / 대각선 방향으로 퀸을 배치했는지 체크
static boolean[] flag_c = new boolean[16]; // \ 대각선 방향으로 퀸을 배치했는지 체크
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++) {
if (flag_a[j] == false && // 가로(j행)에 아직 배치하지 않았다.
flag_b[i + j] == false && // 대각선 /에 아직 배치하지 않았다.
flag_c[i - j + 7] == false) { // 대각선 \에 아직 배치하지 않았다.
pos[i] = j; // 퀸을 j행에 배치한다.
if (i == 7) { // 모든 열에 배치한다.
print();
} else {
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = true;
set(i + 1);
flag_a[j] = flag_b[i + j] = flag_c[i - j + 7] = false;
}
}
}
}
}
'알고리즘' 카테고리의 다른 글
| 8. 위상 정렬 (0) | 2021.08.18 |
|---|---|
| 9. 그래프이론 - 신장 트리 (0) | 2021.08.17 |
| Do it! 자료구조와 함께 배우는 알고리즘 입문 - 검색 (0) | 2019.12.18 |
| [알고리즘] GCD 최대공약수, LCM 최소공배수 (0) | 2019.11.24 |
| [알고리즘] 순열(Permutation) (0) | 2019.10.12 |