알고리즘 메모 정리

• 그리디

  • 기능
    • 전역 최적을 찾기 위해 지역적으로 최적인 선택을 목표
    • 그 순간에 최고인 것처럼 보이는 결정
  • 특성
    • 로컬 최적성 : 모든 단계에서 가장 좋아 보이는 옵션을 선택
    • 역추적 없음 : 일단 선택하면 다시 고려하지 않음
    • 효율성 : 구현이 간단하고 실행 속도가 빠른 경우가 많음
    • 항상 최적은 아님 : 모든 경우에 최상의 전체 솔루션을 보장하지는 않음
  • 사용시기
    • 문제에 최적의 하위 구조가 있을 때 사용
    • 활동 선택, 동전 변경(특정 단위의 경우) 및 분수 배낭과 같은 문제에 적용 가능

function coinChange(coins, amount) {
    coins.sort((a, b) => b - a); // 내림차순
    let count = 0;

    for (let coin of coins) {
        count += Math.floor(amount / coin); // 최대 금액으로 동전 개수 추가
        amount %= coin; // 남은 금액 업데이트
        if (amount === 0) break;
    }

    return amount === 0 ? count : -1; // Check if change was possible
}

최소 스패닝 트리 ( MST )

가능한 최소 총 가장자리 가중치를 가지며 순환이 없는
모든 정점을 포함하는 그래프의 하위 트리

• 프림

  • 기능
    • 함수 : 단일 정점에서 시작하여 트리를 새 정점에 연결하는 가장 작은 가장자리를 추가하여 MST를 구축
  • 특징
    • 다음 최소 에지를 선택하기 위해 우선순위 큐를 활용
    • 에지 추가 방식으로 인해 밀도가 높은 그래프에 적합
  • 사용시기
    • 모서리가 꼭짓점보다 많은 조밀한 그래프에 효과적

// 그래프의 인접 행렬 표현이라고 가정
function primsAlgorithm(graph) {
    const numVertices = graph.length;
    const selected = new Array(numVertices).fill(false);
    const keys = new Array(numVertices).fill(Infinity);
    keys[0] = 0; // 첫 번째 정점부터 시작

    for (let i = 0; i < numVertices - 1; i++) {
        let minKey = Infinity, u = -1;

        // 최소 키 값을 갖는 정점 찾기
        for (let v = 0; v < numVertices; v++) {
            if (!selected[v] && keys[v] < minKey) {
                minKey = keys[v];
                u = v;
            }
        }

        selected[u] = true;

        // 인접한 정점의 키 값 업데이트
        for (let v = 0; v < numVertices; v++) {
            if (graph[u][v] && !selected[v] && graph[u][v] < keys[v]) {
                keys[v] = graph[u][v];
            }
        }
    }

    return keys.reduce((a, b) => a + b, 0); // MST의 총 중량
}

• 크루스칼

  • 기능
    • 모든 모서리를 가중치별로 정렬하고 이를 하나씩 추가하여 순환을 형성하는 모서리를 건너뛰어 MST를 구축
  • 특징
    • 순환을 감지하고 방지하기 위해 disjoint-set(union-find) 데이터 구조를 사용
    • 정점 수가 가장자리보다 많은 희소 그래프에 적합
  • 사용시기
    • 에지 중심 접근 방식으로 인해 희소 그래프에 효과적
  • find
    • 세트를 고유하게 식별하는 루트에 도달할 때까지 상위 노드
    • 특정 요소가 어느 집합(또는 하위 집합)에 속하는지 식별하는 데 사용
    • 일반적으로 두 요소가 동일한 세트에 있는지 확인하는 데 사용
    • 그래프에서 주기를 감지하는 데 도움
  • union
    • 두 개의 하위 집합을 단일 하위 집합으로 병합
    • 동일한 세트에 아직 없는 두 요소를 결합해야 할 때 사용
    • 순환을 형성하지 않고 그래프에 간선을 추가하는 경우

// 'edges'가 [u, v, Weight] 형식의 모서리 배열이라고 가정
function kruskalsAlgorithm(edges, numVertices) {
    edges.sort((a, b) => a[2] - b[2]); // 가중치를 기준으로 가장자리 정렬
    const parent = Array.from({ length: numVertices }, (_, i) => i);

    function find(i) {
        if (parent[i] !== i) parent[i] = find(parent[i]);
        return parent[i];
    }

    function union(i, j) {
        const setI = find(i);
        const setJ = find(j);
        if (setI !== setJ) parent[setI] = setJ;
    }

    let mstWeight = 0;
    for (let [u, v, weight] of edges) {
        if (find(u) !== find(v)) {
            union(u, v);
            mstWeight += weight;
        }
    }

    return mstWeight; // MST의 총 중량
}