00. 자료구조를 공부하는 이유?
상황에 맞는 방식으로 데이터를 저장하고 사용하기 위해 자료구조를 공부해야한다. 또한 데이터 사이에 어떤 관계가 있는가를 중점을 두고 자료구조를 사용하자.
01. 그래프란?
연결 데이터를 저장 할 수 있는 자료구조이다.
(1) 연결 데이터 혹은 연결 관계?
① 위치 데이터(ex. 지하철 앱)
② 사회 연결망(ex. 친구관계)
③ 통신 : 수많은 컴퓨터들의 연결관계
④ 생물 : 유전자와 단백질의 상호작용 관계
02. 그래프 용어
① 노드 : 그래프에서 하나의 데이터 단위를 나타내는 객체
② 엣지 : 그래프에서 두 노드의 직접적인 연결 관계 데이터(ex. 페이스북 유저 그래프)
③ 인접 : 두 노드가 엣지로 연결되어 있으면 '인접해 있다'라고 한다.
④ 경로 : 엣지들이 연결되어 있는 것을 경로라고 한다.
⑤ 사이클 : 특정 노드에서 다시 그 노드로 돌아오는 경로는 사이클이라고 함.
⑥ 차수 : 한 노드가 가지고 있는 엣지의 수
03. 무방향 그래프(undirected graph)
- 무방향그래프 : 쌍방향일 경우 무방향그래프라고 표현한다.
04. 방향 그래프(directed graph)
방향 그래프에서는 엣지들이 방향을 가진다. 인스타그램의 팔로우 관계처럼 한 유저가 다른 유저를 팔로우 하는 일방적인 관계를 나타낼 수 있게 해준다. 방향그래프에서 차수는 출력차수와 입력차수로 나뉜다.
① 출력 차수 : 노드에서 나가는 엣지의 수
② 입력 차수 : 노드에서 들어가는 차수를 입력
05. 가중치 그래프(weighted graph)
① 무 가중치 그래프 : 모든 엣지의 값이 동일한 그래프
② 가중치 그래프 : 엣지의 값이 다른 그래프
06. 인접행렬 VS 인접리스트
인접 행렬이란 "총 노드의 수 x 총 노드의 수" 만큼의 행렬을 만든다. 그리고 여기에 노드들간의 인접 데이터를 저장한다.
인접 리스트란 각 노드가 자신과 인접한 노드들을 가리키는 레퍼런스를 저장하고 있다.
① V : V는 그래프 안에 있는 모든 노드들의 집합이다. 그래프에 있는 하나의 데이터 객체를 노드라고 부르지만 Vertex라는 표현을 사용하기도 한다. Vertex의 가장 앞 알파벳을 따서 V라고 한다.
② E : E는 그래프 안에 있는 모든 엣지들의 집합이다. 엣지를 영어로 쓰면 Edge이다.
③ 그래프를 사용할 땐 O(n), O(\lg(n)) 이런 점근 표기법 대신 O(V), O(E), O(\lg(V))
④ 엣지가 가장 많을 때 : 모든 노드가 서로 다른 노드에 연결되어 있는 경우 (무방향 그래프 : V^2/2, 방향그래프 : V^2 )
⑤ 노드를 저장하는 공간 : 노드를 저장하는데에는 O(V)의 공간을 사용한다고 할 수 있음
⑥ 인접리스트가 차지하는 공간 : 총 V개의 배열 또는 파이썬 리스트를 저장해야 할때 . V^2에 비례하기 때문에 일단 최소 O(V) 만큼의 공간을 차지한다. 인접 리스트는 최악의 경우 엣지 데이터를 O(V^2)로 저장한다.
⑦
⑧ 두 노드가 연결되었는지 확인하는데 걸리는 시간 :
- 인접행렬을 이용(두 노드가 인접했는지 아닌지를 으로 알아낼 수 있다. )
- 인접리시트의 경우 한 노드 안에 특정 데이터가 저장됐는지를 탐색해야한다. 선형 탐색을 해야하기 때문에 리스트 안에 있는 데이터를 다 돌아야 해서 최악의 경우 V개의 요소를 확인해야한다.
⑨ 한 노드에 연결된 모든 노드들을 알아내는데 걸리는 시간 : 인접 행렬의 경우 배열을 다 돌아야하지만 인접리스트의 경우 각 노드가 자신과 인접한 노드들에 대한 레퍼런스만 가지고 있다. 물론 최악의 경우 한 노드가 다른 모든 노드들과 연결되어 있으면, 인접 행렬과 마찬가지로 총 V번 돌아서 인접행렬을 사용하는거보다 더 빨리 실행된다.
08. Breadth First Search (BFS)
너비우선탐색으로 시작을 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법이다.
① 전처리: O(V)
② 큐에서 노드 넣고 빼기: O(V)
③ 인접한 노드들을 도는데 걸리는 시간 O(E)
① 큐에서 가장 앞 노드를 꺼낸다.
② 이 노드에 인접해 있는 노드들을 돌면서:
① 처음 방문한 노드면 :
① 방문한 노드로 표시한다
② 큐에 넣는다.
def bfs(graph, start_node):
"""시작 노드에서 bfs를 실행하는 함수"""
queue = deque() # 빈 큐 생성
# 모든 노드를 방문하지 않은 노드로 표시
for station_node in graph.values():
station_node.visited = False
# 시작점 노드를 방문 표시한 후 큐에 넣어준다
start_node.visited = True
queue.append(start_node)
while queue: # 큐에 노드가 있는 동안
current_station = queue.popleft() # 큐의 가장 앞 데이터를 갖고 온다
for neighbor in current_station.adjacent_stations: # 인접한 노드를 돌면서
if not neighbor.visited: # 방문하지 않은 노드면
neighbor.visited = True # 방문 표시를 하고
queue.append(neighbor) # 큐에 넣는다
09. Depth First Search(DFS)
① 스택에서 가장 위 노드를 꺼낸다.
② 방문처리 표시를 한다.
③ 해당 노드에 인접해 있는 노드들을 돌면서,
① 확인한 노드면
② 표시한다.
③ 스택에 넣는다.
from collections import deque
def dfs(graph, start_node):
"""dfs 함수"""
stack = deque() # 빈 스택 생성
# 모든 노드를 처음 보는 노드로 초기화
for station_node in graph.values():
station_node.visited = 0
start_node.visited = 1 # 시작 노드를 스택에 넣는다는 표시(옅은 회색)를 하고
stack.append(start_node) # 스택에 넣습니다
while stack: # 스택에 노드가 남아 있을 때까지
current_node = stack.pop() # 스택 가장 위(뒤) 데이터를 갖고 온다
current_node.visited = 2 # 현재 노드를 방문 표시한다
for neighbor in current_node.adjacent_stations:
if neighbor.visited == 0: # 처음 보는 노드들만
neighbor.visited = 1 # 스택에 넣는다는 표시를 하고
stack.append(neighbor) # 스택에 넣습니다
10. 그래프를 사용할 때 끊기는게 많을 때는 어떻게 사용해야할까?
11. 스트링으로 key와 value값을 사용해야할때, 중복 값이 있으면 어떻게 해야할까?
'회고록' 카테고리의 다른 글
| 👩🏼💻TIL : 11. 🎄🎄트리🎄🎄 (0) | 2022.10.09 |
|---|---|
| 👩🏼💻TIL : 10. 시간복잡도(Time Complexity) (1) | 2022.10.08 |
| 👩🏼💻TIL : 8. 스택이란? (0) | 2022.10.01 |
| 👩🏼💻TIL : 7. 재귀함수(Recursion) (0) | 2022.09.26 |
| 👩🏼💻TIL : 6. 서버사이드렌더링이 뭘까? (0) | 2022.09.19 |
댓글