ZeroOne

Prefix Sum : 여러 개의 누적합, 구간합을 묻는 쿼리에 대해 효율적인 알고리즘

• 누적합 : [0, Right] 구간의 합
• 구간합 : [Left, Right] 구간의 합

하나의 구간합을 구하는 것이 O(N)이고 구간합을 구하라는 M개의 쿼리가 들어온다면 시간복잡도는 O(NM)이다.

N = 1,000,000 이고 M = 1,000,000이라면 시간복잡도가 너무 안좋다.

이런 경우 사용하는 것이 Prefix Sum 이다.

누적합을 구해놓고 누적합 간에 -연산을 하면 구간합이기 때문이다.

- 시간복잡도 : O(N+M)

- 동작과정

  1) N개의 수에 대하여 접두사 합(Prefix Sum)을 계산하여 배열 P에 저장한다.

  2) 매 M개의 쿼리 정보 [L, R]을 확인할 때 구간 합은 P[R]-P[L-1]이다.

  ▪️ 이때, P[0] 에 0을 넣고 L >= 1 을 만들면 코드가 간결해진다.

#include <iostream>
#include <vector>

using namespace std;

int n = 5;
vector<int> data = {10, 20, 30, 40, 50};
vector<int> prefix_sum;

int main(void) {
    // 첫 배열 0 대입
    prefix_sum.push_back(0);

    int sum_value = 0;
    for (auto d : data) {
        sum_value += d;
        prefix_sum.push_back(sum_value);
    }

    int left = 3;
    int right = 4;
    cout << prefix_sum[right] - prefix_sum[left-1] << endl;


    return 0 ;
}

다만 위 코드는 90도 회전할 때마다 vector를 선언해 heap영역에 계속 쌓이게 된다.

여러번 돌리면 메모리 관점에서 좋지 않다.

그렇기 때문에 4번이 넘어가는 회전은 4로 나눈 나머지만 회전하는 등 사용에 주의가 필요하다.

투 포인터(Two Pointer) 알고리즘 : 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리

투 포인터는 다음 2가지 케이스가 대표적인 문제 유형이다.

1. 특정한 합(M)을 가지는 부분 연속 수열 찾기

   - 시간복잡도 : O(N) { O(2*N)}

   - 동작과정

      1) 시작점(s)와 끝점(e)를 첫 번째 원소의 인덱스(0)로 지정한다

      2) s부터 e까지 현재 부분합이 특정한 합(M)과 같다면 카운트한다.

      3) s부터 e까지 현재 부분합이 특정한 합(M)보다 작다면 e를 1 증가시킨다.

      4) s부터 e까지 현재 부분합이 특정합 합(M)보다 크다면 s를 1 증가시킨다.

      5) 모든 경우를 확인할 떄까지 2)번부터 4)까지의 과정을 반복한다.

#include <iostream>
#include <vector>

using namespace std;

int n = 5, m = 5; // 데이터의 개수 n, 찾고자 하는 부분합 m

int arr[] = {1, 2, 3, 2, 5};

int main(void) {
    int cnt = 0;
    int interval_sum = 0;
    int e = 0;

    // start를 차례때로 증가시키며 반복
    for (int s = 0; s < n; s++) {
        // end를 가능한 만큼 이동시키기
        while (interval_sum < m && e < n) {
            interval_sum += arr[e++];
        }

        // 부분합이 m일 때 카운트 증가
        if (interval_sum == m) {
            cnt++;
        }

        interval_sum -= arr[s];
    }

    cout << cnt << endl;

    return 0 ;
}

2. 정렬되어 있는 두 리스트의 정렬된 합집합

    - 시간복잡도 : O(N+M) [N: a 크기, M: b 크기]

    - 동작과정

      1) 정렬된 리스트 a와 b를 입력 받는다.

      2) 리스트 a에서 처리되지 않은 원소의 인덱스를 i로 지정한다.

      3) 리스트 b에서 처리되지 않은 원소의 인덱스를 j로 지정한다.

      4) a[i]와 b[j]중 저 작은 원소를 결과(result) 리스트에 담고 해당 리스트의 인덱스(i 또는 j)를 1 증가시킨다.

      5) a와 b에 처리할 원소가 없을 때까지 2) ~ 4) 과정을 반복한다.

#include <iostream>
#include <vector>

using namespace std;

// 사전에 정렬된 리스트 a, b 선언
int n = 3, m =4;
vector<int> a = {1, 3, 5};
vector<int> b = {2, 4, 6, 8};

