본문 바로가기
카테고리 없음

그리디 알고리즘 (Greedy Algorithms) 요약

by daily_coming 2024. 9. 12.
반응형

 

그리디 알고리즘 (Greedy Algorithms)

그리디 알고리즘은 매 순간 최선의 선택을 하는 방식으로, 전체 문제를 해결하는 방법입니다. 즉, 각 단계에서 가장 이득이 되는 선택을 함으로써 문제를 해결하며, 이를 통해 전체 문제에 대한 최적의 해답을 찾으려고 합니다. 그리디 알고리즘은 항상 최적의 해를 보장하지는 않지만, 여러 문제에서 매우 효율적으로 작동할 수 있습니다. 그리디 알고리즘을 사용하는 대표적인 문제로는 최소 신장 트리(MST)와 다익스트라 알고리즘이 있습니다.

 

 

 

 

1. 최소 신장 트리 (Minimum Spanning Tree)

최소 신장 트리(MST)는 그래프 내의 모든 정점을 연결하면서 간선들의 가중치 합이 최소가 되는 트리를 찾는 문제입니다. 최소 신장 트리 알고리즘은 주로 연결 그래프에서 사용되며, 대표적인 알고리즘으로는 크루스칼 알고리즘과 프림 알고리즘이 있습니다.

 

