[작성자:] root

문제 설명

여러 개의 빌딩이 하나의 도시를 구성하고 있습니다. 각 빌딩은 고유한 번호를 가지고 있으며,
빌딩들 사이에는 방향성이 있는 도로가 존재합니다. 문제는 이러한 빌딩들을 특정한 순서로
건축해야 하는 규칙이 존재하며, 그 순서를 구하는 것입니다.

모든 빌딩은 주어진 조건에 의해 건축 순서가 결정됩니다. 이 문제는 위상 정렬(Topological Sort) 문제로
나타낼 수 있습니다. 주어진 규칙을 기반으로 원하는 빌딩의 순서를 계산하여 출력하는 것이
목적입니다.

입력 형식

첫 번째 줄에는 빌딩의 수 N과 도로의 수 M이 주어집니다. (1 ≤ N ≤ 10^6, 0 ≤ M ≤ 10^6)
다음 M개의 줄에는 도로의 정보가 주어지며, 두 정수 A, B가 주어질 경우 이는 빌딩 A가
빌딩 B보다 먼저 건축되어야 함을 의미합니다.

출력 형식

빌딩의 건축 순서를 한 줄로 출력합니다. 만약 건축 순서를 정할 수 없는 경우 ‘0’을 출력합니다.

예제

입력

    4 2
    1 2
    2 3
    

출력

    1 2 3 4
    

접근 방법

이 문제를 해결하기 위해 우리는 두 가지 방법을 고려할 수 있습니다.
1. DFS(Depth-First Search)를 활용한 방법
2. Kahn의 알고리즘을 활용한 방법

위상 정렬 문제는 사이클이 없는 방향 그래프에서 가능한 빌딩 순서를 찾아야 하는 문제입니다.
여기서 사이클이 존재하면 문제의 요구사항을 만족할 수 없기 때문에,
이를 체크하는 과정이 필요합니다.

1. DFS를 활용한 방법

DFS를 사용하여 그래프를 탐색하면서 각 노드를 방문하는 방식으로
위상 정렬을 수행할 수 있습니다. 이 방식의 핵심은 각 노드를 스택에
추가할 때, 해당 노드의 모든 자식 노드가 방문되었을 때입니다.

2. Kahn의 알고리즘

Kahn의 알고리즘은 각 노드의 진입 차수를 사용하여 위상 정렬을 수행하는 방법입니다.
이 알고리즘은 다음과 같은 단계를 포함합니다:

1. 그래프의 진입 차수를 계산합니다.
2. 진입 차수가 0인 노드를 큐에 추가합니다.
3. 큐에서 노드를 하나씩 꺼내어 출력하고, 해당 노드와 연결된 모든 노드의
   진입 차수를 감소시킵니다. 만약 진입 차수가 0이 된 노드를 큐에 추가합니다.
4. 이 과정을 반복합니다. 모든 노드를 방문했다면 성공적으로 위상 정렬을
   수행한 것이고, 사이클이 없는 것입니다.

구현

이제 위에 설명한 Kahn의 알고리즘을 사용하여 문제를 해결하는 코드를
구현해보겠습니다.

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

void topologicalSort(int N, vector>& graph, vector& inDegree) {
    queue q;
    vector result;

    // 진입 차수가 0인 노드를 큐에 추가
    for (int i = 1; i <= N; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        result.push_back(current);

        // 현재 노드와 연결된 모든 노드의 진입 차수 감소
        for (int neighbor : graph[current]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                q.push(neighbor);
            }
        }
    }

    // 결과 출력
    if (result.size() == N) {
        for (int i = 0; i < result.size(); i++) {
            cout << result[i] << " ";
        }
        cout << endl;
    } else {
        cout << "0" << endl; // 사이클이 존재할 경우
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    vector> graph(N + 1);
    vector inDegree(N + 1, 0);

    for (int i = 0; i < M; i++) {
        int A, B;
        cin >> A >> B; // A -> B
        graph[A].push_back(B);
        inDegree[B]++;
    }

    topologicalSort(N, graph, inDegree);

    return 0;
}
    

결론

위상 정렬 문제는 많은 알고리즘 문제에서 접할 수 있는 유형 중 하나로,
특히 프로젝트의 작업 순서를 결정해야 할 때 유용하게 사용될 수 있습니다.
이 강좌에서는 Kahn의 알고리즘을 통해 빌딩 순서를 구하는 문제를 해결했습니다.
다양한 변형 문제가 존재하므로, 실제 코딩테스트에서 실력을 쌓기 위해
다양한 문제를 풀어보기를 권장합니다.

수고하셨습니다! 여러분의 코딩테스트 준비에 많은 도움이 되었기를 바랍니다.

