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

현대의 알고리즘 문제풀이에서 그래프는 매우 중요하고 기본적인 데이터 구조입니다. 이 글에서는 그래프의 표현 방식에 대해 설명하고, C++을 사용하여 관련 문제를 해결하는 방법을 배워보겠습니다.

그래프란 무엇인가?

그래프란 정점(vertex)과 간선(edge)으로 구성된 자료구조로, 다양한 관계를 표현하는 데 유용합니다. 예를 들어, 소셜 네트워크에서의 사용자 간의 관계, 도로망에서의 도시 간의 연결, 웹 페이지 간의 링크 등 다양한 상황에서 그래프를 활용할 수 있습니다.

그래프의 표현 방법

그래프는 일반적으로 두 가지 방법으로 표현됩니다: 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)입니다. 각각의 방법은 장단점이 있으므로, 문제의 특성에 따라 적합한 방법을 선택해야 합니다.

1. 인접 행렬

인접 행렬은 2차원 배열을 사용하여 그래프를 표현하는 방법입니다. 행렬의 크기는 V x V(V는 정점의 개수)로, 행렬의 각 원소 (i, j)는 정점 i와 정점 j간의 간선 존재 여부를 나타냅니다.

        // C++에서의 인접 행렬 선언
        const int MAX = 100; // 최대 정점 수
        int adj[MAX][MAX]; // 인접 행렬
        int V; // 정점의 개수
        

인접 행렬의 장점은 특정 간선의 존재 여부를 O(1)로 확인할 수 있다는 점입니다. 그러나 메모리 측면에서는 V의 제곱만큼 사용하므로, 정점 수가 많고 간선 수가 적은 경우 비효율적입니다.

2. 인접 리스트

인접 리스트는 각 정점에 연결된 정점들의 리스트를 사용하는 방법입니다. 이는 간선이 적은 희소 그래프(sparse graph)에 더 적합합니다.

        // C++에서의 인접 리스트 선언
        #include 
        #include 
        using namespace std;

        vector adj[MAX]; // 인접 리스트
        int V; // 정점의 개수
        

인접 리스트는 메모리를 좀 더 효율적으로 사용할 수 있으며, 간선 리스트를 순회하는 데 있어 O(E)의 시간이 소요됩니다.

문제: 연결된 컴포넌트 찾기

이 문제에서는 주어진 유향 그래프에서 서로 연결된 모든 컴포넌트를 찾아야 합니다. 즉, 하나의 정점에서 시작해서 도달할 수 있는 정점들의 집합을 찾아내는 것입니다.

문제 설명

정점의 수 V와 간선의 수 E가 주어지고, 각 간선은 두 정점의 쌍으로 주어집니다. 이 그래프에서 연결된 컴포넌트를 모두 찾아 출력하는 프로그램을 작성하세요.

입력 형식

• 첫 번째 줄: 정점의 수 V (1 ≤ V ≤ 1000)
• 두 번째 줄: 간선의 수 E (0 ≤ E ≤ 10000)
• 다음 E 줄: 간선 (u, v) 형태로 주어짐

출력 형식

연결된 컴포넌트의 수와 각 컴포넌트의 정점을 오름차순으로 출력합니다.

문제 풀이 과정

문제를 해결하기 위해 인접 리스트를 사용하여 그래프를 저장하고, 깊이 우선 탐색(DFS)을 통해 연결된 컴포넌트를 찾겠습니다.

1단계: 인접 리스트 구성하기

우선 입력을 받아 인접 리스트를 구성해야 합니다. 정점의 개수와 간선의 수를 입력받고, 각 간선을 통해 관계를 나타내는 리스트를 완성합니다.

2단계: DFS로 연결된 컴포넌트 찾기

