8퀸 문제 (재귀 호출)

8개의 퀀을 8x8판에 배치시키는데 서로가 잡힐 수 없도록 배치하는 가지수를 찾아내는 것이다.

퀸은 자신과 같은 열에 있는 다른 퀸을 공격하므로 각 열에 퀸을 1개만 배치해야 한다.
pos라는 배열은 각 배열의 인덱스가 열이 되고, 각 인덱스의 값들이 행이 된다.
즉 한 줄로 8x8의 배치 형태를 표시할 수 있다.


문제에 접근하기 앞서 순차적으로 문제에 접근을 해보자.
이것은 단순히 하나의 열에 퀸이 있다면 그 열에는 퀸이 있을 수 없다는 규칙만을 적용하여 도출된 계산이다.
pop[0]에 0이 있다면 퀸은 최상단좌측에 한개가 위치한 것인데 0열은 또 다른 퀸이 들어갈 수 없으므로 그 다음 열에 퀸이 들어갈 경우의 수가 8가지가 된다.
이런식으로 계산을 하면 $8^8$ 가지의 퀸의 배치 경우의 수가 도출된다.
이것은 단순 가지 뻗기 방식의 퀸의 배치방법이다.

* 가지 뻗기 식의 퀸의 배치

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) { //i:열
        for (int j = 0; j < 8; j++) {
            pos[i] = j; //j:행, 퀸을 j행에 배치합니다.
            if (i == 7)
                print(); //배치된 퀸들을 출력한다.
            else
                set(i + 1); //다음 열에 퀸을 배치한다.
        }
    }
    public static void main(String[] args) {
        set(0); //0열에 퀸을 배치한다.
    }
}

여기서 각 열에 퀸을 1개를 배치하는 조건 뿐만이 아니라 각 행에도 퀸을 한개씩만 배치하여야 하는 조건을 추가해 보자.

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();
    }

    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; //j행에 배치했으니 flag를 true로 변경
                    set(i + 1); //그리고 다음 열에 퀸을 배치할 때 0행에는 배치가 되지 않는다.
                    flag[j] = false; //그리고 다시 j행은 false 로 변경한다
                }
            }
        }
    }
    public static void main(String[] args) {
        set(0); //0열에 퀸을 배치한다.
    }
}

퀸은 가로 세로 뿐만아니라 대각선으로도 이동할 수가 있다.
따라서 퀸이 배치가 되면 배치된 퀸에서 대각선으로도 퀸을 배치하지 않도록 해야한다.

public 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 &&
                    flag_b[i + j] == false &&
                    flag_c[i - j + 7] == false) {
                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); //0열에 퀸을 배치한다.
    }

}

대각선 방향에 퀸이 배치가 되었는지 체크하는 배열의 길이가 15개인 이유는 8x8 정사각형의 대각선 방향은 2가지 인데 각 방향마다 15개의 사선이 그려진다.
맨 처음 퀸이 위치하면 가로와 대각선방향으로는 퀸이 위치해서는 안된다. ↗대각선 방향의 사선들 중에 하나의 ↗은 ↗에 배치된 퀸의 행(j)과 열(i)의 합이 동일하다.
고로 flag_b[i + j]를 true로 만든 후 경우의 수를 제거해야한다.
이러한 방법으로 ↘대각선 방향도 규칙을 찾아내어 공식으로 만들면 된다.

하노이의 탑(Tower of Hanoi) 재귀 호출 구현하기

자료구조 책을 공부하다가 재귀함수파트가 너무 어려워서 이해한것을 잊어버릴까봐 글로 남긴다.
책대로 해야하는 것은 알겠는데 실제로 정말 될까를 이해하는 과정이 너무 힘들었다.
재귀 함수 안에 재귀함수가 2개이상 호출되는 경우 머리로 순서가 연산이 잘 안된다.ㅋㅋ

지금 생각해보니 몇시간동안 너무 어렵게 생각한 것 같다.
공부한 김에 정리하고 나중에 추가로 수정을 해야할 것이다.

이 코드에서 계속 잘못 생각하고 있었던 부분은 move 메소드 자체였는데,
move 메소드에서 x, y가 의미하는 바는 x 기둥에서 y기둥으로 옮긴다는 것이다.

어쨌든 이 코드에서의 큰 줄기는 가장 아래 원반을 제외한 나머지 원반그룹들을 두번째 기둥으로 옮긴 후 아래 원반을 세번째 기둥에 옮긴다.
그리고 원반 그룹들을 세번째에 옮기면 된다.

큰원반은 작은원반 위로 올라가질 못한다.
원반을 옮기려면 최소한 가장 작은 원반부터 건드려야 한다.

결국 move 메소드는 n개의 원반을 x 기둥에서 y기둥으로 옮긴다.
요약하면 아래와 같다.
기둥 번호는 차례대로 1,2,3 이다.

1. 위에서부터 n-1개의 원반들을 1번째 기둥에서 2번째 기둥으로 옮긴다. (1 -> 2)
2. 맨 아래의 원반 1개를 3번째 기둥으로 옮긴다 (1 -> 3)
3. 2번째 기둥에 있던 n-1개의 원반들을 3번째 기둥으로 옮긴다. (2 -> 3)

그런데 n-1개의 원반들을 기둥에서 기둥으로 옮길 때 move 메소드를 또다시 호출하게 된다. 다만 x, y인자를 어떤기둥에서 옮겨지는지 제대로 넣어주어야 한다.

