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 + 클릭 을 통해 자바 클래스 내부를 확인 할 수 있다. )

오늘은 자료구조의 기본 구조 중 하나인 스택에 대해서 알아보고자 한다.
가장 기본적인 구조로 후입선출 ( LIFO, Last In First Out ) 방식을 가진다.
접시를 쌓아올린다고 생각하면 된다.

스택 ( Stack )

• 후입 선출 ( LIFO, Last In First Out )
• 한쪽 끝에서만 데이터 삽입( push )과 삭제( pop )가 이루어짐
• 재귀 호출, 백트래킹, 수식 계산 등 다양한 알고리즘에서 활용됨

    private int[] stack;
    private int top;

    public TestStack(int size){
        stack = new int[size];
        top = -1;
    }

스택의 기본 연산

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

• 스택의 맨 위(top)에 데이터를 추가하는 연산

    public void push(int value){
        if(top == stack.length -1 ) {
            System.out.println("스택이 가득 찼습니다.");
            return;
        }

        stack[++top] = value;
    }

2. pop(): 데이터 제거

• 스택의 맨 위(top)에 있는 데이터를 제거하고 반환하는 연산
• 만약 스택이 비어 있다면 언더플로우(Underflow, 데이터 부족 에러) 발생

    public int pop() {
        if (isEmpty()){
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top--];
    }

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

• 스택의 맨 위(top)에 있는 데이터를 반환하지만, 제거하지 않음

    public int peek() {
        if (isEmpty()) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top];
    }

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

• 스택이 비어 있으면 true, 아니면 false 반환

    public boolean isEmpty() {
        return top == -1;
    }

로직 예시)

왼쪽 위부터 오른쪽으로 진행된다

1. 빈 스택이다

2. push를 통해 값 ( 1 ) 을 넣었다. 이 때 top은 1을 가리킨다

3. push를 통해 값 ( 2 ) 을 넣었다. 이 때 top은 2를 가리킨다.

4. peek를 통해 값 ( 2 ) 을 받았다.

5. pop을 통해 값 ( 2 ) 를 꺼냈다. 이 때 top은 1을 가리킨다.

6. pop을 통해 값 ( 1 ) 를 꺼냈다. 이 때 top은 아무것도 가리키지 않는다. ( -1 상태 )

배열을 활용하여 스택에 대해 설명했지만, 
List 클래스 ( 하위 클래스 포함 ArrayList 등 ) 으로도 구현 가능하다.
 개념을 이해하고 상황에 맞게 사용하면 된다.

전체 구현 코드

package org.example;


public class TestStack {
    private int[] stack;
    private int top;

    public TestStack(int size){
        stack = new int[size];
        top = -1;
    }

    public void push(int value){
        if(top == stack.length -1 ) {
            System.out.println("스택이 가득 찼습니다.");
            return;
        }

        stack[++top] = value;
    }

