C++ 코딩테스트 강좌 보관 - 28 중 2 번째 페이지

C++ 코딩테스트 강좌, 특정 거리의 도시 찾기

안녕하세요, 이번 강좌에서는 C++를 이용하여 알고리즘 문제를 해결하는 과정에 대해 알아보겠습니다. 우리는 그래프 탐색을 통해 ‘특정 거리의 도시 찾기’라는 문제를 풀어볼 것입니다. 이 문제는 코딩 테스트에서 자주 등장하는 주제 중 하나로, BFS(너비 우선 탐색) 또는 DFS(깊이 우선 탐색)와 같은 그래프 탐색 기법을 통해 해결할 수 있습니다.

문제 설명

문제의 요구사항은 다음과 같습니다:

N개의 도시가 있다. 각 도시는 서로 연결되어 있으며, 길이 있다. 두 도시 A와 B를 연결하는 도로는 단방향일 수 있다. 도시의 수 N, 도시의 수를 나타내는 간선 M, 그리고 거리 K가 주어졌을 때, 거리 K 를 가지는 도시 번호를 출력하는 프로그램을 작성하시오. 또한, 만약 그러한 도시가 없으면 -1을 출력한다. 두 도시 A와 B를 연결하는 길이 여러 개 있는 경우는 없으며, 모든 도로는 단방향이다.

입력 형식

첫 번째 줄에는 도시의 수 N, 도로의 수 M, 거리 K가 주어진다. 두 번째 줄부터 M개의 줄에는 도로의 정보가 주어지며, 각 도로는 두 개의 정수 A와 B로 주어져 A에서 B로 향하는 단방향 도로가 존재함을 의미한다.

출력 형식

거리 K에 있는 도시의 번호를 출력하고, 만약 그런 도시가 없다면 -1을 출력해야 한다.

예제 입력

예제 출력

문제 해결 과정

우리는 그래프를 이용해 문제를 해결할 것입니다. 각 도시를 정점으로 보고, 도로를 간선으로 생각하여 그래프를 구성합니다. 다음 단계를 통해 문제를 해결해 보겠습니다.

1. 그래프 표현하기

첫번째 단계로, 인접 리스트를 사용하여 그래프를 표현합니다. 인접 리스트는 각 정점에 대해 연결된 정점 리스트를 저장하는 형식입니다. 이렇게 하면 도시 간의 연결 관계를 쉽게 확인할 수 있습니다.

2. BFS를 활용한 탐색

우리는 BFS(너비 우선 탐색) 알고리즘을 사용하여 특정 거리의 도시를 탐색할 것입니다. BFS는 한 정점에서 시작하여 인접한 모든 정점을 레벨별로 탐색할 수 있는 알고리즘으로, 특정 거리에서의 노드를 찾기 적합합니다.

3. 결과 저장 및 처리

거리 K에 해당하는 모든 도시 번호를 수집하고, 이를 출력합니다. 또한, K와 같은 거리를 가지는 도시에 대한 조건이 없을 경우 -1을 출력하도록 설정합니다.

구현 코드

아래는 C++로 구현한 코드입니다. 이 코드를 통해 문제를 해결할 수 있습니다.

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

using namespace std;

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

    vector<vector<int>> graph(N + 1);
    for (int i = 0; i < M; i++) {
        int A, B;
        cin >> A >> B;
        graph[A].push_back(B);
    }

    vector<int> distance(N + 1, -1);
    queue<int> q;

    // 시작 도시 1에서 거리 0으로 설정
    distance[1] = 0;
    q.push(1);

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

        for (int next : graph[current]) {
            if (distance[next] == -1) {
                distance[next] = distance[current] + 1;
                q.push(next);
            }
        }
    }

    vector<int> result;
    for (int i = 1; i <= N; i++) {
        if (distance[i] == K) {
            result.push_back(i);
        }
    }

    if (result.empty()) {
        cout << -1 << endl;
    } else {
        sort(result.begin(), result.end());
        for (int city : result) {
            cout << city << endl;
        }
    }

    return 0;
}