그리고 원반 개수가 1이 될 때 실제로 옮겼다고 텍스트를 출력하게 된다.

public class Hanoi {
    /**
     * n개의 원반을 x 기둥에서 y 기둥으로 옮김
     * @param no 원반 개수
     * @param x 시작 기둥
     * @param y 목표 기둥
     */
    static void move(int no, int x, int y) {
        //가장 아래의 원반을 뺀 윗 그룹의 원반들을
        //처음 기둥에서 중간 기둥으로 이동한다.
        //x,y가 1과 3일때 6-x-y는 중간 기둥 값이다.
        //그리고 가장 마지막 기둥을 세번째 기둥으로 옮긴다.
        if (no > 1)
            move(no - 1, x, 6 - x - y);
        
        //실제 옮겼다고 출력하는 부분
        System.out.println("원반[" + no + "]을 " + x + "기둥에서 " + y + "기둥으로 옮김");

        //그룹 원반들(no-1)을 중간 기둥에서 목표 기둥으로 이동한다.
        if (no > 1)
            move(no - 1, 6 - x - y, y);
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        System.out.println("하노이의 탑");
        System.out.println("원반 개수:");
        int n = s.nextInt();

        //기둥 번호를 순서대로 1,2,3 칭함
        //하노이탑의 목표: n개의 원반을 1번 기둥에서 3번 기둥으로 옮김
        move(n, 1, 3);
    }
}

유클리드 호제법으로 최대공약수 구하기

* 유클리드 호제법 개념 참고

재귀 호출을 이용하여 유클리드 호제법 알고리즘을 구현하였다.
두 수를 서로 나눈 나머지와 두 수중의 하나의 수는 서로 최대 공약수인 점을 이용하여,
나머지와 하나의 수를 계속 나누어 가다보면 나머지가 0이 되는 시점에서 나누어지는 수를 리턴한다.

public class EuclidGCD {
    //유클리드 호제법 알고리즘을 이용합니다.
    //정수 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 sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();

        System.out.println("최대 공약수는 " + gcd(x, y) + "입니다.");
    }
}

Java Queue 구현하기

자료구조와 함께 배우는 알고리즘 실습 내용 (157P)
링버퍼로 큐를 구현한 예제

배열로 구현하되 링버퍼로 구현한 큐는 배열의 끝에 도달할 때 다시 처음으로 돌아가게 되는 구조이다. 따라서 디큐를 할 때 앞요소를 가리키는 포인터를 +1 만 해주면 된다.
데이터들을 전부 이동시키거나 할 필요가 없어 링으로 구현한 큐의 복잡도는 $O(1)$이 된다.

/**
 * Description: 링버퍼로 큐를 구현
 */
public class IntQueue {
    private int max; //큐의 용량
    private int front; //앞 요소
    private int rear; //마지막 요소
    private int num; //현재 데이터 수
    private int[] que; //큐 본체

    //실행 시 예외 : 큐가 비어있음
    public class EmptyIntQueueException extends RuntimeException{
        public EmptyIntQueueException() { }
    }
    //실행 시 예외 : 큐가 가득 참
    public class OverflowIntQueueException extends RuntimeException{
        public OverflowIntQueueException() { }
    }
    //생성자
    public IntQueue(int capacity){
        num = front = rear = 0;
        max = capacity;
        try{
            que = new int[max];
        }catch (OutOfMemoryError e){
            max = 0;
        }
    }
    //큐에 데이터를 인큐
    public int enque(int x) throws OverflowIntQueueException {
        if (num >= max)
            throw new OverflowIntQueueException();
        que[rear++] = x;
        num++;
        if(rear == max)
            rear = 0;
        return x; //인큐한 데이터를 리턴
    }
    //큐에 데이터를 디큐
    public int deque() throws EmptyIntQueueException {
        if(num <= 0)
            throw new EmptyIntQueueException();
        int x = que[front++];
        num--;
        if (front == max)
            front = 0;
        return x;
    }
    //큐에서 데이터를 피크(프런트 데이터를 들여다봄)
    public int peek() throws EmptyIntQueueException {
        if(num <= 0)
            throw new EmptyIntQueueException();
        return que[front];
    }
    //큐에서 x를 검색하여 인덱스를 반환, 찾지 못하면 -1
    public int indexOf(int x) {
        //i는 num의 수만큼만 반복하면 된다.
        for(int i = 0; i < num; i++) { 
            /** 
             * 실제 시작지점에서부터의 인덱스를 구하기 위함.
             * 링형태의 인덱스값을 구해야 하므로 
             * max로 나누어 떨어질때 0부터 시작할 수 있도록 한다.
             */
            int idx = (i + front) % max;
            if(que[idx] == x)
                return idx;
        }
        return -1;
    }
    //큐를 비움
    public void clear() {
        num = front = rear = 0;
    }
    //큐의 용량의 반환
    public int capacity() {
        return max;
    }
    //큐에 쌓여있는 데이터 수를 반환
    public int size() {
        return num;
    }
    //큐가 비어있나요?
    public boolean isEmpty() {
        return num <= 0;
    }
    //큐가 가득 찾나요?
    public boolean isFull() {
        return num >= max;
    }
    //큐 안의 모든 데이터를 프런트 -> 리어 순으로 출력
    public void dump() {
        if (num <= 0)
            System.out.println("큐가 비어 있습니다.");
        else{
            for (int i = 0; i < num ; i++)
                System.out.print(que[(i + front) % max] + " ");
            System.out.println();
        }
    }
}