사용 책 : 코딩 테스트 합격자 되기 C++편
강의 유튜브 주소 : https://www.youtube.com/watch?v=-TGCT74wFeg
코딩 테스트 합격자 되기 C++ - 06/07장 스택과 큐
1. 강의 개요
오늘 강의에서는 스택과 큐의 기본 개념을 배웠다. 스택과 큐는 코딩 테스트에서 자주 등장하는 자료구조이다.
2. 스택 (Stack)
스택의 개념
스택은 후입선출(LIFO, Last In First Out) 방식의 자료구조다. 즉, 가장 나중에 들어간 데이터가 가장 먼저 나온다.
(하노이탑이 생각났다)
스택의 주요 연산
- push: 스택에 데이터를 넣는 연산이다.
- pop: 스택에서 데이터를 꺼내는 연산이다.
- top: 스택의 가장 위에 있는 데이터를 반환하는 연산이다.
스택의 사용 예시
- 함수 호출 스택: 함수 호출 시 현재 함수의 실행 정보를 스택에 저장하고, 함수가 종료되면 스택에서 꺼내어 복원한다.
- 웹페이지 탐색 히스토리: 우리가 웹페이지에서 뒤로가기 할 때, 가장 최근에 방문한 페이지를 먼저 되돌아간다.
- 괄호 짝 맞추기: 여는 괄호와 닫는 괄호의 짝을 맞출 때 사용한다.
(아마도 괄호뿐 아니라 짝이 있는 무언가나 절댓값이 같고 부호가 다른 무언가의 짝을 맞출 때도 응용이 될 것 같다.)
3. 큐 (Queue)
큐의 개념
큐는 선입선출(FIFO, First In First Out) 방식의 자료구조다. 즉, 가장 먼저 들어간 데이터가 가장 먼저 나온다.
일반적인 줄 서기를 생각하면 된다.
큐의 주요 연산
- enqueue: 큐에 데이터를 넣는 연산이다.
- dequeue: 큐에서 데이터를 꺼내는 연산이다.
- front: 큐의 가장 앞에 있는 데이터를 반환하는 연산이다.
큐의 사용 예시
- 줄 서기 시뮬레이션: 먼저 줄을 선 사람이 먼저 처리된다.
- 요세푸스 문제: 원형으로 앉아 있는 사람들 중 특정 규칙에 따라 사람을 제거하는 문제다.
4. 추상 데이터 타입 (ADT)
추상 데이터 타입(ADT)은 자료구조의 세부 구현을 숨기고, 필요한 기능만을 명시한 것이다. ADT의 장점은 복잡한 내부 구현을 감추고, 사용자에게 필요한 기능만을 제공하여 효율성을 높인다. 일상적으로 쓰이는 리모콘, 세탁기, 자판기 등등 우리가 쓰는 제품, 시스템들이 여기에 속한다고 해도 될 것 같다.
5. 요세푸스 문제 해결: 배열 vs 큐
이제는 오늘 배운 개념을 사용해서 요세푸스 문제를 해결할 것이다.
문제 설명
요세푸스 문제는 다음과 같은 규칙을 따른다:
- ( n )명의 사람들이 원형으로 앉아 있다.
- 시작 위치부터 ( k )번째 사람을 제거한다.
- 제거된 사람 다음부터 다시 ( k )번째 사람을 제거하고, 한 명이 남을 때까지 반복한다.
문제 분석
아마 이 문제가 까다로운 이유는 K번째 사람을 제거할 때마다 전체 배열이 변동되면서
동시에 기준점도 바뀐다는 점일 것이다. 반대로 이 까다로운 이유를 해결하면 문제는 쉽게 풀릴 것이다.
배열을 이용한 요세푸스 문제 해결
구현 방법
- 배열 초기화: 1부터 ( n )까지의 사람 번호를 배열에 저장한다.
- 사람 제거 과정: 현재 위치를 추적하며 ( k )번째 사람을 제거하고, 제거된 후에는 남은 사람들을 앞으로 당긴다.
시간 복잡도
- 각 사람을 제거할 때마다 배열을 앞으로 당기는 작업 때문에 최악의 경우 시간 복잡도는 ( O(n^2))이다.
코드 예시
#include <iostream>
#include <vector>
void josephus(int n, int k) {
std::vector<int> people(n);
for (int i = 0; i < n; ++i) {
people[i] = i + 1;
}
int index = 0;
while (people.size() > 1) {
index = (index + k - 1) % people.size();
people.erase(people.begin() + index);
}
std::cout << "The last remaining person is " << people[0] << std::endl;
}큐를 이용한 요세푸스 문제 해결
구현 방법
- 큐 초기화: 1부터 ( n )까지의 사람 번호를 큐에 저장한다.
- 사람 제거 과정: ( k-1 )번째 사람까지는 큐에서 꺼내어 다시 큐의 뒤로 보낸다. ( k )번째 사람은 큐에서 제거한다.
시간 복잡도
- 각 사람을 제거할 때 ( k-1 )번의 큐 연산이 필요하므로, 시간 복잡도는 ( O(n \times k) )이다.
코드 예시
#include <iostream>
#include <queue>
void josephus(int n, int k) {
std::queue<int> people;
for (int i = 1; i <= n; ++i) {
people.push(i);
}
while (people.size() > 1) {
for (int i = 0; i < k - 1; ++i) {
people.push(people.front());
people.pop();
}
people.pop();
}
std::cout << "The last remaining person is " << people.front() << std::endl;
}큐를 이용한 요세푸스 문제 해결과정 실제로 해보기
초기 상태:
큐: [1, 2, 3, 4, 5, 6, 7]
1회차:
첫 번째 ( k-1 )개의 요소를 뒤로 이동:
1-> 뒤로 이동
큐: [2, 3, 4, 5, 6, 7, 1]2-> 뒤로 이동
큐: [3, 4, 5, 6, 7, 1, 2]
세 번째 요소3을 제거:
큐: [4, 5, 6, 7, 1, 2]
2회차:
첫 번째 ( k-1 )개의 요소를 뒤로 이동:
4-> 뒤로 이동
큐: [5, 6, 7, 1, 2, 4]5-> 뒤로 이동
큐: [6, 7, 1, 2, 4, 5]
세 번째 요소6을 제거:
큐: [7, 1, 2, 4, 5]
3회차:
첫 번째 ( k-1 )개의 요소를 뒤로 이동:
7-> 뒤로 이동
큐: [1, 2, 4, 5, 7]1-> 뒤로 이동
큐: [2, 4, 5, 7, 1]
세 번째 요소2를 제거:
큐: [4, 5, 7, 1]
4회차:
첫 번째 ( k-1 )개의 요소를 뒤로 이동:
4-> 뒤로 이동
큐: [5, 7, 1, 4]5-> 뒤로 이동
큐: [7, 1, 4, 5]
세 번째 요소7을 제거:
큐: [1, 4, 5]
5회차:
첫 번째 ( k-1 )개의 요소를 뒤로 이동:
1-> 뒤로 이동
큐: [4, 5, 1]4-> 뒤로 이동
큐: [5, 1, 4]
세 번째 요소5를 제거:
큐: [1, 4]
6회차:
첫 번째 ( k-1 )개의 요소를 뒤로 이동:
1-> 뒤로 이동
큐: [4, 1]4-> 뒤로 이동
큐: [1, 4]
세 번째 요소4를 제거:
큐: [1]
결국, 최후의 생존자는 1이다.
배열 vs 큐: 요세푸스 문제 해결 비교
| 항목 | 배열 | 큐 |
|---|---|---|
| 구현 복잡도 | 상대적으로 복잡함 | 상대적으로 단순함 |
| 시간 복잡도 | $O(n^2)$ | $O(n × k)$ |
| 공간 복잡도 | $O(n)$ | $O(n)$ |
| 효율성 | 대규모 입력에 비효율적 | 대규모 입력에 효율적 |
| 알고리즘 이해도 | 배열의 원형 처리와 인덱스 조정 필요 | 큐의 기본 연산만으로 구현 가능 |
| 유연성 | 고정된 크기의 배열 필요 | 동적 크기 조정이 가능한 큐 활용 가능 |
