대표 사진들을 너무 짱구만 했나? 근데 블로그보면 너무 귀여워서 끊을 수가 없어,,,'ㅅ' ㅎㅎㅎㅎㅎㅎㅎㅎ
거두절미하고 이번 강의는 큐 & 덱에 대해 배워보자!
아 그리고 잡담이지만 난 블로그에 배운걸 정리할 때 노래를 들으면서 하는 편인데 요즘엔 백현의 love again에 꽂혀서 그것만 듣는 중이다ㅎㅎ 원래 백현이 노래 다 좋아하는데 내가 love again듣고 물구나무 서서 발로 박수를 치면서 들어서....ㅋㅋㅋ 이건 들을때마다 좋아ㅠㅠ 특히 sm에서 올려준 백현이 love again live 버전이 있는데 이게 진짜 맛집이라구ㅠㅠ굉굉ㅠㅠ 과제할때 love again하나면 난 두려울게 없다구!! (소프젝1 2차 과제도 이거 들으면서 겨우 울면서 냈따..☆
암튼 백현이 고마워ㅠㅠ 그니까 다들 러버겐 들으러가
https://www.youtube.com/watch?v=gB6NSO4MQ6U
--------------------------------------------------------------------------------------------------------------------------
<큐>
큐(Queue)란 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 자료를 뺄 수 있는 자료구조로, 먼저 넣은 것이 먼저 나오기 때문에 First In First Out(FIFO)라고도 불린다. 큐의 연산은 스택과 거의 유사하지만 다른 점은 push와 pop의 위치가 정해져 있다(?)는 것이다. 따라서 보통 순서가 정해져 있는 연산, 순서를 이용한 연산에서 사용되는 DS이다. 이는 BFS 그래프에서 정말정말 옴청 짱!! 많이 쓰이는 자료구조라고 한다. (강의에서 엄청 강조하길래 나도 강조해봄ㅋ)
이번 강의에서는 큐를 배워서 구현해보지만 C++에서는 STL의 queue, Java에서는 java.util.Queue를 사용하면 된다. 단, Python에서는 collection.deque나 직접 구현하여 큐를 사용해야 하고 list는 큐와 다르기 때문에 이를 큐로 사용하면 안된다.
큐는 일차원 배열 하나로 구현할 수 있다 -> [begin, end)
(자료가 begin부터 end-1까지 채워져 있기 때문에 위와 같이 표현이 가능하다)
push 연산에서는 배열의 end index에 추가하고, pop 연산에서는 begin의 자료를 빼주고 begin의 위치를 뒤로 옮겨주면 된다. empty 연산은 begin과 end가 같으면 빈 큐로 판단한다. size는 end에서 begin 뺴주면 됨~~
이제 예제 문제~
<10845번 / 큐>
이는 큐를 구현하는 문제이다. 함 구현해보지 뭐
아 이 문제ㅠㅠ 알고리즘은 쉬워서 금방 구현해서 제출했는데 자꾸 틀렸다고 하는거야ㅠㅠ 한참 고민하다 찾아낸건 front랑 back함수 예외처리를 안한거임... 그래서 Queue 구조체에 front랑 back함수에 배열이 empty일 경우 추가했더니 겨우 맞았어... 역시 예외처리는 중요하다는걸 새삼 다시 느끼고 가는즁...흑..
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <iostream> #include <string> using namespace std; struct Queue { int arr[10000]; int begin, end; Queue() { begin = 0; end = 0; } void push(int num) { arr[end] = num; end++; } bool empty() { if (begin == end) return true; else return false; } int pop() { if (!empty()) { begin++; return arr[begin - 1]; } else return -1; } int size() { return end - begin; } int front() { if (empty()) return -1; return arr[begin]; } int back() { if (empty()) return -1; return arr[end - 1]; }
}; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);
int n; cin >> n;
Queue q; while (n--) { string cmd; cin >> cmd; if (cmd == "push") { int num; cin >> num; q.push(num); } else if (cmd == "pop") { cout << q.pop() << '\n'; } else if (cmd == "size") { cout << q.size() << '\n'; } else if (cmd == "empty") { cout << q.empty() << '\n'; } else if (cmd == "front") { cout << q.front() << '\n'; } else if (cmd == "back") { cout << q.back() << '\n'; } } return 0; } |
cs |
<1158번 / 요세푸스 문제>
강의에선 조세퍼스라더니 문제에는 요세푸스로 되어있넹? 별안간 문제 설명을 하겠다 'ㅅ'
- 1번부터 N번까지 N명의 사람이 원을 ㅇ루면서 앉아 있고, 양의 정수 M(<=N)이 주어진다.
- 이제 순서대로 M번째 사람을 제거한다.
- 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.
- 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
- 원에서 사람들이 제거되는 순서를 (N, M) - 조세퍼스 순열이라고 한다.
이 문제는 큐를 사용하는게 그렇게 효율적이진 않지만 그냥 공부를 위해 약간 억지로? 사용하는 느낌이 없지않아 있다고 한다. 내 생각에도 큐보다 링크드 리스트같은 다른 알고리즘이 효율적일것같다. 큐로 하면 계속 반복해야해서 코드의 효율이 떨어진달까? 암튼 공부를 위해 구현해보도록 하겠다! 이건 M번만큼 pop/push를 반복하고 M번째는 pop만 하면 된다. 이걸 큐에 아무것도 남지 않을때까지 반복쓰~~
사망년 짬바 나타나쥬~? ㅋㅋㅋㅋㅋㅋ STL의 queue 라이브러리를 통해 아주 쉽~~고 깐딴쓰하게 구현 완료!!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> #include <queue> using namespace std; int main() { queue<int> q; int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { q.push(i); } printf("<"); for (int i = 0; i < n - 1; i++) { for (int j = 1; j < m; j++) { q.push(q.front()); q.pop(); } printf("%d, ", q.front()); q.pop(); } printf("%d>\n",q.front()); return 0; } |
cs |
<덱>
덱(Deque)은 Double-ended queue의 약자로, 양 끝에서만 자료를 넣고 양 끝에서 뺼 수 있는 자료구조이다.
따라서 덱을 구현하면 자연스레 큐와 스택도 구현한게 된다. 아래는 덱의 연산들이다.
덱도 주로 BFS 그래프에서 많이 쓰이는데 그 전까지는 덱으로만 풀 수 있는 문제는 거의 없다고 한다. 다음은 덱을 구현하는 문제다.
<10866번 / 덱>
덱도 STL의 deque이 존재하지만 이 문제는 덱을 구현하는 문제이기 때문에 배열을 통해 구현해보았다. push_front함수에서 시간이 좀 걸렸지만 empty일 때 예외처리를 해주고 end부터 뒤로 한칸씩 미뤄주고 begin에 num을 추가해준후 end를 1 증가시키면 된다!!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
#include <iostream> #include <string> using namespace std; struct Deque { int arr[10000]; int begin, end; Deque() { begin = 0; end = 0; } bool empty() { if (begin == end) return true; else return false; } int size() { return end - begin; } void push_front(int num) { if (empty()) { arr[begin] = num; end++; } else { for (int i = end; i > begin; i--) { arr[i] = arr[i - 1]; } arr[begin] = num; end++; } } void push_back(int num) { arr[end] = num; end++; } int pop_front() { if (!empty()) { begin++; return arr[begin - 1]; } else return -1; } int pop_back() { if (!empty()) { end--; return arr[end]; } else return -1; } int front() { if (!empty()) { return arr[begin]; } else return -1; } int back() { if (!empty()) { return arr[end - 1]; } else return -1; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; Deque d; while (n--) { string str; cin >> str; if (str == "push_front") { int num; cin >> num; d.push_front(num); } else if (str == "push_back") { int num; cin >> num; d.push_back(num); } else if (str == "pop_front") { cout << d.pop_front() << '\n'; } else if (str == "pop_back") { cout << d.pop_back() << '\n'; } else if (str == "size") { cout << d.size() << '\n'; } else if (str == "empty") { cout << d.empty() << '\n'; } else if (str == "front") { cout << d.front() << '\n'; } else if (str == "back") { cout << d.back() << '\n'; } } return 0; } |
cs |
큐와 덱 강의도 끝!!
'코딩테스트 > 알고리즘 기초 강의' 카테고리의 다른 글
| 2강 자료구조 1 - 참고 (0) | 2020.08.20 |
|---|---|
| 3강 수학 1 - 수학 1 (0) | 2020.08.19 |
| 2강 자료구조 1 - 연습 (0) | 2020.08.16 |
| 2강 자료구조 1 - 스택 (0) | 2020.08.09 |
| 1강 - 알고리즘 시작 (0) | 2020.08.06 |
댓글