취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2691번 문제인 이항 쇼다운이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/6591

주어지는 n과 k 값을 받아 입력이 끝날 때까지 이항계수를 계산해나가는 문제이다.

이항계수는 (n부터 하나씩 감소하는 k개의 수의 곱) / (1부터 하나씩 증가하는 k개의 수의 곱)으로 계산할 수 있다.

특히, 연속된 x개의 자연수의 곱에는 x의 배수가 무조건 있으므로 계산 과정에서 소수점이 나오지 않게 식을 만들 수 있다.

답안의 크기는 int범위 내이지만 중간 계산과정에서 int의 범위를 넘어설 수 있으므로 ans 변수를 long long으로 지정하였다.

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int x, y;
    cin >> x >> y;
    while (x + y != 0) {
        if (y > x - y) y = x - y;
        long long ans = 1;
        for (int i = 1;i <= y;i++) {
            ans *= x;
            ans /= i;
            x--;
        }
        cout << ans << '\n';
        cin >> x >> y;
    }
    return 0;
}

0. 필요한 배경지식

 - 가장 긴 단조증가하는 부분수열

 - 비둘기집의 원리(pigeonhole principle)

1. 서론

가장 긴 단조증가하는 부분수열(LIS)를 찾는 문제는 이산수학에서 유명한 문제로, 길이 N인 수열의 LIS의 길이를 구하는 문제나 그런 길이의 단조증가 부분수열을 직접 찾는 문제는 모두 O(NlogN)에 해결할 수 있다.

심지어는 길이가 N인 수열의 서로 다른 LIS가 몇 개 존재하는지 찾는 문제 또한 O(NlogN)에 해결할 수 있다.

LIS를 구하다보면 LIS가 전체 수열의 길이에 비해 특히 짧은 경우들을 자주 만날 수 있다.

이런 경우를 만나면 LIS와 반대방향인, 가장 긴 단조감소하는 부분수열(이후 LDS라 칭한다)의 길이가 길어지는 것이 자주 눈에 띄지 않는가?

Erdős–Szekeres Theorem은 이러한 관점에서 바라볼 때, 주어진 모든 원소가 서로 다른(distinct) 수열이 주어졌을 때 LIS의 길이와 LDS의 길이 사이의 상관관계를 보여주는 정리이다.

2. 정리 소개

Erdős–Szekeres theorem는 다음과 같이 서술할 수 있다.

두 수 r과 s에 대하여, 모든 원소가 서로 다른(distinct) 길이가 rs + 1인 수열은

길이 r + 1인 LIS를 포함하거나 길이 s + 1인 LDS를 포함한다.

rs + 1보다 더 긴 길이의 수열은 길이가 rs + 1인 부분수열을 포함하므로 위의 성질을 만족한다.

증명을 하기 전에, 길이가 (r - 1)(s - 1)인 수열중에서 길이가 r + 1인 단조증가 부분수열과 길이가 s + 1인 단조감소 부분수열이 둘 다 존재하지 않는 예시를 직접 찾아보자. 아래 접은 글로 그러한 수열의 예시를 적어두었다.

3. 증명

이 글에서는 Seidenberg의 증명을 소개한다.

길이가 rs + 1이고 모든 원소가 서로 다른 임의의 수열 a_i를 생각하자.

또한, m_i를 a_i서부터 시작되는 부분수열의 LIS의 길이, n_i를 a_i서부터 시작되는 부분수열의 LDS의 길이로 정의하자.

임의의 i < j에 대하여, 다음이 성립한다는 것을 쉽게 관찰할 수 있다.

 - a_i < a_j 이면 m_i > m_j 이다.

 - 반대로 a_i > a_j 이면 n_i > n_j 이다.

따라서, 각 i에 순서쌍 (m_i, n_i)를 대응시키면, 수열 a_i는 길이가 rs + 1이므로 서로 다른 rs + 1개의 순서쌍 (m_i, n_i)를 얻을 수 있다.

만약 a_i의 LIS의 길이가 r이고 LDS의 길이가 s이면, 만들 수 있는 서로 다른 순서쌍 (m_i, n_i)의 개수는 많아야 rs개이다.

따라서, 수열의 항이 rs개보다 많으므로, 비둘기집의 원리에 의해 이는 모순임을 알 수 있다.

따라서, LIS의 길이가 r보다 크거나, LDS의 길이가 s보다 클 수밖에 없음을 알 수 있다.

이것으로 Erdős–Szekeres Theorem이 증명되었다.

4. 응용

Erdős–Szekeres Theorem을 기하학적으로 생각해보자.

위 증명에서의 수열의 각 항 a_i를 2차원 좌표평면 위의 점 (i, a_i)에 대응시켜 생각을 해보면, Erdős–Szekeres theorem은 좌표평면 위의, 같은 x좌표 또는 y좌표를 가지지 않는 rs + 1개의 점에서 기울기가 연속적으로 양수인 r + 1개의 점 또는 기울기가 연속적으로 음수인 s + 1개의 점을 항상 찾을 수 있다는 것을 말해준다.

