Portfolio

💡

알고리즘 : 문제를 해결하기 위해 정해진 절차를 공식화한 것

면접 질문 💜

각 알고리즘 사용예시

kruskal 알고리즘 구현방법

kruskal, prim 구현 조건

추가할 것

시간/공간 복잡도 신뢰도있는거로 추가 ***

언제 어떤 걸 쓸지 - 크루스칼 VS 프림 프림은 정점 위주의 알고리즘, 크루스칼은 간선 위주의 알고리즘 프림은 시작점을 정하고, 시작점에서 가까운 정점을 선택하면서 트리르 구성 하므로 그 과정에서 사이클을 이루지 않지만 크루스칼은 시작점을 따로 정하지 않고 최소 비용의 간선을 차례로 대입 하면서 트리를 구성하기 때문에 사이클이 이루어지는 항상 확인 해야한다. 프림의 경우 최소 거리의 정점을 찾는 부분에서 자료구조의 성능에 영향을 받는다. 크루스칼은 간선을 기준으로 정렬하는 과정이 오래 걸린다. 간선의 개수가 작은 경우에는 크루스칼, 간선의 개수가 많은 경우에는 프림.

최소비용신장 알고리즘

최소 비용으로 모든 노드를 연결하는 방법 ⇒ 모든 노드를 포함한 트리

필요한 순간

고속도로 건설업자, 서울, 광주, 거제, 부산 4개의 도시를 모두 연결해야하는데..최소비용으로 연결하고 싶을 때

배관: 파이프를 모두 연결할 때, 최소비용으로 작업 (총 길이)

네트워크: 라우터 경로 설정, 최적의 라우팅 경로 선택 (전송 시간, 최단거리)

유통망..

물론, 최소비용은 상황에 따라 뭘 기준으로 할지 다를 수 있음 → 중요한 건 최소비용

구현 방법

조건 : 무방향(양방향), 가중치가 있는 그래프

1) Kruskal : V개의 트리에서 시작해, 하나의 트리로 합침

동작원리

간선, 비용을 기준으로 오름차순 (최소비용 ~ 최대비용)
간선을 하나씩 돌면서, 같은 집합인지 체크

같은 집합이라면, 이미 포함되었기에 넘어감
아니라면, 같은 집합으로 포함함 (union 연산)

구현코드

인접 vertex 정보가 [v1, v2, weight] 로 들어온다고 가정


const adjNode = [
    [0, 1, 1],
    [0, 2, 2],
    [1, 2, 5],
    [1, 3, 1],
    [2, 3, 8],
];

const rootSet = [];

// 최소비용(weight)으로 정렬 -> O(NlogN)
adjNode.sort((a, b) => a[2] - b[2]);

// 집합 초기화: 각 node 독립적인 집합에 속하도록
const makeSet = (n) => {
    for (let i = 0; i < n; i++) {
        rootSet.push(i);
    }
};

// 루트노드 찾기 **
// rootSet [0,0,2,3]: index에 해당하는 루트집합 정보를 담고있음 
// 1의 루트노드를 찾을 경우, 0이지만, 0의 루트집합이 다를 수도 있기에 재귀로 탐색함 
const getRoot = (rootSet, targetNode) => {
    if (rootSet[targetNode] === targetNode) {
        return targetNode;
    } else {
        return getRoot(rootSet, rootSet[targetNode]);
    }
};

// 집합 합치기: UNION, 루트노드 번호가 작은쪽으로 합침
const unionSet = (rootSet, node1, node2) => {
    const root1 = getRoot(rootSet, node1);
    const root2 = getRoot(rootSet, node2);

    if (root1 < root2) { 
        return rootSet[root2] = root1;
    } else {
        return rootSet[root1] = root2;
    }
};

// 같은집합에 속하는지 체크
const isSameSet = (rootSet, node1, node2) => {
    const root1 = getRoot(rootSet, node1);
    const root2 = getRoot(rootSet, node2);
    return root1 === root2;
};

// 크루스칼
let totalCost = 0;
const n = adjNode.length; 
const kruskalEdge = [];

makeSet(n); 
for (const adj of adjNode) {
    const [node1, node2, weight] = adj;
    if (!isSameSet(rootSet, node1, node2)) {
        // 최소비용
        totalCost += weight;
        unionSet(rootSet, node1, node2);

        // edge 정보
        kruskalEdge.push(adj);
    }
}

시간/ 공간 복잡도

시간복잡도: O(ElogE) - edge 정렬
공간복잡도: O(V) - 각 vertex만큼 집합 → 하나로 합침

참고자료

추가 자료

크루스칼 알고리즘의 경우, 전체 간선을 정렬하는 시간이 가장 오래 걸린다.

간선을 정렬하는 과정의 시간 복잡도는 O(ElogE)을 갖는데 이는 O(ElogV)라고도 표현가능합니다.

그 이유는 간선의 개수는 정점의 제곱보다 작거나 같음을 언제나 보장합니다. (E ≤ V^2)

이 식을 이용해 정리하면 O(ElogV^2)가 되고 결국 O(ElogV)로도 표현 가능해지는 것입니다.

E ≤ V^2가 항상 보장되는 이유는, 완전 그래프의 경우 사이클이 존재함에도 불구하고 간선의 개수는 항상 V(V-1)/2로 자명하기 때문입니다. (크루스칼 알고리즘의 대상이 되는 그래프의 경우 사이클이 존재하지 않아야 합니다.)

즉, E ≤ V^2이 항상 참이게 되므로 O(ElogV)로 표현가능하지만 엄연히 말하면 O(ElogE) 표현이 더 정확하다고 할 수 있습니다.

2) Prim : 다익스트라 활용

현재 연결된 트리에 인접한 간선 중, 가장 작은 것을 추가

동작원리

현재 노드에서 인접한 노드 모두, 우선순위큐에 넣음
최소비용 간선 꺼냄

방문한 곳은 넘어감
미방문했다면, 채택 → 위의 반복

구현코드

인접 vertex 정보 [v1, v2, weight] 로 들어온다 가정


// V: vertex 개수 

const visit = Array(+V + 1).fill(0);
const list = [];

for (const [v1, v2, e] of graph) {
	list[v1] ? list[v1].push([e, v2]) : (list[v1] = [[e, v2]]);
	list[v2] ? list[v2].push([e, v1]) : (list[v2] = [[e, v1]]);
}

// 시작노드: weight, vertex_number
const heap = [[0, 1]];

while (heap.length) {
	const [e, node] = heap.sort((a, b) => b[0] - a[0]).pop();

	if (!visit[node]) {
		visit[node] = 1;
		total += Number(e);

		list[node].forEach(([e, nextV]) => {
			if (!visit[nextV]) {
				heap.push([e, nextV]);
			}
		});
	}
}

console.log(total);

시간/ 공간 복잡도

시간복잡도: O(ElogE) - edge 방문(E) * heap sort(NlogN)
공간복잡도: O(E) ?? - heap 크기(= Edge 개수랑 비례하니까..?)

MST(minimum spanning tree)