알고리즘 - Dynamic Programming(동적 계획법)

1. 개요

DP, 즉 다이나믹 프로그래밍은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것이다.
특정한 알고리즘이 아닌 하나의 문제해결 방법으로 볼 수 있다,

간단하게 설명하자면 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하는 기법

2. DP의 사용 조건

• 최적 부분 구조 (Optimal Substructure)
  - 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우의 의미
• 중복되는 부분 문제 (Overlapping Subproblem)
  - 동일한 작은 문제를 반복적으로 해결해야 하는 경우

※ 일반적인 프로그래밍 분야에서 동적(Dynamic)의 의미는?

• 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다.
• 반면에 DP에서 Dynamic은 별다른 의미가 없다. 알고리즘을 만든 사람도 멋있다는 이유로 Dynamic이란 단어를 프로그래밍에 결합했다.

3. 다익스트라(Dijkstra) 알고리즘

다익스트라(Dijkstra) 알고리즘은 DP를 활용한 대표적인 최단 경로 탐색 알고리즘이다. 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘.

사진은 프로그래머스 알고리즘 문제 - 배달 에 있는 예시이다.

알고리즘 과정

1. 출발 노드를 설정한다.

2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.

4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.

5. 위 과정에서 3번 ~ 4번을 반복한다.

   예제문제 : 배달 - 프로그래머스

   연습문제 풀이 과정

 function solution(N, road, K) {
    const arr = Array(N + 1).fill(Number.MAX_SAFE_INTEGER);
    const lines = Array(N + 1).fill().map((_)=>[])
    let answer = 0;

    road.forEach(([v1,v2,c]) => {
    // 연결되어 있는 경로를 모두 lines배열에 저장한다.

        lines[v1].push({ to: v2, cost: c });
        lines[v2].push({ to: v1, cost: c });
    });
    
    let queue = [{ to: 1, cost: 0 }];
    arr[1] = 0;
    
    while(queue.length) {
        let {to} = queue.pop(); 

        lines[to].forEach((next)=> {
            if(arr[next.to] > arr[to] + next.cost) {
                // 기존 경로의 값보다 우회하는 값이 더 작으면 해당 값 저장
                arr[next.to] = arr[to] + next.cost;
                queue.push(next)
            }
        })
    }
    
    answer = arr.filter((item) => item <= K).length

    return answer;
}