5. 여담

글쓴이는 다음 문제를 풀고 관련된 내용을 찾아보다가 위의 내용을 정리하게 되었다.

관심이 있다면 다음 문제를 풀어보자.

www.acmicpc.net/problem/1201

6. 참고한 내용

위키백과 Erdős–Szekeres Theorem: en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem

Seidenberg, A. (1959), "A simple proof of a theorem of Erdős and Szekeres"

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16467번 문제인 병아리의 변신은 무죄이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/16467

이 문제는 최대 100개의 테스트케이스에 대해서, 문제에서 주어진 점화관계를 이용해 최대 1억번째 항을 계산해내는 문제이다. 따라서 만약 점화관계를 그대로 반복계산해 나간다면, 시간초과가 날 수밖에 없다.

따라서 위와 같은 시간초과를 피하기 위해

1) 점화관계를 행렬의 곱으로 표현하고

2) 행렬의 거듭제곱을 binary exponentiation을 통해 빠르게 계산하는 방법을 이용해볼 수 있다.

이 문제에서 요구하는 점화식은 다음과 같은 단순한 형태이다.

(다음 날 병아리 수) = (오늘 병아리 수) + (K일 전날 병아리 수)

이 문제에서 modulo 연산을 요구하는 숫자가 1,000,000,007이 아닌 100,000,007임에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;
typedef long long ll;

int main()
{
    int T; cin >> T;
    for (int t = 0;t < T;t++) {
        int K, N;
        cin >> K >> N;
        ll mat[12][12];
        ll ans[12];
        for (int i = 0;i <= K;i++) {
            ans[i] = 0;
            for (int j = 0;j <= K;j++) {
                mat[i][j] = 0;
            }
        }
        for (int i = 0;i < K;i++) {
            mat[i + 1][i] = 1;
        }
        mat[0][0] = 1;
        mat[0][K] += 1; // K=0인 경우 mat[0][0]에 1을 더하는게 맞다
        ans[0] = 1;
        while (N > 0) {
            if (N & 1) { // ans에 mat을 곱한다
                ll ans_t[11];
                for (int i = 0;i <= K;i++) {
                    ans_t[i] = 0;
                    for (int j = 0;j <= K;j++) {
                        ans_t[i] += mat[i][j] * ans[j];
                    }
                }
                for (int i = 0;i <= K;i++) {
                    ans[i] = ans_t[i]%100000007;
                }
            }
            // mat의 제곱을 구한다.
            ll mat_t[12][12];
            for (int i = 0;i <= K;i++) {
                for (int j = 0;j <= K;j++) {
                    mat_t[i][j] = 0;
                    for (int k = 0;k <= K;k++) {
                        mat_t[i][j] += mat[i][k] * mat[k][j];
                    }
                }
            }
            for (int i = 0;i <= K;i++) {
                for (int j = 0;j <= K;j++) {
                    mat[i][j] = mat_t[i][j]%100000007;
                }
            }
            N >>= 1;
        }
        cout << ans[0] << '\n';
    }

    return 0;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11404번 문제인 플로이드이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11404

이 문제는 플로이드-워셜(Floyd-Warshall) 알고리즘을 연습하는 문제이다.

단, 문제와 예제에 있듯이 한 도시에서 다른 도시로 연결하는 간선이 여러개일 수 있음을 유의해야 한다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
using std::min;
using std::cin;
using std::cout;

int city[101][101];

int main()
{
    int N, M;
    cin >> N >> M;
    for (int i = 1;i <= N;i++) {
        for (int j = 1;j <= N;j++) {
            if (i == j) city[i][j] = 0;
            else city[i][j] = 1000000001;
        }
    }
    for (int i = 0;i < M;i++) {
        int s, e, w;
        cin >> s >> e >> w;
        city[s][e] = min(city[s][e], w); // 입력을 받을 때, 가장 비용이 적은 노선만 입력받는다.
    }
    for (int m = 1;m <= N;m++) { // Floyd-Warshall
        for (int i = 1;i <= N;i++) {
            for (int j = 1;j <= N;j++) {
                city[i][j] = min(city[i][j], city[i][m] + city[m][j]);
            }
        }
    }
    for (int i = 1;i <= N;i++) {
        for (int j = 1;j <= N;j++) {
            cout << ((city[i][j] == 1000000001) ? 0 : city[i][j]) << ' ';
        }
        cout << "\n";
    }
    return 0;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 14938번 문제인 서강그라운드이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/14938

BFS나 Floyd-Warshall로도 충분히 해결 가능하겠지만, 그래프의 크기가 작고, 탐색이 필요한 거리가 짧으므로 다익스트라(dijkstra) 알고리즘으로 풀어보았다.

이 문제를 다익스트라 알고리즘으로 해결하려면 다음과 같이 풀면 된다.

1) 각 노드에서 다익스트라 알고리즘을 실행한다. 이때, 어떤 노드의 가장 짧은 거리가 M을 넘어서면 그 이상의 그래프 정보는 필요없으므로 알고리즘을 중단한다.

2) 각 노드까지의 거리가 M 이하인 노드에 대응되는 아이템의 개수를 더한 합을 구한다.

