loltochess

다익스트라 알고리즘은 방향 그래프에서 최단 거리를 구하는 알고리즘이다.(음수의 가중치는 허용하지 않는다.)보통 시작점에서 다른 점들 간의 거리를 구할 때 사용된다.(시작점에 대해서만 알 수 있음.)만약 노드가 1, 2, 3, 4, 5가 있고 1에서 시작을 하면 2, 3, 4 ,5까지의 최단거리를 구할 수 있다는 의미이다.(2에서 4까지의 최단거리나 2에서 5까지의 최단거리를 구할 수 없음.)만약 모든 노드에 대해 최단거리를 알고 싶다면 플로이드-워셜 알고리즘을 사용하면 된다.(단 이 알고리즘은 시작복잡도가 O(N^3)이기 때문에 입력값이 크면 사용하지 못한다. 다익스트라 알고리즘에서는 우선순위 큐라는 자료구조를 사용한다.지금까지 계산된 거리 중 가장 가까운 거리에 대해 탐색하기 위해 우선순위 큐를 사용한..

위상정렬이란 순서가 정해져 있는 작업을 차례로 수행하여야 할 때 순서를 결정해 주는 알고리즘이다.백준의 2252번 문제를 보자두 학생의 키를 비교하는 방법으로 줄을 세우는 문제이다.그냥 A가 B보다 크다라는 것만 주어지고 키를 작은 순서대로 출력하는 문제이다.A노드->B노드 예제를 그림으로 보면이런식으로 나온다.1이 3보다 키가 작고2도 3보다 키가 작다.그러면 답은 1,2,3 또는 2,1,3이 될 수 있다. 왜냐?? 1과 2에 대한 비교를 하지 않았기 때문에 누가 더 크고 작은 지를 구분할 수 없기 때문이다.(문제에서도 답이 여러 가지인 경우 아무거나 출력한다라고 명시해 놓았다.) 그래서 위상정렬이 무엇이냐!!방향이 있는 그래프여야 하고 그래프는 사이클이 존재하지 않는 그래프에서 순서를 찾는 알고리즘이..

최소 신장 트리란 그래프에서 모든 정점을 포함하면서 가중치의 합이 최소가 되는 트리를 말한다.최소 신장 트리를 구하기 위해서는 프림의 알고리즘을 사용하던지 크루스칼의 알고리즘을 사용하면 된다.일반적으로 프림의 알고리즘이 크루스칼의 알고리즘보다 구현하기 쉬워서 프림의 알고리즘을 많이 사용한다. *프림의 알고리즘*은 한 노드를 딱 정해서 그 노드에서부터 이웃한 노드를 우선순위 큐에 넣고 가장 가까운 노드로 나아가는 방법이다.(나아간 후에는 그 나아간 노드에 있는 이웃한 노드 또한 우선순위 큐에 넣어주는 작업을 수행해야 함. visited배열을 사용해서 이미 방문된 노드는 다시 방문하지 않음.)  *크루스칼의 알고리즘*은 간선을 우선순위 큐에 모두 넣어놓고 짧은 간선부터 하나씩 빼서 MST를 구성하는데 만약 ..

Union은 노드를 연결해서 하나의 집합으로 묶는 작업이다.(Index가 작은게 대표 노드가 된다.)Find는 자신이 속한 집합의 대표 노드를 찾는 연산이다. Find(2), Find(3)을 하면 대표노드 1이 return된다.Find(5), Find(6)을 하면 대표노드 4가 return된다. 만약 Union(3,6)을 하게 되면 3의 대표 노드 *1*과 6의 대표노드 *4*가 이어지게 된다. 4,5,6의 대표 노드는 이제 *1*이다. *경로압축*재귀함수를 이용해서 대표노드에 도달하면 함수를 빠져나오면서 거치는 모든 노드의 값을 대표 노드 값으로 변경한다.경로압축을 통해 Find()연산의 속도를 O(1)로 만들 수 있다. 유니온 파인드는 언제 사용될까??-MST(크루스칼 알고리즘)-무방향 그래프의 사이..