[카테고리:] 자바 코딩테스트 강좌

코딩테스트는 소프트웨어 엔지니어링 분야에서 점점 더 중요해지는 요소 중 하나입니다. 이 글에서는 자바를 활용하여 복잡한 알고리즘 문제를 해결하는 데 필요한 기술을 익히는 방법에 대해 설명하고, ‘블루레이 만들기’라는 주제로 한 문제를 다루어 보겠습니다.

문제 설명

요구사항: 주어진 영화 리스트와 각 영화의 재생 시간을 바탕으로 블루레이의 용량을 고려하여 최소한의 블루레이 개수를 사용하여 모든 영화를 재생할 수 있는 방법을 찾으세요. 블루레이 하나에 담을 수 있는 최대 용량은 지정되어 있습니다.

입력:

• maxSize: 각 블루레이의 최대 용량 (정수)
• movies: 영화의 재생 시간 리스트 (정수 배열)

출력:

• 모든 영화를 재생하기 위해 필요한 최소 블루레이 개수 (정수)

예시

maxSize: 10
movies: [1, 2, 3, 4, 5, 6]
출력: 3

문제 접근 방법

이 문제를 해결하기 위해서는 다음의 단계로 접근할 수 있습니다:

1. 블루레이 하나의 용량을 초과하지 않도록, 가능한 많은 영화를 추가하는 방법을 고려합니다.
2. 영화 리스트를 정렬하여 짧은 영화부터 긴 영화 순으로 재생하도록 합니다.
3. 각 블루레이의 재생 시간을 계산하여 최대 용량을 초과하면 새로운 블루레이가 필요하도록 합니다.
4. 필요한 블루레이 개수를 카운트합니다.

자바 코드 구현

import java.util.Arrays;

public class BluRayMaker {
    
    public static int minBluRays(int maxSize, int[] movies) {
        Arrays.sort(movies); // 영화를 정렬합니다.
        int bluRayCount = 0;
        int currentBluRaySize = 0;

        for (int i = movies.length - 1; i >= 0; i--) {
            // 현재 블루레이에 영화를 추가합니다.
            if (currentBluRaySize + movies[i] <= maxSize) {
                currentBluRaySize += movies[i];
            } else {
                // 블루레이의 용량을 초과하는 경우 새로운 블루레이를 사용합니다.
                bluRayCount++;
                currentBluRaySize = movies[i]; // 현재 영화로 블루레이를 시작합니다.
            }
        }

        // 남아 있는 블루레이가 있으면 카운트를 추가합니다.
        if (currentBluRaySize > 0) {
            bluRayCount++;
        }

        return bluRayCount;
    }

    public static void main(String[] args) {
        int maxSize = 10;
        int[] movies = {1, 2, 3, 4, 5, 6};
        System.out.println("최소 필요한 블루레이 개수: " + minBluRays(maxSize, movies));
    }
}

코드 설명

위의 코드에서는 블루레이를 만들기 위한 클래스를 정의하고, 최적의 영화 선택 방법을 구현하였습니다. 코드는 다음과 같은 방식으로 작동합니다:

1. 영화 리스트를 정렬하여 가장 긴 영화부터 순서대로 처리합니다.
2. 현재 블루레이의 재생 시간이 최대 용량을 넘지 않도록 영화를 추가합니다.
3. 용량을 초과할 경우, 현재 블루레이를 종료하고 새로운 블루레이를 시작합니다.
4. 모든 영화를 처리한 후 마지막 블루레이가 남아 있을 경우 추가 카운트합니다.

분석 및 복잡도

이 문제의 시간 복잡도는 O(N log N)입니다. 이는 주어진 영화 리스트를 정렬하는 데 필요한 시간입니다. 이후 영화 리스트를 한 번 순회하는 O(N) 만큼의 시간이 추가적으로 소요됩니다. 공간 복잡도는 O(1)로, 별도의 추가적인 데이터 구성을 필요로 하지 않습니다.

결론

이와 같이 알고리즘 문제에 대해 접근하고 해결하는 방법을 익히는 것은 코딩테스트 준비에 매우 유용합니다. 실전에서 이러한 문제를 자주 접할 수 있으므로, 다양한 문제를 풀어 보는 것이 중요합니다. “블루레이 만들기”는 자바의 기본 문법과 알고리즘 설계 능력을 동시에 요구하기 때문에 연습하기 좋은 문제입니다.