결론

이번 강좌에서는 ‘특정 거리의 도시 찾기’ 문제를 통해 그래프 탐색 기법을 배우고, BFS를 활용하여 문제를 해결하는 방법을 살펴보았습니다. 이와 같은 문제는 알고리즘 면접에서 많이 출제되므로, 충분한 연습을 통해 문제 해결 능력을 기르는 것이 중요합니다. 다음 강좌에서는 또 다른 알고리즘 문제를 다루어 보겠습니다. 감사합니다!

C++ 코딩테스트 강좌, 평균 구하기

주제: 평균 구하기

이번 강좌에서는 코딩테스트에서 자주 출제되는 문제 중 하나인 평균 구하기 문제를 다루겠습니다. 문제의 정의와 해결 방법을 단계별로 설명하고, 최종적으로 C++ 코드로 구현해보겠습니다.

문제 정의

주어진 정수 배열의 모든 요소의 평균을 구하는 프로그램을 작성하시오. 배열의 길이는 N이고, 배열의 요소는 모두 정수입니다. 평균값은 소수점 이하 2자리까지 구해야 하며, 정수 부분과 소수 부분은 ‘.’으로 구분지어야 합니다.

입력 형식:

첫 번째 줄에 배열의 길이 N (1 ≤ N ≤ 1000)이 주어진다.
두 번째 줄에 배열의 N개의 정수 (각 정수는 -10,000 이상 10,000 이하)가 공백으로 구분되어 주어진다.

출력 형식:

평균값을 소수점 이하 두 자리까지 출력하시오.

예제

입력:
5
10 20 30 40 50

출력:
30.00

문제 해결 방법

이 문제를 해결하기 위한 절차는 다음과 같습니다:

입력에서 N을 읽어來 배열의 길이를 결정합니다.
정수 배열을 읽어올 때, 각 요소를 합산합니다.
N으로 합계를 나누어 평균을 구합니다.
출력 시 소수점 두 자리까지 포맷팅합니다.

C++ 코드 구현

이제 위의 절차를 따르는 C++ 코드를 작성해봅시다:


#include 
#include  // std::setprecision 사용을 위해
#include 

using namespace std;

int main() {
    int N;
    cout << "배열의 길이를 입력하세요: ";
    cin >> N; // 배열의 길이 입력

    vector arr(N); // 크기가 N인 벡터 선언
    int sum = 0;

    cout << "배열의 요소를 공백으로 구분하여 입력하세요: ";
    for (int i = 0; i < N; ++i) {
        cin >> arr[i]; // 배열 요소 입력
        sum += arr[i]; // 요소 합산
    }

    double average = static_cast(sum) / N; // 평균 계산
    cout << "평균: " << fixed << setprecision(2) << average << endl; // 소수점 두 자리 포맷팅

    return 0;
}

코드 설명

#include <iostream>: C++에서 입출력을 위한 라이브러리 입니다.
#include <iomanip>: 출력의 포맷을 지정하기 위해 필요한 헤더 파일입니다. 여기서는 소수점 이하 자릿수를 설정하는 데 사용됩니다.
vector arr(N): C++의 동적 배열인 벡터를 사용하여 크기가 N인 정수형 배열을 선언합니다.
sum: 입력된 배열 요소의 합을 저장하는 변수입니다.
cin >> arr[i]: 사용자가 입력한 값을 배열의 각 요소에 할당합니다.
average: 총합을 N으로 나누어 평균값을 계산합니다. 또한, 정수형 Sum을 double로 형변환하여 소수점 이하 자리를 유지합니다.
std::fixed & std::setprecision(2): 소수점 이하 두 자리까지 출력하기 위한 표기 방식을 설정합니다.

복잡도 분석