int main(void) {
    int i = 0;
    int j = 0;
    // 리스트 a와 b의 모든 원소 담을 수 있는 결과 리스트
    vector<int> result;

    // 더 이상 리스트 a와 b에 처리할 원소가 없을 때까지 반복
    while (i < n || j < m) {
        // 리스트 b의 모든 원소가 처리되었거나, 리스트 a의 원소가 더 작을 경우
        if (j >= m || (i < n && a[i] <= b[j])) {
            result.push_back(a[i++]);
        }
        // 처리되지 않은 리스트 b의 원소가 존재하고 리스트 a의 모든 원소가 처리되었거나, 리스트 b의 원소가 더 작을 경우
        else {
            result.push_back(b[j++]);
        }
    }

    for (int r : result) {
        cout << r << " ";
    }
    cout << endl;

    return 0 ;
}

2번 코드에서 while문 안의 if-else구문에 조건이 여러개 들어가는데 이 부분이 익숙하지 않다.

익숙해지도록 하자.

2차원 리스트를 반시계방향으 90도 돌리는 함수 템플릿이다.

자주 사용될 것 같아 template으로 등록한다.

java, python을 이용한 코드는 많지만 c++을 이용한 코드는 찾기 어려워 따로 정리한다.

시계방향으로 90도 돌리고 싶은 경우 해당함수를 3번 돌리자.

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int> > rotate_a_matrix_by_90_degree(vector<vector<int> > &graph)
{
    int row_len = graph.size();
    int col_len = graph[0].size();

    vector<vector<int> > res(col_len, vector<int>(row_len, 0));    

    for (int i = 0; i < row_len; i++) {
        for (int j = 0; j < col_len; j++) {
            res[col_len-j-1][i] = graph[i][j];
        }
    }
    
    return res;
}
int main(void) {

    vector<int> t1 = {1,2,3,4};
    vector<int> t2 = {5,6,7,8};
    vector<int> t3 = {9,10,11,12};

    vector<vector<int> > a = {t1, t2, t3};


    // 반시계 방향 90도 돌리기
    vector<vector<int> > b = rotate_a_matrix_by_90_degree(a);

    for (int i = 0; i < b.size(); i++) {
        for (int j = 0; j < b[i]. size(); j++) {
            cout << b[i][j] << " ";
        }
        cout << endl;
    }

    // 시계 방향 90도 돌리기 =  반시계 방향 90도* 3 돌리기
    vector<vector<int> > c = rotate_a_matrix_by_90_degree(a);
    vector<vector<int> > d = rotate_a_matrix_by_90_degree(c);
    vector<vector<int> > e = rotate_a_matrix_by_90_degree(d);

    for (int i = 0; i < e.size(); i++) {
        for (int j = 0; j < e[i]. size(); j++) {
            cout << e[i][j] << " ";
        }
        cout << endl;
    }

    return 0 ;
}

1. 가장 기본적인 소수 판별 

   - 시간복잡도 : O(N)

#include <iostream>
#include <vector>

using namespace std;

int x;

bool isPrime(int x) {
    for (int i = 2; i < x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

int main(void) {
    cin >> x;

    cout << isPrime(x) << endl;

    return 0 ;
}

2. 성능을 높인 소수 판별

   - 시간복잡도 : O(sqrt(N))

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int x;

bool isPrime(int x) {
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

int main(void) {
    cin >> x;

    cout << isPrime(x) << endl;

    return 0 ;
}

2. 에라토스테네스의 체(성능 업그레이드 버전)

   - 시간복잡도 : O(N*log(log(N)))

   - 다수의 소수를 구할 경우에 사용한다.

   - 동작 과정

      1) 2부터 N까지의 모든 자연수를 나열한다.

      2) 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.

      3) 남은 수 중에서 i의 배수를 모두 제거한다.(i를 제거하지는 않는다, N까지의 i의 배수 제거)

      4) 더 이상 반복할 수 없을 때까지 2), 3) 과정을 반복한다.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int n = 1000;
vector<bool> prime(n+1, true);

// 에라토스테네스의 체
void makePrime(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        if (prime[i]) {
            int j = 2;
            while (i * j <= n) {
                prime[i * j] = false;
                j++;
            }
        }
    }
}

int main(void) {

    makePrime(n);

    // 0, 1 은 소수가 아니다.
    prime[0] = false;
    prime[1] = false;

    for (int i = 0; i <= n; i++) {
        if (prime[i])
            cout << i << " ";
    }
    cout << endl;

    return 0;
}

총정리 : 다수의 소수를 판별할 땐 3번[O(N*log(log(N)))]을, 적은 수의 소수를 판별할 땐 2번[O(sqrt(N))]을 사용하자.

느낀점