다음 강좌에서는 더욱 복잡한 알고리즘 문제를 다루며, 실전 코딩테스트에서 마주칠 수 있는 다양한 질문에 대한 해답을 제시하도록 하겠습니다. 고맙습니다!

본 글에서는 자바 코딩테스트를 대비하기 위한 알고리즘 문제를 하나 풀어보겠습니다. 주제는 “빌딩 순서 구하기”입니다. 이 문제는 다양한 분야에서 활용될 수 있는 그래프 탐색 알고리즘과 정렬 알고리즘을 결합한 문제입니다. 문제를 해결하기 위해 필요한 이론적 배경 및 코드 구현 방법에 대해 자세히 설명하겠습니다.

문제 설명

당신은 도시의 여러 빌딩을 건설할 계획을 세우고 있습니다. 각 빌딩은 서로의 의존성에 따라 순서를 가지고 있습니다. 즉, 빌딩 A가 빌딩 B보다 먼저 건설되어야 하는 경우, A -> B로 의존성이 나타납니다. 이러한 규칙에 따라 모든 빌딩의 건설 순서를 정하는 문제를 해결해야 합니다.

다음은 입력으로 주어지는 빌딩의 개수 N과 의존성 정보입니다. 당신은 모든 빌딩의 건설 순서를 출력해야 합니다.
예를 들어, 다음과 같은 의존성이 주어졌다고 가정해봅시다:

            5 4
            2 1
            3 1
            4 2
            5 3
            

이 입력은 5개의 빌딩이 있으며, 다음과 같은 의존성이 존재함을 의미합니다.
1번 빌딩은 2번 빌딩이 먼저 건설되어야 하고, 1번은 3번, 2번은 4번, 3번은 5번이 먼저 건설되어야 합니다.
이 경우, 가능한 한 빌딩들의 건설 순서는 다음과 같습니다:

            1, 2, 3, 4, 5 또는 1, 2, 3, 5, 4 등.
            

문제 해결을 위한 전략

이 문제를 해결하기 위해서는 그래프 이론에서의 위상 정렬(Topological Sorting) 개념을 활용할 수 있습니다. 위상 정렬은 방향 그래프에서 모든 정점(노드)을 유향 간선의 방향에 따라 나열하는 것입니다. 이때, 간선 A -> B가 있을 경우 A는 B보다 앞에 나와야 합니다.

알고리즘의 주요 단계는 다음과 같습니다:

1. 그래프를 인접 리스트 형태로 구현합니다.
2. 각 노드의 진입 차수(in-degree)를 계산합니다.
3. 진입 차수가 0인 노드를 시작으로 큐에 추가합니다.
4. 큐에서 노드를 하나씩 꺼내며 순서를 기록하고, 그 노드에 연결된 다른 노드의 진입 차수를 감소시킵니다. 이때, 진입 차수가 0이 된 노드는 다시 큐에 추가합니다.
5. 모든 노드가 처리될 때까지 반복합니다.

자바 구현 코드

위에서 설명한 알고리즘을 바탕으로 자바로 코드를 구현해보겠습니다. 아래는 위상 정렬을 수행하는 자바 코드입니다.

                
public class BuildingOrder {
    import java.util.*;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 빌딩과 의존성을 입력 받기
        int N = scanner.nextInt(); // 빌딩의 수
        int M = scanner.nextInt(); // 의존성의 수
        
        List> graph = new ArrayList<>();
        int[] inDegree = new int[N + 1]; // 진입 차수
        
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int i = 0; i < M; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph.get(a).add(b);
            inDegree[b]++;
        }
        
        // 위상 정렬을 수행하기 위해 과정 구현
        StringBuilder result = new StringBuilder();
        Queue queue = new LinkedList<>();

        // 진입 차수가 0인 노드 큐에 추가
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.append(current).append(" ");

            for (int neighbor : graph.get(current)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // 결과 출력
        System.out.println("빌딩 건설 순서: ");
        System.out.println(result.toString().trim());
        scanner.close();
    }
}
                
            

