애드혹 알고리즘 대표문제 풀이: 요세푸스 문제는 왜 시뮬레이션보다 규칙 찾기가 중요할까

요세푸스 문제는 처음 보면 시뮬레이션이 가장 먼저 떠오릅니다. 원형으로 사람을 세다가 매번 k번째를 지우면 되기 때문입니다. 그런데 이 문제를 대표적인 애드혹 알고리즘 문제로 많이 다루는 이유는, 구현 자체보다 언제 시뮬레이션에서 규칙 찾기로 시선을 옮겨야 하는지를 아주 잘 보여주기 때문입니다.

즉, 요세푸스 문제의 핵심은 원을 잘 도는 기술보다 제거 뒤 남은 구조를 다시 같은 문제로 볼 수 있느냐에 있습니다. 이번 글에서는 작은 예시, 점화식, k=2 패턴까지 순서대로 정리하겠습니다.

문제 조건

• 1번부터 n번까지 사람이 원형으로 서 있다
• 매번 k번째 사람을 제거한다
• 제거된 다음 사람부터 다시 센다
• 마지막에 남는 사람의 번호를 구한다

예를 들어 n = 7, k = 3이면 제거 순서는 3, 6, 2, 7, 5, 1이 되고 마지막 생존자는 4입니다. 이 설명만 보면 대부분은 자연스럽게 “그냥 리스트로 지우면 되겠다”고 생각하게 됩니다.

시뮬레이션이 먼저 보이는 이유

요세푸스 문제는 문제의 행동 규칙이 그대로 보입니다. 사람을 세고, k번째를 지우고, 다음 사람부터 다시 세면 됩니다. 그래서 처음에는 수식보다 시뮬레이션이 더 자연스럽습니다.

이 출발은 틀린 것이 아닙니다. 오히려 애드혹 문제에서는 작은 입력을 직접 돌려봐야 규칙이 보이는 경우가 많습니다. 시뮬레이션은 정답 접근의 반대편이 아니라 규칙 관찰의 첫 단계라고 보는 편이 정확합니다.

손풀이 예시

같은 예시 n = 7, k = 3을 손으로 끝까지 따라가 보겠습니다. 처음 원형은 [1, 2, 3, 4, 5, 6, 7]처럼 생각하면 됩니다.

1. 3 제거 -> 남은 사람 [1, 2, 4, 5, 6, 7]
2. 6 제거 -> 남은 사람 [1, 2, 4, 5, 7]
3. 2 제거 -> 남은 사람 [1, 4, 5, 7]
4. 7 제거 -> 남은 사람 [1, 4, 5]
5. 5 제거 -> 남은 사람 [1, 4]
6. 1 제거 -> 생존자 4

여기까지는 단순 시뮬레이션입니다. 그런데 이제 중요한 질문이 하나 생깁니다. 첫 번째 제거가 끝난 뒤 남은 문제를 원래 문제와 비슷한 모양으로 다시 볼 수 있을까?

번호 다시 붙이기

첫 번째로 3이 제거되면 남은 사람은 [1, 2, 4, 5, 6, 7]입니다. 이 상태를 그대로만 보면 복잡해 보이지만, 4를 새 0번이라고 보고 다시 번호를 붙이면 갑자기 구조가 단순해집니다.

• 4를 새 0번
• 5를 새 1번
• 6을 새 2번
• 7을 새 3번
• 1을 새 4번
• 2를 새 5번

즉, 한 번 제거한 뒤 남은 원형은 단순히 사람 수가 하나 줄어든 같은 요세푸스 문제로 다시 볼 수 있습니다. 바뀐 것은 원래 번호와 새 번호가 어긋난다는 점뿐입니다.

점화식의 뜻

0-index 기준 점화식은 아래처럼 쓸 수 있습니다. J(1, k) = 0, J(n, k) = (J(n-1, k) + k) % n. 처음 보면 외워야 할 식처럼 보이지만, 뜻은 간단합니다.

한 명을 제거하면 문제는 n-1명 문제로 줄어듭니다. 그 작은 문제의 생존자 위치를 안다면, 시작점이 앞으로 이동한 만큼 다시 원래 번호 체계로 돌려놓기만 하면 됩니다. 바로 그 이동량이 식의 + k에 들어 있습니다.

즉, 점화식은 신비한 공식이 아니라 제거 후 인덱스를 다시 붙이는 과정을 짧게 압축한 표현입니다.

n=7, k=3 계산

1. J(1, 3) = 0
2. J(2, 3) = (0 + 3) % 2 = 1
3. J(3, 3) = (1 + 3) % 3 = 1
4. J(4, 3) = (1 + 3) % 4 = 0
5. J(5, 3) = (0 + 3) % 5 = 3
6. J(6, 3) = (3 + 3) % 6 = 0
7. J(7, 3) = (0 + 3) % 7 = 3

