[카테고리:] C++ 코딩테스트 강좌

문제 설명

한 도시에서 여러 개의 버스 노선이 운영되고 있으며, 각 노선은 정해진 정류소를 순회합니다.
당신은 A 정류소에서 B 정류소까지 가는 가장 빠른 경로를 찾아야 합니다.
버스는 정해진 시간에 출발하며, 각 정류소에서 정차하는 시간과 이동 시간을 고려해야 합니다.
아래와 같은 데이터가 주어졌을 때, 가장 빠른 버스 노선을 찾는 알고리즘을 작성하시오.

입력 형식

• 첫 번째 줄에는 정류소의 수 N(1 ≤ N ≤ 1000)과 버스 노선의 수 M(1 ≤ M ≤ 10000)이 주어진다.
• 두 번째 줄부터 M개의 줄에는 각 버스 노선에 대한 정보가 다음 형식으로 주어진다:
  
  시작 정류소, 도착 정류소, 소요 시간
• 마지막 줄에는 A 정류소와 B 정류소의 번호가 주어진다.

출력 형식

첫 번째 줄에 A 정류소에서 B 정류소까지 가는 가장 짧은 시간(분)을 출력한다.
만약 도착할 수 없으면 -1을 출력한다.

예제 입력

    5 7
    1 2 10
    1 3 20
    2 3 5
    2 4 10
    3 4 10
    4 5 15
    1 5
    

예제 출력

    25
    

문제 풀이 과정

이 문제를 해결하기 위해 우리는 최단 경로 알고리즘을 사용해야 합니다.
주어진 그래프는 가중치가 있는 방향 그래프이므로, 다익스트라 알고리즘을 적합하게 사용할 수 있습니다.
다익스트라 알고리즘은 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 방법으로,
주로 비가중치 그래프에 적합합니다. 하지만 가중치가 있을 경우에도 효과적으로 적용할 수 있습니다.

다익스트라 알고리즘의 기본 원리

다익스트라 알고리즘은 다음과 같은 기본 원리로 작동합니다:

1. 출발 정점을 설정하여 최단 경로를 0으로 초기화하고, 나머지 정점은 무한대로 초기화합니다.
2. 처리되지 않은 정점 중에서 최단 경로가 가장 짧은 정점을 선택합니다.
3. 선택된 정점에 인접한 정점들의 경로를 갱신합니다.
4. 이 과정을 모든 정점이 처리될 때까지 반복합니다.

C++ 코드 구현

다음은 위의 알고리즘을 바탕으로 한 C++ 코드 구현입니다.

    #include 
    #include 
    #include 
    #include 

    using namespace std;

    const int INF = numeric_limits::max();

    void dijkstra(int start, int n, vector>> &graph, vector &dist) {
        priority_queue, vector>, greater>> pq;
        dist[start] = 0;
        pq.push({0, start});

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            for (auto &neighbor : graph[u]) {
                int v = neighbor.first;
                int weight = neighbor.second;
                
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.push({dist[v], v});
                }
            }
        }
    }

    int main() {
        int N, M;
        cin >> N >> M;
        vector>> graph(N + 1); // N 정류소

        for (int i = 0; i < M; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            graph[u].push_back({v, w});
        }

        int A, B;
        cin >> A >> B;

        vector dist(N + 1, INF);
        dijkstra(A, N, graph, dist);

        if (dist[B] == INF) {
            cout << -1 << endl;
        } else {
            cout << dist[B] << endl;
        }

        return 0;
    }
    

코드 설명

위의 코드는 다익스트라 알고리즘을 사용하여 주어진 정류소에서 최단 경로를 찾는 방법을 구현하고 있습니다.
주요 단계는 다음과 같습니다:

1. 주어진 입력을 바탕으로 그래프를 인접 리스트 형태로 저장합니다.
2. 시작 정류소에서부터 다른 정류소까지의 최단 경로를 구하기 위해 다익스트라 함수를 호출합니다.
3. 결과적으로 도착 정류소까지의 최단 경로가 무한대이면 도달할 수 없다는 의미로 -1을 출력하고,
   그렇지 않으면 최단 경로의 경과 시간을 출력합니다.

결론

이번 강좌에서는 여러 개의 버스 노선과 정류소를 가진 그래프에서 시작점과 도착점 사이의 최단 경로를
찾는 문제를 다뤄보았습니다. 다익스트라 알고리즘을 통해 최단 경로를 구하는 개념과 그 구현 방법을
학습했습니다. 이를 바탕으로 다른 유사한 문제들도 해결할 수 있는 기초를 다졌습니다.

