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

문제 설명

주어진 N개의 노드와 N-1개의 간선으로 이루어진 트리가 있습니다. 각 노드는 1부터 N까지의 정수로 번호가 매겨져 있습니다. 두 개의 노드 A와 B가 주어질 때, 이 두 노드의 최소 공통 조상(LCA, Lowest Common Ancestor)을 찾는 문제입니다. 단, 이 문제는 트리가 매우 클 수 있기 때문에, 효율적인 알고리즘을 이용해야 합니다.

입력

• 첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)이 주어진다.
• 둘째 줄에는 N-1개의 간선 정보가 주어진다. 각 간선은 “부모 자식”의 형태로 주어진다.
• 셋째 줄에는 LCA를 찾고자 하는 쿼리의 개수 Q (1 ≤ Q ≤ 100,000)와 각 쿼리에 대해 A, B가 주어진다.

예제 입력

7
1 2
1 3
2 4
2 5
3 6
3 7
4 5
3
4 5
4 6
5 6

예제 출력

2
1
3

해결 전략

최소 공통 조상을 효율적으로 찾기 위해서는 다음과 같은 접근 방식을 사용할 것입니다.

• 트리 구조의 표현: 트리는 인접 리스트를 사용하여 표현됩니다. 각 노드는 부모와 자식으로 연결되어 있으므로, 이를 바탕으로 트리를 구성합니다.
• DFS를 통한 깊이 배열과 부모 배열 생성: DFS(Depth First Search) 알고리즘을 사용하여 각 노드의 깊이를 구하고, 부모 노드를 기록합니다. 이 정보는 LCA를 찾는 데 필수적입니다.
• 이진 제안법: LCA를 효율적으로 찾기 위해 이진 제안법(Fast LCA)을 사용합니다. 두 노드의 깊이를 맞추고, 같은 조상을 찾는 방식으로 진행됩니다.

구현 단계

1. 트리 구조 만들기

먼저 간선 정보를 바탕으로 트리를 구축합니다. 이 과정에서는 부모와 자식 간의 관계를 정의하며, 이를 인접 리스트를 통해 표현합니다.

2. DFS로 깊이 및 부모 배열 생성하기

이제 DFS를 사용하여 각 노드의 깊이와 부모를 기록해야 합니다. 깊이는 각 노드가 루트에서 얼마나 떨어져 있는지를 나타내고, 부모는 다음 단계에서 LCA를 찾는 데 필수적입니다.

3. LCA 함수 구현하기

이진 제안법을 사용하여 두 노드의 최소 공통 조상을 찾는 함수를 구현합니다. 이 함수는 두 노드의 깊이를 비교하고, 필요에 따라 깊이를 맞춘 후 조상을 찾아가는 방식입니다.

4. 쿼리 처리하기

쿼리에서 주어진 두 노드 A와 B에 대해 LCA를 찾아 출력합니다.

코드 구현

#include 
#include 
#include 
#include 

using namespace std;

const int MAX_N = 100000;
const int LOG = 17; // log2(100000) ≈ 16.61

int parent[MAX_N + 1][LOG + 1]; // 부모 배열
int depth[MAX_N + 1];            // 깊이 배열
vector tree[MAX_N + 1];     // 인접 리스트 형식의 트리
int N;

void dfs(int node, int par, int d) {
    depth[node] = d;
    parent[node][0] = par;
    for (int i = 1; i <= LOG; i++) {
        parent[node][i] = parent[parent[node][i - 1]][i - 1];
    }
    
    for (int child : tree[node]) {
        if (child != par) {
            dfs(child, node, d + 1);
        }
    }
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);

    for (int i = LOG; i >= 0; i--) {
        if (depth[parent[a][i]] >= depth[b]) {
            a = parent[a][i];
        }
    }

    if (a == b) return a;

    for (int i = LOG; i >= 0; i--) {
        if (parent[a][i] != parent[b][i]) {
            a = parent[a][i];
            b = parent[b][i];
        }
    }

    return parent[a][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    dfs(1, 0, 0); // 루트는 1
    int Q;
    cin >> Q;

    for (int i = 0; i < Q; i++) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << '\n';
    }

    return 0;
}

마무리

이 문제는 최소 공통 조상을 찾기 위해 DFS와 이진 제안법을 사용하는 방법을 잘 이해하는 데 도움을 줍니다. 트리를 처리하는 다양한 알고리즘을 익히고, 효율적인 코딩 능력을 기르는 데 큰 도움이 될 것입니다. 주어진 문제를 기반으로 다양한 방식으로 트리 구조를 탐색하고 LCA를 찾는 방법을 연습하면, 코딩테스트 준비에 매우 유용할 것입니다.