• 그래프 문제를 풀면서 어렵다고 느낀 부분은 말로 풀어진 문제를 그래프로 스스로 해석하여 풀어내는 사고방식이다.
• 이 문제는 '정해진 우선순위에 맞게 전체 팀들의 순서를 나열해야 한다'는 점에서 '위상정렬'을 떠올릴 수 있어야 한다.
• '각 팀'들을 '노드'로 작년 순위를 토대로 '팀 간 우선순위'를 방향성 간선으로 그린다.
• 이후 제시해주는 바뀐 팀간 우선순위를 토대로 간선의 방향을 바꿔 그린다.
• 이후 위상정렬을 통해 그래프를 그릴 수 있는지 확인해본다.
• 위상정렬은 2가지 주의사항이 있다.
  1. 사이클이 발생하는 경우                                 => 일관성이 없다.
  2. 위상정렬의 경우의 수가 2가지 이상인 경우    => 확실한 순위를 찾을 수 없다.

원본문제 : https://www.acmicpc.net/problem/3665

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

using namespace std;

int t;
int n;
int m;
int indegree[501];
bool graph[501][501];

void topologySort() {
    queue<int> q;

    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        } 
    }

    vector<int> ans;
    bool not_certain = false;
    bool cycle = false;
    for (int i = 0; i < n; i++) {
        if (q.size() == 0) {
            cycle = true;
            break;
        }
        if (q.size() > 1) {
            not_certain = true;
            break;
        }

        int now = q.front();
        ans.push_back(now);
        q.pop();

        int chk_double = 0;
        for (int j = 1; j <= n; j++) {
            if (graph[now][j]) {
                indegree[j]--;
                if (indegree[j] == 0) {
                    q.push(j);
                }
            }
        }
    }

    if (cycle) {
        cout << "IMPOSSIBLE" << endl;
        return;
    }
    if (not_certain) {
        cout << "?" << endl;
        return;
    }
    
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";    
    }
    cout << endl;

}

int main(void) {
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;

        fill(indegree, indegree+501, 0);
        fill(graph[0], graph[0]+501*501, false);

        vector<int> v;
        for (int j = 0; j < n; j++) {
            int a;
            cin >> a;
            v.push_back(a);
        }

        for (int j = 0; j < n; j++) {
            for (int k = j+1; k < n; k++) {
                graph[v[j]][v[k]] = true;
                indegree[v[k]]++;
            }
        }

        cin >> m;
        for (int j = 0; j < m; j++) {
            int  a, b;
            cin >> a >> b;
            if (graph[a][b]) {
                indegree[a]++;
                indegree[b]--;
            }
            if (graph[b][a]) {
                indegree[a]--;
                indegree[b]++;
            }
            swap(graph[a][b], graph[b][a]);
        }

        topologySort();
    }
    return 0 ;
}

문제

공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지 번호로 구분된다. 공항에는 P개의 비행기가 차례대로 도착할 예정이며, ii번째 비행기를 1번부터 gigi(1 <= gigi <= G) 탑승구 중 하나에 영구적으로 도킹하려 한다. 이 때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹이 가능하다. 또한 P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중단한다. 공항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 한다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력해라

입력

• 첫째 줄에는 탑승구의 수 G(1 <= G <= 100,000)가 주어진다.
• 둘째 줄에는 비행기의 수 P(1 <= P <= 100,000)가 주어진다.
• 다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 gg(1 <= gg <= G)가 주어진다. 이는 ii번째 비행기가 1번부터 gigi번째(1 <= gigi <= G) 탑승구 중 하나에 도킹할 수 있다는 의미이다.

출력

• 첫째 줄에 도킹할 수 있는 비행기의 최대 개수를 출력해라.

느낀점

• 이 문제는 처음에 단순 구현이 떠올랐다. 그래프 카테고리에 있음에도..이 문제는 추가적인 테스트케이스가 제공되지 않아 정답임을 확인할 수는 없었다. 아마 틀렸을 것이다. 그리고 답안을 보니 너무 쉽다.
• 또한 union-find가 서로소를 판별하기 위한 알고리즘으로 대표적이지만 집합의 제한을 하기에도 사용됨을 깨닫게 해준 문제다.
• 이 문제를 다시 푼다고 해도 union-find를 떠올릴지 의아하다...
• '공항'을 root탑승구를 가진 하나의 '집합'으로 바라보고 하나의 비행기가 탑승구에 집합할 때마다 union 한다.
• "더 이상 union할 수 있는 탑승구가 없다 == 0번 탑승구에 도킹해야 한다" 가 나오면 더이상 도킹할 수 없으므로  공항의 운행을 중단한다.

#include <iostream>
#include <vector>

using namespace std;

int g, p;
int parent[100001];

int findParent(int a) {
    if (parent[a] != a) {
        parent[a] = findParent(parent[a]);
    }
    return parent[a];
}

void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    if (a < b) {
        parent[b] = a;
    }
    else {
        parent[a] = b;
    }
}

