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

이진 트리는 컴퓨터 과학에서 중요한 데이터 구조 중 하나로,
모든 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.
이진 트리는 탐색, 정렬, 데이터 저장 등의 여러 용도로 사용되며,
알고리즘 문제에서 자주 등장합니다.
이번 강좌에서는 이진 트리를 활용한 알고리즘 문제를 풀어보겠습니다.

문제: 이진 트리의 최대 깊이 구하기

이 문제는 주어진 이진 트리를 탐색하여 그 깊이를 계산하는 것입니다.
최대 깊이란 루트 노드부터 가장 깊은 잎 노드까지의 경로의 길이를 의미합니다.
이진 트리가 비어있다면 깊이는 0입니다.
다음은 입력 및 출력 형식입니다.

입력 형식

이진 트리는 배열 형태로 주어지며, 각 노드는 다음과 같이 정의됩니다:

    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    

출력 형식

이진 트리의 최대 깊이를 정수로 반환합니다.

예제

    입력: [3,9,20,null,null,15,7]
    출력: 3
    

문제 해결 접근법

이 문제를 해결하기 위해서는 이진 트리를 탐색하는 방법이 필요합니다.
우리는 주로 두 가지 방법으로 탐색할 수 있습니다:
깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS).
이 문제의 경우 DFS를 사용하여 재귀적으로 트리를 탐색하는 방법을 선택하겠습니다.

깊이 우선 탐색 – 재귀적 방법

재귀를 통해, 트리의 각 노드를 방문하면서
왼쪽과 오른쪽 자식 노드를 계속해서 호출하여 깊이를 확인합니다.
아래는 이 과정을 나타낸 알고리즘의 핵심 아이디어입니다.

1. 현재 노드가 NULL이면 0을 반환합니다.
2. 왼쪽 서브트리의 깊이를 재귀적으로 호출하여 얻습니다.
3. 오른쪽 서브트리의 깊이를 재귀적으로 호출하여 얻습니다.
4. 왼쪽과 오른쪽 깊이 중 더 큰 값을 선택하고, 1을 추가하여 반환합니다.

구현

이제 위에서 설명한 알고리즘을 C++ 코드로 구현해보겠습니다.

    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            if (root == NULL) {
                return 0;
            }
            int leftDepth = maxDepth(root->left);
            int rightDepth = maxDepth(root->right);
            return max(leftDepth, rightDepth) + 1;
        }
    };
    

코드 설명

위 코드는 C++로 작성된 이진 트리 최대 깊이 계산하는 함수입니다.
maxDepth 함수가 재귀적으로 호출되어 주어진 노드의
최대 깊이를 계산합니다.

• if (root == NULL) 에서 노드가 NULL인지 체크합니다. NULL이면 깊이는 0이므로 반환합니다.
• 왼쪽과 오른쪽 자식에 대해 각각의 깊이를 계산하고, 둘 중 더 큰 값을 선택하여 1을 더합니다.
• 최종적으로 반환되는 값은 전반적인 최대 깊이입니다.

테스트

이제 몇 가지 테스트 케이스를 통해 알고리즘의 기능을 확인해보겠습니다.

    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    
    Solution solution;
    int result = solution.maxDepth(root);
    cout << result; // 3
    

결론

이진 트리의 최대 깊이를 계산하는 알고리즘을
C++로 구현하는 방법을 살펴보았습니다.
이 문제를 통해 재귀적인 탐색의 기초를 익힐 수 있었으며,
더 복잡한 트리 관련 문제를 해결하는 데 기초가 될 것입니다.
앞으로도 이진 트리에 대해 깊이 있는 공부를 해보시길 바랍니다.
감사합니다!

이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 효율적인 방법입니다. 이 알고리즘은 배열을 반복적으로 반으로 나누어 목표 값을 찾기 때문에 O(log n)의 시간 복잡도를 가집니다. 본 강의에서는 이진 탐색의 기본 개념, 구현 방법, 그리고 이를 활용한 실습 문제를 다루고자 합니다.

이진 탐색의 기본 원리

이진 탐색은 다음과 같은 절차로 동작합니다:

1. 배열의 중앙 요소를 확인합니다.
2. 중앙 요소와 목표 값을 비교합니다:
• 목표 값이 중앙 요소보다 작으면 배열의 왼쪽 절반을 대상으로 검색합니다.
• 목표 값이 중앙 요소보다 크면 배열의 오른쪽 절반을 대상으로 검색합니다.
• 목표 값이 중앙 요소와 같으면 검색이 완료됩니다.

이 과정을 반복하여 목표 값을 찾습니다.

문제: 정렬된 배열에서 특정 값 찾기