위 코드는 먼저 빌딩의 개수와 의존성을 입력받고, 이를 기반으로 그래프와 진입 차수를 초기화합니다. 그 후, 위상 정렬을 통해 건설 순서를 결정하고 출력합니다.

입출력 예제

예제 입력

            5 4
            2 1
            3 1
            4 2
            5 3
            

예제 출력

            빌딩 건설 순서: 
            1 2 3 4 5 또는 1 2 3 5 4
            

심화 학습

위상 정렬 알고리즘은 많은 실제 상황에서 사용될 수 있습니다. 예를 들어, 프로젝트 일정 관리, 컴파일러의 문법 분석, 그리고 여러 과정의 선후 관계가 있는 문제를 해결하는 데 유용합니다. 이러한 알고리즘을 이해하고 잘 활용한다면, 코딩 테스트는 물론 다양한 분야에서의 문제 해결에도 큰 도움이 될 것입니다.

연습 문제:

1. 위상 정렬을 사용하여 다음과 같은 그래프에 대한 건설 순서를 구해보세요.

2. 다음의 의존성을 구현하고, 그래프를 시각화하여 어떤 문제가 발생할 수 있는지 고민해보세요.

안녕하세요. 오늘은 자바를 활용한 코딩 테스팅 강좌를 통해 불우이웃돕기와 관련된 알고리즘 문제를 다루어보겠습니다. 불우이웃돕기란, 도움이 필요한 이웃을 위해 지원하는 활동을 뜻합니다. 이 문제를 통해 우리는 ‘배정하기’라는 알고리즘을 이해하고 구현해 보겠습니다.

문제 설명

가산호, 성훈, 민재 3명의 자원봉사자는 각각 정해진 시간에 따라 불우이웃에게 도움을 주기로 했습니다. 하지만 각 자원봉사자는 혼자서 모든 불우이웃에게 도움을 줄 수는 없기 때문에, 시간을 효율적으로 배분해야 합니다.

아래의 조건들을 고려하여, 불우이웃들에게 가장 많은 도움을 줄 수 있는 자원봉사자들을 배정하는 알고리즘을 구현하시오:

• 자원봉사자의 수: N (1 ≤ N ≤ 100)
• 불우이웃의 수: M (1 ≤ M ≤ 100)
• 각 자원봉사자는 최대 K명의 불우이웃에게 도움을 줄 수 있다.
• 자원봉사자와 불우이웃 간의 연결을 나타내는 인접 행렬은 주어진다.

입력 형식

첫 번째 줄에는 자원봉사자의 수 N과 불우이웃의 수 M이 주어집니다. 이후 N개의 줄에 걸쳐 각 자원봉사자가 도울 수 있는 불우이웃의 정보가 주어집니다. 1은 도울 수 있다는 의미이며, 0은 도울 수 없다는 의미입니다.

출력 형식

가장 많은 불우이웃에게 도움을 준 자원봉사자의 수와 그들 각각이 도울 수 있는 불우이웃의 번호를 출력합니다.

예제 입력

    3 4
    1 1 0 1
    1 0 1 1
    0 1 1 0
    

예제 출력

    2
    1 2
    2 3
    

문제 풀이 과정

이 문제를 해결하기 위해서 우리는 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)와 같은 탐색 기법을 활용할 수 있습니다. 배정 문제를 해결하기 위한 알고리즘을 설계하기 위해 다음의 과정을 따르도록 합니다:

1단계: 입력 데이터 처리하기

    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt(); // 자원봉사자 수
    int M = sc.nextInt(); // 불우이웃 수
    int[][] graph = new int[N][M]; // 인접 행렬 생성
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            graph[i][j] = sc.nextInt(); // 인접 행렬 입력
        }
    }
    

2단계: 자원봉사자 배정하기

