9건의 항목
그래프 용어 V : vertex E : Edge path 연결 그래프 : 어떤 두 정점 사이에도 경로가 존재하는 그래프 부분 그래프 가중치 포함 그래프 : Edge에 가중치가 달려있음 순환 경로 순환 그래프, 비순환 그래프 트리 - 비순환, 비방향그래프 신장 트리 : 연결된, 비방향성 그래프에서 순환경로를 제거하면서 연결된 부분 그래프가 되도록 하는 트리 신장 트리의 개수는 Cayley’s formula에 따른 개수를 가짐 최소비용신장트리 신장 트리가 되는 부분 그래프 중에서 가중치가 최소가되는 부분 그래프 무조건 트리로 나온다.
골드3 : 그래프 문제이다. 생각 현재 시작 위치에서 다음 쓰레기를 치우고, 그 위치에서 다시 다음 경로를 탐색하는 과정으로 문제를 풀려 했다. 하지만 코드를 짜면서도 탐색과정이 계속하여 중복되서 어떻게 풀어야 할지 고민을 많이했다.
실버1 : dfs를 사용하는 기초적인 문제이다. 이런 문제를 풀 때, 생각보다 실수를 많이하는 부분은, testcase가 있을 때, 초기화를 하지 않는 것이다. 항상 testcase가 있는 문제는, 이 부분을 유념해야 한다.
DFS graph 골드4 : 그래프 문제이다. 생각 이분 그래프란 무엇인가? 문제를 읽고는 파악하는 게 힘들었다. 차라리 그림으로 보는 것이 좋다. {:.center-text} 왼쪽과 같은 그래프가 있을 이걸 오른쪽 그림처럼 바꿀 수 있느냐의 문제이다.
골드3 : dfs 문제이다. 풀이 트리 = 사이클이 없는 무방향 그래프. 어떠한 두 노드를 선택해도 경로는 하나이다. 즉 무조건 연결되어 있다. 쉽게 생각하기 위해서 이미 두 지름인 점을 알고 있다고 가정하자.
실버2 : 그래프 문제이다. 생각 아. 정말 쉽겠지 했는데, 되지도 않는 시간 복잡도 줄여보겠다고 확인 되지 않는 것 썼다가 하루 다 날린 문제이다. 문제는 상당히 간단하게 DFS로 풀 수 있다.
Code import tensorflow as tf tf.set_random_seed(777) # 같은 값이 나오도록 하기 위해서 # 데이터 준비 x_train = [1, 2, 3] y_train = [1, 2, 3] # 초기에 랜덤하게 값을 할당한다.
무향 Graph에서 완전히 연결된 부분 그래프 Reference Clique .
용어 정점(Vertex, Node): 그래프의 노드 간선(Edge): 그래프의 노드를 연결하는 선 방향 (화살표) 무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프 방향 그래프(Directed Graph): 간선에 방향이 있는 그래프 값 가중치(Weight): 간선에 부여된 값 정의 그래프(Graph) 그래프(graph) G는 정점(vertex)의 집합 V와 간선(edge)의 집합 E로 구성된다.