바킹독의 실전 알고리즘 : 큐
정의와 성질
큐는 FIFO 바로 나와주면 된다.
큐의 성질
- 원소의 추가가 O(1)
- 원소의 제거가 O(1)
- 제일 앞/뒤 원소 확인이 O(1)
- 앞뒤 외의 원소들은 원칙적으로 확인/변경 불가능
추가 -rear 제거 -front 로 보통 나타낸다.
기능과 구현
스택 어렵지 않았으니까 걍 내가 구현해보자.
const int MX = 100005;
int dat[MX];
int tail=0; // 추가
int head=0; // 제거
void push(int x){
dat[tail++]=x;
}
void pop(){
head++;
}
int front(){
return dat[head];
}
int back(){
return dat[tail-1];
}
제미나이한테 던졌더니 길이 제한 생각 안 하냐고 혼났다. 그치 대기큐 같은 병목 현상도 있지. 바킹독에서는 이를 다루고 있진 않다. 혹시 필요하다면 % 연산 기호로 원형 큐를 만들 수 있을 거 같다.
#include <bits/stdc++.h>
using namespace std;
int main(void){
queue<int> q;
q.push(10);
q.push(20);
cout<<q.size()<<'\n';
q.empty();
q.pop();
q.front();
q.back();
}
나왔던 오류
연산자 관련
풀다가 연산자 우선순위 관련한 오류가 하나 나왔다.
#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int main(void){
int n;
cin>>n;
while(n--){
string inst;
cin>>inst;
if(inst=="push"){
int nor;
cin>>nor;
q.push(nor);
}
else if(inst=="front") cout<< (q.size()==0) ? -1 : q.front()<<'\n';
else if(inst=="back") cout<< (q.size()==0) ? -1 : q.back() << '\n';
else if(inst=="size") cout<<q.size()<<'\n';
else if(inst=="empty") cout<<q.empty()<<'\n';
else if(inst=="pop") {
cout<< (q.size()==0) ? -1 : q.front()<<'\n';
if(q.size()!=0) q.pop();
}
}
}
/*
❌ Test Case #1: Failed
--------------- Expected ---------------
1
2
2
0
1
2
-1
0
1
-1
0
3
---------------- Actual ----------------
002
0
0010
1
10
0
--------------- 채점 종료 ----------------
*/
자꾸 이런 오류가 뜨길래 제미나이한테 넘겼더니 연산 우선순위 때문이라고 한다.
// 작성하신 코드
cout << (q.size()==0) ? -1 : q.front() << '\n';
// 컴퓨터의 해석 (괄호 위치 주목!)
( cout << (q.size()==0) ) ? -1 : ( q.front() << '\n' );
위와 같이 삼항 연산자보다 출력 연산자가 우선순위가 높다고 한다.
2^31-1
위 키워드 보면 int 최댓값임을 바로 파악해야 한다.
바킹독의 실전 알고리즘 : 스택
정의와 성질
스택은 LIFO이다. 큐, 덱, 스택 같은 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한된 자료구조를 Restricted Structure라고 부른다.
스택의 성질
- 원소의 추가 O(1)
- 원소의 제거 O(1)
- 제일 상단의 원소 확인 O(1)
- 나머지 원소들의 확인/변경 원칙적으로 불가능
기능과 구현
const int MX=1000005;
int dat[MX];
int pos=0;
일단 여기서 원소를 담은 큰 배열과 인덱스를 저장할 변수 한 개만 있으면 구현이 가능하다. pos는 원소의 개수이자 추가할 때 삽입해야 하는 인덱스를 의미한다.
#include <bits/stdc++.h>
using namespace std;
const int MX=1000005;
int dat[MX];
int pos=0;
void push(int x){
dat[pos]=x;
pos++; //dat[pos++]=x;로 한 줄로 표현도 가능, 전치 후치 차이에 대해 알고 있기
}
void pop(){
pos--; //여기까지만 써도 됨
/* 어차피 아래 코드들은 나중에 push할 때 덮어쓸 공간
cout<<dat[pos];
dat[pos]=0; */
}
void top(){
return dat[pos-1];
}
void test(){
}
int main(void){
test();
}
음 연결 리스트 하다가 얘 하니까 구현은 쉽다. 그래도 바킹독 강의에서는 STL을 권장한다. STL stack을 썼으면 최소 스택 쪽에는 문제 없다는 걸 알 수 있으니 로직 개선에 신경 쓸 수 있다.
#include <bits/stdc++.h>
using namespace std;
int main(void){
stack<int> s;
s.push(10);
s.push(20);
cout<<s.size()<<'\n'; // 2
s.empty(); // bool
s.pop(); //10만 남을 것
}
바킹독의 실전 알고리즘 : 연결 리스트
정의와 성질
연결 리스트의 성질
- k번째 원소를 확인/변경하기 위해 O(k)
- 이미 정한 위치에 추가 및 제거는 O(1)
- 메모상에 연속된 데이터는 아니라서 cache hit rate는 낮고, 할당은 쉬움
연결리스트 종류
- 단일 연결 리스트
- 이중 연결 리스트 : 양방향으로 연결되어 있어서 이전 이후 원소 주소를 둘 다 들고 있다.
- 원형 연결 리스트 : 사이클 돈다 생각하면 편하다.
기능과 구현
struct NODE {
struct NODE *prev, *next;
int data;
};
손코딩 문제 1
원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법?
효율적으로 구하라 -> 시간복잡도와 공간복잡도를 생각해봐야 한다. 동일한 노드가 나올 때까지 계속 다음 노드로 가면 된다. O(1), O(N)
손코딩 문제 2
각 연결 포인터가 가리키는 주소가 같아지는 순간이 교차점인데 A,B의 길이가 다르니까 더 긴 길이를 차만큼 빼줘서 동시에 도달할 수 있도록 한다. O(A+B)로 전체 노드 길이를 알기위한 순회는 필요하다.
손코딩 문제 3
주어진 연결 리스트 안에 사이클이 있는지 판단하라. O(N)으로 주소 다 기록해놓고 이전에 나왔던 주소가 있는지 체킹하면 될 거 같은데.. 공간 복잡도 O(1) 방법이 있다고 한다. Floyd’s cycle-finding algorithm으로 한 칸씩 이동하는 slow pointer와 두 칸씩 이동하는 fast pointer를 두면 사이클 내에서 꼭 같은 노드에서 만나게 된다.
야매 연결 리스트 예시
// http://boj.kr/5c97cb6a88324537a722e8de9169e2ab
#include <bits/stdc++.h>
using namespace std;
const int MX = 1000005;
char dat[MX];
int pre[MX];
int nxt[MX];
int unused = 1;
void insert(int addr, char num){
dat[unused] = num;
pre[unused] = addr;
nxt[unused] = nxt[addr];
if(nxt[addr] != -1) pre[nxt[addr]] = unused;
nxt[addr] = unused;
unused++;
}
void erase(int addr){
nxt[pre[addr]] = nxt[addr];
if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}
void traversal(){
int cur = nxt[0];
while(cur != -1){
cout << dat[cur];
cur = nxt[cur];
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
fill(pre,pre+MX,-1);
fill(nxt,nxt+MX,-1);
string init;
cin >> init;
int cursor = 0;
for(auto c : init){
insert(cursor, c);
cursor++;
}
int q;
cin >> q;
while (q--) {
char op;
cin >> op;
if (op == 'P') {
char add;
cin >> add;
insert(cursor, add);
cursor = nxt[cursor];
}
else if (op == 'L') {
if (pre[cursor] != -1) cursor = pre[cursor];
}
else if (op == 'D') {
if (nxt[cursor] != -1) cursor = nxt[cursor];
}
else { // 'B'
if (pre[cursor] != -1) {
erase(cursor);
cursor = pre[cursor];
}
}
}
traversal();
}
알고달레: 큐
큐
큐 하면 일단 귀신 같이 나와야 하는 것이 선입선출이다. 데이터가 입력되는 순대로 바로 처리하고 싶을 때 효율적인 자료구조이다. 이 큐의 시간복잡도는 O(1)이기 때문이다.
파이썬 : from collections import deque를 사용한다.
from collections import deque
queue = deque()
queue.append(1) # [1]
queue.append(2) # [1, 2]
queue.append(3) # [1, 2, 3]
queue.popleft() # [2, 3]
queue.popleft() # [3]
queue.popleft() # []
java : Queue<String> queue = new LinkedList<>();를 사용한다.
Queue<String> queue = new LinkedList<>();
queue.offer(1); // [1]
queue.offer(2); // [1, 2]
queue.offer(3); // [1, 2, 3]
queue.poll(); // [2, 3]
queue.poll(); // [3]
queue.poll(); // []
```cpp #include <bits/stdc++.h> using namespace std;
int main(void){
queue
}