1. 문제 설명

주어진 두 정수 A와 B에 대해 A와 B의 최소 공배수(Least Common Multiple, LCM)를 구하는 문제입니다. 최소 공배수는 두 수의 배수 중에서 가장 작은 수를 의미합니다. 예를 들어, 4와 5의 최소 공배수는 20입니다.

2. 입력 형식

첫 번째 줄에 정수 A와 B가 주어집니다. (1 ≤ A, B ≤ 10⁶)

3. 출력 형식

주어진 정수 A와 B의 최소 공배수를 출력합니다.

4. 문제 예시

    입력:
    4 5

    출력:
    20
    

5. 알고리즘 설계

최소 공배수를 구하는 일반적인 방법은 두 수의 최대 공약수를 사용하는 것입니다. 다음은 이론입니다.

최소 공배수는 다음과 같이 계산할 수 있습니다:

    LCM(A, B) = (A * B) / GCD(A, B)
    

여기서 GCD는 최대 공약수(Greatest Common Divisor)를 의미합니다. 이를 계산하기 위해 유클리드 알고리즘을 사용할 수 있습니다.

5.1 유클리드 알고리즘

유클리드 알고리즘은 두 수의 GCD를 구하기 위한 고전적인 방법으로, 다음과 같이 작동합니다:

1. 두 수 A와 B 중에서 B가 0이 아닐 경우, A를 B로 나눈 나머지를 C로 저장합니다.
2. A를 B로, B를 C로 업데이트합니다.
3. 이 과정을 B가 0이 될 때까지 반복합니다.
4. 최종적으로 A가 GCD입니다.

6. C++ 코드 구현

이제 최종적으로 C++에서 최소 공배수를 구하는 코드를 구현해보겠습니다.

#include <iostream>
using namespace std;

// 최대 공약수 (GCD) 계산
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 최소 공배수 (LCM) 계산
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {
    int A, B;
    cout << "두 정수 A와 B를 입력하세요: ";
    cin >> A >> B;

    int result = lcm(A, B);
    cout << "최소 공배수는: " << result << endl;
    return 0;
}
    

7. 코드 설명

위 코드는 세 가지 주요 부분으로 나눌 수 있습니다:

1. gcd 함수: 두 정수 A와 B의 최대 공약수를 계산합니다.
2. lcm 함수: 두 정수의 최소 공배수를 계산하는 역할을 합니다.
3. main 함수: 프로그램의 진입점으로, 사용자로부터 입력을 받아 최소 공배수를 출력합니다.

8. 테스트 및 검증

코드를 실제로 테스트하기 위해 다양한 입력 값을 사용하여 올바른 결과를 검증해야 합니다.

    입력: 4 5
    출력: 20

    입력: 12 15
    출력: 60

    입력: 7 3
    출력: 21

    입력: 21 14
    출력: 42

    입력: 1 1000000
    출력: 1000000
    

이러한 다양한 테스트 케이스를 통해 코드의 정확성과 안정성을 검증할 수 있습니다.

9. 성능 고려

최소 공배수 계산은 일반적으로 두 수의 곱의 값을 최대 공약수로 나누기 때문에, 실제 성능은 GCD 알고리즘의 성능에 큰 영향을 받습니다. 유클리드 알고리즘은 O(log(min(A, B)))의 시간 복잡도를 가지므로, 입력 크기에 비례하여 효율적으로 동작합니다.

10. 결론

이번 강좌에서는 두 정수의 최소 공배수를 구하는 방법에 대해 알아보았습니다. 유클리드 알고리즘을 이용한 최대 공약수 계산과 이를 활용한 최소 공배수 계산 방법을 배웠습니다. 이 알고리즘은 다양한 문제 해결에 응용될 수 있으므로, 유용한 기초 지식이 될 것입니다.

1. 문제 정의

최단 경로 구하기 문제는 주어진 그래프에서 두 정점 사이의 최소 거리를 찾는 문제입니다. 그래프는 노드(정점)와 이들을 연결하는 간선(엣지)으로 구성되며, 각 간선은 거리 또는 가중치로 표현됩니다.

예를 들어, 다음과 같은 그래프가 있다고 가정합시다. 여기서 A, B, C, D는 노드이며, 간선은 다음과 같은 가중치를 가집니다:

    A --1-- B
    |      /|
    4     2 |
    |  /      |
    C --3-- D
    

문제는 두 노드 A와 D 간의 최단 경로를 구하는 것입니다.