탐색이 이루어질 때마다 방문한 정점을 마킹하고, 더 이상 방문할 정점이 없을 때까지 반복하며 컴포넌트를 찾습니다. DFS의 구현은 재귀를 통해 간단히 진행할 수 있습니다.

        #include 
        #include 
        #include 

        using namespace std;

        vector adj[1001]; // 인접 리스트
        bool visited[1001]; // 방문 여부 체크
        vector> components; // 연결된 컴포넌트 저장

        void dfs(int v, vector &component) {
            visited[v] = true; // 방문 체크
            component.push_back(v); // 컴포넌트에 추가

            for (int u : adj[v]) {
                if (!visited[u]) {
                    dfs(u, component); // 재귀 호출
                }
            }
        }

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

            for (int i = 0; i < E; i++) {
                int u, v;
                cin >> u >> v; // 간선 입력
                adj[u].push_back(v); // 인접 리스트 구성
                adj[v].push_back(u); // 무향 그래프임을 가정
            }

            // 각 정점에 대해 연결된 컴포넌트 찾기
            for (int i = 1; i <= V; i++) {
                if (!visited[i]) {
                    vector component;
                    dfs(i, component); // DFS 탐색
                    components.push_back(component); // 찾은 컴포넌트 저장
                }
            }

            // 결과 출력
            cout << components.size() << "\n"; // 연결된 컴포넌트 수
            for (const auto &component : components) {
                sort(component.begin(), component.end()); // 컴포넌트 정렬
                for (int v : component) {
                    cout << v << " "; // 정점 출력
                }
                cout << "\n";
            }

            return 0;
        }
        

위 코드를 통해 입력된 그래프에서 연결된 컴포넌트를 찾고 출력하는 로직을 구현했습니다. 입력된 그래프의 각 컴포넌트를 오름차순으로 정렬하고 출력하는 방식입니다.

결론

그래프의 표현 방식과 DFS를 통해 문제를 해결하는 과정을 살펴보았습니다. 그래프는 다양한 알고리즘 문제에서 중요한 역할을 하며, 이를 익히는 것은 코딩 테스트에서 좋은 결과를 얻기 위한 기초가 됩니다. 이 강좌를 통해 그래프의 기초적인 이해와 문제 풀이 능력을 향상시키길 바랍니다.

문제 접근 방법

구간 합 문제는 여러 가지 방법으로 해결할 수 있지만, 효율적인 방법으로는
누적 합(Prefix Sum)을 활용한 접근 방식이 있습니다. 누적 합을 통해 주어진 구간
[left, right]의 합을 O(1)의 시간 복잡도로 계산할 수 있습니다.

기본적인 아이디어는 배열의 각 인덱스까지의 합을 미리 계산하여 저장하는 것입니다.
이를 통해 특정 구간의 합은 다음과 같이 구할 수 있습니다.

sum(left, right) = prefixSum[right] - prefixSum[left - 1]

여기서 prefixSum[i]는 배열의 처음부터 i번째 요소까지의 합입니다.
이 방법은 배열을 한 번 순회하는 O(N)의 복잡도를 가지고 있으며, 이후 각 구간 합은 O(1)로 계산할 수 있습니다.

구현

코드

#include <iostream>
#include <vector>

using namespace std;

class SubarraySum {
public:
    SubarraySum(const vector<int>& arr) {
        int n = arr.size();
        prefixSum.resize(n + 1);
        prefixSum[0] = 0; // prefixSum[0]은 0으로 초기화합니다.
        
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
        }
    }

    int getSum(int left, int right) {
        return prefixSum[right] - prefixSum[left - 1];
    }

private:
    vector<int> prefixSum; // 누적 합을 저장하는 배열입니다.
};

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

    SubarraySum subarray(arr);

    int left, right;
    cout << "구간의 왼쪽 경계를 입력하세요 (1부터 시작): ";
    cin >> left;
    cout << "구간의 오른쪽 경계를 입력하세요: ";
    cin >> right;

    int result = subarray.getSum(left, right);
    cout << "구간 [" << left << ", " << right << "]의 합은: " << result << endl;

    return 0;
}
    

코드 설명

클래스 정의