주어진 정수 배열 arr와 정수 target이 있을 때, target의 인덱스를 반환하는 프로그램을 작성하시오. 만약 target이 없는 경우 -1을 반환해야 합니다.

입력 형식

• 첫 번째 줄에는 배열의 크기 n이 주어집니다. (1 ≤ n ≤ 10⁵)
• 두 번째 줄에는 오름차순으로 정렬된 배열 arr가 주어집니다.
• 세 번째 줄에는 찾고자 하는 숫자 target가 주어집니다.

출력 형식

타겟의 인덱스를 출력합니다. (0 이상 n-1 이하의 정수)

예제

입력:
    5
    1 3 5 7 9
    5

    출력:
    2

문제 풀이 과정

1단계: 문제 이해

먼저 문제를 정확히 이해하는 것이 중요합니다. 정렬된 배열에서 특정 요소를 빠르게 찾는 것이니, 이진 탐색을 이용해야 합니다.

2단계: 이진 탐색 알고리즘 구현

이진 탐색 알고리즘을 C++로 구현해보겠습니다.

#include <iostream>
#include <vector>

using namespace std;

int binarySearch(const vector<int> &arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;  // 타겟을 찾았다.
        } else if (arr[mid] < target) {
            left = mid + 1;  // 오른쪽 반으로 이동.
        } else {
            right = mid - 1;  // 왼쪽 반으로 이동.
        }
    }
    return -1;  // 타겟을 찾지 못했다.
}

int main() {
    int n;
    cout << "배열의 크기를 입력하세요: ";
    cin >> n;
    
    vector<int> arr(n);
    cout << "배열의 요소를 입력하세요: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    int target;
    cout << "찾고자 하는 숫자를 입력하세요: ";
    cin >> target;

    int result = binarySearch(arr, target);
    if (result != -1) {
        cout << "타겟의 인덱스: " << result << endl;
    } else {
        cout << "타겟을 찾지 못했습니다." << endl;
    }

    return 0;
}

3단계: 코드 설명

– binarySearch 함수는 정수 벡터와 목표 값을 입력으로 받고, 목표 값의 인덱스를 반환합니다.
– left와 right는 탐색 구간의 시작과 끝 인덱스를 나타냅니다.
– while 루프는 left가 right보다 작거나 같은 동안 실행됩니다.
– 각 반복에서 중앙 인덱스 mid를 계산하고, 중앙 요소와 목표 값을 비교하여 다음 탐색 구간을 결정합니다.

4단계: 테스트 및 검증

코드를 작성한 후, 다양한 테스트 케이스에 대해 실행하여 올바른 결과를 반환하는지 확인해야 합니다. 다음과 같은 테스트를 고려할 수 있습니다:

• 배열에 목표 값이 존재하는 경우
• 배열에 목표 값이 없는 경우
• 배열의 크기가 1인 경우
• 중복된 요소가 있는 경우

결론

이진 탐색은 매우 유용한 알고리즘입니다. 특히, 정렬된 배열에서 속도 면에서 뛰어난 성능을 발휘합니다. 본 강의에서는 이진 탐색의 기본 원리를 이해하고, 실제 코드를 작성해보았습니다. 이진 탐색을 마스터하면, 다른 많은 알고리즘 문제를 해결하는 데도 큰 도움이 될 것입니다.

다음 강의에서는 이진 탐색의 변형 문제 및 다양한 응용 사례에 대해 다룰 예정입니다. 지속적인 학습을 통해 알고리즘 능력을 향상시키시길 바랍니다!

안녕하세요! 오늘은 이분 그래프에 대해서 알아보겠습니다. 이분 그래프는 그래프의 정점 집합을 두 개의 부분 집합으로 나눌 수 있으며, 두 집합에 포함된 정점 간에는 간선이 존재하지 않는 그래프를 의미합니다. 이 내용은 코딩테스트에서 자주 출제되는 문제 중 하나입니다. 다음 시간에는 이 문제를 풀기 위해 필요한 알고리즘과 코딩을 통해 이분 그래프를 판별하는 방법에 대해 알아보겠습니다.

문제 설명

주어진 비방향 그래프가 이분 그래프인지 판별하는 문제입니다. 한 정점에서 시작하여, 가능한 모든 정점을 방문하면서 이분 그래프 조건을 만족하는지를 확인해야 합니다.

문제 예제

다음과 같은 그래프가 주어졌을 때, 이 그래프가 이분 그래프인지 판별하시오.

정점: 6
간선: 
1 - 2
1 - 3
2 - 4
2 - 5
3 - 6