3) 2에서 구한 합들 중 최댓값을 구한다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using std::cin;
using std::cout;
using std::vector;
using std::priority_queue;
using std::pair;

int items[101];
int dist[101];
bool done[101];
vector<pair<int, int>> G[101];

int main()
{
    int N, M, R;
    cin >> N >> M >> R;
    for (int i = 1;i <= N;i++) {
        int x; cin >> x;
        items[i] = x;
    }
    for (int i = 0;i < R;i++) {
        int a, b, w;
        cin >> a >> b >> w;
        G[a].push_back({ b,w });
        G[b].push_back({ a,w });
    }
    int ans = 0;
    for (int i = 1;i <= N;i++) { // 각각의 노드에 대하여 dijkstra를 이용
        priority_queue<pair<int, int>> pq;
        for (int j = 1;j <= N;j++) {
            dist[j] = 2222;
            done[j] = false;
        }
        dist[i] = 0;
        pq.push({ 0,i });
        while (!pq.empty()) {
            int current = pq.top().second; pq.pop();
            if (done[current]) continue;
            else if (dist[current] > M) break; // M을 넘어서는 거리가 등장하면 탐색 중단
            done[current] = true;
            for (auto following : G[current]) {
                int fnode = following.first;
                int fweight = following.second;
                if (dist[fnode] > dist[current] + fweight) {
                    dist[fnode] = dist[current] + fweight;
                    pq.push({ -dist[fnode],fnode });
                }
            }
        }
        int s = 0;
        for (int j = 1;j <= N;j++) s += (dist[j] <= M) ? items[j] : 0; // 거리가 M 이하인 점에 대해서만
        if (s > ans) ans = s;
    }
    cout << ans;

    return 0;
}

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11779번 문제인 최소비용 구하기 2이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11779

이 문제에서는 다익스트라(dijkstra) 알고리즘을 이용해 최단경로를 찾으면서, 그 최단경로에서 지나온 노드를 하나하나 출력해줘야 한다.

다익스트라 알고리즘을 실행하면 출발점에서 각 노드까지의 최단 거리를 얻을 수 있는데, 그 경로를 이으면 출발점을 root로 갖는 트리구조를 얻을 수 있다.

여기서, 도착지점 노드에서 조상(parent) 노드를 출발점 노드인 root 노드까지 하나씩 거슬러 올라가면서 만나는 노드들이 바로 출발지점 노드에서 도착지점 노드까지 가는 최단경로에 있는 노드들이 된다.

따라서, dijkstra를 하면서 priority queue에 다음 방문우선순위를 집어넣을 때, 그 노드의 parent node를 갱신하는 방식으로 알고리즘을 만들면 이 문제는 해결 가능하다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using std::cin;
using std::cout;
using std::priority_queue;
using std::vector;
using std::pair;

vector<pair<int, int>> G[1001];
priority_queue<pair<int, int>> pq;
int dist[1001];
int parent[1001];
bool done[1001];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    for (int i = 0;i < M;i++) {
        int s, e, w; cin >> s >> e >> w;
        G[s].push_back({ e,w });
    }
    int S, E;
    cin >> S >> E;
    for (int i = 1;i <= N;i++) {
        dist[i] = 1000000000;
    }
    dist[S] = 0;
    parent[S] = S;
    pq.push({ 0,S });
    while (!pq.empty()) { // dijkstra
        int current = pq.top().second; pq.pop();
        if (done[current]) continue;
        else if (current == E) break;
        done[current] = true;
        for (auto following : G[current]) {
            int fnode = following.first;
            int fweight = following.second;
            if (dist[fnode] > dist[current] + fweight) {
                dist[fnode] = dist[current] + fweight;
                pq.push({ -dist[fnode],fnode });
                parent[fnode] = current; // parent 정보 갱신
            }
        }
    }
    cout << dist[E] << "\n";
    vector<int> stk; // 역순 출력을 위해 stack에 담기
    while (E != parent[E]) { // parent[S]=S, 나머지 점에서는 각 노드의 조상
        stk.push_back(E);
        E = parent[E];
    }
    stk.push_back(E); // root 노드를 넣어준다
    cout << stk.size() << "\n";
    while (!stk.empty()) {
        cout << stk.back() << ' ';
        stk.pop_back();
    }
}