SubarraySum 클래스는 구간 합을 계산하는 기능을 제공합니다.
이 클래스의 생성자에서 배치된 배열의 원소를 기반으로 누적 합을 초기화합니다.
배열의 크기를 저장하는 n 변수를 정의하고, prefixSum 배열을(`[0]`을 하나 포함하여) 생성합니다.

누적 합 계산

생성자 내부의 for 루프를 통해 배열을 순회하여
각 인덱스까지의 합을 prefixSum 배열에 저장합니다.
이는 배열의 첫 번째 인덱스부터 시작하기 때문에 배열의 크기보다 1 큰 크기를 가지는 것이 특징입니다.

구간 합 계산

getSum(int left, int right) 메소드는 주어진 left와 right 인덱스를
사용하여 구간 합을 반환합니다. 누적 합 배열의 값을 이용하여 간단히
prefixSum[right] - prefixSum[left - 1] 로 구간 합을 계산할 수 있습니다.

테스트 및 활용

본 코드를 통해 사용자는 구간의 왼쪽과 오른쪽 경계를 입력받고,
해당 구간의 합을 쉽게 계산할 수 있습니다. 이 알고리즘은 입력 배열의 크기가 커져도
매끄럽게 동작하며, 구간 합을 O(1)의 시간 복잡도로 신속하게 처리할 수 있는 장점을 가집니다.

결론

구간 합 문제는 다양한 응용 프로그램에서도 널리 사용되며,
이러한 누적 합 방식은 데이터 분석, 통계 처리 등 여러 분야에서 유용성을 보여줍니다.
이 간단하지만 뛰어난 방법을 통해 문제 해결의 효율성을 높일 수 있습니다.

이 강좌가 여러분의 C++ 코딩 테스트 준비에 도움이 되길 바랍니다!

이번 강좌에서는 구간 합을 구하는 두 번째 문제를 다룹니다. 구간 합 문제는 알고리즘과 데이터 구조에서 매우 중요한 주제로, 여러 상황에서 유용하게 사용됩니다. 효율적인 알고리즘을 통해 주어진 구간의 합을 계산하는 방법을 배울 것입니다.

문제 설명

다음과 같은 배열이 주어졌을 때, 여러 쌍의 시작 인덱스와 끝 인덱스가 주어질 것입니다. 각 쌍에 대해 구간의 합을 구하는 프로그램을 작성하세요.

입력

• 첫 번째 줄에 배열의 크기 N (1 ≤ N ≤ 100,000)과 질의의 수 M (1 ≤ M ≤ 100,000)이 주어진다.
• 두 번째 줄에 N개의 정수가 배열의 원소로 주어진다. 각 원소의 값은 -10,000 이상 10,000 이하이다.
• 이후 M개의 줄에 각각 두 개의 정수 S와 E가 주어지며, 이는 구간 [S, E]의 합을 구하는 것을 의미한다. (S, E는 1부터 시작하는 인덱스이다.)

출력

각 질의에 대한 구간 합을 각각의 줄에 출력한다.

문제 분석

구간 합 구하기 문제는 단순히 직접적으로 합을 계산할 경우 시간복잡도가 O(N)으로, M이 클 경우에는 O(N*M)으로 매우 비효율적입니다. 따라서 이런 경우에는 누적합(Prefix Sum) 기법을 사용하여 O(1)로 구간 합을 구할 수 있도록 개선합니다.

알고리즘

1. 누적합 배열을 만든다.
2. 각 질의에 대해 구간의 시작과 끝 인덱스를 사용하여 O(1) 시간에 구간 합을 구한다.

구현

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

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<int> arr(N + 1, 0);
    vector<int> prefixSum(N + 1, 0);

    // 배열 입력
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        prefixSum[i] = prefixSum[i - 1] + arr[i]; // 누적합 계산
    }

    // 쿼리 처리
    for (int i = 0; i < M; i++) {
        int S, E;
        cin >> S >> E;
        // 구간 합 계산
        cout << prefixSum[E] - prefixSum[S - 1] << endl;
    }

    return 0;
}
    