2. 알고리즘 선택

최단 경로 구하기 문제를 해결하기 위해 일반적으로 사용하는 알고리즘은 다익스트라(Dijkstra) 알고리즘과 벨만-포드(Bellman-Ford) 알고리즘이 있습니다.

이 문제에서는 다익스트라 알고리즘을 사용하겠습니다. 다익스트라 알고리즘은 가중치가 음수가 아닌 그래프에서 최단 경로를 찾는 데 적합합니다.

2.1 다익스트라 알고리즘 설명

다익스트라 알고리즘은 다음과 같은 단계로 작동합니다:

1. 시작 노드를 설정하고, 그 노드에 대한 최단 거리를 0으로 초기화합니다.
2. 모든 다른 노드의 최단 거리를 무한대로 초기화합니다.
3. 방문하지 않은 노드 중 가장 최단 거리 값이 낮은 노드를 선택합니다.
4. 이 노드를 현재 노드로 설정하고, 이 노드를 통해 접근할 수 있는 모든 인접 노드의 최단 거리 값을 업데이트합니다.
5. 모든 노드를 방문할 때까지 3-4 단계를 반복합니다.

3. C++ 구현

이제 C++로 다익스트라 알고리즘을 구현해 보겠습니다. 다음은 위에서 설명한 그래프의 최단 경로를 찾는 코드입니다:

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // numeric_limits를 위해
using namespace std;

// 그래프 구조체 정의
struct Edge {
    int destination;
    int weight;
};

// 다익스트라 알고리즘 구현
vector dijkstra(int start, const vector>& graph) {
    int n = graph.size();
    vector distance(n, numeric_limits::max());
    distance[start] = 0;
    
    priority_queue, vector>, greater>> minHeap;
    minHeap.push({0, start});

    while (!minHeap.empty()) {
        int currentDistance = minHeap.top().first;
        int currentNode = minHeap.top().second;
        minHeap.pop();

        // 현재 노드의 거리 값이 더 크면 무시
        if (currentDistance > distance[currentNode]) continue;

        // 인접 노드 탐색
        for (const Edge& edge : graph[currentNode]) {
            int newDistance = currentDistance + edge.weight;
            if (newDistance < distance[edge.destination]) {
                distance[edge.destination] = newDistance;
                minHeap.push({newDistance, edge.destination});
            }
        }
    }

    return distance;
}

int main() {
    // 그래프 초기화
    int n = 4; // 노드 개수
    vector> graph(n);
    
    // 간선 추가 (0-based index)
    graph[0].push_back({1, 1});
    graph[0].push_back({2, 4});
    graph[1].push_back({2, 2});
    graph[1].push_back({3, 1});
    graph[2].push_back({3, 3});
    
    int startNode = 0; // A
    vector shortestPaths = dijkstra(startNode, graph);

    // 결과 출력
    cout << "최단 경로:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "A에서 " << char('A' + i) << "까지의 최단 경로: ";
        if (shortestPaths[i] == numeric_limits::max()) {
            cout << "도달 불가능" << endl;
        } else {
            cout << shortestPaths[i] << endl;
        }
    }

    return 0;
}
    

4. 코드 설명

4.1 그래프 구조 설정

먼저, 간선 구조체를 정의하여 각 노드와 가중치 정보를 포함한 그래프를 설정합니다. vector<vector<Edge>>를 사용하여 그래프를 표현합니다.

4.2 다익스트라 구현

다익스트라 알고리즘을 위한 함수 dijkstra를 작성했습니다. 시작 노드에서부터 각 노드까지의 최단 거리를 계산하여 distance 벡터에 저장합니다. priority_queue를 사용하여 현재까지의 최단 경로를 효율적으로 관리합니다.

4.3 메인 함수

main 함수에서 그래프를 초기화하고, 다익스트라 함수를 호출하여 최단 경로를 구한 뒤, 결과를 출력합니다.

5. 복잡도 분석

다익스트라 알고리즘의 시간 복잡도는 사용된 자료 구조에 따라 달라집니다. 일반적으로 힙을 사용할 경우 O(E log V)로 나타내며, 여기서 E는 간선의 수, V는 노드의 수입니다.

6. 참고 자료

• 다익스트라 알고리즘 – 위키백과
• 지크스포크스 – 다익스트라 알고리즘 구현

7. 결론

