제가 재학 중인 대학교에서 열린 `파이썬 알고리즘 코딩캠프(25.02.03 ~ 25.02.14)` 수업을 듣고 정리한 글입니다.
목차 :
- 스택
- 큐
- 덱
- 그래프
- 인접 행렬
- 인접 리스트
스택
스택은 ADT에서 `push, pop` 두 가지 대표적인 연산을 가짐.
후입선출
파이썬은 스택이 따로 라이브러리로 정의되어있진 않고,
리스트에서 append와 pop으로 정의되어 있음.
이 정도만 알아도 나머진 문제푸는 데 지장 없고, 나머진 우리들의 사고력 문제.
# 파이썬에서 스택은 리스트로 구현한다.
stack = []
# push
stack.append(1)
stack.append(2)
stack.append(3)
print(stack)
# peek (top에 있는 요소를 삭제하지 않고 조회만 하는 연산)
# 따로 peek 연산이 있는 건 아니고, index를 통해 확인.
print(stack[-1])
# pop
print(stack.pop())
print(stack.pop())큐
큐는 ADT에서 enqueue, dequeue 두 가지 대표적인 연산을 가짐.
- `enqueue` : 큐의 맨 뒤에 데이터를 삽입하는 행위
- `dequeue` : 큐의 맨 앞 데이터를 가져오는 행위
선입선출
파이썬은 큐가 따로 라이브러리로 정의되어있진 않고,
리스트에서 append와 pop으로 정의되어 있음.
# 파이썬은 큐를 리스트로 구현한다.
queue = []
# enqueue
queue.append(1)
queue.append(2)
queue.append(3)
print(queue)
# peek
print(queue[-1])
# dequeue
print(queue.pop(0))
print(queue)덱
double-ended queue의 줄임말.
양방향 큐. 양 방향에서 넣고 뺄 수 있는 queue라는 말.
사용이유 : list로 큐를 구현하면, pop을 위해 pop(0)을 쓰면 당겨주는 것 때문에 O(n)이 걸리기 때문.
그래서 덱은 appendleft(), popleft()라는 추가적인 연산이 ADT에 존재함.
덱은 동적 배열인 리스트랑 달리, 링크트 리스트로 구현되어 있기 때문에, index n에 있는 놈을 조회하려고 할 때도 앞에서부터 화살표 쭉쭉 가야하기 때문에 O(n)이 걸림.
그러나, 덱은 애초에 조회에 초점이 있는 게 아닌, 넣고 때는 거에 초점이 잡혀있기 때문에, 조회가 느려도 괜찮은거임.
즉, 조회보다 양방향에서 넣고 빼는 게 자주 일어날 것 같은 상황에는, 리스트 대신 덱을 쓰는 게 더 효율적이다!!
왜 덱을 썼나요? 하는 근거를 말할 수 있어야 함.
덱 클래스의 주요 메서드들
- `popleft()`: 왼쪽에서 원소를 추출하여 반환한다.
- `appendleft(item)`: 왼쪽으로 원소를 삽입한다.
- `pop()`: 오른쪽에서 원소를 추출하여 반환한다.
- `append(item)`: 오른쪽으로 원소를 삽입한다.
⇒ 따라서 `popleft()`와 `append(item)`을 활용하여 큐를 구현할 수 있다.
# 덱(Deque, Double-Ended Queue)
# 얘는 리스트로 구현하지 않고, 별도로 클래스로 구현되어 있기 때문에,
# 덱 클래스를 import해줘야 함.
from collections import deque
queue = deque()
# enqueue
queue.append(1)
queue.appendleft(2)
print(queue)
# peek
print(queue[0])
print(queue[-1])
# dequeue
print(queue.popleft())
print(queue.pop())
그래프
그래프 = 노드 집합과 엣지 집합으로 이루어진 집합.
`G = {V, E}`
그래프는 경로 문제가 많이 나옴.
다음주에 우리가, `이 그래프에 싸이클이 있나요?` 를 판별하는 알고리즘도 배워볼 거임.
인접은 두 개의 정점이 하나의 간선으로 직접 연결된 상태를 의미함.
그래프의 종류가 크게 두 가지가 있음. 무방향 그래프, 유방향 그래프.
개념은 쉽지만, 이제 코드로 구현해보세요 하면 으잉? 하게됨.
그래프를 보고 어떻게 코드로 구현할까 하는 게 문제.
백준같은 곳에선 간선을 의미하는 문자열들이 주어짐. : 이를 `간선 정보` 라고 함.
ex. `0 1` : 0 → 1 또는 0 - 1 간선을 의미.
그래프의 표현 방식은 두가지가 있음: 인접 행렬, 인접 그래프.
인접 행렬
다음의 인접 행렬은 쓸모없는 정보 0이 많이 들어가, 불필요한 메모리를 사용하게 됨.
즉, 공간복잡도가 불필요하게 크고,
이에 따라 필연적으로 나중에 시간복잡도도 늘어나게 됨. 따라서, 이 다음의 인접 리스트를 통한 그래프 표현 방식이 더 효율적.
# 그래프 표현 - 인접 행렬
'''
0 1
0 2
0 5
0 6
3 4
3 5
4 5
4 6
'''
# 그래프를 인접 행렬로 표현하기
# 1. 정점과 간선 개수 정의
n = 7 # 정점 개수
m = 8 # 간선 개수
# 2. 인접 행렬 초기화
# (정점 개수) x (정점 개수) 크기의 행렬
graph = [[0] * n for _ in range(n)]
# 3. 인접 행렬 채워 그래프 나타내기
for _ in range(m):
v1, v2 = map(int, input().split())
graph[v1][v2] = 1
graph[v2][v1] = 1 # <- 이거 없애면 유방향 그래프
for line in graph:
print(line)
'''
[0, 1, 1, 0, 0, 1, 1]
[1, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1, 0]
[0, 0, 0, 1, 0, 1, 1]
[1, 0, 0, 1, 1, 0, 0]
[1, 0, 0, 0, 1, 0, 0]
'''
# 근데, 보통 문제에서는 0번 정점 잘 안주는데? 그러면 어떻게 해야 할까?
# => 아래처럼 행렬의 0행과 0열에 쓸모없는 더미 데이터 0 넣으면 됨.
# 이러면, 나중에 조회할 때도 v1 v2 그대로 쓰면 됨.
graph = [[] for _ in range(N + 1)]인접 리스트
# 그래프의 표현 - 인접 리스트
'''
0 1
0 2
0 5
0 6
3 4
3 5
4 5
4 6
'''
# 1. 정점과 간선 개수 정의
n = 7 # 정점 개수
m = 8 # 간선 개수
# 2. 인접 행렬 초기화
graph = [[] for _ in range(n)]
# 3. 인접 리스트 채워 그래프 나타내기
for _ in range(m):
v1, v2 = map(int, input().split())
graph[v1].append(v2)
graph[v2].append(v1) # <- 이거 없애면 유방향 그래프
for line in graph:
print(line)
# 근데, 보통 문제에서는 0번 정점 잘 안주는데? 그러면 어떻게 해야 할까?
# => 아래처럼 쓸모없는 더미 리스트 하나 넣으면 됨.
# 이러면, 나중에 조회할 때도 v1 v2 그대로 쓰면 됨.
graph2 = [[] for _ in range(n + 1)]
# 근데, 문제에서는 보통 이게 유방향 그래프인데 무방향 그래프인지 잘 안줌.
# 그럴 땐 내가 알아서 문제를 읽고 어느 그래프로 정의할 지 판단해야함.
# 아까 인접 행렬에 비해 공간, 시간 복잡도 이득.
# 따라서 우리가 일반적으로 푸는 문제들은 따라서 거의 인접 그래프로만 풀면 됨.
# 코테 수준에서는 98% 이상.
# 플레 다이아 가면 인접 행렬로만 풀 수 있는 문제가 있기도 함.Quiz) 백준에서 그래프 입력받고 표현하기
import sys
input = sys.stdin.readline
'''
첫 줄은 정점과 간선 개수, 둘째 줄부터는 간선 정보
6 7
1 2
1 3
2 3
2 5
2 6
3 4
5 6
위 그래프를 각각 인접 행렬, 인접 리스트로 표현하시오.
단, 정점 번호는 1번부터 시작한다.
'''
N, M = map(int, input().split())
# # 인접 행렬 구현
# graph_adj_matrix = [[0] * (N + 1) for _ in range(N + 1)]
#
# for _ in range(M): # 간선 개수만큼 반복
# v1, v2 = map(int, input().split())
# graph_adj_matrix[v1][v2] = 1
# graph_adj_matrix[v2][v1] = 1
#
# for line in graph_adj_matrix:
# print(line)
'''
[0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 0, 0]
[0, 1, 0, 1, 0, 1, 1]
[0, 1, 1, 0, 1, 0, 0]
[0, 0, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 1, 0]
'''
# 인접 리스트 구현
graph_adj_list = [[] for _ in range(N + 1)]
for _ in range(M): # 간선 개수만큼 반복
v1, v2 = map(int, input().split())
graph_adj_list[v1].append(v2)
graph_adj_list[v2].append(v1)
for line in graph_adj_list:
print(line)
'''
[]
[2, 3]
[1, 3, 5, 6]
[1, 2, 4]
[3]
[2, 6]
[2, 5]
'''과제 및 풀이 정리
<스택>
- 스택
- 제로
- 괄호
- 크레인 인형뽑기 게임
<큐 덱>
- 큐
- 덱
- 카드 2
- 뱀