코드 설명

코드의 각 부분은 다음과 같은 작업을 수행합니다:

• 입력: N과 M을 입력 받고, 이후 N개의 숫자를 읽어 배열 arr에 저장합니다.
• 누적합 배열 생성: prefixSum 배열을 생성하여, i번째 원소까지의 합을 계산하여 저장합니다.
• 쿼리 처리: 각 쿼리에 대해 S와 E를 읽고, prefixSum을 활용하여 O(1) 시간에 구간 합을 계산합니다.

복잡도 분석

이 알고리즘의 시간 복잡도는 다음과 같습니다:

• 누적합 배열 생성: O(N)
• 각 쿼리에 대한 처리: O(M)
• 전체 시간 복잡도: O(N + M)

결론

이번 강좌에서는 구간 합을 효율적으로 계산하는 방법을 배웠습니다. 누적합 기법을 활용함으로써, 직접적인 반복을 피하고 시간 복잡도를 크게 줄일 수 있었습니다. 이러한 기법은 많은 문제에서 응용될 수 있으므로 꼭 숙지하시기 바랍니다.

다음 강좌에서는 좀 더 복잡한 데이터 구조를 사용한 구간 합 문제를 다룰 예정입니다. 감사합니다!

안녕하세요! 이번 시간에는 C++ 코딩테스트에서 자주 등장하는 ‘구간 합’ 문제를 통해 알고리즘 문제 해결 능력을 키워보겠습니다. 구간 합 문제는 주어진 배열의 특정 구간에 속한 요소들의 합을 구하는 문제로, 이 문제를 해결하기 위한 다양한 방법과 최적화 기법을 알아보도록 하겠습니다.

문제 설명

주어진 정수 배열 A와 정수 M이 있습니다. 우리는 A의 각 요소에 대해 A[i]에서 시작하는 구간의 합을 A[i] + A[i+1] + ... + A[j]의 형태로 구해야 합니다. 아래는 문제의 구체적인 요구 사항입니다.

문제

정수 배열 A와 정수 M이 주어졌을 때, A[i]에서 시작해 M개의 연속된 원소들의 합을 구하는 함수를 구현하시오.

입력

• 첫 번째 줄에 배열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)
• 두 번째 줄에 N개의 정수로 이루어진 배열 A가 주어진다. (−1,000,000,000 ≤ A[i] ≤ 1,000,000,000)
• 세 번째 줄에 정수 M이 주어진다. (1 ≤ M ≤ N)

출력

구간 합을 출력하시오. 만약 A[i]에서 시작해 M개 원소의 합이 가능한 경우, 그 합을 출력하고, 그렇지 않은 경우 -1을 출력하시오.

해결 과정

이 문제를 해결하기 위해 여러 가지 접근 방식이 있을 수 있지만, 가장 일반적이고 효율적인 방법은 슬라이딩 윈도우(Sliding Window) 기법을 사용하는 것입니다. 슬라이딩 윈도우 기법을 사용하면 O(N)의 시간 복잡도로 문제를 해결할 수 있습니다.

슬라이딩 윈도우 접근법 설명

슬라이딩 윈도우 기법에서는 구간의 시작과 끝을 창과 같이 설정하여, 그 창을 이동시키면서 해당 구간의 값을 계산합니다. 초기 구간을 설정한 후, 다음 요소를 추가하고 시작점의 요소를 빼면서 구간의 합을 갱신합니다. 이를 통해 불필요한 계산을 줄이고 효율성을 높일 수 있습니다.

코드 구현

이제 우리의 접근 방식을 C++로 구현해 보겠습니다.

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