자원봉사자가 각 불우이웃에게 도움을 줄 수 있는 상황을 바탕으로 DFS를 활용하여 가능한 모든 조합을 탐색합니다:

    boolean[] visited = new boolean[M]; // 방문 여부 체크
    int[] result = new int[N]; // 결과 배열
    int[] assignment = new int[N]; // 자원봉사자 할당
    
    for (int i = 0; i < N; i++) {
        Arrays.fill(visited, false); // 방문 배열 초기화
        assignVolunteerToNeighbour(i, graph, visited, assignment);
    }
    
    private static boolean assignVolunteerToNeighbour(int volunteer, int[][] graph, boolean[] visited, int[] assignment) {
        for (int neighbour = 0; neighbour < M; neighbour++) {
            if (graph[volunteer][neighbour] == 1 && !visited[neighbour]) {
                visited[neighbour] = true; 
                if (assignment[neighbour] == -1 || assignVolunteerToNeighbour(assignment[neighbour], graph, visited, assignment)) {
                    assignment[neighbour] = volunteer; 
                    return true;
                }
            }
        }
        return false;
    }
    

3단계: 최종 결과 출력하기

    for (int i = 0; i < N; i++) {
        if (assignment[i] != -1) {
            System.out.println((assignment[i] + 1) + " " + (i + 1));
        }
    }
    

결론

오늘은 불우이웃돕기와 관련된 자바 코딩 테스트 문제를 통해 자원봉사자를 배정하는 알고리즘을 구현해 보았습니다. 이 문제를 통해 그래프 이론과 탐색 알고리즘에 대해 더 깊이 이해할 수 있었으면 좋겠습니다. 또한, 코딩테스트와 실무에서 직접적으로 활용할 수 있는 기술을 연습하는 데 도움이 되었기를 바랍니다. 다음 강좌에서도 새로운 알고리즘 문제를 가지고 돌아오겠습니다. 감사합니다!

이번 글에서는 자바 코딩테스트의 유명한 문제 중 하나인 “부녀회장이 될 테야” 문제를 살펴보겠습니다.
이 문제는 동적 프로그래밍의 기초를 배울 수 있는 좋은 사례로, 효율적인 알고리즘을 통해 주어진 문제를 해결하는 과정을 자세히 설명하겠습니다.

문제 설명

부녀회장이 될 테야는 다음과 같은 문제입니다.

문제:
아파트가 N층 K개가 있다고 가정할 때, K층 N호에 살고 있는 사람의 수를 구하는 알고리즘을 작성하세요.

아파트의 각 호수에는 K층 N호에 사는 사람 수를 구하는 문제가 있습니다. 0층은 모두 1명이고, 각 층의 N호에 있는 사람 수는 아래층의 모든 호수의 사람 수의 합입니다. 그러므로,

• 0층 1호 = 1
• 0층 2호 = 1
• 1층 1호 = 1
• 1층 2호 = 1 + 1 = 2
• 2층 1호 = 1
• 2층 2호 = 1 + 2 = 3

와 같은 패턴이 나타납니다.

주어진 K층과 N호에 대해, 해당 호수에 살고 있는 사람의 수를 구하는 함수를 만들어주세요.

입력 및 출력 형식

입력: 첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 14)가 주어집니다.
각 테스트 케이스는 두 개의 정수 K, N (0 ≤ K ≤ 14, 1 ≤ N ≤ 14)로 구성되어 있습니다.
출력: 각 테스트 케이스마다 K층 N호에 사는 사람 수를 출력하세요.

문제 풀이 과정

1단계: 문제 이해하기

문제의 본질은 0층에서 K층까지의 사람 수 패턴을 이해하고, 이 패턴을 기반으로 N호에 사는 사람 수를 구하는 것입니다.
이해한 바에 따르면, 아파트 문제는 동적 프로그래밍의 규칙을 적용할 수 있습니다.
즉, 각각의 층에서 N호의 값은 이전 층에서의 N호와 (N-1)호의 합으로 정의될 수 있습니다.

2단계: 동적 프로그래밍 테이블 설계

이 문제를 해결하기 위해, 우리는 K층 N호를 계산하기 위한 2차원 배열을 선언합니다.
이 배열을 통해 각 위치에 사람 수를 채워넣는 방식으로 진행합니다.

    // 자바 코드 예시
    int[][] dp = new int[15][15]; // 15 x 15 배열 선언
    for (int i = 0; i < 15; i++) {
        dp[i][1] = 1; // 0층의 모든 호수에 대해서 초기화
        dp[0][i] = i; // 0층의 사람 수 설정
    }
    
    for (int i = 1; i < 15; i++) {
        for (int j = 2; j < 15; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 동적 프로그래밍 점화식
        }
    }
    