    public int pop() {
        if (isEmpty()){
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("스택이 비어 있습니다.");
            return -1;
        }
        return stack[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }
}

요즘 다시 알고리즘 공부를 시작하려고 하여
백준에서 문제를 풀어나가며 알고리즘을 따로 정리, 기술하는 방향으로 계획하고 있다.
그 중 정렬 알고리즘을 먼저 살펴보려고 하며,
오늘은 기본 중 하나인 선택 정렬를 알아보고자 한다.

선택 정렬 ( Selection Sort )

선택 정렬은 간단하지만 비효율적인 정렬 알고리즘 중 하나로, 배열에서 가장 큰 or 가장 작은 값을 찾아 현재 위치에 배치하는 과정을 반복하여 정렬된다.

순서는 다음과 같다.

1. 정렬되지 않은 부분에서 최솟값 or 최댓값 찾기

2. 현재 위치와 최솟 값 or 최대 값 교환

3. 다음 위치로 이동하며 반복

다음 그림과 같이 예시로 알아보자

5개의 정수 값을 가진 배열 Array가 존재한다.

이를 오름차순으로 왼쪽부터 최솟값을 찾아 정렬하고자 한다.

기본 형태

1회차

첫번 째 위치인 4를 기준

차례로 5, 3, 1, 2 와 비교

최솟값을 찾아 위치를 교환

1회차 완료

2회차

두번 째 위치인 5를 기준

차례로 3, 4, 2 와 비교

최솟값을 찾아 위치를 교환

2회차 완료

2회차만에 정렬되어 정렬된 배열은 다음과 같다.

전체 코드

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int [] arr = {6,4,2,1,3,5};
        selectionSort(arr);
        Arrays.stream(arr).forEach(System.out::println);
    }

    private static void selectionSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }

        int minIndex;
        for(int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for(int j = i + 1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            if(minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }
}

구현은 쉽고 직관적이긴 하나,  선택 정렬은 앞서 말했듯 입력 배열에 관계없이(2회차에 정렬이 되었더라도)
외부 반복문에서 n -1 회, 내부 루프에서 n - 1, n - 2, ..., 1번 비교함으로
시간복잡도는 항상 O(n^2) 으로 비효율적이다. 

에라토스테네스의 체 는 소수를 찾는 쉽고 빠르게 찾을 수 있는 방법이다.

( 고대 그리수 수학자 에라토스테네스가 발견 )

알고리즘

다음과 같은 알고리즘을 따른다.

0 ~ 50 까지의 수를 찾고자 할때, 0과 1을 제외

1.  2부터 시작하여 2를 제외한 2의 배수를 모두 지운다.

2. 지워지지 않은 다음 숫자부터 1번과 같이 반복한다. ( 3을 제외한 3의 배수 지우기 )

3.  √50 = 7.071 이므로 구하는 수의 제곱근 이하의 소수, 즉, 7의 배수까지 제외하면 된다.

4. 제외 되지 않은 숫자가 소수

 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Code

자바를 통해 다음과 같이 구현할 수 있다.

Boolean[] primeNumbers = new Boolean[number + 1]; // N이 0일 때, 0 ~ 100 까지 101개의 수
        primeNumbers[0] = false; // 1
        primeNumbers[1] = false; // 2

먼저 0 ~ 100까지의 101개의 배열을 생성해주고 0, 1은 제외 시킨다.

 // 모두 true로 초기화
 for (int i = 2; i <= number; i++) {
 	primeNumbers[i] = true;
 }

2부터 모두 소수라 가정하고 true로 지정한다. 

for (int i = 2; i <= Math.sqrt(number); i++) {
	if (primeNumbers[i] == false)
    	continue;
    for (int j = i + i; j <= number; j += i) {
    	primeNumbers[j] = false;
    }
}

에라토스테네스의 체 공식으로

1. 이미 제외시킨 숫자라면 다음 숫자

2. 제외시킨 숫자가 아니라면 그 수를 제외하고 배수를 false로 변환한다.

다음과 같은 결과를 얻을 수 있다.

전체 코드

import java.util.Scanner;

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

        System.out.print("2이상의 숫자를 입력해 주세요 : ");
        int N = scanner.nextInt();

        fintPrimeNumber(N);
    }

        private static void fintPrimeNumber(int number) {
        Boolean[] primeNumbers = new Boolean[number + 1]; // N이 0일 때, 0 ~ 100 까지 101개의 수
        primeNumbers[0] = false; // 1
        primeNumbers[1] = false; // 2

        // 모두 true로 초기화
        for (int i = 2; i <= number; i++) {
            primeNumbers[i] = true;
        }

        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (primeNumbers[i] == false)
                continue;
            for (int j = i + i; j <= number; j += i) {
                primeNumbers[j] = false;
            }
        }

        System.out.println();
        System.out.println(number + "이하의 소수 입니다.");
        
        for (int i = 0; i < primeNumbers.length; i++) {
            if (primeNumbers[i]) {
                System.out.print(i + " ");
            }
        }
    }
}