// 함수: 구간 합 구하기
long long rangeSum(const vector<int> &A, int M) {
    long long sum = 0; // 초기 합 변수
    int N = A.size(); // 배열 크기

    // 첫 번째 구간의 합을 구한다
    for (int i = 0; i < M; i++) {
        sum += A[i];
    }
    
    // 첫 번째 구간 합을 출력
    cout << "구간 합: " << sum << endl;

    // 슬라이딩 윈도우로 구간 합 갱신
    for (int i = M; i < N; i++) {
        sum += A[i] - A[i - M]; // 기존 요소 빼고 새로운 요소 더하기
        cout << "구간 합: " << sum << endl; // 갱신된 구간 합 출력
    }
    
    return sum; // 최종 반환값
}

int main() {
    int N, M;
    cout << "배열의 길이 N: ";
    cin >> N; // 배열 크기 입력받기
    vector<int> A(N);

    cout << "정수 배열 A: ";
    for (int i = 0; i < N; i++) {
        cin >> A[i]; // 배열 원소 입력받기
    }

    cout << "구간의 길이 M: ";
    cin >> M; // 구간 합의 길이 입력받기

    long long totalSum = rangeSum(A, M); // 구간 합 함수 호출
    if (N < M) {
        cout << "-1" << endl; // 구간 합이 불가능한 경우 -1 출력
    } else {
        cout << "구간 합의 총합: " << totalSum << endl; // 총합 출력
    }

    return 0;
}
    

코드 설명

위 코드는 다음과 같은 과정을 거쳐 구간 합을 구하는 과정을 보여줍니다.

1. 먼저, 크기 N의 배열 A와 구간 길이 M을 입력받습니다.
2. 구간의 초기 합을 계산하기 위해 첫 번째 M개의 원소를 더합니다.
3. 슬라이딩 윈도우 기법을 적용하여, 다음 구간 합을 얻기 위해 기존의 요소를 빼고 새로운 요소를 더합니다.
4. 모든 구간의 합을 출력합니다.

결론

이번 시간에는 C++을 이용해 구간 합을 구하는 문제를 해결해 보았습니다. 슬라이딩 윈도우 기법은 아주 간단하면서도 효율적인 방법이라, 다양한 문제를 해결하는 데 유용하게 사용할 수 있습니다. 이와 같은 기법을 익혀두면 코딩 테스트를 준비하는 데 많은 도움이 될 것입니다.

다음 강좌에서는 더욱 다양한 문제를 다루고 더 깊이 있는 알고리즘의 이해를 도와드리겠습니다. 그럼 다음 시간까지 연습하시고 좋은 결과 있으시길 바랍니다!

구간 합 문제는 주어진 배열 안에서 특정 범위의 합을 효율적으로 구하는 알고리즘 문제입니다. 이 문제는 다양한 프로그래밍 언어에서 자주 등장하며, 특히 C++에서의 구현이 중요합니다. 이번 강좌에서는 구간 합 문제에 대해 구체적인 문제를 설정하고, 이를 해결하기 위한 과정을 상세히 설명하겠습니다.

1. 문제 설명

다음과 같이 정수로 구성된 배열이 주어졌다고 가정해봅시다. 정수 배열 A의 크기는 N입니다. 우리는 M개의 쿼리를 통해 배열의 특정 구간의 합을 계산해야 합니다. 구간의 시작 인덱스는 L, 끝 인덱스는 R로 주어지며, 우리는 A[L] + A[L+1] + ... + A[R]를 계산해야 합니다.

예를 들어, 배열 A가 다음과 같다고 합시다:

A = [10, 20, 30, 40, 50]

그리고 다음과 같은 쿼리가 주어졌다고 가정해봅시다:

1. L = 1, R = 3
2. L = 0, R = 4
3. L = 2, R = 2

주어진 쿼리에 대한 구간 합을 구하면 다음과 같습니다:

1. A[1] + A[2] + A[3] = 20 + 30 + 40 = 90
2. A[0] + A[1] + A[2] + A[3] + A[4] = 10 + 20 + 30 + 40 + 50 = 150
3. A[2] = 30

2. 문제 해결 접근 방법