문제 설명

주어진 정수 배열에서 가장 길게 증가하는 부분 수열(Longest Increasing Subsequence, LIS)을 찾아야 합니다.
부분 수열은 원본 배열에서 요소의 순서를 유지하며 선택된 요소들로 구성됩니다.
이 문제는 동적 프로그래밍(Dynamic Programming) 또는 이분 탐색(Binary Search)을 통해 해결할 수 있습니다.

예시

입력: [10, 9, 2, 5, 3, 7, 101, 18]
출력: 4 (가장 긴 증가하는 부분 수열: [2, 3, 7, 101])

문제 접근 방법

이 문제를 해결하기 위한 방법은 여러 가지가 있습니다. 가장 대표적인 방법은 동적 프로그래밍을 사용하는 것이며,
이 방법은 O(N^2)의 시간 복잡도를 가집니다. 그러나 이 문제는 이분 탐색을 이용하여 O(N log N)의 시간 복잡도로도 해결할 수 있습니다.

1. 동적 프로그래밍(Dynamic Programming) 접근법

동적 프로그래밍 접근법의 핵심은 ‘중간 결과’를 저장하여, 동일한 계산을 반복하지 않도록 하는 것입니다.
다음과 같은 단계로 진행합니다.

1. 길이를 저장하기 위한 dp 배열을 초기화합니다. dp[i]는 i번째 인덱스의 원소를 끝으로 하는
   증가하는 부분 수열의 최대 길이를 저장합니다.
2. 이중 반복문을 통해 각 원소를 비교하고, dp 배열을 업데이트합니다.
   i번째 원소가 j번째 원소보다 클 경우, dp[i]를 max(dp[i], dp[j] + 1)로 설정합니다.
3. 최종적으로 dp 배열의 최대 값을 찾아 출력합니다.

