bdfgdfg

크루스칼과 같은 최소 스패닝 트리를 구하는 알고리즘. 크루스칼 알고리즘은 탐욕(greedy)적인 방법으로 작은 가중치의 간선만을 선택해서 사이클이 발생하지 않는다는 가정하에 간선을 붙여줬다. 프림 알고리즘의 특징은 하나의 시작점(어느 정점이든 상관x)으로 구성된 트리에 간선을 하나씩 수집하며 진행한다. 네모가 쳐진 정점을 기준으로 15와 35라는 간선을 선택할 수 있는데. 당연히 15가 더 적은 가중치를 가진 간선이니 15를 선택한다. 이제 그 다음 정점을 확인해보면 5,10이라는 가중치를 가진 간선들. 더 작은 5 간선을 선택하고. 10이라는 간선을 확인했을때. 시작정점을 기준으로 15 + 10 = 25이니. 35보다 작다는것을 알 수 있음. 그러므로 35는 선택이 불필요. 이런식으로 나머지 간선도 선..

Union-find : 합치기-찾기. 이 알고리즘은 예로들어 어떤 배열에서. 어떤 인덱스에 접근해보았더니 그 원소가 가진 값이 이 인덱스의 부모. 즉 나와 연결고리를 찾는 과정. -> 최고 부모가 누구인지(Find). 혹은 내가 원한다면 다른 원소와의 연결고리를 합치는(Union) 알고리즘. 이 구조를 단순히 배열만을 이용한다면 찾는과정은 바로 찾을 수 있겠지만, 합치기 과정에서 모든 배열을 순회하면서. 합쳐야할 원소를 찾아야 한다. 그렇기에 트리 구조를 통한 Union-Find의 표현을 본다. 트리 구조를 통한 Union-Find의 첫번째 특징은. 먼저 Union-Find를 하기전에 모든 노드가 자기자신을 가리킨다. 즉. 처음에는 자기자신이 연결된 노드간의 꼭대기. 루트노드라고 보는것. class Un..

최소 비용 신장 트리 트리는 그래프의 한 유형. 다음 그래프를 보고 정점 B에서 정점 D에 이르는 모든 경로를 찾아서 열거해본다. 이렇게 두 개의 정점을 잇는 간선을 순서대로 나열한 것을 가리켜 '경로'라 한다. 그리고 위의 네 경로와 같이 동일한 간선을 중복하여 포함하지 않는 경로를 가리켜 '단순 경로'라 한다. 단순 경로가 아닌 예를 들어보면 B-A-C-B-A-D -> B와 A를 잇는 간선이 두 번 포함됨. 그렇다면 A-B-C-A는 단순 경로가 일까? 단순 경로가 맞다. A정점이 두 번 등장하지만 중복된 간선이 포함되지 않기 때문이다. 이렇게 단순 경로이면서 시작과 끝이 같은 경로를 가리켜 '사이클'이라 한다. 간단히 말해 사이클은 어느 정점에서 다른 경로를 통해 다시 돌아올 수 있다면 사이클이라 한..

깊이 우선 탐색(Depth First Search : DFS) 이름에서 알 수 있듯이 깊이를 우선하여 탐색한다. 즉 탐색의 진행 방향에 있어서 순서상으로 만나는 정점을 대상으로 바로 탐색을 진행한다. 그러다가 더이상 탐색을 진행할 곳이 없다면 이때까지 방문했던 녀석들을 하나씩 돌아가면서 다른 정점을 방문할 수 있는지 체크한다. 우선 DFS의 과정을 그림으로 살펴본다. 위 그림에서도 보이듯이 탐색의 진행이 한 길을 깊이 파고든다. (누구를 먼저 선택할 것인지에 대한 것은 구현하는 이가 결정) 그러다가 그림 3에서 길이 막힌다면 역으로 돌아가면서 수정->정희->민석까지 돌아가다가 아직 방문안한 지율을 방문하고 다시 시작점으로 돌아간다. (시작점으로 돌아가는 이유는 방문안한 녀석들을 돌아오면서 다시 다 체크하..