[코테] 그래프 알고리즘 & 동적 계획법 예제

이름만 들어도 어려워보이는 그래프 알고리즘과 동적 계획법니다.

그래프 알고리즘은 그래프를 탐색하고 원하는 정보를 찾는 데 사용된다. 예를 들어, 소셜 네트워크에서 친구 관계를 탐색하거나, 지도 애플리케이션에서 최단 경로를 찾는 데 활용될 수 있다.

너비 우선 탐색(BFS):
시작 정점에서부터 인접한 정점을 먼저 모두 방문한 후, 그 정점들의 인접한 정점들을 차례대로 방문하는 방식. 큐(queue) 자료구조를 사용하여 구현.

깊이 우선 탐색(DFS):
시작 정점에서부터 한 정점의 모든 인접한 정점을 방문한 후, 방문한 정점을 시작으로 다시 깊이 우선 탐색을 진행. 스택(stack) 자료구조나 재귀 함수를 사용하여 구현

 

// 너비 우선 탐색(BFS) 함수
function bfs(graph, start) {
    const visited = [];
    const queue = [start];

    while (queue.length > 0) {
        const vertex = queue.shift();
        if (!visited.includes(vertex)) {
            visited.push(vertex);
            queue.push(...graph[vertex]);
        }
    }

    return visited;
}

// 깊이 우선 탐색(DFS) 함수
function dfs(graph, start, visited = []) {
    visited.push(start);
    graph[start].forEach(neighbor => {
        if (!visited.includes(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    });
    return visited;
}

 

 

동적 계획법(Dynamic Programming)은 큰 문제를 작은 하위 문제로 나누어 해결하는 알고리즘 기법이다.

중복 부분 문제 (Overlapping Subproblems): 큰 문제를 해결하는 과정에서 중복되는 하위 문제들이 발생
최적 부분 구조 (Optimal Substructure): 큰 문제를 작은 문제의 최적해를 토대로 결정될 수 있다.

주로 최적화 문제나 최단 경로 문제를 해결하는 데에 사용

function dijkstra(graph, start) {
    const distances = {}; // 각 정점까지의 최단 거리를 저장할 객체
    const visited = {}; // 방문한 정점을 표시할 객체
    for (let vertex in graph) {
        distances[vertex] = Infinity; // 시작 정점으로부터의 거리를 무한대로 초기화
        visited[vertex] = false; // 모든 정점을 방문하지 않은 상태로 표시
    }
    distances[start] = 0; // 시작 정점까지의 거리는 0

    while (true) {
        let closestVertex = null;
        let shortestDistance = Infinity;
        // 방문하지 않은 정점 중에서 시작 정점으로부터 가장 가까운 정점을 찾음
        for (let vertex in distances) {
            if (!visited[vertex] && distances[vertex] < shortestDistance) {
                closestVertex = vertex;
                shortestDistance = distances[vertex];
            }
        }
        if (!closestVertex) break; // 모든 정점을 방문한 경우 반복문 종료

        visited[closestVertex] = true; // 가장 가까운 정점을 방문 처리

        // 가장 가까운 정점의 이웃 정점들의 최단 거리를 업데이트
        for (let neighbor in graph[closestVertex]) {
            const distance = shortestDistance + graph[closestVertex][neighbor];
            if (distance < distances[neighbor]) {
                distances[neighbor] = distance;
            }
        }
    }

    return distances;
}