정보처리기사를 준비하며 '자료 구조'에 대해 깊이 고민하지 않았다는 것을 알게되었다.
코딩테스트도 함께 준비하는 과정에서 알고리즘의 방식은 이해했지만
왜❓ 그래프(Graph) 자료구조를 사용하고 스택(stack)과 큐(queue)를 사용하는지
명확한 이해 없이 사용해왔다고 정리가 필요하다고 생각되었다.
🅰️ 사전 지식
1️⃣ 기본 자료 구조에 대하여
자료 구조란❓
자료(Data)를 저장하는 논리적인 방법
너무 직관적인 답변이여서 '이정도는 알지~'하고 넘어갈 수 있지만 기본이 정말 중요하다.
개발을 하며 자료 즉, 데이터란 단어를 정말 많이 사용하지만 데이터는 정말 다양한 형태로 사용된다.
문자열(String), 문자(Char), 정수(Int), 실수(Float), 배열(array), 리스트(list), 딕셔너리(Dictionary), 구조체(Struct), 클래스(Class), 프로토콜(Protocol), ... 등등
Q) 우린 왜 이 많은 타입들을 알아야했을까??
A1) 데이터 검색 편하게 하려고
A2) 객체를 좀 더 명확하게 분리하려고
A3) 디자인 패턴과 아키텍쳐를 구현하는데 사용하려고
이와 같이 흔히 너무 많이 들었던 얘기들이었다.
하지만 필자는 그냥 '학습 항목이였을 뿐' 혹은 '책에서 제일 처음 알려주니까'와 같이 깊게 고민해 본 경험이 없었던 것 같다.
사설은 다음을 기약하며 이제 블로그 제목에 맞게 빠르게 필요한 자료구조를 분류해보자!
2️⃣ 자료구조 분류
우선! 선형 구조(Linear Structure)와 비선형 구조(Non-Linear Structure)으로 분리하여 보자.
선형(순차적) 🆚 비선형(비순차적)
- 선형 구조
- 배열(Array)
- 선형 리스트(Linear List) : 연결 리스트, 연속 리스트
- 스택(Stack)
- 큐(Queue)
- 데크(Deque)
- 비선형 구조
- 트리(Tree)
- 그래프(Graph)
여기서 트리(Tree)와 그래프(Graph)의 차이점은 순환(Cycle)이 가능 여부이다.
트리는 순환이 안되지만 그래프는 가능하다.
트리와 함께 설명하면 너무 글이 길어져 그래프만 쉽게 알고 들어가보자!
2-1. 그래프(Graph)
그래프(Graph)란?
정점(V, Vertex)와 간선(E, Edge)의 두 집합으로 이루어진 순환 즉, 사이클(Cycle)이 있는 자료구조
네트워크 형태로 상호 연결되어 있는 구조를 표현할 때 유용하다.
그래프의 종류
- 기본 구조
- 무방향 그래프 & 방향 그래프 (방향의 유무에 따라 결정)
- 특수 형태
- 가중치 그래프
- 연결 그래프 & 비연결 그래프 (노드 쌍 경로에 따라 결정)
- 순환 그래프 & 비순환 그래프 (순환 여부)
- 완전 그래프
🔥 그래프(Graph)를 인접 행렬로 표현하기❗️
인접 행렬(Adjacency matrix)이란?
그래프의 구조를 표현하기 위해 정점 수만큼의 열과 행을 가진 행렬을 이용하는 방법
즉, 그래프를 2차원 배열로 표현하는 방식이다.
각 노드 간의 연결 여부를 0과 1로 표현한다.
이 방식은 노드 수에 비해 간선 수가 많은 경우 효율적이다.
7 8 # Vertex = 7개, Edge = 8
V, E = map(int, input().split())
adj_matrix = [[0] * (V + 1) for _ in range(V + 1)]
for _ in range(E): # 간선 갯수만큼 돌면서 연결 정보를 받음
start, end = map(int, input().split()) # 시작점과 끝점
adj_matrix[start][end] = 1
adj_matrix[end][start] = 1 # 양방향 그래프니까!! (거꾸로 돌려서 찍기)
# 예시) 컴퓨터가 인식하는 그래프
# [[0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 1, 1, 0, 0, 0, 0],
# [0, 1, 0, 0, 1, 1, 0, 0],
# [0, 1, 0, 0, 0, 0, 0, 1],
# [0, 0, 1, 0, 0, 0, 1, 0],
# [0, 0, 1, 0, 0, 0, 1, 0],
# [0, 0, 0, 0, 1, 1, 0, 1],
# [0, 0, 0, 1, 0, 0, 1, 0]]그리고 흔히 DFS, BFS 코드를 작성할 때 아래와 같이 함수의 매개변수로 받아온다.
def dfs(graph, start, visited=None):
...
def bfs(graph, start_node):
...트리(Tree)와 그래프(Graph)를 이용한 문제 해결
- Tree
- 한 노드(Node)가 다수의 자식 노드(Child Node)를 가질 수 있으나,
자식 노드는 오직 하나의 부모 노드(Parent Node)만을 가진다. - 이러한 특성으로 인해 계층적 데이터를 다루거나,
특정 조건을 만족하는 경로를 찾는 등의 문제에서 사용된다. - DFS - 특정 노드부터 시작하여 깊게(Depth) 탐색 진행
- BFS - 레벨별로 넓게(Breadth) 탐색 진행
- 한 노드(Node)가 다수의 자식 노드(Child Node)를 가질 수 있으나,
- Graph
- 복잡한 네크워크 관계를 모델링하는 데 사용될 수 있으며,
다양한 형태의 문제 해결에 적용된다. - DFS - 가능한 한 멀리 있는 노드를 우선적으로 탐색 진행
- BFS - 시작 노드부터 가까운 노드를 먼저 탐색 진행
- 복잡한 네크워크 관계를 모델링하는 데 사용될 수 있으며,
🅱️ DFS와 BFS
| 깊이 우선 탐색 (Depth First Search) | 너비 우선 탐색 (Breadth First Search |
|---|---|
| 한 노드의 자식을 끝까지 순회 후 다른 노드 순회 | 한 단계씩 내려가며 같은 레벨에 있는 노드들을 먼저 순회 |
| 자식 우선 | 형제 우선 |
| Stack(LIFO) 또는 재귀함수 | Queue(FIFO) |
처음에 Graph 탐색에 왜 스택과 큐를 사용할까? 짧게 고민했는데
방향이 있어야 탐색이 될 것이고 각 알고리즘의 특성에 맞춰 깊이(Depth) 순서로 확인하는 스택과 레벨(Breadth) 순서로 확인하는 큐가 사용되는 것을 이해함이 중요했다!
예제코드를 통해 확인하기
DFS
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in graph[start] - visited:
dfs(graph, next, visited) # 재귀 함수를 사용
return visited
graph = {
'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])
}
print(dfs(graph, 'A')) # {'C', 'E', 'F', 'A', 'D', 'B'}BFS
from collections import deque
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
def bfs(graph, start_node):
visited = [] # 방문한 노드를 기록
queue = deque([start_node])
while queue:
node = queue.popleft() # 큐에서 하나의 노드를 꺼냄
if node not in visited:
visited.append(node)
neighbours = graph[node]
for neighbour in neighbours:
if neighbour not in visited:
queue.append(neighbour)
return visited
print(bfs(graph, 'A')) # ['A', 'B', 'C', 'D', 'E', 'F']마치며..
알고리즘과 자료구조를 학습하며 너무 프로젝트에 집중하려 본질을 놓쳤던 과거가 아쉬운 점이 많아 DFS & BFS 라는 제목으로 작성했지만 사실 회고에 가깝게 작성하고싶었다.
항상 '타입을 중요하게 생각합니다.'라고 말했지만 정작 그 타입들 즉, 자료구조가 지니고 있는 특징과 어떻게 구현해야지 올바르게 동작(알고리즘)하는 지 깨닫지 못하고 코드를 썼던 것 아닐까하며 반성하는 계기가 되었다.
빠르게 구현해서 결과를 내는 것도 중요하지만 내가 작성하는 코드에 대한 명확한 이해를 가지고 있어야 함을 다시 한 번 느끼고 포트폴리오도 중요하지만 왜 채용 절차에서 코딩테스트를 통해 개발자로서의 기본 소양을 갖추고 있는지를 이해할 수 있는 부분이였다.