위 그래프를 보면 두 개의 집합으로 나눌 수 있는지 파악할 수 있습니다. 집합 A는 {1, 4, 5, 6}이고, 집합 B는 {2, 3}입니다. 이 그래프는 이분 그래프가 맞습니다.

문제 해결 전략

이분 그래프를 확인하기 위해 우리가 사용할 수 있는 방법 중 하나는 너비 우선 탐색(BFS) 혹은 깊이 우선 탐색(DFS)입니다. 두 방법 모두 그래프를 순회할 때 각 정점에 색깔(또는 그룹)을 부여하여 이분 그래프 조건을 확인하는 데 사용할 수 있습니다.

알고리즘 단계

1. 그래프를 인접 리스트 형태로 표현합니다.
2. 모든 노드를 방문할 수 있도록 반복문을 실행합니다.
3. 현재 정점에 색칠을 하여 두 그룹으로 나눕니다.
4. 인접한 정점이 같은 색깔인지 확인합니다.
5. 모든 노드를 방문하였거나 갈 수 있는 노드를 모두 방문할 때까지 반복합니다.

C++ 코드 구현

이 비방향 그래프에서 이분 그래프를 판별하기 위한 C++ 코드를 살펴보겠습니다.

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

using namespace std;

const int MAX = 1000; // 정점의 최대 개수
vector<int> graph[MAX];
int color[MAX]; // 색상 설정: -1은 미방문, 0과 1은 그룹

bool isBipartite(int start) {
    queue<int> q;
    q.push(start);
    color[start] = 0; // 시작 정점에 색칠

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

        for (int neighbor : graph[v]) {
            // 이웃 정점이 방문하지 않았다면 색칠한다.
            if (color[neighbor] == -1) {
                color[neighbor] = 1 - color[v]; // 현재 정점과 다른 색상을 부여
                q.push(neighbor);
            }
            // 이웃 정점이 현재 정점과 같은 색이라면 이분 그래프가 아니다.
            else if (color[neighbor] == color[v]) {
                return false; // 이분 그래프 조건 위배
            }
        }
    }
    return true;
}

int main() {
    int v, e;
    cout << "정점의 개수와 간선의 개수를 입력하세요: ";
    cin >> v >> e;

    // 그래프 초기화
    for (int i = 0; i < MAX; i++) {
        color[i] = -1;
    }

    cout << "간선 입력 (형식: a b): " << endl;
    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a); // 양방향 그래프
    }

    bool result = true;
    for (int i = 1; i <= v; i++) {
        if (color[i] == -1) {
            // 이 정점이 미방문 상태라면 이분 그래프 판별
            if (!isBipartite(i)) {
                result = false;
                break;
            }
        }
    }

    if (result) {
        cout << "이 그래프는 이분 그래프입니다." << endl;
    } else {
        cout << "이 그래프는 이분 그래프가 아닙니다." << endl;
    }

    return 0;
}

코드 설명

이 코드는 주어진 그래프의 정점과 간선을 입력받아 그 그래프가 이분 그래프인지 판단하는 과정입니다. isBipartite 함수는 모든 인접한 정점이 다른 색상으로 되어 있는지 검사합니다.

변수 및 구조체 설명

• graph[MAX]: 그래프의 인접 리스트 표현입니다.
• color[MAX]: 정점의 색상을 나타내는 배열입니다.
• queue<int> q: BFS에 사용되는 큐입니다.

입력 예시 및 출력 결과

위 코드를 실행할 때 간선을 입력하는 예시는 다음과 같습니다.

정점의 개수와 간선의 개수를 입력하세요: 6 5
간선 입력 (형식: a b): 
1 2
1 3
2 4
2 5
3 6

위와 같은 입력을 주었을 때, 아래와 같은 결과를 출력합니다.

이 그래프는 이분 그래프입니다.

결론

이상으로, C++를 이용하여 이분 그래프를 판별하는 방법을 배웠습니다. BFS 또는 DFS 방식을 사용하여 문제를 해결하는 기본적인 원리를 이해했다면, 이는 다양한 그래프 문제에 적용될 수 있습니다. 여러분의 코딩테스트 준비에 많은 도움이 되기를 바랍니다!

알고리즘 문제 해결에 있어 유니온-파인드(Union-Find) 자료구조는 매우 유용합니다. 이 글에서는 유니온-파인드의 개념과 C++을 사용한 문제 풀이 과정을 상세히 설명하겠습니다.

유니온 파인드란?

유니온 파인드 유니온-파인드(Union-Find) 알고리즘은 데이터의 집합을 효율적으로 관리하는 자료구조입니다. 이 자료구조는 서로소 집합(Disjoint Set)으로도 알려져 있으며, 주로 다음 두 가지 연산을 지원합니다:

• Find: 특정 원소가 어떤 집합에 속하는지를 찾는 연산입니다. 이 연산은 집합의 대표 원소(루트 노드)를 반환합니다.
• Union: 두 개의 집합을 통합하는 연산입니다. 이 연산은 두 집합의 루트 노드를 연결하여 하나의 집합으로 만듭니다.

주로 그래프 이론에서 사이클을 찾거나, 연결 요소를 검사하는 문제에서 많이 사용됩니다. 유니온 파인드를 효과적으로 활용하기 위해 두 가지 최적화 기법이 있습니다:

1. 경로 압축(Path Compression)

Find 연산을 수행할 때, 경로를 따라 모든 노드의 부모를 루트 노드로 업데이트하여, 다음 번에 보다 빠르게 루트 노드를 찾을 수 있도록 합니다.

2. 랭크 기반 유니온(Rank-based Union)

Union 연산을 수행할 때, 두 집합의 크기를 비교하여 더 작은 집합을 더 큰 집합의 자식으로 연결합니다. 이렇게 하면 트리의 높이를 줄일 수 있습니다.

문제 설명

이제 유니온-파인드 알고리즘을 사용하여 해결할 수 있는 문제를 보겠습니다. 아래의 문제를 풀어보겠습니다.

문제: 친구 네트워크

여러 친구들이 서로 연결되어 있는 친구 네트워크가 있습니다. 각 친구는 1에서 N까지의 번호로 식별됩니다. 두 친구가 서로 친구라고 불리려면 그들은 직접적인 친구이거나 간접적으로 친구가 되어야 합니다. 당신에게 주어진 친구의 쌍 (a, b)가 있을 때, 친구 네트워크에서 a와 b가 같은 친구 그룹에 속하는지 확인하시오.

입력 형식

• 첫째 줄에 친구의 수 N과 친구 관계의 수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)
• 둘째 줄부터 M개의 줄에 걸쳐 친구 관계 a, b 의 쌍이 주어진다.
• 마지막 줄에는 쿼리 Q가 들어오며, 각 쿼리에는 친구 쌍 그들 (x, y)가 주어진다.

출력 형식

각 쿼리에 대해, x와 y가 같은 친구 그룹에 속하면 ‘YES’, 그렇지 않으면 ‘NO’를 출력하시오.

알고리즘 접근 방법

1. 유니온-파인드를 사용하여 친구 관계를 초기화하고 연결합니다. Union(a, b) 를 사용하여 a와 b를 같은 집합으로 연결합니다.
2. 쿼리에 대해 Find(x)와 Find(y)를 사용하여 두 친구의 루트 노드를 확인합니다. 둘이 동일한 루트 노드를 가지면 ‘YES’, 그렇지 않으면 ‘NO’를 출력합니다.

C++ 코드 구현

아래는 유니온-파인드 알고리즘을 구현한 C++ 코드입니다:

#include 
#include 
using namespace std;

class UnionFind {
public:
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

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

    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // 랭크 기반 유니온
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

private:
    vector parent;
    vector rank;
};

int main() {
    int N, M;
    cin >> N >> M;
    UnionFind uf(N + 1);

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        uf.unionSets(a, b);
    }

    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        int x, y;
        cin >> x >> y;
        if (uf.find(x) == uf.find(y)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }

    return 0;
}

코드 설명

위의 C++ 코드에서 우리는 다음과 같은 구성 요소를 구현하였습니다:

• UnionFind 클래스: 유니온-파인드 알고리즘의 주요 로직을 포함하고 있습니다. find 함수는 루트 노드를 찾고, unionSets 함수는 두 집합을 통합합니다.
• 메인 함수: 친구 관계를 입력 받아 유니온-파인드 구조에 저장하고 주어진 쿼리에 대한 결과를 출력합니다.

시간 복잡도

유니온-파인드 알고리즘의 시간 복잡도는 다음과 같습니다:

• Find 연산: 거의 상수 시간 (α(N), 아커만 함수의 역함수에 비례)
• Union 연산: 거의 상수 시간

따라서 전체 알고리즘의 시간 복잡도는 O(M * α(N)) 입니다. 여기서 M은 친구 관계의 수입니다.

결론

이번 강좌에서는 유니온-파인드 자료구조의 개념과 C++을 활용한 문제 풀이 과정을 자세히 살펴보았습니다. 유니온-파인드는 다양한 문제에서 효과적으로 활용될 수 있는 강력한 도구입니다. 앞으로의 코딩 테스트에서 많은 도움이 되기를 바랍니다.