[백준 1168] 요세푸스 문제 2 - 펜윅트리 응용

 

요세푸스 문제 2

https://www.acmicpc.net/problem/1168

문제는 간단하다.. 

알고리즘 구현이 어려울 뿐..!  

 

 

플래티넘 3

1168번: 요세푸스 문제 2

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000)

 

출력

예제와 같이 요세푸스 순열을 출력한다.

 

 

 

그렇다..! 이 문제는 플래티넘 3의 수준으로 "세그먼트 트리의 응용" 문제이다. 

 

이 문제를 철저히 뜯어보자. 

 

 

 

제한

시간	0.15초
1 ≤ K ≤ N ≤ 100,000

 

알고리즘 선정

이 문제는 시간 복잡도가 관건인 문제이다. 

1초도 아닌 0.15초다.

 

n과 k도100,000이기에 더더욱 시간 복잡도에 최적화된 알고리즘을 선택해야 한다. 

 

시간 복잡도에 최적화된 알고리즘
DP, 백트래킹, 이진탐색, 투포인트, 세그먼트트리, 펜윅트리

 

필자는 "펜윅트리"를 이용하여 문제를 해결했다. 

 

 

펜윅트리란? 

 

위 사진처럼, 최하위 노드를 빼가며 갱신하고 업데이트 하는 간단한 트리이다.

세그먼트 트리와 고민을 했는데 구현이 더 쉽고, 공간 복잡도도 O(N) 으로 낮출 수 있어 선정했다. 

 

구현

1. update함수, sum 함수는 흔한 펜윅트리 코드이다. 

유의사항 2가지 

1. update함수는 모든 index에 1을 저장하면 된다. 

--> 저장된 값은 node가 존재하는지 아닌지 파악하는 용도! 

 

2. 최하위 인덱스를 구하는 방법만 유의하면 된다!

최하위 인덱스 = (idx & -idx) 

 

✨ -idx는 idx의 2의 보수를 의미 
즉, idx의 모든 비트를 반전시킨 후 1을 더한 것

따라서 idx와 -idx를 AND 연산하면,
가장 낮은 자리의 1을 제외한 나머지 비트는 반드시 0이 되고,
가장 낮은 자리의 1은 그대로 1이 됩니다.

예를 들어, idx가 12(이진수로 1100)라고 하면 -idx는 -12이고 이는 2의 보수로 0100입니다.
따라서 idx & -idx는 1100 & 0100이 되어 결과는 0100, 즉 4가 됩니다.

이처럼 idx & -idx는 idx의 이진 표현에서 가장 낮은 자리의 1을 찾는 데 사용됩니다. 이는 트리 구조에서 가장 낮은 레벨의 노드를 찾는 데 유용하게 사용됩니다.

 

 

2. 💡getNumber(int index)함수💡 

강조를 10번 해도 모자랄 만큼 이 문제를 푸는 핵심코드이다! 

 

이 함수로 k번째 함수를 선정할 수 있다.

 

기능

- k번째 인덱스를 return

- 즉, 문제에서 제시된 제거된 사람을 의미! 

 

 

a. 최대 최소 범위 선정

-  left = 1, right = n으로 저장한다. 

 

b. while문으로 반복

- 단, left <= right로 조건 설정

 

c. mid 선정 후 탐색 방향 설정

-  mid 가 구하려고 하는 k보다 크다 --> 왼쪽으로

-  mid 가 구하려고 하는 k보다 작다 --> 오른쪽으로

 

코드는 다음과 같다. 

int getNumber(int k)

{

    int left = 1, right = N;

    while (left <= right)

    {

        int mid = (left + right) / 2;

        int count = sum(mid);

        if (count >= k)

            right = mid - 1;

        else

            left = mid + 1;

    }

    return left;

}

 

 

3. main 함수

a. update함수 

- 모든 인덱스 1로 설정 

 

for (int i = 1; i <= N; i++)

        update(i, 1);

 

b. for(1 --> N -1) 까지 반복

-   뽑아낼 index 선정

-   update(index,-1)

    --> 없어졌으니까 0으로 초기화

-   k 재설정

 

🧡 k = k - 1 + K;
💙 k = (k - 1) % (N - i) + 1;

 

 

