금방 끝낼 수 있을 거라고 생각했는데, 생각보다 소요되는 시간이 꽤 된다..
자꾸 문제를 풀다가 어떤 덫에 걸리면 그걸 내 힘으로 풀어보겠다고 미련하게 시간을 날린다.
어느 정도의 시간을 보내면 덫에서 빠져나와 정신을 차리는 지혜도 좀 발휘하자 미련한 놈아
큐, 덱 정리다.
-
* 큐: 한쪽 끝에서만 넣고, 다른 한쪽 끝에서만 뺄 수 있는 자료 구조다. FIFO. 먼저 온 놈이 먼저 나간다. 주로 BFS에서 많이 사용된다. 스택처럼 일차원 배열 하나로 구현이 가능하고, STL이 있지만 일단 한번 구현해본다.
10845번: 큐
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 ��
www.acmicpc.net
|
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
|
#include <iostream>
#include <string>
using namespace std;
int queue[10000], front = 0, rear = 0;
int empty()
{
if (rear-front != 0)
return 0;
return 1;
}
void push(int x)
{
queue[rear] = x;
rear += 1;
}
int pop()
{
if (empty())
return -1;
front += 1;
return queue[front-1];
}
int start()
{
if (empty())
return -1;
return queue[front];
}
int end()
{
if (empty())
return -1;
return queue[rear-1];
}
int main()
{
int n;
string cmp;
cin >> n;
while (n--)
{
cin >> cmp;
if (cmp == "push") {
int p;
cin >> p;
push(p);
}
else if (cmp == "pop") {
cout << pop() << '\n';
}
else if (cmp == "size") {
cout << rear-front << '\n';
}
else if (cmp == "empty") {
cout << empty() << '\n';
}
else if (cmp == "front") {
cout << start() << '\n';
}
else if (cmp == "back") {
cout << end() << '\n';
}
}
return 0;
}
|
cs |
STL을 사용해서도 구현 해봤다.
|
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
|
#include <iostream>
#include <queue>
#include <string>
using namespace std;
queue<int> q;
int main()
{
int n;
string cmp;
cin >> n;
while (n--)
{
cin >> cmp;
if (cmp == "push") {
int p;
cin >> p;
q.push(p);
}
else if (cmp == "pop") {
if (q.empty())
cout << -1 << '\n';
else {
cout << q.front() << '\n';
q.pop();
}
}
else if (cmp == "size") {
if (q.empty())
cout << 0 << '\n';
else
cout << q.size() << '\n';
}
else if (cmp == "empty") {
cout << q.empty() << '\n';
}
else if (cmp == "front") {
if (q.empty())
cout << -1 << '\n';
else
cout << q.front() << '\n';
}
else if (cmp == "back") {
if (q.empty())
cout << -1 << '\n';
else
cout << q.back() << '\n';
}
}
return 0;
}
|
cs |
뭔가 이 문제에서는 STL이 더 번거로운 것 같다
* 조세퍼스 순열: 원에서 사람들이 일정한 순서로 제거되는 순열이다. 큐를 사용해서 풀어봤다.
1158번: 요세푸스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net
|
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
|
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main()
{
queue<int> q;
int n, k, p;
cin >> n >> k;
for (int i = 1; i <= n; i++)
q.push(i);
cout << '<';
while (!q.empty())
{
int cnt = k;
while (cnt--)
{
p = q.front();
q.pop();
if (cnt)
q.push(p);
}
if(!q.empty())
cout << p << ", ";
}
cout << p << '>';
return 0;
}
|
cs |
큐를 사용하면 생각보다 어렵지 않게 풀린다.
* 덱: double - ended queue를 줄여서 dequeue. 말 그대로 양 끝에서 자료를 넣고, 빼고 다 할 수 있는 자료구조. 스택과 큐의 성질을 포함하고 있다. 이건 따로 STL이 없으니 한번 구현해보자.
|
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
|
#include <iostream>
#include <string>
using namespace std;
int deque[10000], front = 0, rear = 0;
int empty()
{
if (rear - front != 0)
return 0;
return 1;
}
void push_front(int x)
{
int tmp = rear;
while (tmp > front)
{
deque[tmp] = deque[tmp - 1];
tmp -= 1;
}
deque[front] = x;
rear += 1;
}
void push_back(int x)
{
deque[rear] = x;
rear += 1;
}
int pop_front()
{
if (!empty()) {
int p = deque[front];
front += 1;
return p;
}
return -1;
}
int pop_back()
{
if (!empty()) {
int p = deque[rear-1];
rear -= 1;
return p;
}
return -1;
}
int start()
{
if (empty())
return -1;
return deque[front];
}
int end()
{
if (empty())
return -1;
return deque[rear - 1];
}
int main()
{
int n;
string cmp;
cin >> n;
while (n--)
{
cin >> cmp;
if (cmp == "push_front") {
int p;
cin >> p;
push_front(p);
}
else if (cmp == "push_back") {
int p;
cin >> p;
push_back(p);
}
else if (cmp == "pop_front") {
cout << pop_front() << '\n';
}
else if (cmp == "pop_back") {
cout << pop_back() << '\n';
}
else if (cmp == "size") {
cout << rear - front << '\n';
}
else if (cmp == "empty") {
cout << empty() << '\n';
}
else if (cmp == "front") {
cout << start() << '\n';
}
else if (cmp == "back") {
cout << end() << '\n';
}
}
return 0;
}
|
cs |
스택이나 큐만큼 많이 쓰이지는 않는 것 같다.
-
연습 문제까지 같이 포스팅 하려고 했는데 너무 길어질 것 같아서 따로 해야겠다.
남은 오늘도 화이팅 해보자!
'알고리즘 > 백준 알고리즘 강의' 카테고리의 다른 글
| 백준 알고리즘 기초 - 수학1 (연습) (0) | 2020.07.07 |
|---|---|
| 백준 알고리즘 기초 - 수학1 (0) | 2020.07.07 |
| 백준 알고리즘 기초 - 자료구조1 (연습) (0) | 2020.07.06 |
| 백준 알고리즘 기초 - 자료구조1 (스택) (0) | 2020.07.04 |
| 백준 알고리즘 기초 - 알고리즘 시작 (0) | 2020.07.04 |
