P-coding

다음 문제를 통해 재귀 함수와 이항계수를 활용해 보자.

---

 

문제 핵심

• N : 자연수
• K : 정수

풀이 과정

이항 계수는 다음과 같은 공식에 따라 이루어 진다. 이걸 코드로 구현해 보자.

재귀 방식

재귀를 통해 factorial를 해결한다.

public static int factorial(int n){
    if(n == 1){
        return 1;
    }
    return factorial(n-1) * n;
}

반복문 방식

반복문을 통해 factorial를 해결한다.

public static int factorial(int n){
    int result = 1;
    for (int i = n; i > 1; i--){
        result *= i;
    }
    return result;
}

int result = factorial(N) / (factorial(K) * factorial(N - K));

재귀 방식은 위와 같이 StackOverflow현상이 일어났다.
자바의 JVM의 기준 스택 크기의 한계 때문에 재귀 함수 호출 과정에서
StackOverflow현상이 일어난 것으로 보인다.

때문에 반복문을 통해 이를 해결하였다.

이번 글에서 백준 11866번 문제를 통해 요세푸스 순열을 활용,
이를 통해 원형 큐와 결합하여 사용해보자.

문제 핵심

• N : 사람 수
• K : 건너뛸 수
• ( 1 <= K <= N <= 1,000 )

풀이 과정

다음 문제는 요세푸스를 순열을 통해 한 사람씩 제거해 나가는 문제이다.

다음 글을 통해 개념을 참고하면 좋을 것 같다. 비교적 간단하다.

1. 반복

해당 문제는 K의 배수마다 값을 꺼내오면 된다.

때문에 이전 값들은 모두 다시 큐의 뒤에 넣어주고 그 과정을 마지막 한 사람이 남을 때까지 반복해준다. 

        while(1 < queue.size()) {
            count++;
            if(count % K == 0){
                stringBuilder.append(queue.remove() + ", ");
                continue;
            }
            queue.add(queue.remove());
        }

2. 출력

백준의 문제 출력 조건에 따라 마지막 값은 기호와 함께 처리해 준다.

        stringBuilder.append(queue.remove() + ">");
        System.out.println(stringBuilder);

이번 문제는 큐의 개념과 요세푸스 순열을 이해하고 있다면, 
결합하여 아주 쉽게 풀 수 있는 문제이다.
요세푸스 문제는 재귀로도 풀 수 있는 만큼 한 번 시도해보는 것도 좋다.

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Queue<Integer> queue = new LinkedList<Integer>();
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("<");
        int N = Integer.parseInt(stringTokenizer.nextToken());
        int K = Integer.parseInt(stringTokenizer.nextToken());


        for(int i = 0; i < N; i++) {
            queue.add(i + 1);
        }
        int count = 0;

        while(1 < queue.size()) {
            count++;
            if(count % K == 0){
                stringBuilder.append(queue.remove() + ", ");
                continue;
            }
            queue.add(queue.remove());
        }

        stringBuilder.append(queue.remove() + ">");
        System.out.println(stringBuilder);

    }
}

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

요세푸스의 이야기

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

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