이번 주는 재귀 알고리즘에 대해 학습하고 대표 문제들에 대한 풀이를 할 예정이다.
지금까지는 구현이나 간단한 연습 문제였다면 이번 시간에는 대표 문제들이 나오기 때문에
코딩테스트 준비에도 유용한 시간이 될 것 같다.
특히 재귀는 정렬과 이진 검색 트리에서도 자주 활용된다.
재귀: 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여
정의될 때 재귀적(recursive)이라고 한다.
- 팩토리얼 구하기
- 0! = 1
- n > 0 이면 n! = n x (n-1)! / (n-1)! = (n-1) x (n-2)! / ,,,,,
- 우변에 있는 식으로 반복적으로 활용하여 구현할 수 있다.
import java.util.Scanner;
class WeekFour {
static int factorial(int n){
if(n>0){
return n*factorial(n-1);
}
else{
return 1; // 마지막은 1이다.
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("정수를 입력하세요 : ");
int n =sc.nextInt();
System.out.println(n+"의 팩토리얼은 "+factorial(n) + "입니다.");
}
}
-구체적인 과정
이러한 메소드 호출을 재귀 호출(recursive call)이라고 한다.
자기 자신을 호출한다기 보다 자신과 똑같은 메서드를 호출한다고 이해하면 자연스럽다.
- 직접 재귀
- factorial 메소드처럼 자기 자신과 똑같은 메소드를 호출하면 직접 재귀
- 간접 재귀
- 메소드 a 가 메소드 b를 호출하고
메소드 b가 메소드 a를 다시 호출하는 구조
- 메소드 a 가 메소드 b를 호출하고
- 유클리드 호제법
- 두 정수의 최대공약수를 재귀적으로 구한다
- 두 정수를 직사각형의 두 변으로 간주했을 때, 큰 값을 작은 값으로 나눈 나머지에 대해 연속적으로 나눈다.
최종적으로 나누어 떨어지는 수가 최대공약수이다.
기억하기 쉽도록 이 직사각형을 머리에 그려두자!
import java.util.Scanner;
class WeekFour {
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 sc = new Scanner(System.in);
System.out.println("두 수의 최대공약수를 구합니다.");
System.out.print("정수를 입력하세요 : ");
int x = sc.nextInt();
System.out.print("정수를 입력하세요 : ");
int y = sc.nextInt();
System.out.println("최대공약수는 " + gcd(x, y) + "입니다.");
}
}
큰 수를 작은 수로 나눈 나머지에 대해 다시 나누는 과정을 코드로 구현한다.
재귀 알고리즘의 분석
static void recur(int n){
if(n > 0){
recur(n - 1);
System.out.println(n);
recur(n - 2);
}
}
}
이 코드는 재귀 호출을 2회 실행한다.
이처럼 재귀 호출을 여러 번 하는 메서드를 순수하게 재귀적이라고 한다.
매우 복잡한 구조를 지니기 때문에 하향식 분석과 상향식 분석으로 나누어서 파악할 수 있다.
- 하향식 분석(top-down analysis)
- 가장 위쪽에 위치한 상자의 메서드 호출부터 시작해 계단식으로 분석하는 기법
top부터 분석하면 같은 메서드의 호출이 여러 번 나올 수 있다. => 하향식 분석이 반드시 효율적이진 않다.
- 상향식 분석 (bottom-up analysis)
- 아래쪽부터 쌓아 올리며 분석하는 방법
재귀 알고리즘의 비재귀적 표현
- 꼬리 재귀의 제거
- recur을 재귀를 한 번만 호출하는 메서드로 변경한다.
static void recur(int n){
while(n > 0){
recur(n - 1);
System.out.println(n);
n = n - 2;
}
}
}
recur(n-2) 라는 말은 n의 값을 n-2로 업데이트하고 메서드의 시작점으로 돌아간다는 의미이다.
- 재귀의 제거
- recur에서 재귀를 완전히 제거하기 위해서는 recur(n-1)을 완료하고 n을 출력해야 한다는 점이 걸린다.
- 이렇게 되면 n의 값을 n-1로 업데이트 하게 되고 n이 바뀌어버린다.
- 따라서 n의 값을 잠시 저장했다가 recur(n-1)처리가 완료되면 다시 꺼내어 출력한다.
- 스택을 이용하여 비재귀적으로 구현한다.
static void recur(int n){
if(n > 0){
recur(n - 1);
System.out.println(n);
recur(n - 2);
}
}
}
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;
}
}
스택이 구현되어 있다는 가정 하에 진행
이런 식으로 재귀를 사용하지 않고 구현 가능하다!
하노이의 탑
쌓아놓은 원반을 3개의 기둥에서 최소의 횟수로 옮기기 위한 알고리즘
import java.util.Scanner;
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); //기둥 번호의 합이 6이므로 중간 기둥으로 구할 수 있다.
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
System.out.println("하노이의 탑");
System.out.print("원반 개수 : ");
int n = sc.nextInt();
move(n, 1, 3);
}
}
코드상으로만 보면 상당히 복잡하다.
출력 순서를 위주로 보면 쉽다.
- 그룹(1번과 2번)을 중간기둥으로 옮긴다.
- 바닥을 목표 기둥으로 옮긴다.
- 그룹을 중간 기둥에서 목표 기둥으로 옮긴다.
이렇게 크게 3단계로 이루어져 있다.
목표 기둥은 옮기고자 하는 기둥, 중간 기둥은 남은 하나의 기둥이다.
문제는 총 3개의 기둥을 전제로 하기 때문에 6-x-y로 목표 기둥이 어느 것이든 중간 기둥을 구할 수 있다.
저번 시간에 작성했던 제네릭 기법에 대해 다시 복습해보자.
제네릭은 상자에 무엇을 담을지 미리 라벨을 붙여놓는 것이다.
// 제네릭 사용 (<String> 라벨 부착)
List<String> list = new ArrayList<>();
list.add("사과");
// list.add(10); // <--- 컴파일러가 빨간 줄을 그으며 미리 에러를 냅니다! "여기엔 숫자 못 넣어!"
// 꺼낼 때 편함
String text = list.get(0); // (String) 형변환 필요 없음
이는 자바에서 지원하는 기능이기 때문에 안전한 방법으로 사용 가능하다.
제네릭 클래스는 클래스나 인터페이스 이름 바로 뒤에 <Type> 같은 형식의 파라미터를 붙여 선언한다.
파라미터를 쉼표로 구분하면 여러 개를 지정할 수 있다.
- 제네릭은 원래 엄격하다: List<Number>에 List<Integer>를 넣을 수 없다.
- 와일드카드로 유연하게 푼다: List<? extends Number>라고 쓰면 List<Integer>도 받아준다.
- extends: ~의 자식들만 (읽기 전용으로 많이 씀)
- super: ~의 조상들만 (쓰기 전용으로 많이 씀)
public static final Comparator<PhyscData> HEIGHT_ORDER
= new HeightOrderComparator();
private static class HeightOrderComparator implements Comparator<PhyscData> {
public int compare(PhsycData d1, PhsycData d2){
return (d1.height > d2.height) ? 1 :
(d1.height < d2.height) ? -1 : 0;
}
}
연습 문제에서의 예시: 오름차순으로 정렬하기 위한 comparator 코드이다. d1이 더 크면 1을 반환하고 d1이 d2보다 작으면 -1을 반환한다. 같으면 0이다. 단순 판단의 작업을 수행한다.
- 제네릭 스택 클래스 작성
- 스택의 본체인 배열의 타입을 임의로 설정하여 작성한 코드이다.
- E타입의 배열에서 요소를 푸시, 팝, 읽기로 한다.
public Gstack(int capacity) {
ptr = 0;
max = capacity;
try{
stk = (E[]) new Object[max]; //임의의 데이터형이기 때문에 Object 타입으로
//생성하고 E 타입으로 캐스팅 해야한다.
}catch(OutOfMemoryError e){
max = 0;
}
}
public static class OverflowException extends RuntimeException{
public OverflowException(){}
}
public static class EmptyStackException extends RuntimeException{
public EmptyStackException(){}
}
public E push(E x) throws OverflowException{
if(ptr >= max){
throw new OverflowException();
}
return stk[ptr++] = x;
}
public E pop() throws EmptyStackException{
if(ptr <= 0){
throw new EmptyStackException();
}
return stk[--ptr];
}
public E peek() throws EmptyStackException{
if(ptr <= 0){
throw new EmptyStackException();
}
return stk[ptr - 1];
}
public void dump(){
if(ptr <= 0){
System.out.println("스택이 비어있습니다.");
}
else{
for(int i = 0; i < ptr; i++){
System.out.println(stk[i] + " ");
}
System.out.println();
}
}
public int capacity(){
return max;
}
public int size(){
return ptr;
}
}
사용자 정의 예외 코드를 작성했는데 제네릭 타입이라 static을 붙여서 사용한다.
생성자에서 generic을 바로 new해서 인스턴스를 생성할 수 없기 때문에
Object타입으로 생성하고 임의의 데이터형인 E형으로 캐스팅한다.
큐도 마찬가지 방법으로 수행할 수 있었다.
- 이중스택 구현
public class TwoStack {
private int max;//스택 용량
private int ptr;//스택 포인터
private int ptr2;
private int[] stk; //스택 본체
public class EmptyStackException extends RuntimeException{
public EmptyStackException(){}
}
public class OverflowException extends RuntimeException{
public OverflowException(){}
}
public TwoStack(int capacity){
ptr = 0;
max = capacity;
ptr2 = max;
try{
stk = new int[max];
}catch(OutOfMemoryError e){
max = 0;
}
}
public int push(int x) throws OverflowException{
if(ptr >= ptr2){
throw new OverflowException();
}
return stk[ptr++] = x; //푸시한 값을 반환
}
public int push2(int x) throws OverflowException{
if(ptr >= ptr2){
throw new OverflowException();
}
return stk[--ptr2] = x;
}
public int pop() throws EmptyStackException {
if (ptr <= 0) {
throw new EmptyStackException();
}
return stk[--ptr];
}
public int pop2() throws EmptyStackException {
if (ptr2 >= max) {
throw new EmptyStackException();
}
return stk[ptr2++];
}
public int peek() throws EmptyStackException{
if(ptr<=0){
throw new EmptyStackException();
}
return stk[ptr-1];
}
public int peek2() throws EmptyStackException{
if(ptr2>=max){
throw new EmptyStackException();
}
return stk[ptr2];
}
public int capacity(){
return max;
}
public int size(){
return ptr;
}
public boolean isFull(){
return ptr == ptr2;
}
public void dump(){
if(ptr<=0){
System.out.println("스택이 비어있습니다.");
}
else{
for(int i = 0; i<max ;i++){
System.out.println(stk[i]+" ");
}
System.out.println();
}
}
}
배열 하나를 가지고 두 스택을 구현할 수 있다.
스택 포인터를 하나는 앞이 바닥인 스택, 다른 하나는 맨 뒤가 바닥인 스택을 구현해보았다.
스택이 다 찬 경우는 두 포인터가 같아질 때 Full임을 알 수 있다.
class TwoStackTester{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
TwoStack s = new TwoStack(64);
while(true){
System.out.println("현재 데이터 수 : " + s.size() + "/" + s.capacity());
System.out.print("1.앞에 push 2. 뒤에 push 3. 1스택 팝 4. 2스택 팝" +
"5. 1스택 피크 6. 2스택 피크 7. 덤프 : ");
int menu = sc. nextInt();
if(menu==0){
break;
}
int x;
switch(menu){
case 1:
System.out.print("데이터 : ");
x = sc.nextInt();
try{
s.push(x);
}catch(IntStack.OverflowException e){
System.out.println("스택이 가득 찼습니다.");
}
break;
case 2:
System.out.print("데이터 : ");
x = sc.nextInt();
try{
s.push2(x);
}catch(IntStack.OverflowException e){
System.out.println("스택이 가득 찼습니다.");
}
break;
case 3:
try{
x = s.pop();
System.out.println("팝한 데이터는 " + x +"입니다.");
}catch(IntStack.EmptyStackException e){
System.out.println("스택이 비어있습니다.");
}
break;
case 4:
try{
x = s.pop2();
System.out.println("팝한 데이터는 " + x +"입니다.");
}catch(IntStack.EmptyStackException e){
System.out.println("스택이 비어있습니다.");
}
break;
case 5:
try{
x = s.peek();
System.out.println("피크한 데이터는 "+x+"입니다.");
}catch(IntStack.EmptyStackException e){
System.out.println("스택이 비어있습니다.");
}
break;
case 6:
try{
x = s.peek2();
System.out.println("피크한 데이터는 "+x+"입니다.");
}catch(IntStack.EmptyStackException e){
System.out.println("스택이 비어있습니다.");
}
break;
case 7:
s.dump();
break;
}
}
}
}
코드가 조금 지저분하지만 그래도 잘 검증했다!
8퀸 문제
서로 공격하여 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓으세요.
퀸은 어떤 방향으로든 이동이 가능하다.
- 체스판의 가로를 행 / 세로를 열 이라 하면 배열 인덱스를 부여할 수 있다.
- 퀸을 배치하는 조합
- 체스판은 총 64칸이다.
- 첫 퀸을 배치하면 다음은 나머지 63칸에서 임의로 선택할 수 있다.
- 64 x 63 x 62 x 61 .... = 178,462,987,637,760 가지의 조합이 만들어진다.
- 규칙1
- 각 열에 퀸을 1개만 배치한다.
- 퀸은 자신과 같은 열에 있는 다른 퀸을 공격할 수 있기 때문이다.
- 첫 퀸을 배치하면 다음은 다른 열에 있는 8칸 중에서 임의로 선택할 수 있다.
- 8 x 8 x 8 x ... = 16,777,216 가지의 조합이 만들어진다.
- 그러나 이 조합은 같은 행에 있는 다른 퀸을 공격할 수 있기 때문에 만족하지 않는다.
- 규칙2
- 각 행에 퀸을 1개만 배치한다.
- 구현
- 0열에 퀸을 배치할 수 있는 방법은 8가지이다.
- 0열에 배치하고 나서 1열에 퀸을 배치하는 방법은 또 8가지이다.
- 0~1 열에 배치하는 방법은 64가지이다.
- 원래 문제를 8개의 부분 문제로 나눌 수 있다
- 이 방법을 0~7 열까지 반복하면 16,777,216 가지
- '같은 행에 2개 이상의 퀸을 배치하지 않는다' 의 조합을 만드는 계산을 생략 가능
퀸을 1개 배치하고 나서 문제를 8개의 부분 문제로 나누는 작업을 반복한다.
배열 작성
i열에 놓인 퀸의 위치가 j행이면 pos[i] = j
ex) pos[1] = 4 는 1열에 놓인 퀸은 4행에 위치한다. / 인덱스가 열, 요소가 행
- set 메서드
- pos[i]에 0행부터 7행까지의 값을 순서대로 대입하는 재귀 메서드
- 구현 부분에 0열에 1개의 퀸을 배치하는 8가지 조합을 for문에 의해 나열한다.
- set(i + 1)에 의해 앞에서 했던 작업을 다음 열에서 수행하도록 한다.
- i가 7이 되면 8개의 퀸이 모두 배치된다.
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();
}
static void set(int i){
for(int j = 0; j < 8; j++){
pos[i] = j;
if(i == 7){
print();
}
else{
set(i+1);
}
}
}
public static void main(String[] args){
set(0);
}
}이러한 방법을 가지뻗기 라고 한다
하노이 탑이나 8퀸 문제처럼 문제를 세분하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이하는 기법을
분할 정복법이라고 한다.
각 행에 퀸을 1개만 두는 규칙을 적용해보자.
import java.util.Scanner;
class QueenBB {
static boolean[] flag = new boolean[10];
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();
}
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);
}
}
flag[0]의 값이 true이므로 퀸이 배치되었다.
이 행에는 이미 퀸이 있기 때문에 여기에는 배치하지 않는다.
따라서 262,144개의 조합이 생략된다
이처럼 필요하지 않는 분기를 없애 불필요한 조합을 줄이는 방법을 한정 조작이라고 하고,
가지 뻗기와 한정 조작을 조합하여 문제를 풀어가는 방법을 분기 한정법이라고 한다.
퀸은 대각선 방향도 이동할 수 있기 때문에 대각선을 보더라고
퀸을 1개만 배치하는 한정 조작을 추가해야 한다.
import java.util.Scanner;
class QueenBB {
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();
}
static void set(int i) {
for (int j = 0; j < 8; j++) {
if (!flag_a[j] &&
!flag_b[i + j] &&
!flag_c[i - j + 7]) {
pos[i] = 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);
}
}
이렇게 하면 총 92개의 조합이 출력된다.
8퀸 문제가 매우 복잡하지만 이해하면 쉽게 풀어낼 수 있다.
코드를 다시 분석해보면서 이해하는 시간이 꼭 필요할 것 같다.
제네릭 기법을 정리해둔 내용이 없어서 이번에 한 번 짚고 넘어갔다.
다음 시간은 정렬 알고리즘에 대해 학습할 계획이다!