0-index 결과가 3이라는 뜻은 1-index로 바꾸면 생존자가 4라는 뜻입니다. 손으로 시뮬레이션한 결과와 정확히 같습니다. 중요한 것은 정답 숫자보다, 이전 크기 문제의 답이 다음 크기 문제의 답으로 자연스럽게 이어진다는 구조입니다.

시뮬레이션의 한계

작은 입력에서는 리스트에서 사람을 지우는 시뮬레이션이 아주 편합니다. 하지만 입력이 커지면 중간 원소를 계속 제거하는 비용이 커집니다. 단순 배열이나 리스트 기반 구현은 전체적으로 O(n^2)까지 가기 쉽다는 점이 문제입니다.

이 지점에서 질문이 바뀝니다. 어떻게 잘 지울까보다, 지운 뒤 남은 구조를 어떻게 다시 표현할까가 더 중요해집니다. 요세푸스 문제는 바로 그 전환을 배우기 좋은 대표문제입니다.

반복문 구현

점화식을 이해했다면 구현은 짧아집니다. 아래 Java 코드는 0-index 기준 생존자 위치를 누적한 뒤 마지막에 1을 더해 1-index 답을 반환합니다.

public class Josephus {

    public static int josephus(int n, int k) {
        int result = 0; // J(1, k) = 0

        for (int size = 2; size <= n; size++) {
            result = (result + k) % size;
        }

        return result + 1; // 1-index로 변환
    }

    public static void main(String[] args) {
        System.out.println(josephus(7, 3)); // 4
    }
}

public class Josephus {

    public static int josephus(int n, int k) {
        int result = 0; // J(1, k) = 0

        for (int size = 2; size <= n; size++) {
            result = (result + k) % size;
        }

        return result + 1; // 1-index로 변환
    }

    public static void main(String[] args) {
        System.out.println(josephus(7, 3)); // 4
    }
}

이 코드의 장점은 짧다는 것보다 의미가 분명하다는 데 있습니다. 현재 크기의 답이 직전 크기의 답에서 어떻게 이동하는지가 그대로 드러납니다.

k=2 패턴

요세푸스 문제에서 유명한 보너스 인사이트는 k = 2일 때입니다. 이 경우 답을 써보면 1, 1, 3, 1, 3, 5, 7, 1처럼 홀수로 올라가다가 n이 2의 거듭제곱이 되는 순간 다시 1로 돌아가는 패턴이 보입니다.

그래서 n = 2^m + L이라고 쓰면 답은 J(n, 2) = 2L + 1로 정리됩니다. 예를 들어 n = 10이면 가장 큰 2의 거듭제곱은 8이고 L = 2이므로 답은 5입니다.

다만 이 식은 k = 2 특수 규칙입니다. 모든 k에 대해 이렇게 간단한 닫힌형 공식이 있다고 생각하면 안 됩니다.

문제 접근 순서

1. 먼저 작은 입력으로 시뮬레이션해본다
2. 첫 제거 뒤 남은 구조가 같은 문제인지 본다
3. 시작점이 어디로 옮겨졌는지 본다
4. 번호를 다시 붙였을 때 답이 어떻게 변하는지 본다
5. 그 변환을 점화식이나 반복문으로 옮긴다

이 흐름은 요세푸스 문제 하나에만 쓰는 요령이 아닙니다. 애드혹 알고리즘 문제에서 규칙을 찾아야 할 때 거의 그대로 다시 등장합니다.

규칙 찾기로 넘어가는 시점

• 제거 과정을 그대로 구현하면 비용이 커진다
• 한 번 줄어든 문제가 원래 문제와 닮아 있다
• 이전 크기 문제의 답을 다음 문제로 옮길 수 있다
• 전체 과정보다 인덱스 이동 규칙이 더 본질적으로 보인다

요세푸스 문제는 이 신호가 아주 선명하게 드러납니다. 그래서 시뮬레이션과 규칙 관찰의 경계를 배우는 대표 애드혹 문제로 자주 등장합니다.

정리

요세푸스 문제는 처음에는 시뮬레이션 문제처럼 보이고, 실제 출발도 그게 맞습니다. 하지만 거기서 멈추지 않고 제거 뒤 남은 원을 다시 같은 문제로 보고, 인덱스 이동을 읽고, 그것을 점화식으로 압축하는 순간 이 문제의 핵심이 보입니다.

즉, 요세푸스 문제에서 더 중요한 것은 사람을 잘 지우는 기술보다 남은 구조를 다시 해석하는 눈입니다. 함께 읽으면 좋은 글로는 애드혹 알고리즘 접근법: 그리디와 완전탐색 판단 기준, 애드혹 알고리즘 반례 찾는 법, 시뮬레이션 문제 풀이법: 상태 정의와 구현 순서가 자연스럽게 이어집니다.

참고한 자료로는 cp-algorithms의 Josephus problem 정리와 Wikipedia의 Josephus problem 문서를 확인했습니다.