안녕하세요! 이번 포스팅에서는 C++ 코딩테스트를 대비하기 위한 알고리즘 문제를 풀어보며, ‘블루레이 만들기’라는 주제에 대해 심도 있게 탐구해 보겠습니다. 이 문제는 주로 동적 프로그래밍과 이분 탐색을 활용하여 접근할 수 있습니다. 함께 코드를 작성하고, 단계별로 문제를 해결하는 과정을 따라가 봅시다.

문제 설명

블루레이는 영화와 같은 미디어 콘텐츠를 저장하고 재생하는 디스크입니다. 한 사용자에게 특정 영화 목록이 주어지고, 이 목록의 영화를 블루레이에 저장하기 위해 최대한 효율적으로 저장하려고 합니다. 사용자는 각 블루레이에 저장할 수 있는 영화의 최대 시간을 설정할 수 있으며, 이를 이용해 블루레이 몇 개가 필요한지를 최소화하려고 합니다.

문제 정의

    영화 목록은 N개의 영화로 구성되어 있으며, 각 영화의 길이는 A[i]와 같이 주어집니다. 이제 우리는 기간 T로 제한된 블루레이를 사용하여 최소한의 블루레이 수로 모든 영화를 저장하고자 합니다. 
    주어진 제약 조건을 활용하여 블루레이의 개수를 알고리즘으로 계산하는 문제를 해결합시다.
    

입력

• 첫 번째 줄에 영화의 개수 N (1 ≤ N ≤ 1000)과 최대 블루레이에 저장할 수 있는 시간 T (1 ≤ T ≤ 10000)가 주어집니다.
• 두 번째 줄에 각 영화의 길이를 나타내는 N개의 정수가 주어집니다. 각 영화의 길이는 1 이상 T 이하입니다.

출력

필요한 블루레이의 최소 개수를 출력합니다.

문제 접근 방식

문제를 해결하기 위해서 우리는 다음과 같은 단계를 따릅니다:

1. 이분 탐색을 활용하여 가능한 블루레이의 최대 저장 시간 범위를 설정합니다.
2. 각 블루레이에 영화를 저장하는 데 필요한 블루레이 수를 카운트합니다.
3. T 시간을 초과하는 경우 블루레이 개수를 증가시키고, T 이하인 경우 최대 블루레이 저장 시간을 조정합니다.
4. 최종적으로 필요한 블루레이 개수를 출력합니다.

코드 구현

    
    #include <iostream>
    #include <vector>
    #include <algorithm>

    using namespace std;

    int countBluRays(const vector<int>& movies, int maxTime) {
        int count = 1; // 최소 1개의 블루레이는 필요
        int currentTime = 0;

        for (int movie : movies) {
            if (currentTime + movie > maxTime) {
                count++; // 새로운 블루레이 필요
                currentTime = movie; // 현재 영화 대입
            } else {
                currentTime += movie; // 현재 블루레이에 영화 추가
            }
        }
        return count;
    }

    int main() {
        int N, T;
        cin >> N >> T;

        vector<int> movies(N);
        for (int i = 0; i < N; i++) {
            cin >> movies[i];
        }

        // 이분 탐색을 통한 블루레이 최대 시간 결정
        int low = *max_element(movies.begin(), movies.end());
        int high = accumulate(movies.begin(), movies.end(), 0);
        int result = high;

        while (low <= high) {
            int mid = (low + high) / 2;
            int requiredBluRays = countBluRays(movies, mid);

            if (requiredBluRays <= T) {
                result = mid; // 블루레이 최대 시간을 줄일 수 있다.
                high = mid - 1;
            } else {
                low = mid + 1; // 블루레이 최대 시간을 늘린다.
            }
        }

        cout << result << endl;
        return 0;
    }
    
    

코드 설명

위 코드는 다음의 주요 부분으로 구성되어 있습니다:

1. countBluRays 함수: 주어진 최대 블루레이 시간(maxTime)에 따라 영화를 저장하기 위해 필요한 블루레이의 개수를 계산합니다. 각 영화를 순회하며 현재 블루레이에 담을 수 있는지 확인하고, 필요시 블루레이를 추가합니다.
2. main 함수: 입력으로 영화 개수 N과 블루레이의 최대 시간 T를 받고, 영화의 길이를 저장합니다. 이어서 이분 탐색을 통해 모든 영화를 저장하는 데 필요한 최소 블루레이 시간을 찾아냅니다.

알고리즘 복잡도

위 알고리즘의 시간 복잡도는 O(N log S)입니다. 여기서 N은 영화의 개수이고, S는 영화 길이의 합입니다. 이분 탐색 과정에서 매번 모든 영화를 순회하므로 효율적입니다.

결론

