Greedy

[dlehdanakf]

개요

• 탐욕 알고리즘은 말 그대로 탐욕적이게(?) 문제를 해결하는 방법이다.
• 우선순위가 높은 것 부터 차례대로 처리한다는 뜻으로 당연히 우선순위가 높은 순으로 정렬이 선행되어야한다.
• 어떤 기준으로 어떻게 정렬할 것인지 선정하는게 알고리즘을 학습하는 것과 더불어 중요한 센스같다.

예제

섬 연결하기

• 문제 바로가기
• 문제를 처음 접근할 때 한 가지 실수를 저질렀다.
• 정렬하고 섬끼리 연결한건 좋았으나, 연결되었는지 확인하는 작업이 빠진거였다.

function solution(n, costs) {
    const nodes = new Array(n).fill(false);
    const sorted = costs.sort((a, b) => a[2] - b[2]);

    let answer = 0;
    for(let i = 0; i < sorted.length; i++) {
        const [ n1, n2, w ] = sorted[i];
        if(nodes[n1] === false || nodes[n2] === false) {
            nodes[n1] = nodes[n2] = true;
            answer += w;

            if(nodes.every(e => e === true)) {
                break;
            }
        }
    }

    return answer;
}

• nodes 배열을 false 에서 true로 바꾸면 연결되었다는 뜻이다.
• 하지만 1,2,3,4 총 네 개의 섬이 있을 때 1 - 2, 3 - 4 끼리만 연결되더라도 배열 속 섬들은 모두 true로 표시된다.
• 다른 방법이 필요하다.

function solution(n, costs) {
    const groups = new Array(n).fill(undefined).map((_, i) => [i]);
    const sorted = costs.sort((a, b) => a[2] - b[2]);

    let answer = 0;
    for(const [ n1, n2, w ] of sorted) {
        const n1_i = groups.findIndex(g => g.includes(n1));
        const n2_i = groups.findIndex(g => g.includes(n2));
        if(n1_i === n2_i) {
            continue;
        }

        groups[n1_i] = [...groups[n1_i], ...groups[n2_i]];
        groups[n2_i].length = 0;
        answer += w;
    }

    return answer;
}

• 처음 코드에서는 연결 여부만 boolean 값으로 표시했던 것과는 달리, 이번에는 각 노드들을 그룹으로 묶어서 관리했다.
• 처음에는 각 한 개의 섬들이 속한 총 N개의 그룹으로 시작한다.
• 다리가 건설되면 Node1 섬과 Node2 섬이 이어진다. 따라서 N2 그룹에 속한 모든 노드들이 N1 으로 이동하고, N2 그룹은 빈 배열로 초기화된다.
• N1 과 N2 가 서로 같은 그룹에 속해있다면 다리를 지을 필요가 없다. 왜냐하면 Greedy 알고리즘에 의해 이미 최소한의 다리길이로 이어져있을 것이기 때문이다.
• 중간에 모든 섬들이 한 그룹에 속해있을 경우 반복문을 break 하는 조건문을 추가할까 고민했지만 어차피 시간복잡도는 O(N) 으로 모든 edge 배열을 한번 돌아야하는 것과 동일하다.

[dlehdanakf]

섬 연결하기 예전코드

• 알고리즘 공부나 JavaScript 언어에 본격적으로 뛰어들기 전 문제를 풀기위해 애썼던 코드가 컴퓨터에 남아있길래 기록해둔다.
• 아래 코드도 프로그래머스에서 채점했을 때 모두 통과하는 코드...지만 괴랄하기 짝이없다.

function build_bridge(connected_group, from, to) {
    /* if is duplicated */
    for(const group of connected_group) {
        if(group.includes(from) && group.includes(to)) {
            return false;
        }
    }

    let _from_group_index = null, _to_group_index = null;
    for(const i in connected_group) {
        if(connected_group[i].includes(from)) { _from_group_index = i; }
        if(connected_group[i].includes(to)) { _to_group_index = i; }
    }

    if(_from_group_index === null && _to_group_index === null) {
        /* if is new group */
        connected_group.push([ from, to ]);
    } else if(_from_group_index !== null && _to_group_index !== null) {
        /* if is connecting group */
        connected_group[_from_group_index] = connected_group[_from_group_index].concat(connected_group[_to_group_index]);
        connected_group.splice(_to_group_index, 1);
    } else if(_from_group_index !== null) {
        /* if is `from` connected */
        connected_group[_from_group_index].push(to);
    } else {
        /* if is `to` connected */
        connected_group[_to_group_index].push(from);
    }

    return true;
}
function solution(n, costs) {
    const c = costs
        .map((v, i) => {
            const [ from, to, cost ] = v;
            return { from, to, cost };
        })
        .sort((a, b) => { return a.cost < b.cost ? -1 : a.cost > b.cost ? 1 : 0; });

    let answer = 0;
    const connected_group = [];
    while(c.length > 0) {
        const [{ from, to, cost }] = c.splice(0, 1);
        const result = build_bridge(connected_group, from, to);
        if(result === true) {
            answer += cost;
        }

        if(connected_group.length > 0 && connected_group[0].length === n) {
            break;
        }
    }

    return answer;
}