CS Study

1. Topological sort- 순서에 어긋나지 않도록 주어진 Directed Graph의 모든 Node를 한 번씩 방문하는 방법ex) 주어진 Directed Graph에서 N1 -> N2 엣지가 존재할 시, N1을 N2보다 먼저 방문해야 함ex)- (5 -> 4 -> 2 -> 3 -> 1 -> 0) 2. Topological Sort과정- (진입 차수) = (들어오는 Node의 수)- 진입 차수가 0인 Node 및 연결된 엣지 모두 제거 (기록)- 제거 대상 Node가 여러개면 그들 가운데 하나만 제거 - 모든 Node를 방문할 때 까지 같은 과정 반복- 제거한 Node의 순서가 Topological Sort한 순서가 된다. 3. Codedef topological_sort(graph): w..

1. DFS(Depth-first search)?- 갈 수 있는 가장 깊은 곳까지 내려가는 알고리즘- Pre/In/Post - order순회- 재귀를 이용하여 구현 가능하다. - 다음과 같은 그래프를 3을 기준으로 DFS한다고 생각해보자. (인접노드일때 값이 작은것부터 탐색한다.)- (3 -> 1 -> 0 -> 2 -> 4 -> 5 -> 6) 이 될것이다. 2. Code 구현dfs_visit = list()def DFS(graph,start_node): dfs_visit.append(start_node) for each_node in graph[start_node]: if (each_node in dfs_visit) == False: DFS(graph,each_..

1. BFS?- BFS는 인접한 노드를 우선 방문하는 것을 의미한다.- Level-order 순회와 동일하다.- Queue로 구현이 가능하다. - 4를 기준으로 BFS를 한다고 생각해보자. (단 인접노드는 작은값부터 탐색한다.)- walk는 다음과 같다.- (4 -> (2 -> 3 -> 5)-> (0 -> 1) -> 6)2. Code 구현from collections import dequedef BFS(graph,start_node): visit = list() queue = deque() visit.append(start_node) queue.append(start_node) while len(queue) > 0 : for each_node in graph[que..

1. Graph?- 두 대상 사이 관계를 나타낼 수 있는 자료구조- 아래의 그림처럼 동그란 점들이 Node, 점끼리 이어진 선들이 edge가 됨.1.1. wark?- 두 Node을 잇는 edge가 존재하는 경우 둘을 인접한다고 정의한다.-- 인접한 꼭짓점을 따라 이동한 족적을 Walk라고 한다.- 시작점과 끝점이 동일한 경우 닫힌 walk라고 하며,- 다른경우 열린 walk라고 한다. 1.2. path- walk 가운데 중복된 꼭짓점이 존재하지 않는 것을 path라고한다.1.3. cycle- 닫힌 walk와 path의 조건을 모두 만족하는 경우 이를 cycle이라고 한다.ex) 위의 그림에선 A - B - D - A 가 된다. 2. Directed Graph- 엣지에 방향이 존재하는 경우 Directed..