이번 포스팅에서는 ‘블루레이 만들기’라는 코딩 문제를 통해 이분 탐색과 동적 프로그래밍의 기초를 쉽게 이해했습니다. 알고리즘 문제를 해결하는데 있어서는 문제의 본질을 파악하고, 적절한 접근 방식을 찾는 것이 중요합니다. 연습을 통한 경험이 쌓이게 되면, 더 복잡한 문제들도 수월하게 해결할 수 있을 것입니다. 다음 포스팅에선 좀 더 다양한 문제들에 대해 탐구해 보겠습니다!

안녕하세요! 이번 블로그 포스트에서는 C++을 사용한 알고리즘 문제를 풀어보며, 불우이웃 돕기라는 주제로 사회에 기여할 수 있는 방법을 알아보겠습니다. 알고리즘 문제는 우리에게 문제 해결 능력을 기르는 데 중요한 역할을 하며, 실제 취업 면접에서도 자주 등장하는 주제입니다.

문제 설명

많은 사람들이 어려움을 겪고 있는 사회적인 문제에서, 해마다 크리스마스를 맞이하여 자선 기부를 진행합니다. 각 기부자는 자신이 원하는 금액을 기부할 수 있고, 이 기부자들의 기부액을 통해 특정한 수의 불우이웃들을 도울 수 있도록 하려고 합니다. 하지만 각 불우이웃은 기부 받을 수 있는 최대 금액이 정해져 있습니다.

문제 정의

주어진 기부자들의 기부액과 불우이웃이 받을 수 있는 최대 금액의 배열이 있을 때, 모든 불우이웃들이 받을 수 있는 최대 기부 총액을 구하시오.

입력 형식

• 첫 번째 줄: 기부자의 수 N (1 ≤ N ≤ 1000)
• 두 번째 줄: 각 기부자의 기부액을 나타내는 N개의 정수 A1, A2, ..., AN (1 ≤ Ai ≤ 10000)
• 세 번째 줄: 불우이웃의 수 M (1 ≤ M ≤ 1000)
• 네 번째 줄: 각 불우이웃이 받을 수 있는 최대 금액을 나타내는 M개의 정수 B1, B2, ..., BM (1 ≤ Bj ≤ 10000)

출력 형식

모든 불우이웃들이 받을 수 있는 최대 기부 총액을 출력하시오.

예제 입력

5
1500 2000 3000 4000 5000
3
2000 3000 10000

예제 출력

10000

문제 해결 접근 방법

이 문제를 해결하기 위한 접근 방법은 다음과 같습니다:

1. 자선 기부자들의 기부액과 각 불우이웃이 받을 수 있는 최대 금액을 정렬합니다.
2. 각 기부자가 최대로 기부할 수 있는 금액을 한 사람씩 확인하면서 각 불우이웃의 최대 금액을 초과하지 않는 범위 내에서 할당합니다.
3. 각 기부의 결과를 누적하여 총 기부액을 계산합니다.

C++ 코드 구현

아래는 위의 접근 방법에 대한 C++ 코드입니다:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cout << "기부자 수 입력: ";
    cin >> N;

    vector<int> donations(N);
    cout << "기부액 입력: ";
    for (int i = 0; i < N; i++) {
        cin >> donations[i];
    }

    int M;
    cout << "불우이웃 수 입력: ";
    cin >> M;

    vector<int> beneficiaries(M);
    cout << "불우이웃 최대 받을 금액 입력: ";
    for (int i = 0; i < M; i++) {
        cin >> beneficiaries[i];
    }

    // 기부자와 불우이웃의 배열 정렬
    sort(donations.rbegin(), donations.rend());
    sort(beneficiaries.rbegin(), beneficiaries.rend());

    int totalDonated = 0;
    int donationIndex = 0;
    int beneficiaryIndex = 0;

    // 기부자와 불우이웃 매칭
    while (donationIndex < N && beneficiaryIndex < M) {
        if (donations[donationIndex] <= beneficiaries[beneficiaryIndex]) {
            totalDonated += donations[donationIndex];
            donationIndex++;
        } else {
            totalDonated += beneficiaries[beneficiaryIndex];
            beneficiaryIndex++;
        }
    }

    cout << "최대 기부 총액: " << totalDonated << endl;
    return 0;
}

코드 설명

위 코드는 다음과 같은 방식으로 동작합니다:

1. 기부자 수와 불우이웃 수를 입력받고, 각각의 기부액과 최대 수혜 금액을 입력받습니다.
2. 각 배열을 내림차순으로 정렬합니다. 이렇게 하면 높은 기부부터 낮은 기부로 비교할 수 있어 최적의 배분이 가능해집니다.
3. 각 기부자가 최대 금액에 도달하거나 불우이웃의 최대 수혜 금액을 초과하지 않도록 작동하여 가능하면 많은 기부가 이루어지도록 합니다.
4. 총 기부액을 계산하여 출력합니다.

