재귀 알고리즘
팩토리얼 구하기
class Factorial {
static int factorial(int n) {
if (n > 0)
return n * factorial(n - 1);
else
return 1;
}
}
유클리드 호제법으로 최대 공약수 구하기
class EuclidGCD {
static int gcd(int x, int y) {
if (y == 0)
return x;
else
return gcd(y, x % y);
}
}
재귀 알고리즘 분석
💬 주어지는 알고리즘을 이용하여 원리를 파악하고, 재귀 알고리즘을 비재귀 알고리즘으로 풀어보자.
class Recur {
// 재귀 함수
static void recur(int n) {
if (n > 0)
recur(n - 1);
System.out.println(n);
recur(n - 2);
}
}◽ 구체적으로 n에 4를 넣은 경우를 분석해보자. 각 경우에 따른 전개도를 나열하면 아래와 같다.
◽ 전개도에 의하면 출력 결과는 아래와 같다.
꼬리 재귀의 제거
💬 메서드의 꼬리에서 재귀 호출하는 메서드 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;
}
}
재귀의 제거
💬 꼬리 재귀 제거와는 다르게 앞에서 호출한 재귀 제거는 쉽지 않다. 변수 n의 값을 출력하기 전에 recur(n - 1)을 먼저 수행해야 하기 때문이다.
💬 예를 들어 n이 4인 경우 재귀 호출 recur(3)의 처리가 완료되지 않으면 n의 값인 '4'를 저장해야 한다. 이에 대한 처리가 이루어지기 위해서는 앞서 구현했던 스택을 사용해야 한다.
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()) {
n = s.pop();
System.out.println(n);
n = n - 2;
continue;
}
break;
}
}
하노이의 탑
💬 간단한 예제를 이해하면서 코드를 일반화해보자.
💬 과정을 간추려서 원반 그룹(1)과 바닥 원반(2)에 대한 과정을 진행해보면서 알고리즘의 흐름을 파악하자.
💬 세 가지 과정으로 정리해볼 수 있다.
class Hanoi {
static int count = 0;
// no개의 원반을 x번 기둥에서 y번 기둥으로 옮김
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 stdIn = new Scanner(System.in);
System.out.println("하노이의 탑");
System.out.print("원반 개수 : ");
int n = stdIn.nextInt();
move(n, 1, 3);
System.out.print("진행 횟수 : " + count);
}
}
8퀸 문제
💬 서로 공격하여 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓는 알고리즘
💬 [ 규칙 1 ] : 각 열에 퀸을 1개만 배치한다.
💬 [ 규칙 2 ] : 각 행에 퀸을 1개만 배치한다.
가지 뻗기
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); // 다음 열에 퀸을 배치
}
}
public static void main(String[] args) {
set(0); // 0열에 퀸을 배치
}
}
분기 한정법
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) {
pos[i] = j;
if (i == 7)
print();
else {
flag[j] = true;
set(i + 1);
flag[j] = false;
}
}
}
}
public static void main(String[] args) {
set(0);
}
}
💬 재귀 set 함수가 호출됨에 따라 열 인덱스가 늘어나면서, flag가 막혀있지 않은 행을 앞에서부터 for 문으로 찾아다니면서 배치한다.
❓ 하지만 퀸은 가로, 세로만 갈 수 있는 것이 아닌 대각선도 이동할 수 있기 때문에 어떤 대각선에서 보더라도 퀸을 1개만 배치하는 한정 조작을 추가해야 한다.
최종 알고리즘
class EightQueen {
static boolean[] flag_a = new boolean[8]; // 각 행에 퀸을 배치했는지 체크
static boolean[] flag_b = new boolean[15]; // 우상향 방향으로 퀸을 배치했는지 체크
static boolean[] flag_c = new boolean[15]; // 우하향 방향으로 퀸을 배치했는지 체크
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;
}
}
}
}
public static void main(String[] args) {
set(0);
}
}💬 같은 행, 우상향 대각선, 우하향 대각선에 대해 각각 중복을 체크해야 하기 때문에 중복 체크를 위한 배열 3개를 만든다.