이 문제의 시간 복잡도는 O(N)입니다. 각 요소를 한 번씩만 순회하면서 합계를 구하므로, 입력의 크기에 비례하여 계산 시간이 증가합니다. 공간 복잡도 또한 O(N)으로, 입력된 데이터를 저장하기 위해 N개의 공간을 사용합니다.

결론

이번 강좌에서는 평균값을 계산하는 문제를 통해 C++의 기본적인 입출력 및 벡터 사용법을 익혔습니다. 문제를 해결하기 위해 단계를 나누어 체계적으로 접근하는 것이 중요하며, 각 단계에서 발생할 수 있는 오류를 예상하고 처리하는 것이 코딩 테스트에서의 좋은 습관입니다. 앞으로 더 다양한 문제를 연습하며 알고리즘 실력을 키워 나가세요!

C++ 코딩테스트 강좌, 트리의 부모 찾기

문제 설명

주어진 이진 트리에서 각 노드의 부모 노드를 찾는 프로그램을 작성하세요. 이진 트리의 노드는 숫자로 레이블이 붙어 있으며, 다음과 같은 구조로 정의됩니다:


    struct Node {
        int value;
        Node* left;
        Node* right;
        
        Node(int val) : value(val), left(nullptr), right(nullptr) {}
    };

입력으로는 노드의 리스트와 요청된 노드의 값이 주어집니다. 출력으로는 해당 노드의 부모 노드의 값이 출력되어야 하며, 부모 노드가 없는 경우에는 -1을 반환해야 합니다.

예시

문제 접근 방식

문제를 해결하기 위해 이진 트리를 탐색하여 각 노드의 부모를 파악하는 방법을 사용할 것입니다. 우리는 다음과 같은 과정을 따릅니다:

트리의 루트 노드를 시작점으로 설정합니다.
큐를 사용하여 BFS(너비 우선 탐색) 방식으로 트리의 노드를 탐색합니다.
각 노드를 확인하고 요청된 노드의 부모를 저장합니다.
요청된 노드를 찾으면 해당 부모 노드를 출력합니다.

코드 구현


    #include 
    #include 
    #include 
    using namespace std;

    struct Node {
        int value;
        Node* left;
        Node* right;

        Node(int val) : value(val), left(nullptr), right(nullptr) {}
    };

    Node* buildTree(const vector>& nodes) {
        unordered_map nodeMap;
        for (const auto& p : nodes) {
            int child = p.first;
            int parent = p.second;

            if (nodeMap.find(child) == nodeMap.end())
                nodeMap[child] = new Node(child);

            if (parent != -1) {
                if (nodeMap.find(parent) == nodeMap.end())
                    nodeMap[parent] = new Node(parent);

                if (!nodeMap[parent]->left)
                    nodeMap[parent]->left = nodeMap[child];
                else
                    nodeMap[parent]->right = nodeMap[child];
            }
        }
        return nodeMap.begin()->second; // 첫번째로 추가된 노드를 루트로 반환
    }

    int findParent(Node* root, int target) {
        if (!root) return -1;

        queue q;
        q.push(root);
        Node* parent = nullptr;

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                Node* current = q.front();
                q.pop();
                
                if (current->left) {
                    if (current->left->value == target) {
                        return current->value;
                    }
                    q.push(current->left);
                }

                if (current->right) {
                    if (current->right->value == target) {
                        return current->value;
                    }
                    q.push(current->right);
                }
            }
        }
        
        return -1; // 부모를 찾지 못한 경우
    }

    int main() {
        // 트리 구성: (child, parent)
        vector> nodes = {{2, 1}, {7, 3}, {6, 4}, {5, -1}};

        Node* root = buildTree(nodes); // 트리 빌드
        int target = 3; // 요청 노드
        int parentValue = findParent(root, target);

        cout << parentValue << endl; // 부모 출력

        return 0;
    }

코드 설명

위 코드는 이진 트리를 만들고 요청된 노드의 부모를 찾는 전반적인 과정을 보여줍니다.

