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

본 강좌에서는 최소 신장 트리(Minimum Spanning Tree, MST)에 대해 배워보겠습니다. 최소 신장 트리는 가중치가 있는 그래프에서 모든 정점을 포함하면서도 가중치의 총합이 최소가 되도록 하는 트리입니다. 이러한 문제는 여러 분야에서 응용 가능하며, 특히 네트워크 설계, 도로 건설, 통신망 구축 등에서 중요한 역할을 합니다.

문제 설명

다음과 같은 가중치가 있는 무방향 그래프가 주어졌을 때, 최소 신장 트리를 구하시오.

입력:
첫 줄에 정점의 수 V와 간선의 수 E가 주어진다. (1 ≤ V ≤ 1000, 1 ≤ E ≤ 10000)
다음 E줄에는 각각의 간선 정보 u, v, w가 주어진다. 이는 정점 u와 정점 v를 연결하는 간선의 가중치가 w라는 의미이다.

출력:
최소 신장 트리의 가중치 총합을 출력하시오.

예제 입력

3 3
1 2 1
2 3 2
1 3 3

예제 출력

3

해결 방법

이 문제를 해결하기 위해 Prim 알고리즘 또는 Kruskal 알고리즘을 사용할 수 있습니다. 여기서는 Kruskal 알고리즘을 사용하여 풀이해보겠습니다.

Kruskal 알고리즘 설명

Kruskal 알고리즘은 간선 기반의 알고리즘으로, 다음과 같은 단계로 진행됩니다:

1. 모든 간선을 가중치의 오름차순으로 정렬한다.
2. 정점 집합을 초기화한다. (Union-Find 자료구조를 사용)
3. 간선을 하나씩 선택하여 두 정점이 서로 연결되어 있지 않으면 이 간선을 선택한다. 이런 과정을 반복하여 모든 정점을 연결하는 최소 신장 트리를 만든다.

코드 구현

이제 C++로 Kruskal 알고리즘을 구현해보겠습니다.

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

using namespace std;

struct Edge {
    int u, v, weight;
};

bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

int find(int parent[], int x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}

