[BOJ알고리즘, C++]#11866_요세푸스 문제0, 선형 자료구조, 큐

 

[BOJ알고리즘, C++]#11866_요세푸스 문제 0

 

BOJ 알고리즘 문제 풀이, 11866번 요세푸스 문제 0

queue 컨테이너를 활용하는 방법에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#0. 문제

1. 문제

 

#1. 풀이

1. 큐

[자료 구조]#0_선형 자료구조

 

• 큐는 선입선출(FIFO) 방식으로 동작하는 선형 자료구조입니다. 데이터 목록의 한쪽 끝에서는 데이터의 삽입만 이루어지며, 다른 한쪽은 데이터의 삭제 작업만 이루어집니다.
• 데이터 목록의 한쪽에서만(top) 접근이 가능한 스택과 달리, 큐는 데이터 목록의 양쪽 끝(front, back)에서 접근이 가능합니다.
• 삽입/제거의 위치와 방법이 제한된 유한 순차 리스트라는 점에서 스택과 동일하지만, 큐는 스택과 달리 push 한 데이터와 pop 한 데이터가 다릅니다!
• 큐는 그래프 자료구조의 BFS(너비 우선 탐색)에 활용되며, 작업들을 순차적으로 처리하거나, 멀티 스레드 환경에서 동기화를 위한 버퍼로 활용됩니다.

 

2. queue 컨테이너

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> q;

    // 큐에 데이터 삽입
    q.push(1);
    q.push(2);
    q.push(3);

    // 큐의 맨 앞 데이터 제거
    q.pop();

    // 큐의 맨 앞 데이터 출력
    cout << "Front element of the queue: " << q.front() << endl;

    // 큐의 맨 뒤 데이터 출력
    cout << "Back element of the queue: " << q.back() << endl;

    // 큐의 크기 출력
    cout << "Size of the queue: " << q.size() << endl;

    return 0;
}

 

Details

 

1. C++의 STL이 제공하는 queue 컨테이너의 삽입 방법은 push입니다.
2. C++의 STL이 제공하는 queue 컨테이너의 제거 방법은 pop입니다.
3. C++의 STL이 제공하는 queue 컨테이너의 접근 방법은 front(), 그리고 back()입니다.

 

3. While 문 + For 문

#include <iostream>
using namespace std;

int main()
{
	while (true)
	{
		for (int i = 0; i < N; i++)
		{
			//...
		}
	}
}

 

Details

 

• While 문 내 For문을 사용하는 경우를 많이 발견했습니다. 특히, stack 혹은 queue에서 많이 사용하는 듯합니다.

 

#2. 코드

1. 코드

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int N,K;
    queue<int> q;
    cin >> N >> K;
    
    for(int i=1; i<=N; i++)
    {
        q.push(i);
    }
    
    int cnt = 1;
    cout << "<";
    while(!q.empty())
    {
        for(int i=1; i<K; i++)
        {
            q.push(q.front());
            q.pop();
        }
        cout << q.front();
        if(q.size() != 1)
            cout << ", ";
        q.pop();
    }
    cout << ">";
}