buildTree: 주어진 (child, parent) 리스트를 사용하여 트리를 구성하는 함수입니다. 각 노드를 맵에 저장하여 부모-자식 관계를 설정합니다.
findParent: BFS를 사용하여 요청된 값의 부모를 찾는 함수입니다. 각 노드를 탐색하면서 자식 노드가 요청된 값과 같으면 현재 노드의 값을 반환합니다.
main: 프로그램의 진입점으로, 샘플 입력을 통해 트리를 빌드하고 부모를 찾습니다.

종합 정리

이 문제는 이진 트리의 기본 구조를 이해하고, 자료구조를 효과적으로 활용하는 방법을 배우는 데 유익합니다. BFS를 통해 노드를 탐색하며 부모 노드를 찾는 과정은 실무에서도 많이 사용되는 접근 방법입니다. 각 단계별로 주의를 기울여야 하며, 예외 처리를 통해 문제를 예방할 수 있습니다.

추가 문제

이 문제의 변형으로, 특정 노드의 자식 노드들을 찾는 문제나, 트리의 깊이를 구하는 문제 등을 고려할 수 있습니다. 다양한 변형 문제를 통해 트리에 대한 이해를 더욱 깊게 할 수 있습니다.

팁 및 주의사항

재귀를 사용할 때는 무한 루프에 빠지지 않도록 주의해야 합니다.
노드의 부모가 없는 경우를 처리하기 위한 조건을 명확히 설정해야 합니다.
트리의 구조에 따라 알고리즘의 성능이 달라질 수 있으니, 다양한 경우를 실험해보세요.

C++ 코딩테스트 강좌, 트리의 지름 구하기

1. 문제 정의

주어진 트리의 지름을 구하는 문제입니다. 트리의 지름은 두 노드 간의 최장 경로의 길이를 말합니다. 트리는 노드와 간선으로 구성된 그래프로, 사이클이 없는 연결 그래프입니다. 이 문제를 해결하기 위해 DFS(Depth First Search) 또는 BFS(Breadth First Search) 알고리즘을 사용할 수 있습니다.

2. 문제 입력

첫 번째 줄에 노드의 개수 N이 주어집니다. 다음 줄부터 N-1개의 줄에는 간선이 주어지며, 각 간선은 두 개의 정수 a와 b로 표현됩니다. 이는 노드 a와 노드 b 사이에 간선이 존재함을 의미합니다.

입력 예시

3. 문제 출력

트리의 지름을 출력합니다.

출력 예시

4. 알고리즘 설명

트리의 지름을 구하기 위한 알고리즘은 다음과 같은 단계로 진행됩니다:

트리를 인접 리스트 형태로 저장합니다.
첫 번째 DFS를 통해 가장 멀리 있는 노드를 찾습니다.
두 번째 DFS를 사용해 첫 번째 DFS에서 찾은 노드로부터 가장 멀리 있는 노드를 찾습니다.
두 번째 DFS의 결과가 트리의 지름입니다.

5. C++ 코드 구현

트리의 지름을 계산하는 C++ 코드는 아래와 같습니다:


#include 
#include 
#include 

using namespace std;

vector> tree;
vector visited;

int furthestNode(int node) {
    visited[node] = true;

    int maxDistance = 0;
    int farthestNode = node;

    for (int neighbor : tree[node]) {
        if (!visited[neighbor]) {
            int distance = furthestNode(neighbor) + 1;
            if (distance > maxDistance) {
                maxDistance = distance;
                farthestNode = neighbor;
            }
        }
    }

    return farthestNode;
}

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

    tree.resize(N + 1);
    visited.resize(N + 1, false);

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

    int farthestFromStart = furthestNode(1);
    
    fill(visited.begin(), visited.end(), false);
    
    int diameterEnd = furthestNode(farthestFromStart);
    
    cout << diameterEnd << endl;

    return 0;
}

