SK Networks AI Camp
알고리즘 스터디 - 1주차
이번 주 알고리즘 스터디에서 다룬 내용은 기초 자료구조인 스택(Stack)과 큐(Queue)입니다.
이 두 가지 자료구조는 이전에 블로그에 올려놓은 탐색 알고리즘 글의 Depth-First Search와 Breadth-Fist Search 구현에 필수적인 자료구조인만큼 다소 어렵더라도 꾸준히 연습해서 자유롭게 다룰 수 있어야 합니다!
Stack
스택은 첫 번째로 들어온 값이 마지막에 나가게 되는 후입선출(Last-In First-Out, LIFO) 형태의 자료구조입니다. 일상 생활에 대입해서 생각해보자면, 박스 쌓는 것에 비유할 수 있습니다. 아래에서 위로 박스를 쌓게되면 첫 번째로 쌓은 박스를 꺼내기 위해선 그 위에 쌓아놓은 박스들을 먼저 꺼내야 하겠죠? 스택도 그와 마찬가지로 가장 앞의 값을 참고하기 위해선 그 뒤에 남아있는 값이 없어야 합니다.
이제 이론적인 설명은 그만하고, 파이썬에서 스택을 사용하는 방법에 대해 설명해보겠습니다. 파이썬에서의 스택은 리스트로 구현할 수 있습니다. 파이썬의 리스트는 append 메서드를 이용하여 맨 뒤에 값을 추가하는 것이 가능하고 pop 메서드를 이용하여 맨 뒤에 값을 제거하는 것이 가능합니다. 얘기만 들어도 스택과 같은 역할을 할 수 있음을 알 수 있죠?
그럼 코드로 스택을 구현해봅시다!
예 제
빈 스택에 1, 2, 3, 4, 5를 순서대로 삽입하고 전체 배열을 출력한다. 그 이후, 5번동안 삭제 연산과 배열 출력을 반복한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
stack = []
# 초기 배열 출력
print(f"초기 배열 : {stack}")
# 삽입(1)
stack.append(1)
# 삽입(2)
stack.append(2)
# 삽입(3)
stack.append(3)
# 삽입(4)
stack.append(4)
# 삽입(5)
stack.append(5)
# 전체 배열 출력하기
print(f"전체 배열 : {stack}")
# 순차적으로 제거
print(f"제거됨 : {stack.pop()}, 남은 배열 : {stack}")
print(f"제거됨 : {stack.pop()}, 남은 배열 : {stack}")
print(f"제거됨 : {stack.pop()}, 남은 배열 : {stack}")
print(f"제거됨 : {stack.pop()}, 남은 배열 : {stack}")
print(f"제거됨 : {stack.pop()}, 남은 배열 : {stack}")
|
위와 같이 파이썬의 리스트를 이용하여 스택을 구현할 수 있음을 알 수 있습니다!
연습 문제
아래 연습 문제들은 백준 온라인 저지에서 풀어볼 수 있습니다.
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
|
import sys
n = int(sys.stdin.readline())
arr = list()
for _ in range(n):
a = list(sys.stdin.readline().rstrip().split())
if 'push' in a:
arr.append(int(a[1]))
elif 'top' in a:
if len(arr) == 0:
print(-1)
else:
print(arr[-1])
elif 'size' in a:
print(len(arr))
elif 'empty' in a:
if len(arr) == 0:
print(1)
else:
print(0)
elif 'pop' in a:
if len(arr) == 0:
print(-1)
else:
print(arr[-1])
arr.pop()
|
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
|
import sys
n = int(sys.stdin.readline())
stack = []
i = 0
ans = []
for _ in range(n):
num = int(sys.stdin.readline())
while i < num:
i += 1
stack.append(i)
ans.append('+')
if stack[-1] == num:
stack.pop()
ans.append('-')
else:
print('NO')
exit(0)
for i in arr:
print(i)
|
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
|
import sys
input = sys.stdin.readline
ans = 0
N, P = map(int, input().strip().split())
stack = [[] for _ in range(7)]
for _ in range(N):
n, p = map(int, input().strip().split())
if not stack[n]:
ans += 1
stack[n].append(p)
else:
while stack[n] and stack[n][-1] > p:
stack[n].pop()
ans += 1
if stack[n]:
if stack[n][-1] != p:
stack[n].append(p)
ans += 1
else:
stack[n].append(p)
ans += 1
print(ans)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
import sys
n = int(sys.stdin.readline())
result = 0
for _ in range(n):
s = sys.stdin.readline().rstrip()
stack = []
for i in s:
if not stack:
stack.append(i)
continue
if stack[-1] == i:
stack.pop()
else:
stack.append(i)
if not stack:
result += 1
print(result)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
import sys
s = sys.stdin.readline().rstrip()
pipe = 0
count = 0
for i in range(len(s)):
if s[i] == "(":
if s[i + 1] == ")":
if pipe != 0:
count += pipe
else:
pipe += 1
elif s[i] == ")":
if s[i - 1] != "(":
count += 1
pipe -= 1
print(count)
|
풀이를 참고하는 것은 괜찮지만 혼자 풀어본 다음에 참고하도록 합시다!
Queue
스택은 첫 번째로 들어온 값이 첫 번째로 나가게 되는 선입선출(First-In First-Out, FIFO) 형태의 자료구조입니다. 일상 생활에 대입해서 생각해보자면, 프린터의 출력 순서를 생각하시면 좋을 것 같습니다. 프린터에서 문서를 여러 개 출력하려고 하면, 맨 처음 출력 요청을 보낸 문서가 다 출력되고 나서야 다음 문서를 출력할 수 있겠죠?
큐도 그와 마찬가지로 어떤 원소를 사용하기 위해선 그 앞에 들어온 원소가 먼저 큐에서 나가야 합니다.
파이썬에서 큐는 배열 또는 collections 모듈의 deque로 구현할 수 있습니다.
일반적으로 알고리즘 문제 풀이에서 배열을 이용한 풀이는 시간초과 가능성이 높으므로 collections.deque를 이용합니다. deque의 append 메서드는 큐에 원소를 삽입하는 역할을 하고, popleft는 큐에서 원소를 제거하는 역할을 합니다.
이제 큐를 사용하러 가봅시다!
예 제
빈 큐에 1, 2, 3, 4, 5를 순서대로 삽입하고 전체 배열을 출력한다. 그 이후, 5번동안 삭제 연산과 배열 출력을 반복한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
from collections import deque
queue = deque()
# 초기 배열 출력
print(f"초기 배열 : {queue}")
# 삽입(1)
queue.append(1)
# 삽입(2)
queue.append(2)
# 삽입(3)
queue.append(3)
# 삽입(4)
queue.append(4)
# 삽입(5)
queue.append(5)
# 전체 배열 출력하기
print(f"전체 배열 : {queue}")
# 순차적으로 제거
print(f"제거됨 : {queue.popleft()}, 남은 배열 : {queue}")
print(f"제거됨 : {queue.popleft()}, 남은 배열 : {queue}")
print(f"제거됨 : {queue.popleft()}, 남은 배열 : {queue}")
print(f"제거됨 : {queue.popleft()}, 남은 배열 : {queue}")
print(f"제거됨 : {queue.popleft()}, 남은 배열 : {queue}")
|
collections.deque를 이용하여 큐를 구현할 수 있음을 알 수 있습니다!
연습 문제
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
|
import sys
from collections import deque
n = int(sys.stdin.readline())
arr = deque()
for _ in range(n):
a = list(sys.stdin.readline().rstrip().split())
if 'push' in a:
arr.append(a[1])
elif 'pop' in a:
if len(arr) != 0:
x = arr.popleft()
print(x)
else:
print(-1)
elif 'size' in a:
print(len(arr))
elif 'empty' in a:
if len(arr) == 0:
print(1)
else:
print(0)
elif 'front' in a:
if len(arr) == 0:
print(-1)
else:
print(arr[0])
elif 'back' in a:
if len(arr) == 0:
print(-1)
else:
print(arr[-1])
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
import sys
from collections import deque
n = int(sys.stdin.readline())
q = deque()
Max = -1
ans = 0
for _ in range(n):
com = list(map(int, sys.stdin.readline().strip().split()))
if com[0] == 1:
q.append(com[1])
else:
q.popleft()
if Max < len(q):
Max = len(q)
ans = q[-1]
elif Max == len(q) and ans > q[-1]:
ans = q[-1]
print(Max, ans)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
from collections import deque
n = int(input())
queue = deque()
for i in range(1, n + 1):
queue.append(i)
while len(queue) > 1:
print(queue.popleft(), end=" ")
queue.append(queue.popleft())
print(queue.popleft())
|
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
|
import sys
from collections import deque
n = int(sys.stdin.readline())
queue = deque()
a = []
b = []
for _ in range(n):
com = list(map(int, sys.stdin.readline().strip().split()))
if com[0] == 1:
queue.append((com[1], com[2]))
else:
x, y = queue.popleft()
if y == com[1]:
a.append(x)
else:
b.append(x)
a.sort()
b.sort()
c = sorted(list(queue))
if not a:
print("None")
else:
print(*a, sep=" ")
if not b:
print("None")
else:
print(*b, sep=" ")
if not c:
print("None")
else:
for i in c:
print(i[0], end=" ")
|
풀이를 참고하는 것은 괜찮지만 혼자 풀어본 다음에 참고하도록 합시다!
더 궁금한 내용이 있다면, 댓글 남겨주세요!
감사합니다.