3단계: 최종 계산

위의 규칙을 기반으로 K층 N호에 대한 값을 계산할 수 있습니다. 각 테스트 케이스마다 dp[K][N]의 값을 출력하면 됩니다.

4단계: 코드 구현

    import java.util.Scanner;

    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int T = sc.nextInt(); // 테스트 케이스 수
            int[][] dp = new int[15][15]; // 15x15 배열

            // DP 배열 초기화
            for (int i = 0; i < 15; i++) {
                dp[i][1] = 1; // 0층의 모든 호수 초기화
                dp[0][i] = i; // 0층의 사람 수 설정
            }

            // DP 테이블을 채우기
            for (int i = 1; i < 15; i++) {
                for (int j = 2; j < 15; j++) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // 점화식
                }
            }

            // 각 테스트 케이스 처리
            for (int t = 0; t < T; t++) {
                int K = sc.nextInt(); // 층 수
                int N = sc.nextInt(); // 호 수
                System.out.println(dp[K][N]); // 결과 출력
            }

            sc.close();
        }
    }
    

결론

이번 강좌를 통해 “부녀회장이 될 테야” 문제를 해결하는 과정과 관련된 동적 프로그래밍의 기초를 이해하셨기를 바랍니다.
이 문제는 알고리즘 설계 및 구현의 중요한 원리를 배울 수 있는 좋은 사례입니다.
다양한 문제에 이와 같은 패턴을 적용하면 더 복잡한 문제도 상대적으로 쉽게 풀 수 있습니다.
연습을 통해 더 많은 유형의 문제를 해결해 보시기 바랍니다!

참고 자료

• BOJ 2775: 부녀회장이 될 테야 (백준)
• 다이나믹 프로그래밍 – 피보나치 수열

코딩 테스트에 자주 등장하는 알고리즘 중 하나가 바로 벨만-포드 알고리즘입니다. 이 글에서는 벨만-포드 알고리즘의 개념, 작동 방법, 그리고 실제 문제에 적용하는 방법을 단계별로 설명하겠습니다. 코딩 테스트와 취업 준비에 유용한 정보를 제공하기 위해 다양한 예제와 함께 상세한 풀이 과정을 포함시켰습니다.

벨만-포드 알고리즘 소개

벨만-포드 알고리즘은 가중치가 있는 그래프에서 단일 출발점(source)에서 다른 모든 정점까지의 최단 경로를 찾는 데 사용됩니다. 이 알고리즘은 음의 가중치가 있는 간선을 허용하지만, 음의 사이클이 포함된 경우에는 최단 경로를 제공할 수 없습니다. 따라서 알고리즘을 적용하기 전 그래프에 음의 사이클이 존재하는지 여부를 확인해야 합니다.

벨만-포드 알고리즘의 특징

• 정점 수가 V일 때, 시간 복잡도는 O(VE)입니다.
• 다리 데이터의 포맷이 다양할 수 있습니다.
• 최단 경로는 음의 가중치가 없는 그래프에서도 효과적으로 탐색이 가능합니다.
• 음의 사이클 검출 기능이 내장되어 있습니다.

문제: 최단 경로 찾기

다음은 벨만-포드 알고리즘을 이용하여 최단 경로를 찾는 문제입니다.

문제 설명

가중치가 있는 방향 그래프가 주어질 때, 특정 출발점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하세요. 그래프는 음의 가중치를 포함할 수 있습니다. 만약 음의 사이클이 존재하면, ‘Negative Cycle’이라는 메시지를 출력해야 합니다.

입력 형식

첫 번째 줄에는 정점의 수 V (1 ≤ V ≤ 1000)와 간선의 수 E (1 ≤ E ≤ 10,000)가 주어진다.
두 번째 줄에는 출발 정점 S (1 ≤ S ≤ V)가 주어진다.
이후 E줄에 걸쳐 각 간선에 대한 정보가 u, v, w (1 ≤ u, v ≤ V, -10^5 ≤ w ≤ 10^5)의 형태로 주어진다.

출력 형식

