본문 바로가기

분류 전체보기

 (154)
최소 비용 신장 트리 (2) Minimum Spanning Tree Kruskal Algorithm 서로소인 집합들의 표현- 각 집합을 하나의 트리로 표현한다.- disjoint 특성(두 집합이 공집합)을 가진 sets - find(u)=u가 속한 집합 찾기, union(u, v)=두 집합을 하나로 합치기- Ex) 2개의 집합- 리프 노드로부터 루트 노드까지 따라 올라가면서 연산을 수행한다. 이 때 각 노드는 자식 노드가 아닌 부모 노드의 주소를 가지기 때문에 링크 구조를 쓰지 않아도 좋다. 또한 부모 노드의 주소가 자신의 주소와 동일하다면 그 노드는 루트 노드라는 것을 뜻한다.- 트리의 모양은 크루스칼의 진행에 따라 얼마든지 바뀔 수 있다.- 여러 트리가 있어도 모두 한 개의 배열로 표현이 가능하다. 이때 배열은 상향식으로 표현하..
최소 비용 신장 트리 (1) Minimum Spanning Tree 최소비용 신장 트리 (MST)- 입력 : n개의 도시, 도시와 도시를 연결하는 도로의 비용- 출력 : 최소의 비용으로 모든 도시들이 서로 연결된 상태- 무방향 가중치 그래프이며 가중치들은 전부 양수라고 가정한다.- (b, c) 엣지대신 (a, h) 엣지를 연결하는 등 문제에 대한 해가 유일하지 않다. - 무방향 가중치 그래프 G = (V, E) / 가중치들은 양수들이다.- 각 엣지 (u, v) ∈ E에 대해 가중치 w(u, v)Ex) 아래와 같은 조건을 만족하는 엣지들의 부분집합인 T ⊆ E를 구해라.1) T에 속한 엣지들에 의해 그래프의 모든 정점들이 서로 연결된다.2) 가중치의 합 $\sum _{ (u,v)∈T }{ w(u,v) } $이 최소가 된다. 트리라고 ..
DAG와 위상 순서 DAG (Directed Acyclic Graph) Directed Acyclic Graph- DAG는 방향 사이클 (directed cycle)이 없는 방향 그래프이다.- 유효한 순서의 그래프가 되려면 그래프 상의 엣지들의 방향이 항상 왼쪽에서 오른쪽의 방향으로 진행되어야 한다.- ex) 작업들의 우선 순위 등 위상 정렬 (topological ordering)- DAG에서 노드들의 순서 $v_1$, $v_2$, ... , $v_n$ (단, 모든 엣지 ($v_i$, $v_j$)에 대해 i < j가 되어야 한다.)- indegree : 노드를 기준으로 들어오는 엣지의 개수, outdegree : 나오는 엣지의 개수, incoming : 들어오는 엣지, outgoing : 나가는 엣지첫 번째 위상 정렬에서..
그래프에서의 DFS 깊이 우선 순회 (DFS)1) 출발점 s에서 시작한다.2) 현재 노드를 visited로 마크한 후 인접 노드들 중 unvisited 노드가 존재한다면 그 노드로 이동한다. (노드는 임의로 결정.)3) 2번 작업을 반복한다.4) 만약 unvisited인 이웃 노드가 존재하지 않는다면 발견할때까지 직전에 방문했었던 노드를 따라 되돌아간다.5) unvisited 노드를 발견하게 된다면 2번 작업을 다시 반복한다.6) 시작 노드 s로 돌아온 후 더 이상 갈 곳이 없다면 순회 작업을 종료한다. - 다른 예시- 슈도 코드 DFS (G, v)visited[v] n : 노드의 개수
그래프에서의 BFS Graph Traversal 그래프 순회- 순회 (traversal)그래프의 모든 노드들을 방문하는 일을 말한다.- 순회를 하는 두 가지 방법BFS (Breadth-First Search, 너비 우선 순회)DFS (Depth-First Search, 깊이 우선 순회) 너비 우선 순회 (BFS)- BFS 알고리즘은 아래와 같은 순서로 노드들을 방문하게 된다.$L_0$ = {s} (s : 출발 노드)$L_1$ = $L_0$의 모든 이웃 노드들$L_2$ = $L_1$의 이웃들 중 $L_0$의 이웃에 속하지 않은 노드들...$L_i$ = $L_{i-1}$의 이웃들 중에 $L_{i-2}$에 속하지 않는 노드들*level order은 BFS의 이진 트리 버전이다. 큐를 이용한 너비 우선 순회1) check the ..
그래프의 개념과 표현 그래프 알고리즘 (Graph Algorithms) 그래프- (무방향) 그래프 G = (V, E)V : 노드(node) 혹은 정점(vertex)을 의미한다.E : 노드 쌍을 연결하는 엣지(edge) 혹은 링크(link)를 의미한다.개체(object)들 간의 이진관계를 표현한다.E(1, 2)는 (2, 1)과도 같은 의미를 내포한다.보통 두 접점을 연결하는 엣지는 하나 혹은 없다고 가정한다. 또한 self edge도 없다고 가정한다.n = | V |, m = | E | 방향 그래프와 가중치 그래프- 방향 그래프(Directed Graph) G = (V, E)엣지 (u, v)는 u로부터 v로의 방향성을 가지고 있다.self edge를 허용한다.- 가중치(weighted) 그래프엣지마다 가중치(weight)가 지..
String.valueOf()와 obj.toString()의 차이 (스크랩) https://medium.com/@pyeonjy97/string-valueof-%EC%99%80-obj-tostring-%EC%9D%98-%EC%B0%A8%EC%9D%B4-96e11460a813
해싱 (Hashing) (3) Hashing 좋은 해쉬 함수의 조건- 현실에서의 키들은 무작위값이 아니다.- 만일 키들의 통계적인 분포에 대해 알고 있다면 이를 활용하여 해쉬 함수를 고안할 수 있겠지만 현실적으로 할 수 없는 방법이다.- 키들이 어떤 특정한(가시적인) 패턴을 가지더라도 해쉬함수 값이 불규칙적이도록 하는 것이 바람직하다. 이는 곧 해쉬합수의 값이 키의 특정 부분에 의해서만 결정되지 않도록 만들어야 한다는 뜻이다. 해쉬 함수를 만드는 방법- Division 기법h(k) = k mod m => 거의 모든 해쉬함수들이 가장 마지막에 수행하는 경향이 있다.Ex) m = 20, k = 91 -> h(k) = 11장점 : 한 번의 mod연산으로 계산하기 때문에 속도가 빠르다.단점 : 어떠한 m값에 대해서는 해쉬 함수의 값이 키 값..

티스토리툴바