이번 글에서는 C++을 이용한 다익스트라 알고리즘을 통해 주어진 그래프에서 최단 경로를 구하는 방법을 배웠습니다. 알고리즘의 기본 개념, C++ 구현 방법과 예제를 통해 이해를 심화시킬 수 있었습니다. 실제 코딩 테스트에서는 이러한 알고리즘을 문제 해결에 응용하는 것이 중요합니다. 지속적으로 다양한 문제를 해결하며 경험을 쌓아 나가시길 바랍니다.

1. 서론

프로그래밍 대회나 코딩 테스트에서 자주 등장하는 문제 중 하나는 두 수의 최대 공약수(GCD, Greatest Common Divisor)를 구하는 문제입니다.
최대 공약수는 두 개의 자연수에서 공통으로 나누어 떨어지는 가장 큰 수를 의미합니다.
이 글에서는 C++을 사용하여 최대 공약수를 구하는 알고리즘을 설명하고, 문제를 해결하는 과정을 자세히 알아보겠습니다.

2. 문제 정의

두 개의 자연수 a와 b가 주어졌을 때, 이 두 수의 최대 공약수를 구하는 프로그램을 작성하시오.
입력으로 두 개의 자연수 a, b (1 <= a, b <= 1,000,000)가 주어지며, 결과로 최대 공약수 값을 출력해야 합니다.

예제 입력


48 18


예제 출력


6


3. 알고리즘 설명

최대 공약수를 구하는 방법에는 여러 가지가 있습니다.
여기서는 유클리드 호제법(Euclidean algorithm)을 사용하여 효율적으로 최대 공약수를 찾는 방법을 설명하겠습니다.
유클리드 호제법은 다음과 같은 원리를 기반으로 합니다.

두 수 a와 b의 최대 공약수 GCD(a, b)는 GCD(b, a mod b)와 같습니다.

이 과정을 반복하여 b가 0이 될 때까지 계속하면, a가 두 수의 최대 공약수가 됩니다.
즉, GCD(a, 0) = a이므로 마지막 남은 숫자가 최대 공약수입니다.

유클리드 호제법의 의사코드

    function GCD(a, b):
        while b ≠ 0:
            temp := b
            b := a mod b
            a := temp
        return a
    

4. C++ 코드 구현

위에서 설명한 알고리즘을 기반으로 C++로 최대 공약수(GCD)를 구하는 프로그램을 작성해보겠습니다.
다음은 해당 프로그램의 소스 코드입니다.

    #include <iostream>

    using namespace std;

    int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    int main() {
        int a, b;
        cout << "두 개의 자연수를 입력하세요: ";
        cin >> a >> b;

        cout << "최대 공약수 (GCD): " << gcd(a, b) << endl;

        return 0;
    }
    

5. 코드 설명

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

• 헤더 파일 포함: #include <iostream>를 사용하여 입출력 스트림을 사용할 수 있도록 설정합니다.
• gcd 함수 정의: 두 개의 정수 a, b를 매개변수로 받아 최대 공약수를 계산하는 함수를 정의합니다.
• 메인 함수: 사용자로부터 두 개의 자연수를 입력받고, gcd 함수를 호출하여 결과를 출력합니다.

6. 테스트 케이스

위에 작성한 코드가 올바르게 작동하는지 확인하기 위해 몇 가지 테스트 케이스를 정의해보겠습니다.

테스트 케이스 1

입력


48 18


출력


6


테스트 케이스 2

입력


100 25


출력


25


테스트 케이스 3

입력


13 29


출력


1


7. 시간 복잡도 분석

유클리드 호제법의 시간 복잡도는 O(log(min(a, b)))입니다.
이는 두 수의 크기가 작아질수록 계산 시간이 줄어들기 때문입니다.
따라서 이 알고리즘은 효율적으로 최대 공약수를 계산할 수 있는 방법 중 하나입니다.

8. 결론

이번 글에서는 C++를 이용하여 최대 공약수를 구하는 방법에 대해 알아보았습니다.
유클리드 호제법을 사용하여 효과적으로 문제를 해결하는 과정을 살펴보았습니다.
알고리즘 문제 풀이에 있어, 이러한 기본적인 수학적 지식과 알고리즘은 매우 중요하니, 충분히 연습하고 숙지해두시길 권장합니다.

9. 참고 자료

• 정수론 – 위키백과
• Euclidean algorithm – Wikipedia

문제 설명

N명의 학생들이 교실에서 줄을 서고 있습니다. 각 학생의 키는 배열로 주어지며, 주어진 키 순서와 다르게 서 있을 경우, 학생들은 자신의 위치를 바꿔줄 수 있습니다.
이때, 학생들을 키의 오름차순으로 정렬하기 위한 최소의 스왑 수를 구하는 문제입니다.