코드 (동적 프로그래밍)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lengthOfLIS(vector& nums) {
    if (nums.empty()) return 0;
    vector dp(nums.size(), 1);
    
    for (int i = 1; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

int main() {
    vector nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "가장 길게 증가하는 부분 수열의 길이: " << lengthOfLIS(nums) << endl;
    return 0;
}
    

2. 이분 탐색(Binary Search) 접근법

이 방법은 더 효율적이며, O(N log N)의 시간 복잡도를 가집니다. 이 방법의 기본 아이디어는
‘부분 수열의 끝 요소들을 저장하는 배열’을 유지하는 것입니다.

1. 결과를 저장할 배열을 초기화합니다.
2. 각 원소에 대해 다음을 수행합니다:
   • 현재 숫자가 result 배열의 마지막 원소보다 크면 배열에 추가합니다.
   • 그렇지 않으면 이분 탐색을 통해 현재 숫자가 들어갈 위치를 찾은 후 대체합니다.
3. 결과 배열의 크기가 가장 길게 증가하는 부분 수열의 길이가 됩니다.

코드 (이분 탐색)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int lengthOfLIS(vector& nums) {
    vector tails;
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    return tails.size();
}

int main() {
    vector nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "가장 길게 증가하는 부분 수열의 길이: " << lengthOfLIS(nums) << endl;
    return 0;
}
    

결론

“가장 길게 증가하는 부분 수열 찾기” 문제는 다양한 방법으로 해결할 수 있는 알고리즘 문제입니다.
문제 해결을 위한 접근 방법을 이해하고 구현하는 것은 코딩 테스트에서 큰 도움이 됩니다.
이 문제를 통해 동적 프로그래밍 및 이분 탐색의 기초를 익히고, 다양한 알고리즘 문제에 적용하는 능력을 키워보세요.

추가 학습 자료

• GeeksforGeeks – Longest Increasing Subsequence
• LeetCode – Longest Increasing Subsequence

1. 소개

알고리즘 문제 풀이는 취업 준비에 있어 매우 중요한 요소입니다. 오늘은 많은 개발자들이 마주하는 ‘좋은 수’ 구하기 문제에 대해 깊이 있게 살펴보겠습니다. ‘좋은 수’란 어떤 수를 특정 조건 하에서 구하는 것을 의미하며, 이 문제를 통해 사고력을 키우고 실력을 향상시킬 수 있습니다.

2. 문제 설명

당신은 정수 n을 입력받습니다. n보다 작거나 같은 모든 수 중에서, 각 자릿수의 합이 10 이하인 수를 ‘좋은 수’라고 정의합니다.
예를 들어, 23은 좋은 수이지만 24는 2+4=6으로 좋은 수가 아닙니다. 문제는 주어진 n 이하의 ‘좋은 수’를 모두 구하는 것입니다.

2.1. 입력

정수 n (1 <= n <= 10000)

2.2. 출력

n 이하의 ‘좋은 수’를 출력합니다.

3. 접근 방법

이 문제를 해결하기 위해서는 다음과 같은 접근 방법을 사용할 수 있습니다.

• 1부터 n까지의 수를 반복하여 각 수의 자릿수를 분리합니다.
• 각 자릿수들의 합을 계산합니다.
• 자릿수 합이 10 이하인 경우 ‘좋은 수’로 판단하여 출력합니다.

3.1. 자릿수 합 구하기

자릿수 합을 구하는 방법으로는 수를 10으로 나누어 나머지를 구하는 방식을 사용할 수 있습니다. 예를 들어, 23을 나누면 3(23 % 10)과 2(23 / 10)로 나아갑니다.
이러한 과정을 통해 각 수의 자릿수를 파악하고 합을 계산할 수 있습니다.

4. 코드 구현

이제 위의 접근 방법을 기반으로 C++ 코드를 작성해보겠습니다. 아래는 ‘좋은 수’를 구하는 프로그램의 코드입니다.

#include 
using namespace std;

bool isGoodNumber(int number) {
    int sum = 0;
    while (number > 0) {
        sum += number % 10; // 현재 자릿수 더하기
        number /= 10; // 다음 자릿수 계산
    }
    return sum <= 10; // 자릿수 합이 10 이하인지 체크
}

int main() {
    int n;
    cout << "정수를 입력하세요: ";
    cin >> n;

    cout << "좋은 수들: ";
    for (int i = 1; i <= n; i++) {
        if (isGoodNumber(i)) {
            cout << i << " "; // 좋은 수 출력
        }
    }
    cout << endl;
    return 0;
}
    

5. 코드 설명

위 코드는 간단한 형태의 프로그램으로, ‘좋은 수’ 판단을 위한 isGoodNumber 함수와 메인 함수 main으로 구성되어 있습니다.

5.1. isGoodNumber 함수

이 함수는 정수를 입력으로 받아, 각 자릿수의 합을 계산한 후 그 결과에 따라 true 또는 false를 반환합니다.
반복문을 사용하여 수의 각 자릿수를 분리하고 합산합니다.

5.2. main 함수

메인 함수에서는 사용자로부터 n을 입력받고, 1부터 n까지의 수를 체크합니다. 각 수에 대해 isGoodNumber를 호출하여 좋은 수인지를 판단합니다.

6. 시간 복잡도

이 알고리즘의 시간 복잡도는 O(d * n)입니다. 여기서 d는 n의 자릿 수입니다.
각 수에 대해 자릿수를 더하는 것은 최대 4회 수행되므로 n이 커져도 실시간으로 대처할 수 있습니다.

7. 최적화

현재 코드는 모든 수를 고려하고 자릿수 합을 계산하므로 비효율적일 수 있습니다.
대신에 자릿수 합을 미리 계산하고 저장하여 중복 계산을 줄일 수 있습니다. 다음은 이를 위한 코드 개선 예시입니다.

#include 
#include 
using namespace std;

vector precomputeGoodNumbers(int maxNum) {
    vector goodNumbers;
    for (int i = 1; i <= maxNum; i++) {
        if (isGoodNumber(i)) {
            goodNumbers.push_back(i); // 좋은 수 저장
        }
    }
    return goodNumbers;
}

int main() {
    int n;
    cout << "정수를 입력하세요: ";
    cin >> n;

    vector goodNumbers = precomputeGoodNumbers(n);
    cout << "좋은 수들: ";
    for (int number : goodNumbers) {
        cout << number << " "; // 미리 저장된 좋은 수 출력
    }
    cout << endl;
    return 0;
}
    

8. 결론

오늘은 ‘좋은 수’ 구하기 문제를 함께 살펴보았습니다. 이 문제는 기본적인 알고리즘 사고를 발전시키고 문제 해결 능력을 향상시키는 좋은 예제입니다.
앞으로도 다양한 문제를 통해 알고리즘 역량을 강화할 수 있도록 노력하시기 바랍니다. Happy coding!

안녕하세요! 이번 강좌에서는 알고리즘 문제 중 하나인 “K번째 최단 경로 찾기”에 대해 이야기하겠습니다. 이 문제는 실전 코딩 테스트에서 자주 등장하며, 그래프와 최단 경로 알고리즘에 대한 깊은 이해를 요구합니다. 이 문제를 통해 다익스트라 알고리즘과 우선순위 큐를 활용하는 방법을 배워보겠습니다.

문제 설명

주어진 그래프에서 두 정점 A와 B 사이의 K번째 최단 경로의 길이를 알아내는 문제입니다. 최단 경로는 다수의 경로 중에서 가장 짧은 길이를 가진 경로를 의미하며, K번째 최단 경로란 최단 경로보다 길이가 더 길면서 가장 짧은 경로를 의미합니다. 동일한 경로가 여러 번 존재할 수 있습니다.

입력

• 정점의 개수 N (1 ≤ N ≤ 400)
• 간선의 개수 M (1 ≤ M ≤ 100,000)
• K (1 ≤ K ≤ 3000)
• 각 간선 정보 (시작 정점, 종료 정점, 가중치)
• 정점 A와 B

출력

K번째 최단 경로의 길이를 출력합니다. 만약 K번째 최단 경로가 존재하지 않는다면 -1을 출력합니다.

문제 접근 방법

이 문제를 풀기 위해서는 K번째 최단 경로를 찾는 방법에 대해 고민해야 합니다. 일반적인 다익스트라 알고리즘은 최단 경로를 찾는 데 효과적이지만, K번째 경로를 찾기 위해서는 추가적인 조치를 취해야 합니다.

해당 문제를 해결하기 위해 사용하는 자료구조는 다음과 같습니다:

• 우선순위 큐 (Priority Queue): 최소 값이 우선으로 처리되도록 합니다.
• 벡터 (Vector): 그래프 구조를 표시하는 데 사용합니다.

알고리즘 단계

1. 그래프를 입력받아 인접 리스트(adjacent list)로 표현합니다.
2. 각 정점에 대한 경로 리스트를 우선순위 큐에 저장합니다.
3. 시작 정점으로부터 다익스트라 알고리즘을 사용하여 K번째 최단 경로를 찾습니다.
4. 경로 리스트에서 K번째로 작은 값을 찾아 출력합니다.

C++ 코드 구현

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>

using namespace std;

const int INF = 1e9;  // 무한대 정의

struct Edge {
    int to, weight;
};

int N, M, K;
vector<Edge> graph[401];
vector<int> dist[401];  // 각 정점의 K번째 최단 경로 길이

void findKthShortestPath(int start, int end) {
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    pq.push(make_tuple(0, start, 0));  // (길이, 현재정점, 경로 수)
    
    while (!pq.empty()) {
        auto [length, current, count] = pq.top();
        pq.pop();
        
        if (count >= K) continue; // K개 이상의 경로를 탐색할 필요 없음
        dist[current].push_back(length);
        
        for (auto &edge : graph[current]) {
            int next = edge.to;
            int weight = edge.weight;
            pq.push(make_tuple(length + weight, next, count + 1));
        }
    }
}

int main() {
    cin >> N >> M >> K; // 정점, 간선, K 가져오기
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w}); // 간선 추가
    }

    int A, B;
    cin >> A >> B;

    findKthShortestPath(A, B);
    
    if (dist[B].size() < K) {
        cout << -1 << endl; // K번째 최단 경로가 없으면 -1 반환
    } else {
        cout << dist[B][K-1] << endl; // K번째 최단 경로 출력
    }

    return 0;
}

결론

이번 강좌에서는 K번째 최단 경로 찾기라는 문제를 통해 그래프 탐색의 다양한 방법과 우선순위 큐를 이용한 효율적인 경로 탐색 방법을 살펴보았습니다. 이 문제를 해결하는 과정에서 다익스트라 알고리즘의 변형을 통해 K번째 경로를 찾는 방법에 대해 배울 수 있었습니다. 이러한 문제들에 대한 이해는 실제 코딩 테스트에서 높은 점수를 받을 수 있는 기회를 제공할 것입니다.

여러분도 이 문제를 연습하면서 그래프 탐색에 대한 이해를 높이고, 코딩 실력을 한 단계 끌어올리길 바랍니다. 감사합니다!