각 정점까지의 최단 경로 길이를, 공백으로 구분하여 출력한다.
음의 사이클이 존재하면 'Negative Cycle'를 출력한다.

문제 풀이

1. 문제 이해 및 분석

문제를 해결하기 위해 먼저 입력으로 주어지는 그래프 정보를 파악해야 합니다. 정점과 간선의 개수, 출발 정점을 이해해야 최단 경로를 구하는 과정으로 나아갈 수 있습니다. 이 문제는 벨만-포드 알고리즘의 기본적인 구조를 잘 활용해야 합니다.

2. 알고리즘 설계

벨만-포드 알고리즘은 다음의 단계로 진행됩니다:

1. 모든 간선을 기반으로 최단 경로 값을 초기화합니다. 출발점은 0, 다른 모든 정점은 무한대(infinity)로 설정합니다.
2. 정점의 수 – 1 만큼의 횟수 동안 모든 간선을 검사하고, 최단 경로를 갱신합니다.
3. 모든 간선을 다시 검사하여, 최단 경로를 갱신할 수 있다면 음의 사이클이 존재하는 것으로 판단합니다.

3. 자바 코드 구현

이제 위에서 설명한 알고리즘을 바탕으로 자바 코드를 작성해 보겠습니다.

import java.util.*;

public class BellmanFord {
    static class Edge {
        int u, v, weight;
        Edge(int u, int v, int weight) {
            this.u = u;
            this.v = v;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt(); // 정점의 수
        int E = sc.nextInt(); // 간선의 수
        int S = sc.nextInt(); // 출발 정점

        List edges = new ArrayList<>();
        for (int i = 0; i < E; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int weight = sc.nextInt();
            edges.add(new Edge(u, v, weight));
        }

        int[] dist = new int[V + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[S] = 0;

        // 알고리즘 실행
        for (int i = 1; i <= V - 1; i++) {
            for (Edge edge : edges) {
                if (dist[edge.u] != Integer.MAX_VALUE && 
                    dist[edge.u] + edge.weight < dist[edge.v]) {
                    dist[edge.v] = dist[edge.u] + edge.weight;
                }
            }
        }

        // 음의 사이클 검출
        for (Edge edge : edges) {
            if (dist[edge.u] != Integer.MAX_VALUE && 
                dist[edge.u] + edge.weight < dist[edge.v]) {
                System.out.println("Negative Cycle");
                return;
            }
        }

        // 최단 경로 출력
        for (int i = 1; i <= V; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.print("Infinity ");
            } else {
                System.out.print(dist[i] + " ");
            }
        }
    }
}

4. 코드 설명

위 코드는 벨만-포드 알고리즘의 전체 흐름을 담고 있습니다:

• 우선 edge 리스트를 사용하여 모든 간선 데이터를 저장합니다.
• 거리 배열(dist)을 선언하고 출발점의 거리를 0으로 초기화합니다.
• 안쪽 loop에서 각 간선을 반복하며, 최단 거리를 갱신합니다.
• 모든 간선에 대해서 다시 검토한 후, 음의 사이클 여부를 확인합니다.

5. 테스트 및 검증

코드를 완성한 후, 다양한 테스트 케이스를 통해 알고리즘의 올바른 작동 여부를 확인해야 합니다. 예를 들어:

입력:
5 8
1
1 2 4
1 3 3
2 3 1
3 2 -1
2 4 2
3 4 5
4 5 -3
5 4 2

출력:
0 3 3 5 Infinity 

6. 결론

벨만-포드 알고리즘은 최단 경로 문제를 해결하기 위해 매우 유용한 도구입니다. 음의 가중치를 허용하는 특성 덕분에 다양한 그래프 문제에 적용할 수 있습니다. 이 알고리즘의 이해와 구현은 코딩 인터뷰 및 알고리즘 시험에서 높은 점수를 얻기 위한 필수 능력 중 하나입니다.

마무리

벨만-포드 알고리즘에 대한 이번 강좌가 도움이 되셨다면 좋겠습니다. 코딩 테스트 준비에 실질적인 기여를 할 수 있기를 바랍니다. 알고리즘을 다양한 문제에 적용해 보며 심화 학습을 이어가세요!