int main(void) {
    cin >> g >> p;

    for (int i = 1; i <= g; i++) {
        parent[i] = i;
    }

    int ans = 0;
    for (int i = 0; i < p; i++) {
        int a;
        cin >> a;
        int root = findParent(a);
        if (root != 0) {
            ans++;
            unionParent(root, root-1);
        }
        else {
            break;
        }
    }

    cout << ans << endl;


    return 0 ;
}

위상정렬이란, 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다.

키 포인트는 '진입차수(indegree)'이다.

1) 진입차수가 0인 노드를 큐에 넣는다.

2) 큐가 빌 때까지 다음의 과정을 반복한다.

   2-1) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.

   2-2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

위상정렬의 시간복잡도는 O(V+E)이다.

차례대로 모든 노드를 확인하면서 해당노드에서 출발하는 간선을 제거한다.

즉, 노드와 간선을 전부 한번씩 탐색한다고 생각하면 된다.

큐에 I/O하는 시간은 V와 같으므로 무시한다.

주의사항은 다음과 같다.

1. 위상정렬 도중, 사이클이 발생할 수도 있다.

2. 위상정렬로 나열한 경우의 수가 2가지 이상일 수 있다.

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

using namespace std;

// 노드의 개수(v)와 간선의 개수(e)
// 노드의 개수는 최대 100000개 라고 가정
int v, e;
// 모든 노드에 대한 진입차수는 0으로 초기화
int indegree[100001];
// 각 노드에 연결된 간선 정보를 담기위한 인접 리스트 초기화
vector<int> graph[100001];

// 위상 정렬 함수
void topologySort() {
    vector<int> result; // 알고리즘 수행 결과를 담을 리스트
    queue<int> q; // 진입차수 0인 노드를 넣을 큐


    // 처음 시작할 때는 진입차수 0인 노드를 큐에 삽입
    for (int i = 1; i <= v; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    // 큐가 빌때까지 반복
    while (!q.empty()) {
        // 큐에서 원소 꺼내기
        int now = q.front();
        q.pop();
        result.push_back(now);

        // 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for (int e : graph[now]) {
            indegree[e]--;    
            // 새롭게 진입차수가 0이 되는 노드 큐에 삽입
            if (indegree[e] == 0) {
                q.push(e);    
            }
        }
    }

    // 위상 정렬을 수행한 결과 출력
    for (int x: result) {
        cout << x << " ";
    }
    cout << endl;

}

int main(void) {
    cin >> v >> e;
    // 방향그래프의 모든 간선 정보를 입력 받기
    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b); // 정점 a에서 b로 이동 가능
        // 진입 차수를 1 증가
        indegree[b] += 1;
    }

    topologySort();

    return 0 ;
}

📌 신장트리(Spanning Tree) : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

크루스칼 알고리즘 : 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘, Union-FInd를 이용

1) 간선 데이터를 비용에 따라 오름차순으로 정렬한다.

2) 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.

    2-1) 사이클 발생하지 않는 경우 : 최소 신장트리에 포함시킨다.

    2-2) 사이클이 발생하는 경우 : 최소 신장트리에 포함시키지 않는다.

3) 모든 간선에 대하여 2번의 과정을 반복한다.

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

using namespace std;

// 노드의 개수(v)와 간선(e)의 개수
// 노드의 개수는 최대 100000개라고 가정
int v, e;
int parent[100001];

// 특정 원소가 속한 집합을 찾기
int findParent(int x) {
     if (parent[x] != x) {
         parent[x] = findParent(parent[x]);
     }
     return parent[x];
 }

// 두 원소가 속한 집합을 합치기
void unionParent(int x, int y) {
    x = findParent(x);
    y = findParent(y);

    if (x < y) {
        parent[y] = x;
    }
    else {
        parent[x] = y;
    }
}

int main(void) {
    vector<tuple<int, int, int> > edge;

    cin >> v >> e;

    // 부모테이블 상에서, 부모를 자기 자신으로 초기화
    for (int i = 1; i <= v; i++) {
        parent[i] = i;
    }

    // union 연산을 각각 수행
    for (int i = 0; i < e; i++) {
        int a, b, d;
        cin >> a >> b >> d;
        edge.push_back(make_tuple(d, a, b));
    }

    // 간선 거리별 오름차순 정렬
    sort(edge.begin(), edge.end()); // greater<int>()

    int sum = 0;
    for (auto t : edge) {
        int a, b, d;
        tie(d, a, b) = t;
        if (findParent(a) != findParent(b)) {
            unionParent(a, b);
            sum += d;
        }
    }
    
    cout << sum << endl;

    return 0 ;
}

🛑 유의사항 : template에서 사용한 tuple은 c++11버전에서만 사용할 수 있다.