programmer life guidance 101

> BFS(Breadth-First Search, 너비우선탐색) 그래프 순회 순회(traversal) 그래프의 모든 노드들을 방문하는 일 대표적 두 가지 방법 BFS (Breadth-First Search, 너비우선순회) DFS (Depth-First Search, 깊이우선순회) 너비우선탐색(BFS) BFS 알고리즘은 다음 순서로 노드들을 방문 L0 = {s}, 여기서 s는 출발 노드 L1 = L0의 모든 이웃 노드들 L2 = L1의 이웃들 중 L0에 속하지 않는 노드들 ... Li = Li-1의 이웃들 중 Li-2에 속하지 않는 노드들 한마디로 그래프에서 노드들을 동심원의 형태로 순회하는 방법 큐를 이용한 너비우선탐색 출발노드를 check하고 시작한다. 큐에 스타트 노드(1번노드)를 삽입한다. whil..

> Graph Algorithm - 개념과 표현 Graph (무방향) 그래프 G = (V, E) V : 노드 혹은 정점(vertex) E : 노드쌍을 연결하는 Edge 혹은 Link Object들 간의 이진관계를 표현 n = |V|, m = |E| 방향 그래프와 가중치 그래프 방향그래프(Directed Graph) G = (V, E) Edge (u, v)는 u로부터 v로의 방향을 가짐 가중치 그래프 Edge마다 가중치(weight)가 존재 그래프의 표현 인접행렬(adjacency matrix) 인접리스트(adjacency list) 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결 리스트 저장 공간 : O(n + m) 어떤 노드 v에 인접한 모든 노드 찾기 : O(degree(v)) ..