05 - 재귀 알고리즘 (자바편)

🌏 주제 : 재귀 알고리즘 

---

• 재귀란? - 어떤 사건이 자기 자신을 포함하고 있거나, 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적이라고 한다.

 

 

 

 

 

 

 

 

 

🌏  유클리드 호제법

---

• 두 정수의 최대공약수(greatest common divisor)를 재귀적으로 구하는 방법

 

package Chapter5;

import java.util.Scanner;

public class ex5_2 {
// 정수 x,y의 최대공약수를 구하여 반환
	static int gcd(int x, int y) {
		if (y == 0)
			return x;
		else 
			return gcd(y, x % y);
	}
	
	
	
	
	
	
	public static void main(String[] args) {
		// 유클리드 호제법으로 최대공약수를 구함
		Scanner scan = new Scanner(System.in);
		
		System.out.println("두 정수의 최대공약수를 구합니다.");
		System.out.print("정수를 입력하세요: ");
		int x = scan.nextInt();
		System.out.print("정수를 입력하세요: ");
		int y = scan.nextInt();
		
		System.out.println("최대공약수는 "+ gcd(x,y) + "입니다.");

	}

}
-------
두 정수의 최대공약수를 구합니다.
정수를 입력하세요: 22
정수를 입력하세요: 8
최대공약수는 2입니다.

 

 

 

 

 

 

 

 

 

 

🌏 8퀸 문제

---

• 서로 공격하여 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓으세요.

package Chapter5;

public class ex5_10 {
	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) {
		// 8퀸 문제 풀이
		set(0);

	}

}

-----
0 4 7 5 2 6 1 3
 0 5 7 2 6 3 1 4
 0 6 3 5 7 1 4 2
 0 6 4 7 1 3 5 2
 1 3 5 7 2 0 6 4
 1 4 6 0 2 7 5 3
 1 4 6 3 0 7 5 2
 1 5 0 6 3 7 2 4
 1 5 7 2 0 3 6 4
 1 6 2 5 7 4 0 3
 1 6 4 7 0 3 5 2
 1 7 5 0 2 4 6 3
 2 0 6 4 7 1 3 5
 2 4 1 7 0 6 3 5
 2 4 1 7 5 3 6 0
 2 4 6 0 3 1 7 5
 2 4 7 3 0 6 1 5
 2 5 1 4 7 0 6 3
 2 5 1 6 0 3 7 4
 2 5 1 6 4 0 7 3
 2 5 3 0 7 4 6 1
 2 5 3 1 7 4 6 0
 2 5 7 0 3 6 4 1
 2 5 7 0 4 6 1 3
 2 5 7 1 3 0 6 4
 2 6 1 7 4 0 3 5
 2 6 1 7 5 3 0 4
 2 7 3 6 0 5 1 4
 3 0 4 7 1 6 2 5
 3 0 4 7 5 2 6 1
 3 1 4 7 5 0 2 6
 3 1 6 2 5 7 0 4
 3 1 6 2 5 7 4 0
 3 1 6 4 0 7 5 2
 3 1 7 4 6 0 2 5
 3 1 7 5 0 2 4 6
 3 5 0 4 1 7 2 6
 3 5 7 1 6 0 2 4
 3 5 7 2 0 6 4 1
 3 6 0 7 4 1 5 2
 3 6 2 7 1 4 0 5
 3 6 4 1 5 0 2 7
 3 6 4 2 0 5 7 1
 3 7 0 2 5 1 6 4
 3 7 0 4 6 1 5 2
 3 7 4 2 0 6 1 5
 4 0 3 5 7 1 6 2
 4 0 7 3 1 6 2 5
 4 0 7 5 2 6 1 3
 4 1 3 5 7 2 0 6
 4 1 3 6 2 7 5 0
 4 1 5 0 6 3 7 2
 4 1 7 0 3 6 2 5
 4 2 0 5 7 1 3 6
 4 2 0 6 1 7 5 3
 4 2 7 3 6 0 5 1
 4 6 0 2 7 5 3 1
 4 6 0 3 1 7 5 2
 4 6 1 3 7 0 2 5
 4 6 1 5 2 0 3 7
 4 6 1 5 2 0 7 3
 4 6 3 0 2 7 5 1
 4 7 3 0 2 5 1 6
 4 7 3 0 6 1 5 2
 5 0 4 1 7 2 6 3
 5 1 6 0 2 4 7 3
 5 1 6 0 3 7 4 2
 5 2 0 6 4 7 1 3
 5 2 0 7 3 1 6 4
 5 2 0 7 4 1 3 6
 5 2 4 6 0 3 1 7
 5 2 4 7 0 3 1 6
 5 2 6 1 3 7 0 4
 5 2 6 1 7 4 0 3
 5 2 6 3 0 7 1 4
 5 3 0 4 7 1 6 2
 5 3 1 7 4 6 0 2
 5 3 6 0 2 4 1 7
 5 3 6 0 7 1 4 2
 5 7 1 3 0 6 4 2
 6 0 2 7 5 3 1 4
 6 1 3 0 7 4 2 5
 6 1 5 2 0 3 7 4
 6 2 0 5 7 4 1 3
 6 2 7 1 4 0 5 3
 6 3 1 4 7 0 2 5
 6 3 1 7 5 0 2 4
 6 4 2 0 5 7 1 3
 7 1 3 0 6 4 2 5
 7 1 4 2 0 6 3 5
 7 2 0 5 1 4 6 3
 7 3 0 2 5 1 6 4