1. 학습목표
대망의 모각코 마지막 회차!!! 오늘은 스택, 큐, 덱을 파이썬으로 구현해보고 5회차에 학습한 그래프를 바탕으로 dfs를 구현해보고 이를 응용한 문제를 풀어보자!!
2. 학습내용
지난 회차에서 파이썬을 쓰지 않고 자료구조를 구현했는데 그 코드를 파이썬으로 구현해보았다. 스택, 큐, 덱,. 그래프 모두 다 구현해보았는데 확실히 복습하는데 도움이 되었다고 생각한다.
먼저 스택, 큐, 덱을 구현한 코드이다.
1. 스택(LIFO)
스택에서 가장 중요한 부분은 값이 어떻게 들어가고 어떻게 나오냐이다. 스택은 프링글스 통을 생각하면 쉽다. 가장 위에 있는 것이 가장 먼저 나오는데 가장 위에 있는 것은 가장 마지막에 넣은 것이다. 따라서 후입 선출의 구조를 갖는다.
import sys
n = int(sys.stdin.readline())
stack = []
def size(stack):
print(len(stack))
def push(stack, a):
stack.append(a)
def _pop_(stack):
if len(stack) == 0:
print(-1)
else:
print(stack.pop())
def empty(stack):
if len(stack) == 0:
print(1)
else:
print(0)
def top(stack):
if len(stack) == 0:
print(-1)
else:
print(stack[len(stack)-1])
for i in range(0, n):
user_input = list(sys.stdin.readline().split())
if user_input[0] == "push":
push(stack,int(user_input[1]))
elif user_input[0] == "pop":
_pop_(stack)
elif user_input[0] == "size":
size(stack)
elif user_input[0] == "empty":
empty(stack)
elif user_input[0] == "top":
top(stack)
else:
break
# 적용 문제
위에 만든 코드를 실행하면 정상적으로 작동하는 것을 확인할 수 있다. 시간 초과 문제 때문에 입력을 input() 이 아니라 sys 내장 라이브러리를 이용해 입력을 받았다.
2. 큐
큐와 스택의 차이점은 큐는 선입선출 방식이라는 것이다. 편의점에서 음료수를 진열할 때 뒤에서 유통기한이 가장 빠른 음료를 앞에다 넣으면 앞에 있는 것부터 빠져나가는 것을 예시로 들 수 있다. 쉽게 말해 양쪽이 다 뚫려있는 구조이다. 스택을 만들었다면 큐를 만드는 것은 크게 어렵지 않을 것이다.
import sys
n = int(sys.stdin.readline())
queue = []
def size(queue):
print(len(queue))
def push(queue, a):
queue.append(a)
def _pop_(queue):
if len(queue) == 0:
print(-1)
else:
print(queue.pop(0))
def empty(queue):
if len(queue) == 0:
print(1)
else:
print(0)
def front(queue):
if len(queue) == 0:
print(-1)
else:
print(queue[0])
def back(queue):
if len(queue) == 0:
print(-1)
else:
print(queue[len(queue)-1])
for i in range(0, n):
user_input = list(sys.stdin.readline().split())
if user_input[0] == "push":
push(queue,int(user_input[1]))
elif user_input[0] == "pop":
_pop_(queue)
elif user_input[0] == "size":
size(queue)
elif user_input[0] == "empty":
empty(queue)
elif user_input[0] == "front":
front(queue)
elif user_input[0] == "back":
back(queue)
else:
break
# 적용 문제
위의 스택과 마찬가지로 코드를 실행하였을 때 정상적으로 작동하는 것을 알 수 있다.
3. 덱
스택과 큐가 한 쪽방향으로만 값을 넣고 한쪽으로만 값이 나올 수 있었다면 덱은 양방향으로 모두 입출력이 가능한 자료구조이다. 따라서 코드에 앞쪽에서 값을 넣는 함수, 뒤쪽에서 넣는 함수, 앞쪽에서 빼는 함수, 뒤쪽에서 빼는 함수가 추가되어 있다.
import sys
n = int(sys.stdin.readline())
deque = []
def size(deque):
print(len(deque))
def push_front(deque, a):
deque.insert(0, a)
def push_back(deque, a):
deque.append(a)
def pop_front(deque):
if len(deque) == 0:
print(-1)
else:
print(deque.pop(0))
def pop_back(deque):
if len(deque) == 0:
print(-1)
else:
print(deque.pop(len(deque)-1))
def empty(deque):
if len(deque) == 0:
print(1)
else:
print(0)
def front(deque):
if len(deque) == 0:
print(-1)
else:
print(deque[0])
def back(deque):
if len(deque) == 0:
print(-1)
else:
print(deque[len(deque)-1])
for i in range(0, n):
user_input = list(sys.stdin.readline().split())
if user_input[0] == "push_front":
push_front(deque,int(user_input[1]))
elif user_input[0] == "push_back":
push_back(deque,int(user_input[1]))
elif user_input[0] == "pop_front":
pop_front(deque)
elif user_input[0] == "pop_back":
pop_back(deque)
elif user_input[0] == "size":
size(deque)
elif user_input[0] == "empty":
empty(deque)
elif user_input[0] == "front":
front(deque)
elif user_input[0] == "back":
back(deque)
else:
break
# 적용 문제
코드를 작성하다보면 알게 된다. 스택, 큐, 덱은 기본적인 구조가 거의 비슷하다는 것을...하나만 짤 줄 알고 각 구조가 어떤 특징의 차이를 갖는지 안다면 크게 어려움 없이 코드를 작성할 수 있다.
## DFS ##
앞에 한 것은 알고 있으면 나쁠 것이 없고 즉석에 보고서 천천히 짜도 상관 없지만 얘는 외워두는 것이 정신 건강에 좋을 것이다. 왜냐하면 그래프 관련해서 탐색을 해야할 때 정말 많이 사용할 것이기 때문이다.
dfs란 깊이 우선 탐색으로 어떻게 작동하는지 아는 것이 가장 중요하다. 이를 알면 코드를 구현 하는데 크게 어렵지는 않을 것이다. 아래의 그림처럼 한 쪽으로 아래 방향으로 쭉 탐색하고 그 후에 다시 돌아와서 방문하지 않은 쪽을 탐색한다. 시간 복잡도는 O(V+M) (V: 정점의 수, M: 간선의 수)이다.
이제 1번 노드의 탐색이 모두 끝난 것이다. 나머지 2번 노드 역시 위와 같은 방식으로 진행하면, 모든 노드를 탐색할 수 있다.
DFS의 장점:
- DFS는 현재 순회 중인 정점만 저장하는 스택 데이터 구조를 사용하기 때문에 BFS에 비해 메모리 공간을 덜 차지한다.
- DFS는 목표가 특정 정점(또는 모든 정점)에 최대한 빨리 도달하는 것일 때 유용하다.
- DFS를 사용하여 그래프에서 순환을 감지할 수 있다.
DFS의 단점:
- 순환 그래프의 경우 DFS가 무한 루프에 빠질 수 있다.
- DFS는 두 정점 사이의 최단 경로를 찾으려는 경우 사용하기에 가장 좋은 알고리즘이 아닐 수 있다.
# 코드 구현
dfs 알고리즘의 방식은 다음과 같다.
# 1. 현재 노드를 방문한 것으로 표시한다.
# 2. 방문한 표시가 되어 있지 않은 각각의 인접한 정점을 탐색한다.
# 3. 더 이상 방문하지 않은 정점이 없으면 이전 정점으로 역추적(backtracking) 한다.
# 4. 모든 정점을 방문할 때까지 프로세스를 반복한다.
따라서 이를 통해 코드에서 방문했음을 확인할 변수가 필요하다는 것을 알 수 있다. 그리고 인접한 노드들을 나타낼 인접리스트 또한 필요함을 알 수 있다.
import sys
n, m = map(int, sys.stdin.readline().split())
visited = [False] * (n+1)
adjacent = [[] for _ in range(n+1)] # 인접 행렬 // e.g n = 5, 0은 1,2와 인접, 2는 3과 인접 하다 가정 >> [ [1,2] [] [3] [] [] ]
# 그래프 생성
for _ in range(m):
u, v = map(int, sys.stdin.readline().split())
adjacent[u].append(v)
adjacent[v].append(u)
# 그래프 출력
for i in range(n):
print(f"{i}와 인접한 노드들: {adjacent[i]}")
def dfs(start):
visited[start] = True
print(f"{start}를 방문했습니다.")
for neighbor in adjacent[start]:
if not visited[neighbor]:
dfs(neighbor)
# 적용 문제
# 작성한 답안
import sys
n, m = map(int, sys.stdin.readline().split())
visited = [False] * n
adjacent = [[] for _ in range(n)]
arrive = False
# 그래프 생성
for _ in range(m):
u, v = map(int, sys.stdin.readline().split())
adjacent[u].append(v)
adjacent[v].append(u)
def dfs(start, cnt):
global arrive
if cnt == 4:
arrive = 1
return
visited[start] = True
for neighbor in adjacent[start]:
if not visited[neighbor]:
dfs(neighbor, cnt+1)
visited[start] = False
for i in range(n):
arrive = 0
visited = [False for _ in range(n)]
dfs(i, 0)
if arrive == 1:
print(arrive)
break
else:
print(0)
위에 만든 dfs 틀을 응용해서 사용해야 한다. 문제를 읽어보면 하나의 노드에서 출발했을 때 5번째 노드까지 방문할 수 있는가를묻는 문제이다. 백트래킹을 이용하여 탐색이 실패한 경우 방문 상태를 False로 초기화해주고 다음 노드에서 시행하는 방식을 반복한다. 따라서 각 점에서 dfs를 수행해주고 조건에 맞는 경우 1을 출력, 아닐 경우 0을 출력한다.
느낀 점
모각코를 처음 계획한대로 학습을 다 하진 못했다. 그건 내 학습 속도가 예상보다 느려서 차근차근 하는 것이 더 중요하다는 판단하에 깊이 있는 이해로 방향을 잡았다. 그래도 알고리즘 중 dfs까지는 학습하였기 때문에 이후에 그래프를 이용한 다른 알고리즘(최단거리 알고리즘, 그리디..)들을 학습할 것이다. 계획을 어떻게 세우고 학습을 어떻게 해야할 지 어느정도 가닥이 잡힌거 같다. 남은 방학 기간동안 열심히 학습해서 다른 사람들보다 늦게 학습하기 시작한만큼 열심히 따라가겠다.
