P-coding

요세푸스 순열은
유대인 역사가 플라비우스 요세푸스의 이야기에서 유래한 수학적 문제이다.

요세푸스의 이야기

1세기 로마 제국 시대, 유대인은 로마에 대항하여 대규모 반란을 일으켰다.
이 때, 요세푸스는 유대 반군의 장군 중 한명으로 로마군에 의해 포위당했다.
전투에서 패배한 요세푸스와 동료들은 로마군에 항복하는 대신 자결하는 것을 택했다.
하지만 자결하는 것은 두려웠는지 원형으로 앉았고, 특정 규칙에 따라 순차적으로 서로 죽여주는 방식을 택했다.

1. 특정 수의 인원을 건너 뛰고 다음 사람을 제거한다.
2. 마지막 한 사람이 남을 때까지 반복.

그러나 요세푸스는 동료들의 뜻에 반대하여 살고 싶었고, 위 규칙을 이용하여 마지막 한 사람이 되어 로마군에 항복하였다.

공식

일반적인 공식은 다음과 같다. 

n : 인원 수

k : 건너뛸 수

재귀함수 형식을 띄고 있다.

예시)

f( 7, 3 ) 인 경우

코드

재귀 코드로 구현하면 다음과 같이 구현할 수 있다.

package org.example;

public class Main {
    public static int josephus(int N, int K) {
        if (N == 1) return 0;
        return (josephus(N - 1, K) + K) % N; // 재귀 호출
    }

    public static void main(String[] args) {
        int N = 7;
        int K = 3;
        System.out.println("Last survivor: " + (josephus(N, K) + 1));
    }
}

결과 ( 마지막 생존 자리 )

4

이번에는 재귀함수로 해결하였지만, 원형 큐 등 다양한 방법들이 있다.
생존을 위해서 역사가의 새로운 순열 공식
순차적인 제거 문제에서 다양하게 사용되고 있다.

오늘은 자료구조의 기본 구조 중 하나인 큐에 대해서 알아보고자 한다.
가장 기본적인 구조로 선입선출 ( FIFO, First In First Out ) 방식을 가진다.
먼저 온 사람이 나가는 흔히 매장에 줄 서는 과정이라 볼 수 있다.
( Queue 단어 자체가 표 같은 것을 구매하기 위해 줄 서는 것을 의미 )

큐 ( Queue )

• 선입 선출 ( FIFO, First In First Out )
• 데이터가 들어오는 위치는 가장 뒤 Rear or Back 에서 이루어지고, 데이터가 나가는 위치인 가장 앞 Front, 양쪽에서 삽입 삭제가 이루어진다.
• BFS ( 너비 우선 탐색 ), 프로세서 핸들링 ( CPU 헤드링 ) 등에 사용.

class Queue{
    private LinkedList<Integer> queue;

    public Queue(){
        queue = new LinkedList<>();
    }
    ....
}

큐의 기본 연산

1. Enqueue(value): 데이터 삽입

• 큐의 맨 뒤(back)에 데이터를 추가하는 연산

    public void enQueue(int x){
        queue.addLast(x);
    }

2. Dequeue(): 데이터 제거

• 큐의 맨 앞(front)에 있는 데이터를 제거하고 반환하는 연산

    public int depQueue(){
        if(queue.isEmpty()){
            return -1;
        }
        return queue.removeFirst();
    }

3. peek() : 최상단 데이터 확인

• 큐의 맨 앞(front)에 있는 데이터를 반환하지만, 제거하지 않음

    public int peek(){
        if(queue.isEmpty()){
            return -1;
        }
        return queue.getFirst();
    }

4. isEmpty(): 큐이 비어 있는지 확인

• 큐가 비어 있으면 true, 아니면 false 반환

    public boolean isEmpty(){
        return queue.isEmpty() ? true : false;
    }

로직 예시)

1. 빈 큐다

2. Enqueue ( 2 ) 를 통해 가장 앞 부터 채워 넣는다.

3. Enqueue ( 4 ) 를 통해 2 다음에(뒤에서부터) 채워 넣는다.

4. Dequeue 릍 통해 가장 앞에 있는 2를 꺼내고 4를 앞으로 옮긴다.

추가 - JAVA의 큐 관련 클래스

자바에서 큐는 Interface로 구현되어 ArrayDeque, LinkedList, PriorityQueue로 직접 구현할 수 있다.

그 밖에도 Blocking 즉 고정된 크기의 배열을 사용하는 큐도 존재한다.

이는 자바에서 원형 큐의 고정된 크기를 구현하기 위함으로 보인다.

이 글에서는 LinkedList로 정의된 큐와 달리 양쪽에서 삽입과 삭제가 이루어질 수 있는 양방향 큐이며, 메모리 동적인 요소를 가지고 있다.

ArrayDeque도 비슷하나 LinkedList와는 다르다. 배열로 사용되며 동적으로 변하긴 하지만, 배열을 다시 늘려야하는 번거로움이 있다. 추후 ArrayList와 LinkedList의 차이에 대해 포스팅할 예정이다.

DeQueue

 양방향에서 삽입/삭제가 이루어 질 수 있는 양방향 큐를 의미한다.

원형 큐

blocking으로 정의된 큐는 원형 큐라고 할 수 있으며 다음과 같은 형태을 가진다.

데이터가 삽입/삭제 됨에 따라 front와 back(rear)를 가리키는 위치가 계속 변하지만, 크기는 고정된 상태로 이루어진다.

다음과 같이 예시를 볼 수 있다.

PriorityQueue

우선순위 큐로 우선순위 비교는 Comparable interface를 활용하여 구현하거나 Comparator를 사용하여 설정할 수 있다.

중복 요소를 허용하고, 정렬된 순서로 요소를 처리하기 때문에 성능에 영향이 줄 수 있는 큐다.

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(3);
queue.add(1);
queue.add(2);

System.out.println(queue.poll());  // 1 (가장 작은 값이 먼저 출력됨)

PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
queue.add(1);
queue.add(3);
queue.add(2);

System.out.println(queue.poll());  // 3 (가장 큰 값이 먼저 출력됨)

이미 많고 다양한 큐가 만들어져 있기 때문에
편한 방법과 편한 클래스가 자바처럼 다양하게 존재하지만,
기본 자료구조를 이해하지 못한다면 활용하기가 어렵다.
때문에 그걸 사용하기 이전에 기본에 대한 이해를 점검하고 사용하도록 하자.
( ctrl + 클릭 을 통해 자바 클래스 내부를 확인 할 수 있다. )