크루스칼 알고리즘 (Kruskal's Algorithm)

크루스칼 알고리즘은 간선 중심의 알고리즘으로, 그래프 내의 간선을 가중치 순으로 정렬한 후, 최소 가중치의 간선부터 순차적으로 선택하여 최소 신장 트리를 구성하는 방식입니다. 간선 선택 시 사이클이 발생하지 않도록 유의해야 합니다.

 

크루스칼 알고리즘의 단계

  1. 모든 간선을 가중치에 따라 오름차순으로 정렬합니다.
  2. 가장 작은 가중치의 간선부터 선택하여, 두 정점이 연결된 트리에 포함되지 않은 경우 그 간선을 추가합니다.
  3. 사이클이 생기지 않도록 간선 선택을 주의하면서, 모든 정점을 포함할 때까지 반복합니다.

 

크루스칼 알고리즘 예제 코드

// 크루스칼 알고리즘 (JavaScript) - Union-Find 사용
function find(parent, i) {
    if (parent[i] === i) {
        return i;
    }
    return find(parent, parent[i]);
}

function union(parent, rank, x, y) {
    let rootX = find(parent, x);
    let rootY = find(parent, y);

    if (rootX !== rootY) {
        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

function kruskal(graph) {
    let result = [];
    let i = 0;
    let e = 0;
    let edges = graph.edges.sort((a, b) => a[2] - b[2]);

    let parent = [];
    let rank = [];

    for (let node = 0; node < graph.V; node++) {
        parent[node] = node;
        rank[node] = 0;
    }

    while (e < graph.V - 1) {
        let [u, v, w] = edges[i++];
        let x = find(parent, u);
        let y = find(parent, v);

        if (x !== y) {
            result.push([u, v, w]);
            union(parent, rank, x, y);
            e++;
        }
    }

    return result;
}

let graph = {
    V: 4,
    edges: [
        [0, 1, 10],
        [0, 2, 6],
        [0, 3, 5],
        [1, 3, 15],
        [2, 3, 4]
    ]
};

console.log(kruskal(graph));
// 출력: [[2, 3, 4], [0, 3, 5], [0, 1, 10]]

 

프림 알고리즘 (Prim's Algorithm)

프림 알고리즘은 정점 중심의 알고리즘으로, 하나의 정점에서 시작하여 가장 작은 가중치의 간선을 선택하고, 연결된 다른 정점들을 차례대로 트리에 추가하여 최소 신장 트리를 구성하는 방식입니다.

 

프림 알고리즘의 단계

  1. 임의의 정점을 시작 정점으로 선택합니다.
  2. 정점에 연결된 간선 중에서 가중치가 가장 작은 간선을 선택하여 트리에 추가합니다.
  3. 이미 추가된 정점과 연결된 간선 중 가장 작은 가중치의 간선을 선택하여 트리를 확장합니다.
  4. 모든 정점을 포함할 때까지 반복합니다.

 

프림 알고리즘 예제 코드

// 프림 알고리즘 (JavaScript)
function prim(graph) {
    let key = Array(graph.V).fill(Infinity);
    let parent = Array(graph.V).fill(-1);
    let mstSet = Array(graph.V).fill(false);

    key[0] = 0;

    for (let count = 0; count < graph.V - 1; count++) {
        let u = minKey(key, mstSet);
        mstSet[u] = true;

        for (let v = 0; v < graph.V; v++) {
            if (graph.adj[u][v] && mstSet[v] === false && graph.adj[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph.adj[u][v];
            }
        }
    }

    return parent;
}

function minKey(key, mstSet) {
    let min = Infinity;
    let minIndex = -1;

    for (let v = 0; v < key.length; v++) {
        if (mstSet[v] === false && key[v] < min) {
            min = key[v];
            minIndex = v;
        }
    }

    return minIndex;
}

let graph = {
    V: 5,
    adj: [
        [0, 2, 0, 6, 0],
        [2, 0, 3, 8, 5],
        [0, 3, 0, 0, 7],
        [6, 8, 0, 0, 9],
        [0, 5, 7, 9, 0]
    ]
};

console.log(prim(graph));
// 출력: [ -1, 0, 1, 0, 1 ]

 

 

 

 

 

2. 다익스트라 알고리즘 (Dijkstra's Algorithm)

다익스트라 알고리즘은 가중치가 있는 그래프에서 특정 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 다익스트라 알고리즘은 그리디 알고리즘을 사용하여 각 단계에서 가장 작은 비용의 경로를 선택하는 방식으로 동작합니다.

 

 

다익스트라 알고리즘의 단계

  1. 시작 정점을 설정하고, 모든 정점까지의 거리를 무한대로 초기화합니다. 시작 정점의 거리는 0으로 설정합니다.
  2. 가장 작은 거리를 가진 정점을 선택하고, 그 정점을 방문 처리합니다.
  3. 선택된 정점과 연결된 다른 정점들의 거리를 업데이트합니다.
  4. 모든 정점을 방문할 때까지 반복합니다.

 

 

다익스트라 알고리즘 예제 코드

// 다익스트라 알고리즘 (JavaScript)
function dijkstra(graph, src) {
    let dist = Array(graph.V).fill(Infinity);
    let sptSet = Array(graph.V).fill(false);
    dist[src] = 0;

    for (let count = 0; count < graph.V - 1; count++) {
        let u = minDistance(dist, sptSet);
        sptSet[u] = true;

        for (let v = 0; v < graph.V; v++) {
            if (!sptSet[v] && graph.adj[u][v] && dist[u] !== Infinity && dist[u] + graph.adj[u][v] < dist[v]) {
                dist[v] = dist[u] + graph.adj[u][v];
            }
        }
    }

    return dist;
}

function minDistance(dist, sptSet) {
    let min = Infinity;
    let minIndex = -1;

    for (let v = 0; v < dist.length; v++) {
        if (!sptSet[v] && dist[v] < min) {
            min = dist[v];
            minIndex = v;
        }
    }

    return minIndex;
}

let graph = {
    V: 9,
    adj: [
        [0, 4, 0, 0, 0, 0, 0, 8, 0],
        [4, 0, 8, 0, 0, 0, 0, 11, 0],
        [0, 8, 0, 7, 0, 4, 0, 0, 2],
        [0, 0, 7, 0, 9, 14, 0, 0, 0],
        [0, 0, 0, 9, 0, 10, 0, 0, 0],
        [0, 0, 4, 14, 10, 0, 2, 0, 0],
        [0, 0, 0, 0, 0, 2, 0, 1, 6],
        [8, 11, 0, 0, 0, 0, 1, 0, 7],
        [0, 0, 2, 0, 0, 0, 6, 7, 0]
    ]
};

console.log(dijkstra(graph, 0));
// 출력: [ 0, 4, 12, 19, 21, 11, 9, 8, 14 ]

 

 

 

 

결론

그리디 알고리즘은 매 순간 최선의 선택을 통해 문제를 해결하는 방식입니다. 최소 신장 트리(MST) 문제에서 크루스칼 알고리즘과 프림 알고리즘, 그리고 최단 경로 문제에서 다익스트라 알고리즘은 그리디 알고리즘의 대표적인 예시입니다. 각 알고리즘은 효율적인 해결책을 제공하며, 문제의 특성에 맞게 적절한 알고리즘을 선택해야 합니다.

반응형

티스토리툴바