성과 검증 및 테스트

작성한 코드는 다양한 입력 예제를 통해 검증되어야 합니다. 일반적인 사례 외에도 극단적인 사례(예: 모든 기부자가 동일한 금액 기부 등)도 고려하여 테스트를 진행해야 합니다.

테스트 케이스 예시

입력:
3
3000 3000 3000
4
1500 3000 2000 1000

출력:
9000

위 코드에서 기부자는 3000, 3000, 3000을 기부하고, 불우이웃은 각각 1500, 3000, 2000, 1000을 받을 수 있습니다. 이 경우 가능한 최대 기부 금액은 9000입니다.

마치며

이번 포스트에서는 C++을 사용하여 기부자와 불우이웃을 매칭하는 알고리즘 문제를 통해 논리적인 사고를 기르는 방법을 살펴보았습니다. 코딩테스트에서 자주 사용되는 문제 해결 방법이자 실질적으로 사회적 기여를 할 수 있는 문제를 학습하여 여러분의 프로그래밍 능력을 발전시킬 수 있기를 바랍니다. 코딩 테스트 준비에 많은 도움이 되기를 기원합니다!

문제 설명

“부녀회장이 될 테야” 문제는 아파트의 층과 호수에 따라 사람의 수를 계산하는 문제입니다.
주어진 층의 인덱스와 호수의 인덱스를 통해 몇 명이 거주하는지를 파악해야 합니다.
이 문제의 핵심은 피라미드 구조를 활용하여 각 층에서의 거주자 수를 계산하는 것입니다.

문제 이해하기

어느 아파트에 거주하는 사람의 수를 정의하는 규칙은 다음과 같습니다.
0층(i=0)의 경우, i호는 항상 1명입니다.
1층(i=1)에서는 i호가 1명에서 시작해, 위층의 모든 호수에 해당하는 사람의 수를 합산하여 나타납니다.

즉, f(n, k)는 n층 k호의 사람 수를 나타내면, 다음과 같은 재귀 방정식을 세울 수 있습니다:

f(n, k) = f(n-1, 1) + f(n-1, 2) + ... + f(n-1, k)

이 규칙을 바탕으로, n층 k호에 거주하는 사람 수는 (n-1)층 1호부터 k호까지의 합입니다.

문제 풀이 접근법

1. **기본 재귀 함수 구현**: 문제를 단순하게 풀기 위해, 재귀적으로 많은 호출이 발생하는 방법을 사용할 수 있습니다.
2. **동적 프로그래밍 활용**: 재귀적인 접근 방식은 동일한 값을 여러 번 호출할 수 있어 비효율적입니다.
세부적인 결과를 저장하는 메모이제이션(또는 다이나믹 프로그래밍)을 통해 성능을 개선할 수 있습니다.

이 문제는 층과 호수를 기반으로 테이블을 생성하여, 모든 계산된 값들을 저장할 수 있습니다.

C++ 코드 구현

아래의 코드는 동적 프로그래밍을 사용하여, 주어진 층과 호수의 사람 수를 계산하는 방식입니다:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int T; // 테스트 케이스 수
    cin >> T;
    
    while (T--) {
        int k, n; // k: 호수, n: 층
        cin >> k >> n;
        
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));

        // 0층 초기화
        for (int i = 1; i <= k; ++i) {
            dp[0][i] = 1; // 0층 i호에는 항상 1명
        }

        // DP 테이블 구성
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        // 결과 출력
        cout << dp[n][k] << endl;
    }
    
    return 0;
}

시간 복잡도 분석

위의 구현 방식은 T개의 테스트 케이스에 대해 각각 n층 k호까지 계산하므로, 최악의 경우 O(n * k)의 시간 복잡도를 가집니다.
구현된 동적 프로그래밍 방식은 공간 복잡도 또한 O(n * k)를 요구합니다.

결론

“부녀회장이 될 테야” 문제는 문제의 규칙을 이해하고, 적절한 알고리즘을 선택해 구현함으로써 효율적으로 해결할 수 있습니다.
C++의 동적 프로그래밍 기법을 통해 성능을 극대화할 수 있으며, 이러한 접근은 다양한 유사한 문제를 풀 때에도 유용하게 사용할 수 있습니다.

추가 문제 및 연습

문제를 더 깊이 이해하고 싶다면, 다음과 같은 변형 문제를 시도해보는 것을 추천합니다:

• 층의 수를 고정하고 호수를 변화시키기
• 층과 호수를 반대로 바꿔서 문제를 설정하기
• 기존의 DP 테이블을 최적화하여 공간 복잡도 줄이기