구간 합 문제를 해결하기 위한 전통적인 방법은 직접 배열을 순회하는 것입니다. 그러나 이는 비효율적일 수 있습니다. 예를 들어, M개의 쿼리에서 각 쿼리마다 O(R - L + 1)의 시간이 소모된다면 최악의 경우 O(N * M)의 시간이 걸리게 됩니다. 이를 개선하기 위해 다음과 같은 방법을 사용합니다.

2.1. 전처리 방식 – 누적 합 배열

모든 쿼리의 합을 빠르게 계산하기 위해 누적 합 배열을 활용할 수 있습니다. 먼저 주어진 배열 A의 누적합 배열 S를 정의합니다. 누적합 배열은 다음과 같이 계산됩니다:

S[i] = S[i - 1] + A[i]

여기서 S[0]는 0으로 초기화됩니다. 누적합 배열을 사용하면 구간의 합을 다음과 같이 쉽게 구할 수 있습니다:

sum(L, R) = S[R] - S[L - 1]

이제 구간 합을 O(1)의 시간복잡도로 계산할 수 있습니다. 아래는 누적 합 배열을 사용하는 C++ 해결 방법입니다.

3. C++ 코드 예제

#include 
#include 
using namespace std;

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

    vector A(N);
    vector S(N + 1, 0); // S[0]은 0으로 초기화

    for (int i = 0; i < N; i++) {
        cin >> A[i];
        S[i + 1] = S[i] + A[i]; // 누적 합 계산
    }

    for (int i = 0; i < M; i++) {
        int L, R;
        cin >> L >> R;
        // 구간 합 출력
        cout << S[R] - S[L - 1] << endl;
    }
    return 0;
}

4. 코드 설명

위 코드를 단계별로 설명하겠습니다:

1. 입력 받기: 배열의 크기 N과 쿼리 수 M을 입력받고, 배열 A의 값을 입력받습니다.
2. 누적 합 배열 생성: 각 인덱스에 대해 누적 합을 계산하여 S 배열에 저장합니다. 이 배열은 원본 배열 A의 값들의 합을 쉽게 찾아올 수 있게 돕습니다.
3. 쿼리 처리: 각 쿼리마다 구간의 시작 및 끝 인덱스 L와 R을 입력받고, 누적 합 배열 S를 통해 구간의 합을 계산하여 출력합니다.

5. 성능 분석

위의 C++ 코드의 시간 복잡도는 배열 A의 누적합을 계산하는 데 O(N), 각 쿼리를 처리하는 데 O(1)이므로 전체 시간 복잡도는 O(N + M)입니다. 이는 매우 효율적인 방법으로, 수천 개의 쿼리에서도 빠른 시간 내에 결과를 얻을 수 있습니다.

6. 다양한 변형 문제

구간 합 문제는 여러 가지 변형이 가능합니다. 예를 들어:

• 구간 최소값/최대값: 주어진 파라미터에 대한 최소값이나 최대값을 찾는 문제로 변형 가능.
• 구간 업데이트: 특정 범위의 값을 변경한 후 다시 구간 합을 계산해야 하는 경우. 이 경우 세그먼트 트리를 활용할 수 있습니다.
• 2차원 구간 합: 2차원 배열에서 특정 구간의 합을 계산하는 문제로, 이중 누적합을 사용할 수 있습니다.

7. 마무리

구간 합 문제는 프로그래밍에서 매우 유용한 기술 중 하나이며, 특히 대규모 데이터 처리가 필요한 경우 상당한 효율성을 제공합니다. 이번 강좌에서는 누적 합 배열을 이용하여 구간 합 문제를 해결하는 방법을 알아보았습니다. 다양한 변형 문제를 통해 이 기술을 더욱 발전시킬 수 있습니다. 여러 문제를 풀어보며 경험을 쌓고, C++ 코딩 테스트에서 높은 점수를 얻기를 바랍니다.

강좌를 마치며, 추가적인 질문이나 요청 사항이 있을 경우 댓글로 남겨주세요.