6. 코드 설명

코드는 아래와 같은 구조로 이루어져 있습니다:

라이브러리를 포함하고, 전역 변수를 선언합니다.
furthestNode 함수를 통해 DFS를 수행하며 가장 멀리 있는 노드를 반환합니다.
메인 함수에서 입력을 받고, 트리를 구성합니다.
첫 번째 DFS를 통해 시작 노드에서 가장 멀리 있는 노드를 찾습니다.
두 번째 DFS를 통해 첫 번째 DFS에서 찾은 노드로부터 가장 멀리 있는 노드를 찾고, 이 노드가 지름의 끝입니다.
지름의 길이를 출력합니다.

7. 시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)입니다. N개의 노드를 방문하는 과정에서 각 노드에 대해 DFS를 수행하기 때문에, 트리의 크기에 비례합니다.

8. 결론

이번 강좌에서는 트리의 지름을 구하는 문제를 해결하는 방법을 알게 되었습니다. DFS를 활용하여 트리의 구조를 탐색하고 솔루션을 도출하는 과정을 이해하는 것이 중요합니다. 다양한 그래프 문제를 연습함으로써 알고리즘 실력을 향상시키길 바랍니다.

9. 참고 자료

추천 책: Introduction to Algorithms by Thomas H. Cormen et al.
웹사이트: GeeksforGeeks
문서: Wikipedia: Tree Data Structure

C++ 코딩테스트 강좌, 트리 알아보기

작성자: 블로그 작성자 | 날짜: 2023년 10월 1일

1. 문제 설명

이번 강좌에서는 C++ 코딩테스트에서 자주 등장하는 트리(Tree) 자료구조에 대해 알아보고, 이를 활용한 알고리즘 문제를 풀어보도록 하겠습니다.

주어진 문제는 다음과 같습니다:

문제: 이진 탐색 트리의 최솟값과 최댓값 찾기

문제 설명: 이진 탐색 트리(Binary Search Tree, BST)가 주어질 때, 그 트리의 최솟값과 최댓값을 찾아 출력하는 프로그램을 작성하세요.

이진 탐색 트리는 다음과 같은 성질을 가집니다:

왼쪽 서브트리의 모든 노드는 현재 노드보다 작다.
오른쪽 서브트리의 모든 노드는 현재 노드보다 크다.

입력으로 주어지는 트리는 다음과 같은 형식으로 주어집니다:

출력으로는 최솟값과 최댓값을 차례로 출력해야 하며, 위 예시의 경우 출력은 다음과 같습니다:

            1
            8

이와 같은 문제를 해결하기 위해 이진 탐색 트리에 대한 이해가 필요합니다.

2. 이진 탐색 트리(BST)의 통찰

이진 탐색 트리(BST)는 각 노드가 데이터를 가지고 있으며, 자식 노드는 두 개(왼쪽 및 오른쪽)입니다. 왼쪽 자식 노드는 항상 그 부모 노드보다 작고, 오른쪽 자식 노드는 항상 그 부모 노드보다 큽니다.

이런 성질 덕분에 이진 탐색 트리를 사용하면 데이터의 검색, 삽입, 삭제를 O(log n) 시간 안에 수행할 수 있습니다.

최솟값은 왼쪽 서브트리의 가장 왼쪽에 있는 노드입니다.
최댓값은 오른쪽 서브트리의 가장 오른쪽에 있는 노드입니다.

트리의 깊이가 n인 경우 최솟값과 최댓값을 찾기 위해 단순히 트리를 탐색하면 되므로, 매우 효율적입니다.

3. 알고리즘 설계