1. k는 처음에 K번재니까 K로 시작한다.     - K <= N이니까 처음에는 제약이 없다.  2. 두 번째 부턴 k를 재설정해야 한다. - 우선, k는 현재 인덱스다! 현재 인덱스에서 K번째 다음이니 k += K인데, 배열은 0부터가 아니라 🧡1부터 시작되니 1을 빼야 한다. 3. k가 남아있는 사람 수를 넘어가는 것 처리한다.  -  k번째 다음이 사람수를 넘어갈 수 있다. 💙그렇다면 사람수로 % 나머지 연산을 하자.

 

 

🧡1부터 시작되니 1을 빼야 한다. 부연설명! 

 

 N= 7 , k=3, K=3이라고 가정합시다. 

처음에 3, 6이 뽑히잖아요! 그 과정을 코드로 작성해 보면 아래와 같다.

 

🧡 k = k - 1 + K;

 

 

위 사진을 해석하면 되는데,

처음에는 모든 사람이 있기에 Sum(K)를 하면 처음 나가는 사람을 선정할 수 있다. 

그 후 나간 사람은 0으로 설정한다. 

 

그렇다면 두 번째 부터 index는 지금 현재 + K -1를 해줘야 한다

왜냐고? 한 명이 없으니까 sum(k)의 값이 줄어들겠죠 

헷갈린다고? 그렇다면 Sum으로 생각합시다!! 

즉 k = sum의 값!!

 

 

 

두 번째 줄 `index = (index - 1) % (N - i) + 1;`는 새로운 위치를 찾는 것입니다. `(N - i)`는 현재 남아 있는 사람의 수를 나타내며, `(index - 1) % (N - i)`는 그 사람들 중에서 새로운 위치를 찾는 것입니다. 만약에 index 값이 남아 있는 사람의 수보다 크다면, 원형으로 돌아가서 계산을 해야 하므로 `%` 연산을 사용합니다. 그리고 마지막에 `+1`을 하는 이유는 배열이 1부터 시작하기 때문입니다. 따라서 이 코드는 현재 위치에서 K번째 사람을 찾고, 그 사람을 제거한 후에 새로운 시작 위치를 찾는 것을 반복하면서 조세푸스 문제를 해결합니다.

 

 

💙그렇다면 사람수로 % 나머지 연산을 하자.  부연설명

 

N= 7 , k=3, K=3이라고 가정합시다. 

3, 6 다음 2가 뽑힌다! 그 과정을 코드로 작성해 보면 아래와 같습니다.

🧡 k = k - 1 + K;
💙 k = (k - 1) % (N - i) + 1;

 

 

 

보다시피 2명이 빠져서 sum이 7인 값은 없다 

-->k -1을 하고 

k-1을 하는 이유
0부터 시작하는 index로 변환하기 위함!!

 

이해가 되지 않아 디버그를 했다. 

디버그 과정이 궁금하면 ⬇

3, 5 = (5 - 1) (7 - 1) + 1 : 5
6, 7 = (7 - 1) (7 - 2) + 1 : 2
2, 4 = (4 - 1) (7 - 3) + 1 : 4
7, 6 = (6 - 1) (7 - 4) + 1 : 3
5, 5 = (5 - 1) (7 - 5) + 1 : 1
1, 3 = (3 - 1) (7 - 6) + 1 : 1
4

 

----------------------------------------------------------------------------------

sum이 7이고 남은 사람은 5명이다!

일단, 남은 사람으로 나눠보자 

7 % 5 + 1 = 3이다! 

 

but 정답은 2! 

그렇다면 어떻게 해야 할까? 

우리는 0부터가 아니라 1부터 tree를 채워나갔으니 현재 위치를 0부터 시작하는 인덱스로 변환해야 한다!! 

--> 남은 사람으로 나눠주고 +1

 +1을 하는 이유
% 연산을 하면 0~ n-1이다. 
tree를 1~n까지 저장했으니 +1을 해준다. --> 1부터 시작하는 index로 변환! 

 

 

최종 main 코드

 

int main()

{

    scanf("%d %d", &N, &K);

    for (int i = 1; i <= N; i++)

        update(i, 1);

    int k = K;

    printf("<");

    for (int i = 1; i <= N - 1; i++)

    {

        int number = getNumber(k);

        printf("%d, ", number);

        update(number, -1);

        k = k - 1 + K;

        k = (k - 1) % (N - i) + 1;

    }

    printf("%d>\n", getNumber(1));

    return 0;

}

 

 

 

필자는 k를 구하는 과정이 생각보다 어려웠다....! 
k를 구하는 과정이 어려웠던 사람에게 도움이 되길

 

전체코드

공유 소스 보기