입력 형식

첫 번째 줄에 학생의 수 N이 주어집니다. (1 ≤ N ≤ 1000)
두 번째 줄에는 N명의 학생의 키가 공백으로 구분되어 주어집니다. 각 키는 1 이상 1000 이하의 정수입니다.

출력 형식

최소 스왑 수를 출력합니다.

예제 입력/출력

        입력:
        5
        5 3 2 4 1
        
        출력:
        4
    

문제 풀이

이 문제를 해결하기 위해 우리는 다음 단계를 따릅니다:

1단계: 문제 이해하기

주어진 학생의 키를 오름차순으로 정렬하기 위한 최소 스왑 수를 찾는 것입니다.
예를 들어, 위의 입력에서 학생들은 {5, 3, 2, 4, 1}의 순서로 서 있었고, 이를 {1, 2, 3, 4, 5}로 바꿔야 합니다.
이 과정에서 몇 번의 교환이 필요한지를 세는 것이 목표입니다.

2단계: 접근 방법

최적의 스왑 수를 찾기 위해서는 각 스왑을 통해 배열의 순서를 한 단계씩 정렬하는 것이 효과적입니다.
우리는 다음과 같은 방법으로 이 문제를 해결할 수 있습니다:

1. 학생들의 키와 그 인덱스를 쌍으로 묶어 주어진 리스트를 정렬합니다.
2. 각 학생의 현재 위치와 정렬된 위치를 비교합니다.
3. 스왑을 통해 학생들을 정렬된 위치로 이동해야 하며, 이미 방문한 학생들은 다시 고려하지 않습니다.

3단계: 알고리즘 구현

        #include 
        #include 
        #include 
        
        using namespace std;

        // 구조체 정의: 인덱스와 키를 쌍으로 관리
        struct Student {
            int index;
            int height;
        };

        // 스왑 함수를 정의
        void swap(Student& a, Student& b) {
            Student temp = a;
            a = b;
            b = temp;
        }

        int minSwaps(vector& heights) {
            int n = heights.size();
            vector students(n);
            for (int i = 0; i < n; i++) {
                students[i] = {i, heights[i]};
            }
            
            // 학생들을 키 기준으로 정렬
            sort(students.begin(), students.end(), [](Student a, Student b) {
                return a.height < b.height;
            });
            
            vector visited(n, false);
            int swapCount = 0;
            
            for (int i = 0; i < n; i++) {
                if (visited[i] || students[i].index == i) {
                    continue;
                }
                
                // 사이클의 크기를 계산
                int cycle_size = 0;
                int j = i;
                while (!visited[j]) {
                    visited[j] = true;
                    j = students[j].index;
                    cycle_size++;
                }
                
                if (cycle_size > 0) {
                    swapCount += (cycle_size - 1);
                }
            }
            return swapCount;
        }

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

            cout << "학생들의 키를 입력하세요: ";
            for (int i = 0; i < n; i++) {
                cin >> heights[i];
            }

            int result = minSwaps(heights);
            cout << "최소 스왑 수: " << result << endl;
            return 0;
        }
    

4단계: 코드 설명

위의 코드는 C++로 작성된 줄 세우기 문제의 해결 방법을 보여줍니다.

• 구조체 Student: 인덱스와 학생의 키를 쌍으로 묶어 관리합니다.
• swap 함수: 두 학생의 정보를 스왑합니다.
• minSwaps 함수: 최소 스왑 수를 계산하는 주 함수입니다. 학생 리스트를 정렬하고, 각 방문 여부를 체크하여 사이클을 계산합니다.
• main 함수: 사용자로부터 입력을 받고 결과를 출력하는 주 함수입니다.

5단계: 테스트 및 검증

코드를 작성한 후 다양한 케이스로 테스트를 수행합니다.
다양한 입력을 통해 예상되는 출력과 일치하는지 확인해야 합니다.
예를 들어, 가장 간단한 테스트 케이스를 추가하여 정확성을 검사합니다:

        입력:
        3
        3 1 2
        
        출력:
        2
    

추가적으로, 큰 입력을 통해 성능을 확인하는 것도 중요합니다.

결론

이 문제를 통해 스왑과 정렬의 개념, 구조체의 활용 및 알고리즘의 복잡성에 대한 이해를 높일 수 있었습니다.
C++ 코딩테스트에서 자주 출제되는 유형이므로, 충분한 연습을 통해 알고리즘적 사고를 키워야 합니다.

참고자료

• GeeksforGeeks
• Codewars
• LeetCode