최솟값과 최댓값을 찾기 위해 두 개의 함수를 정의할 수 있습니다. 각각의 함수는 재귀적 방법 또는 반복적 방법을 사용하여 트리를 탐색합니다.

            // 이진 탐색 트리의 노드 구조 정의
            struct Node {
                int data;
                Node* left;
                Node* right;
                
                Node(int val) : data(val), left(nullptr), right(nullptr) {}
            };

            // 최솟값을 찾는 함수
            Node* findMin(Node* root) {
                if (root == nullptr) return nullptr;
                if (root->left == nullptr) return root;
                return findMin(root->left);
            }

            // 최댓값을 찾는 함수
            Node* findMax(Node* root) {
                if (root == nullptr) return nullptr;
                if (root->right == nullptr) return root;
                return findMax(root->right);
            }

각 함수는 주어진 노드에서 시작하여 왼쪽 혹은 오른쪽 방향으로 계속 이동하면서 최솟값 또는 최댓값을 찾아내는 길을 제공합니다.

4. C++ 코드 구현

이진 탐색 트리에서 최솟값과 최댓값을 구하는 전체 코드는 다음과 같습니다:

            #include 
            using namespace std;

            // 이진 탐색 트리의 노드 구조 정의
            struct Node {
                int data;
                Node* left;
                Node* right;

                Node(int val) : data(val), left(nullptr), right(nullptr) {}
            };

            // 최솟값을 찾는 함수
            Node* findMin(Node* root) {
                if (root == nullptr) return nullptr;
                if (root->left == nullptr) return root;
                return findMin(root->left);
            }

            // 최댓값을 찾는 함수
            Node* findMax(Node* root) {
                if (root == nullptr) return nullptr;
                if (root->right == nullptr) return root;
                return findMax(root->right);
            }

            int main() {
                // 샘플 트리 생성
                Node* root = new Node(5);
                root->left = new Node(3);
                root->right = new Node(7);
                root->left->left = new Node(1);
                root->left->right = new Node(4);
                root->right->right = new Node(8);
                
                Node* minNode = findMin(root);
                Node* maxNode = findMax(root);

                if (minNode) cout << "최솟값: " << minNode->data << endl;
                if (maxNode) cout << "최댓값: " << maxNode->data << endl;

                // 동적 메모리 해제
                delete root->left->left;
                delete root->left->right;
                delete root->left;
                delete root->right->right;
                delete root->right;
                delete root;

                return 0;
            }

위 코드를 실행시키면 해당 이진 탐색 트리의 최솟값과 최댓값이 출력됩니다.

5. 코드 설명

프로그램의 주요 구성 요소에 대해 설명하겠습니다:

Node 구조체: 이 구조체는 이진 탐색 트리를 구성하는 각 노드를 정의합니다. 각 노드는 정수형 데이터와 두 개의 자식 포인터(왼쪽 및 오른쪽)를 가집니다.
findMin 함수: 주어진 노드에서 왼쪽 자식 노드를 계속 따라가면서 최솟값 노드를 찾습니다. 왼쪽 자식이 더 이상 없으면 그 노드가 최솟값이 됩니다.
findMax 함수: 주어진 노드에서 오른쪽 자식 노드를 계속 따라가면서 최댓값 노드를 찾습니다. 오른쪽 자식이 더 이상 없으면 그 노드가 최댓값이 됩니다.
main 함수: 샘플 트리를 생성하고, 최솟값과 최댓값을 찾기 위해 각각의 함수를 호출합니다. 결과를 출력한 뒤, 동적으로 할당된 메모리를 해제합니다.

6. 결론

이번 강좌에서는 C++의 이진 탐색 트리를 이용하여 최솟값과 최댓값을 찾는 알고리즘을 살펴보았습니다. 이진 탐색 트리는 매우 효율적인 데이터 구조로, 다양한 응용이 가능합니다. 트리 구조에 대한 더 깊은 이해를 통해 다른 트리 관련 문제를 해결하는 데 도움이 될 것입니다.

앞으로 보다 복잡한 트리 문제나, 트리를 응용한 알고리즘을 다루는 강좌도 준비하겠습니다. 다음 강좌를 기대해 주세요!