void unionSet(int parent[], int rank[], int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);

    if (rootX != rootY) {
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

int kruskal(int V, vector& edges) {
    sort(edges.begin(), edges.end(), compare);
    int parent[V + 1];
    int rank[V + 1];
    for (int i = 0; i <= V; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    int totalWeight = 0;
    for (Edge edge : edges) {
        if (find(parent, edge.u) != find(parent, edge.v)) {
            totalWeight += edge.weight;
            unionSet(parent, rank, edge.u, edge.v);
        }
    }
    return totalWeight;
}

int main() {
    int V, E;
    cin >> V >> E;
    vector edges(E);
    for (int i = 0; i < E; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
    }
    cout << kruskal(V, edges) << endl;
    return 0;
}

코드 설명

먼저, Edge 구조체를 정의하고 비교 함수로 가중치를 기준으로 정렬합니다.

find 함수는 경로 압축 기법을 사용하여 효율적으로 부모 노드를 찾습니다. unionSet 함수는 두 정점의 집합을 합치는 역할을 하며, 랭크를 사용하여 트리가 너무 커지지 않도록 합니다.

메인 함수에서는 입력을 받고 Kruskal 알고리즘을 통해 최소 신장 트리의 가중치 총합을 구하여 출력합니다.

복잡도 분석

Kruskal 알고리즘의 시간 복잡도는 O(E log E)입니다. 이는 간선 정렬에 소요되는 시간입니다. Union-Find의 연산을 최적화할 경우 매우 효율적인 알고리즘으로 작동합니다.

결론

최소 신장 트리는 많은 실제 문제에서 사용되므로 이를 체계적으로 이해하는 것이 중요합니다. 본 예제를 통해 Kruskal 알고리즘을 적용하여 MST를 찾는 방법을 학습하였으며, 다양한 변형 문제에도 적용할 수 있는 기반 이론을 습득하게 되었습니다. 추가적으로 Prim 알고리즘도 실습해보시길 권장합니다.

다음 강좌에서는 최소 신장 트리에 대한 다른 알고리즘이나 다양한 문제 풀기를 다룰 예정이니 많은 기대 바랍니다.

안녕하세요! 이번 포스트에서는 최소 비용 구하기라는 주제로 C++ 알고리즘 문제를 다뤄보겠습니다. 이 문제는 여러 상황에서 최적의 해결책을 찾는 데 유용하게 쓰이는 알고리즘 개념들을 살펴보는 좋은 기회가 될 것입니다. 이 글을 통해 우리는 문제분석, 알고리즘 선택, 코드 구현, 테스트, 그리고 최적화 방법까지 상세히 알아보겠습니다.

문제 설명

우리에게는 여러 개의 도시와 이들 사이의 도로가 있습니다. 각 도로는 특정 비용을 가지고 있습니다. 주어진 여러 도시들 간에 이동할 때, 우리의 목표는 시작 도시에서 목표 도시까지의 최소 이동 비용을 구하는 것입니다. 이를 다익스트라 알고리즘을 통해 해결할 수 있습니다.

문제 정의

다음은 문제의 수학적 정의입니다:

• 주어진 도시의 수 n (1 이상 10,000 이하)
• 경로의 개수 m (1 이상 100,000 이하)
• 각 경로는 u, v, cost의 형태로 입력됩니다. 이는 도시 u에서 도시 v로 가는 비용이 cost라는 것을 의미합니다.
• 시작 도시 start와 목표 도시 end가 주어집니다.

입력

    n m
    u1 v1 cost1
    u2 v2 cost2
    ...
    um vm costm
    start end
    

출력

목표 도시까지 가는 최소 비용을 출력합니다. 만약 도착할 수 없다면 -1을 출력합니다.

알고리즘 선택

이 문제는 가중치 그래프에서 최단 경로를 찾는 문제로, 대표적인 알고리즘인 다익스트라 알고리즘을 사용하여 해결할 수 있습니다. 다익스트라 알고리즘은 O((n + m) log n)의 시간 복잡도를 가지므로, 최대 입력 조건에서도 효율적으로 동작합니다.

다익스트라 알고리즘 개요

다익스트라 알고리즘의 기본 아이디어는 다음과 같습니다:

1. 시작 노드를 선택하고, 이 노드까지의 거리를 0으로 초기화합니다.
2. 나머지 모든 노드까지의 거리를 무한대로 초기화합니다.
3. 현재 노드와 인접한 노드로의 거리를 계산하여, 더 짧은 거리가 발견되면 거리를 업데이트합니다.
4. 모든 노드가 방문될 때까지 과정을 반복합니다.

문제 해결 과정

1단계: 문제 분석

주어진 입력을 통해 그래프를 구성하고, 각 도시에 대한 비용 정보를 저장할 데이터 구조가 필요합니다. 우리는 인접 리스트를 사용할 것입니다.

2단계: 코드 구현

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

vector<pair<int, int>> graph[10001];

void dijkstra(int start, int n) {
    vector<int> cost(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    cost[start] = 0;
    pq.push(make_pair(0, start));

    while (!pq.empty()) {
        int currentCost = pq.top().first;
        int currentNode = pq.top().second;
        pq.pop();

        if (currentCost > cost[currentNode]) continue;

        for (auto &edge : graph[currentNode]) {
            int nextNode = edge.first;
            int nextCost = edge.second;

            if (cost[currentNode] + nextCost < cost[nextNode]) {
                cost[nextNode] = cost[currentNode] + nextCost;
                pq.push(make_pair(cost[nextNode], nextNode));
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (cost[i] == INF) {
            cout << -1 << endl;  // 도달할 수 없는 경우
        } else {
            cout << cost[i] << endl;
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int u, v, cost;
        cin >> u >> v >> cost;
        graph[u].push_back(make_pair(v, cost));
        graph[v].push_back(make_pair(u, cost));  // 양방향 도로 가정
    }

    int start, end;
    cin >> start >> end;

    dijkstra(start, n);
    
    return 0;
}
    

3단계: 코드 테스트

위 코드를 통해 입력을 테스트합니다. 예를 들어, 다음 입력을 통해 테스트를 해 볼 수 있습니다:

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

위 입력은 도시 5개와 6개의 도로가 있는 경우로, 시작 도시가 1번, 목표 도시가 5번입니다. 이 경우 알고리즘은 최소 비용으로 1번 도시에서 5번 도시까지 가는 방법을 출력해야 합니다.

4단계: 최적화

다익스트라 알고리즘은 일반적으로 Priority Queue를 사용하여 구현하지만, 제한이 있는 경우에는 Fibonacci Heap 등을 사용할 수 있습니다. 그러나 이 글에서는 일반적인 Priority Queue를 사용하여 간단하고 효율적인 구현을 보여주었습니다.

결론

이번 강좌에서는 C++로 최소 비용 구하기 문제를 해결하는 방법을 살펴보았습니다. 다익스트라 알고리즘의 원리를 이해하고 이를 실제 문제에 어떻게 적용하는지 다뤘습니다. 이는 코딩 테스트를 대비하는 데 도움이 될 것입니다.

계속해서 더 많은 알고리즘 문제를 해결하는 방법을 배우고 연습하시길 바랍니다. 감사합니다!

안녕하세요! 이번 블로그 포스트에서는 C++을 이용한 코딩 테스트에서 자주 출제되는 문제 중 하나인 최소 신장 트리(Minimum Spanning Tree)에 대해 다뤄보겠습니다. 우리는 Prim 알고리즘과 Kruskal 알고리즘을 사용할 것이며, 구체적인 문제를 풀어보며 이론을 정리할 것입니다.

문제 설명

다음과 같은 그래프가 주어질 때, 최소 신장 트리를 구하시오. 최종적으로 트리의 가중치의 합을 출력한다.

입력:
5 7
1 2 3
1 3 4
2 3 2
2 4 6
3 4 1
3 5 5
4 5 2

출력:
6

여기서 입력의 구조는 다음과 같습니다:

• 첫 번째 줄: 정점의 수 V와 간선의 수 E
• 그 다음 E개의 줄: 각 간선의 정보 (정점1, 정점2, 가중치)

문제 해결 방법

위의 문제를 해결하기 위해 Prim 알고리즘과 Kruskal 알고리즘을 사용할 수 있습니다. 여기서는 Prim 알고리즘을 사용하여 문제를 풀어보겠습니다. Prim 알고리즘은 임의의 정점에서 시작해, 가장 작은 가중치의 간선을 선택하여 점차 그래프를 확장하는 방식입니다.

1. Prim 알고리즘 개요

Prim 알고리즘은 다음의 단계로 이루어집니다:

1. 시작 정점을 선택하고, 이에 연결된 간선 중에서 최소 가중치의 간선을 선택합니다.
2. 선택한 간선에 연결된 정점을 포함시킵니다.
3. 위의 과정을 반복하여 모든 정점을 포함할 때까지 진행합니다.

2. C++로 Prim 알고리즘 구현하기

이제 Prim 알고리즘을 C++로 구현해보겠습니다. 이 구현을 통해 실제 문제를 해결하는 과정을 살펴보겠습니다.

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAX_V = 100; // 최대 정점 수
const int INF = 1e9; // 무한대 표시

vector> graph[MAX_V]; // 인접 리스트
int key[MAX_V]; // 최소 가중치 배열
bool inMST[MAX_V]; // MST 포함 여부

int prim(int start, int V) {
    priority_queue, vector>, greater>> pq;
    fill(key, key + V, INF);
    fill(inMST, inMST + V, false);

    key[start] = 0; // 시작 정점의 키 값은 0
    pq.push({0, start}); // (가중치, 정점)

    int totalWeight = 0; // 최소 신장 트리의 총 가중치

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

        if (inMST[u]) continue; // 이미 MST에 포함된 경우

        totalWeight += key[u]; // 총 가중치에 현재 정점의 키 값을 추가
        inMST[u] = true; // MST에 추가

        for (auto& edge : graph[u]) {
            int v = edge.first;
            int weight = edge.second;

            // 현재 간선이 MST에 포함되지 않고, 가중치가 더 작은 경우
            if (!inMST[v] && weight < key[v]) {
                key[v] = weight; // 최소 가중치 업데이트
                pq.push({key[v], v}); // 큐에 추가
            }
        }
    }

    return totalWeight;
}

int main() {
    int V, E;
    cin >> V >> E;

    for (int i = 0; i < E; i++) {
        int u, v, weight;
        cin >> u >> v >> weight;
        // 0-indexed로 저장
        graph[u - 1].push_back({v - 1, weight});
        graph[v - 1].push_back({u - 1, weight});
    }

    cout << prim(0, V) << endl; // 시작 정점 0
    return 0;
}

3. 코드 설명

위 코드의 설명은 다음과 같습니다:

• 그래프는 인접 리스트를 사용하여 표현합니다. 각 정점은 연결된 정점과 그 가중치를 가지는 리스트로 되어 있습니다.
• 우선순위 큐를 사용하여 현재 정점에서 연결된 간선 중 최소 가중치의 간선을 효율적으로 선택합니다.
• MST에 포함된 정점은 inMST 배열로 관리합니다.
• 최종적으로 모든 정점을 포함한 MST의 총 가중치를 반환합니다.

4. 실행 예시

입력 데이터를 실행하면 다음과 같은 결과가 나옵니다:

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

출력 결과:

6

Kruskal 알고리즘을 통한 최소 신장 트리 구하기

Prim 알고리즘에 이어, Kruskal 알고리즘을 사용하여 동일한 문제를 해결하는 방법을 살펴보겠습니다. Kruskal 알고리즘은 간선을 기준으로 동작하며, 모든 간선을 가중치 기준으로 정렬한 후 작은 것부터 추가하는 방식입니다.

1. Kruskal 알고리즘 개요

Kruskal 알고리즘은 다음의 단계로 이루어집니다:

1. 간선을 가중치 기준으로 정렬합니다.
2. 가장 작은 간선을 선택하여 사이클이 생기지 않는 경우 MST에 추가합니다.
3. 모든 간선을 처리할 때까지 반복합니다.

2. C++로 Kruskal 알고리즘 구현하기

이제 Kruskal 알고리즘을 C++로 구현해보겠습니다.

#include 
#include 
#include 
using namespace std;

struct Edge {
    int u, v, weight;
};

bool compare(Edge a, Edge b) {
    return a.weight < b.weight;
}

int find(int parent[], int u) {
    if (parent[u] != u) {
        parent[u] = find(parent, parent[u]); // 경로 압축
    }
    return parent[u];
}

void unionSet(int parent[], int rank[], int u, int v) {
    int root_u = find(parent, u);
    int root_v = find(parent, v);
    
    if (root_u != root_v) {
        if (rank[root_u] > rank[root_v]) {
            parent[root_v] = root_u;
        } else if (rank[root_u] < rank[root_v]) {
            parent[root_u] = root_v;
        } else {
            parent[root_v] = root_u;
            rank[root_u]++;
        }
    }
}

int kruskal(int V, vector& edges) {
    sort(edges.begin(), edges.end(), compare);
    int parent[V], rank[V];
    for (int i = 0; i < V; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    int totalWeight = 0; // MST의 총 가중치
    for (Edge edge : edges) {
        int u = edge.u, v = edge.v;
        
        // 사이클이 발생하지 않는 경우 MST에 추가
        if (find(parent, u) != find(parent, v)) {
            unionSet(parent, rank, u, v);
            totalWeight += edge.weight; // 가중치 추가
        }
    }
    
    return totalWeight;
}

int main() {
    int V, E;
    cin >> V >> E;
    vector edges(E);

    for (int i = 0; i < E; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
        edges[i].u--; // 0-indexed
        edges[i].v--; // 0-indexed
    }

    cout << kruskal(V, edges) << endl; // MST의 총 가중치 출력
    return 0;
}

3. 코드 설명

위 코드의 설명은 다음과 같습니다:

• 간선을 저장하는 구조체 Edge를 정의합니다.
• 간선을 가중치 기준으로 정렬합니다.
• 유니온-파인드(Union-Find) 자료구조를 이용해 사이클을 체크하고, 사이클이 발생하지 않으면 간선을 MST에 추가합니다.

4. 실행 예시

입력 데이터를 실행하면 다음과 같은 결과가 나옵니다:

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

출력 결과:

6

결론

이번 시간에는 최소 신장 트리 문제를 Prim 알고리즘과 Kruskal 알고리즘을 통해 해결하는 방법에 대해 배우았습니다. 각 알고리즘의 특징과 실제 구현 방식을 이해하는 것이 중요하며, 다양한 문제를 해결하기 위해 이러한 알고리즘을 숙지해야 합니다.

최소 신장 트리 문제는 그래프 이론의 기본 개념 중 하나이며, 알고리즘 문제에서도 자주 등장합니다. 위의 구현을 활용하여 다양한 그래프 문제를 효율적으로 해결할 수 있도록 연습하시기 바랍니다.

뷰어 여러분께서도 이 강좌가 도움이 되었기를 바라며, 추가적인 질문이 있으면 댓글로 남겨주세요. 다음 포스트에는 또 다른 알고리즘 문제를 다룰 예정입니다. 감사합니다!

안녕하세요! 이번 강좌에서는 코딩테스트에서 자주 출제되는 개념 중 하나인 ‘최소 공통 조상’에 대해 다루어 보겠습니다. 이 강좌는 C++를 사용하여 문제를 해결하는 방법을 배우는 데 중점을 두고 있습니다. 먼저 최소 공통 조상이 무엇인지, 그리고 이를 찾기 위한 알고리즘을 자세히 설명하겠습니다.

1. 문제 설명

주어진 이진 트리에서 두 개의 노드가 있을 때, 이 노드의 최소 공통 조상을 찾는 문제를 다룰 것입니다. 이진 트리의 노드는 부모 노드와 자식 노드의 관계를 가지며, 각 노드는 고유한 값을 가집니다.

문제 정의

이진 트리와 두 노드 A, B가 주어질 때, A와 B의 최소 공통 조상을 찾아 반환하는 함수를 작성하시오.

입력 형식

• 이진 트리: 트리의 루트 노드가 주어집니다.
• 두 노드 A와 B: 두 노드는 트리 내의 유효한 노드입니다.

출력 형식

노드 A와 B의 최소 공통 조상을 반환합니다. 만약 공통 조상이 없다면 nullptr을 반환합니다.

예제 입력

     3
    / \
   5   1
  / \ / \
 6  2 0  8
   / \
  7   4

예제 출력

최소 공통 조상: 5 (A: 5, B: 1)

2. 알고리즘 접근 방법

최소 공통 조상을 찾기 위해 주로 사용되는 두 가지 접근 방법이 있습니다:

1. 재귀적인 방법
2. 탐색 트리의 부모를 저장하여 간접적으로 탐색하는 방법

2.1. 재귀적 접근 방법

가장 일반적인 방법은 트리의 루트에서 시작하여 재귀적으로 탐색하는 것입니다. 두 노드가 현재 노드의 왼쪽 또는 오른쪽 서브트리에 있을 때, 그 서브트리를 계속 탐색합니다. 만약 현재 노드가 A 또는 B를 발견하면 해당 노드를 반환하고, 두 노드를 모두 찾으면 현재 노드를 반환합니다.

2.2. 부모 저장 방법

이 방법은 각 노드의 부모 정보를 저장하는 것입니다. 두 노드의 조상을 부모 정보를 통해 간접적으로 찾아가며 공통 조상을 찾는 방법입니다. 하지만 이 방법은 추가적인 메모리를 사용해야 합니다.

3. C++ 코드 구현

아래는 최소 공통 조상을 찾기 위한 C++ 코드입니다.

#include 
using namespace std;

// 이진 트리 노드 정의
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 최소 공통 조상을 찾는 함수
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    // 기본 사례: root가 nullptr이거나 p 또는 q인 경우
    if (root == nullptr || root == p || root == q) {
        return root;
    }

    // 왼쪽과 오른쪽 서브트리에서 최소 공통 조상 검색
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);

    // 각 서브트리에서 공통 조상이 발견된 경우
    if (left != nullptr && right != nullptr) {
        return root; // 현재 노드가 최소 공통 조상
    }

    // 하나의 서브트리에서만 공통 조상이 발견된 경우
    return left != nullptr ? left : right;
}

// 메인 함수
int main() {
    // 이진 트리 생성
    TreeNode *root = new TreeNode(3);
    TreeNode *n1 = new TreeNode(5);
    TreeNode *n2 = new TreeNode(1);
    TreeNode *n3 = new TreeNode(6);
    TreeNode *n4 = new TreeNode(2);
    TreeNode *n5 = new TreeNode(0);
    TreeNode *n6 = new TreeNode(8);
    TreeNode *n7 = new TreeNode(7);
    TreeNode *n8 = new TreeNode(4);

    root->left = n1;
    root->right = n2;
    n1->left = n3;
    n1->right = n4;
    n2->left = n5;
    n2->right = n6;
    n4->left = n7;
    n4->right = n8;

    // 최소 공통 조상 호출
    TreeNode* ancestor = lowestCommonAncestor(root, n1, n2);
    cout << "최소 공통 조상: " << ancestor->val << endl;

    return 0;
}

4. 코드 설명

위의 코드는 이진 트리에서 두 노드 A와 B의 최소 공통 조상을 찾는 방법을 구현한 것입니다. 이제 각 부분에 대해 설명하도록 하겠습니다.

4.1. TreeNode 구조체

TreeNode 구조체는 이진 트리의 노드를 정의합니다. 각 노드는 정수 값과 왼쪽 및 오른쪽 자식 노드를 가리키는 포인터를 포함합니다.

4.2. lowestCommonAncestor 함수

• 기본 사례를 처리합니다: root가 nullptr이거나 현재 노드가 A 또는 B인 경우 해당 노드를 반환합니다.
• 왼쪽과 오른쪽 서브트리에서 각각 최소 공통 조상을 검색합니다.
• 왼쪽과 오른쪽 서브트리 모두에서 노드를 찾은 경우, 현재 노드를 반환합니다.
• 하나의 서브트리에서만 발견된 경우 그 서브트리의 조상을 반환합니다.

4.3. 메인 함수

이진 트리를 생성하고, 두 노드 A와 B를 지정하여 최소 공통 조상을 검색하는 함수 호출을 포함합니다. 결과는 콘솔에 출력됩니다.

5. 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)입니다. 여기서 N은 이진 트리의 노드 개수입니다. 모든 노드를 탐색할 수 있으므로 최악의 경우에는 모든 노드를 확인해야 할 수 있습니다.

공간 복잡도는 O(H)입니다. 여기서 H는 이진 트리의 높이입니다. 최악의 경우에는 스택 깊이가 트리의 깊이와 같아질 수 있습니다.

6. 맺음말

이번 강좌에서는 최소 공통 조상 문제를 다루었습니다. 이 문제는 이진 트리와 관련된 다양한 알고리즘 문제에서 출제되는 빈도가 높기 때문에, 충분히 이해하고 연습하는 것이 중요합니다. 각자의 이해도를 높이기 위해 추가적인 문제를 풀어보는 것도 좋은 방법입니다.

감사합니다! 다음 강좌에서는 또 다른 흥미로운 알고리즘 주제를 다루겠습니다. 질문이나 의견이 있으시면 댓글로 남겨주세요.

본 강좌에서는 C++ 프로그래밍을 이용해 최소 공통 조상(Lowest Common Ancestor, LCA)을 구하는 문제를 다룹니다.
최소 공통 조상은 두 노드의 조상이면서 두 조상 중 가장 깊은 노드를 의미합니다. 이 문제는 트리 자료구조와 깊이 우선 탐색(DFS)을 이해하는 데 유용합니다.

문제 설명

트리가 주어질 때, 두 노드 A와 B의 최소 공통 조상을 구하는 문제를 해결해야 합니다.
트리는 비어 있지 않으며, 중복된 노드는 없다고 가정합니다. 노드의 번호는 1부터 시작합니다.

입력 형식

N
A B
에서 N은 노드의 수, A와 B는 최소 공통 조상을 찾을 두 노드입니다. 

트리는 다음과 같이 주어집니다.
부모 노드와 자식 노드로 이루어진 M개의 줄이 주어지며, 
각 줄은 'P C' 형식으로 부모 P와 자식 C를 나타냅니다.

출력 형식

두 노드 A와 B의 최소 공통 조상의 노드 번호를 출력합니다.

예제

입력

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

출력

4

문제 분석

주어진 예제에서 트리는 다음과 같이 나타낼 수 있습니다:

        1
       / \
      4   7
     / \
    5   6
   /     \
  3       2

노드 A(5)와 B(3)의 최상위 부모인 4가 최소 공통 조상입니다.
만약 노드 A와 B가 동일한 경우, 그 노드 자체가 최소 공통 조상이 됩니다.

알고리즘 접근법

최소 공통 조상을 찾기 위해 다양한 알고리즘이 존재하지만, 여기에서는 깊이 우선 탐색(DFS)와 부모 노드 추적 방식을 이용한 방법을 설명하겠습니다.

1. 트리 구조 저장

먼저 인접 리스트를 사용하여 트리를 저장하겠습니다. 부모 노드를 알고 있다면 자식 노드를 리스트에 추가하는 방식으로 트리를 구성합니다.

2. DFS를 통한 깊이 저장

각 노드의 깊이를 저장하고, 노드의 부모를 추적하여 LCA를 찾는 방법입니다.
각 노드에 대해 탐색하면서 깊이를 기록하고, 부모 노드도 함께 저장합니다.

3. LCA 구하기

두 노드 A와 B의 깊이를 비교하여 깊이가 얕은 노드를 올리면서 부모 노드를 추적합니다.
두 노드가 같아지면 그 노드가 LCA입니다.

C++ 코드 구현

다음은 C++를 사용한 알고리즘 코드입니다:

#include 
#include 
#include 

using namespace std;

vector tree[100001];
int parent[100001];
int depth[100001];

// DFS를 통한 깊이와 부모 저장
void dfs(int node, int par, int dep) {
    parent[node] = par;
    depth[node] = dep;
    for (int child : tree[node]) {
        if (child != par) {
            dfs(child, node, dep + 1);
        }
    }
}

// 두 노드의 LCA 구하기
int findLCA(int a, int b) {
    // 깊이 맞추기
    while (depth[a] > depth[b]) {
        a = parent[a];
    }
    while (depth[b] > depth[a]) {
        b = parent[b];
    }

    // LCA 찾기
    while (a != b) {
        a = parent[a];
        b = parent[b];
    }
    return a;
}

int main() {
    int N;
    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로 깊이와 부모 정보 저장
    dfs(1, 0, 0);

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

    cout << findLCA(A, B) << endl;
    return 0;
}

코드 설명

1. 트리 표현

주어진 입력에 따라 트리를 인접 리스트 형태로 표현합니다.
각각의 부모-자식 관계를 저장하여 나중에 DFS 동안 참조할 수 있도록 합니다.

2. DFS 함수

dfs 함수는 현재 노드, 부모 노드, 깊이를 입력받아, 해당 노드의 부모와 깊이를 저장하고 순회합니다.
자식 노드는 부모와 동일하지 않을 때만 탐색합니다.

3. LCA 함수

두 노드의 깊이를 조정한 뒤, 부모를 타고 올라가며 두 노드가 같아지는 지점을 찾습니다.
이 지점이 바로 최소 공통 조상입니다.

결론

이번 강좌에서는 최소 공통 조상 문제의 개념, 접근법 및 C++ 구현을 살펴보았습니다.
이 문제는 트리 자료구조의 기본 개념을 이해하는 데 매우 유용하며, 다양한 응용 문제에서도 자주 등장합니다.
알고리즘 문제 해결 능력을 기르기 위해 다각도로 이 문제를 풀어보시기 바랍니다.