2학기 3주차_알고리즘( 백준11866번 : 요세푸스 문제 0 )

두번째 문제이다.

 

문제

 

 

➡️문제

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

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 ≤ 1,000)

➡️출력

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

 

 코드 (1차 시도)

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
    int N;
    int K;
    int i;
    int result;

    scanf("%d %d", &N,&K);
    for (i = 0; i < N; i++)
        result++;
        if (i == K)
        result--;
            if (N == 0)
        
                break;


    return 0;
}

 

조금 많이 부족한 코드라는 걸 알지만 틀을 만들고자 시도했다.

 

 

 

역시나 첫시도는 가뿐하게 틀렸다.

어차피 내가 어디까지 생각할 수 있을지 그게 답이랑 얼마나 일치하는지, 어디가 부족한지 보려고 시도한거긴하다.

 

저기에 배열을 추가하면 어찌저찌 풀수있을 것 같은데, 방법을 한번 찾아봐야겠다.

 

코드 ( 두번째 시도 - 큐를 사용하지 않고 배열로 풀기 )

 

#include <stdio.h>

int main() {
    int N, K;
    scanf("%d %d", &N, &K);

    int people[1001];
    for (int i = 1; i <= N; i++) {
        people[i] = i;
    }

    int index = 1;
    printf("<");
    for (int count = 0; count < N; count++) {
        int step = 0;
        while (step < K) {
            if (people[index] != 0) {
                step++;
            }
            if (step < K) {
                index = (index % N) + 1;
            }
        }

        printf("%d", people[index]);
        people[index] = 0;  // 해당 위치의 사람을 제거

        if (count < N - 1) {
            printf(", ");
        }
    }
    printf(">\n");

    return 0;
}

 

풀이 설명

 

 1) 일단 내가 했던 방법대로 처음에는 변수 정의 및 초기화 작업을 한다.

 2) 그리고 scanf를 통해 띄어쓰기를 통해 N, K을 한줄에 입력한다.

 3) 그리고 정수형으로 배열을 정의하고, 반복문을 통해서 배열에 인덱스값을 저장한다.

 4) index 변수는 현재 위치를 나타내는데 사용된다.
 5) 반복문을 통해 원형 테이블에서 K번째로 앉아 있는 사람을 찾고, 그 사람을 출력하며 배열에서 제거한다.
 6) 이 과정을 모든 사람이 제거될 때까지 반복합니다.

 7) people[index] = 0은 해당 위치의 사람을 제거하는데 사용된다.

 

이 코드는 Josephus problem을 해결하는 전형적인 방식 중 하나이다.

Josephus problem은 역사적으로 관련이 있었던 문제로, 원형 테이블에서 일정한 간격으로 사람들을 제거하는 과정을 모델링한다.

   

코드 ( 세번째 시도 - 큐를 사용해서 풀기 )

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define SIZE 1001

typedef struct {
	int queue[SIZE];
	int front, rear;
}QueueType;

void init_queue(QueueType* q)
{
	q->front = q->rear = 0;
}

int is_full(QueueType* q)
{
	return ((q->rear + 1) % SIZE == q->front);
}

int is_empty(QueueType* q)
{
	return (q->front == q->rear);
}

void push(QueueType* q, int e)
{
	if (is_full(q))
		return;

	q->rear = (q->rear + 1) % SIZE;
	q->queue[q->rear] = e;
}

int pop(QueueType* q)
{
	if (is_empty(q))
		return -1;

	q->front = (q->front + 1) % SIZE;
	return q->queue[q->front];
}

int size(QueueType* q)
{
	if (q->front < q->rear)
		return q->rear - q->front;
	else
		return SIZE - q->front + q->rear;
}

int main()
{
	QueueType Q; init_queue(&Q);

	int i, j, N, K, tmp;

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

	for (i = 0; i < N; i++)
	{
		push(&Q, i + 1);
	}

	printf("<");
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < K - 1; j++)
		{
			tmp = pop(&Q);
			push(&Q, tmp);
		}
		if (size(&Q) == 1)
			break;
		tmp = pop(&Q);
		printf("%d, ", tmp);
	}
	printf("%d>", pop(&Q));

	return 0;
}

 

풀이 설명

 

1) 구조체 정의

큐 자료구조를 나타내는 구조체를 정의한다.

queue 배열은 실제 큐의 요소를 저장하고, front와 rear는 각각 큐의 시작과 끝을 가리키는 인덱스이다.

 

2) 큐 초기화 함수

큐를 초기화하는 함수입니다. 큐의 front와 rear를 0으로 설정한다.

 

3) 큐가 꽉 찼는지 확인하는 함수

큐가 꽉 찼는지 확인하는 함수이다. rear 다음이 front인 경우 큐는 꽉 찬 상태이다.

 

4) 큐가 비어 있는지 확인하는 함수

큐가 비어 있는지 확인하는 함수이다. front와 rear가 같은 경우 큐는 비어 있는 상태이다.

 

5) 큐에 요소를 추가하는 함수

큐에 요소를 추가하는 함수이다. 큐가 꽉 차있지 않은 경우에만 요소를 추가한다.

 

6) 큐에서 요소를 제거하는 함수

큐에서 요소를 제거하고 해당 요소를 반환하는 함수이다. 큐가 비어 있으면 -1을 반환한다.

 

7) 큐의 크기를 반환하는 함수

큐의 크기를 반환하는 함수이다. 큐의 크기는 front와 rear의 상대적 위치에 따라 계산된다.

 

8) 메인 함수 부분

큐를 초기화하고, 1부터 N까지의 숫자를 큐에 삽입한다.
Josephus problem 알고리즘을 사용하여 K번째로 앉아 있는 사람을 찾고 출력한다.
큐의 크기가 1이 될 때까지 반복하며 사람들을 출력하고, 마지막 사람을 출력한 후에는 큐를 비운다.

 

 

해당 풀이는 큐 ( queue ) 자료구조를 이용해서 푼 것이다.

배열에 비해서 확실히 처음보는 개념이라 익숙하지 않았다. 구조체 자체도 학습한 후 자주 사용하지 않아서 

많이 낯설었는데, 자료구조를 학습하고 나면 조금은 더 수월해질지 모르겠다.

일단은 추가학습을 하기위해 링크를 걸어두었으니, 큐라는 개념이 익숙해질때까지 여러번 봐보도록 해야겠다.

 

 

 

참고 학습 자료

[자료구조 - C언어] 자료구조 제18강: 큐(queue)의 개념과 구현(1) (tistory.com)

[자료구조 - C언어] 자료구조 제18강: 큐(queue)의 개념과 구현(1)

[C] 백준 | 11866번 코드 - 요세푸스 문제 0 (tistory.com)

[C] 백준 | 11866번 코드 - 요세푸스 문제 0