UCPC 2022 예선 D-16, D-15 문제풀이 일지

목차

1. 오늘의 알고리즘 진도

- 24416번: 알고리즘 수업 - 피보나치 수 1

- 9184번: 신나는 함수 실행

- 1912번: 연속합

- 1932번: 정수 삼각형

- 14002번: 가장 긴 증가하는 부분 수열 4

- 11054번: 가장 긴 바이토닉 부분 수열

- 12105번: 가장 긴 증가하는 부분 수열 2

- 14003번: 가장 긴 증가하는 부분 수열 5

- 2565번: 전깃줄

- 2568번: 전깃줄 - 2

- 9251번: LCS

- 9252번: LCS 2

- 12865번: 평범한 배낭

- 9084번: 동전

---

오늘의 알고리즘 진도

오늘은 다이나믹 프로그래밍 수련의 날로 정했습니다. 그래서 다이나믹 프로그래밍 문제를 14개 풉니다.

C++ 코드 템플릿

혹시 제 코드를 참고하실 분들은 코드 최상단에 아래의 코드를 붙여넣어 주세요.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
#define F first
#define S second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define forn(i, a, b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()

24416번: 알고리즘 수업 - 피보나치 수 1

https://www.acmicpc.net/problem/24416

24416번: 알고리즘 수업 - 피보나치 수 1

피보나치 수를 계산할 때 재귀 호출과 다이나믹 프로그래밍의 효율성을 비교하는 실습 문제입니다.

int code1 = 0;
int code2 = 0;

int fib(int n) {
    if (n <= 2) {
        ++code1;
        return 1;
    }
    return fib(n-1) + fib(n-2);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    fib(n);
    vector<int> fibonacci(n+1);
    fibonacci[1] = fibonacci[2] = 1;
    forn(i, 3, n) {
        ++code2;
        fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
    }
    cout << code1 << " " << code2;

    return 0;
}

알고리즘 분류: 수학, 다이나믹 프로그래밍

현 시점 난이도: 브론즈 I

9184번: 신나는 함수 실행

https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

3차원 테이블이 사용되지만, 점화식이 문제에 주어져 있어 쉬운 문제.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b, c;
    cin >> a >> b >> c;
    vector<vector<vector<int>>> w(21, vector<vector<int>>(21, vector<int>(21)));
    forn(i, 0, 20) {
        forn(j, 0, 20) {
            forn(k, 0, 20) {
                if (i == 0 || j == 0 || k == 0) {
                    w[i][j][k] = 1;
                } else if (i < j && j < k) {
                    w[i][j][k] = w[i][j][k-1] + w[i][j-1][k-1] - w[i][j-1][k];
                } else {
                    w[i][j][k] = w[i-1][j][k] + w[i-1][j-1][k] + w[i-1][j][k-1] - w[i-1][j-1][k-1];
                }
            }
        }
    }
    while (a != -1 || b != -1 || c != -1) {
        if (a <= 0 || b <= 0 || c <= 0) {
            cout << "w(" << a << ", " << b << ", " << c << ") = 1\n";
        } else if (a > 20 || b > 20 || c > 20) {
            cout << "w(" << a << ", " << b << ", " << c << ") = " << w[20][20][20] << "\n";
        } else {
            cout << "w(" << a << ", " << b << ", " << c << ") = " << w[a][b][c] << "\n";
        }
        cin >> a >> b >> c;
    }

    return 0;
}

알고리즘 분류: 다이나믹 프로그래밍, 재귀

현 시점 난이도: 실버 II

1912번: 연속합

https://www.acmicpc.net/problem/1912

1912번: 연속합

DP 문제긴 한데, DP 테이블 없이도 풀 수 있습니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int ans = -1e9;
    int cur = 0;
    forn(i, 1, n) {
        int a;
        cin >> a;
        cur = max(cur+a, a);
        ans = max(ans, cur);
    }
    cout << ans;

    return 0;
}

알고리즘 분류: 다이나믹 프로그래밍

현 시점 난이도: 실버 II

1932번: 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

2차원 테이블로 해결되는 기본 DP 문제.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<int>> tri(n, vector<int>(n));
    forn(i, 0, n-1) {
        forn(j, 0, i) cin >> tri[i][j];
    }
    vector<vector<int>> ans(n, vector<int>(n));
    ans[0][0] = tri[0][0];
    forn(i, 1, n-1) {
        ans[i][0] = ans[i-1][0] + tri[i][0];
        ans[i][i] = ans[i-1][i-1] + tri[i][i];
        forn(j, 1, i-1) {
            ans[i][j] = max(ans[i-1][j-1], ans[i-1][j]) + tri[i][j];
        }
    }
    int mx = 0;
    forn(i, 0, n-1) mx = max(mx, ans[n-1][i]);
    cout << mx;

    return 0;
}

알고리즘 분류: 다이나믹 프로그래밍

현 시점 난이도: 실버 I

14002번: 가장 긴 증가하는 부분 수열 4

https://www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

LIS(Longest Increasing Subsequence) 문제인데, 길이뿐 아니라 실제로 부분 수열이 어떻게 이루어지는지를 출력해야 합니다.

i번째 원소를 포함하는 최장 증가 부분 수열의 길이와 그 부분 수열의 직전 원소를 저장하는 lis 배열을 정의하여 해결해 보았습니다.

 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N);
    forn(i, 0, N-1) cin >> A[i];
    vector<pii> lis(N); // {length, prev}
    int mx = 0;
    forn(i, 0, N-1) {
        lis[i] = {1, -1};
        forn(j, 0, i-1) {
            if (A[j] < A[i] && lis[j].F + 1 > lis[i].F) {
                lis[i] = {lis[j].F + 1, j};
            }
        }
        if (lis[mx].F < lis[i].F) mx = i;
    }
    int l = lis[mx].F;
    cout << l << "\n";
    vector<int> ans;
    while (mx != -1) {
        ans.PB(mx);
        mx = lis[mx].S;
    }
    forn(i, 1, l) {
        cout << A[ans[l-i]] << " ";
    }

    return 0;
}

알고리즘 분류: 다이나믹 프로그래밍

현 시점 난이도: 골드 IV

11054번: 가장 긴 바이토닉 부분 수열

https://www.acmicpc.net/problem/11054

11054번: 가장 긴 바이토닉 부분 수열

가장 긴 바이토닉 부분 수열을 최대 원소를 기준으로 두 부분으로 나눌 수 있습니다.

그렇기 때문에, 각 인덱스 i에 대해 i를 끝점으로 하는 최대 증가 부분 수열과, i를 시작점으로 하는 최대 감소 부분 수열을 각각 구하면 됩니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N);
    forn(i, 0, N-1) cin >> A[i];
    vector<int> lis(N), lds(N);
    forn(i, 0, N-1) {
        lis[i] = 1;
        forn(j, 0, i-1) {
            if (A[j] < A[i]) lis[i] = max(lis[i], lis[j] + 1);
        }
        lds[N-1-i] = 1;
        forn(j, 0, i-1) {
            if (A[N-1-j] < A[N-1-i]) lds[N-1-i] = max(lds[N-1-i], lds[N-1-j] + 1);
        }
    }
    int mx = 0;
    forn(i, 0, N-1) mx = max(mx, lis[i] + lds[i] - 1);
    cout << mx;

    return 0;
}

알고리즘 분류: 다이나믹 프로그래밍

현 시점 난이도: 골드 III

12105번: 가장 긴 증가하는 부분 수열 2

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

이 문제를 풀려면 O(nlogn) LIS 풀이를 알고 있어야 합니다. 스스로 깨닫기는 어려우니 검색해 보시고 풀이에 들어갑시다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> lis;
    forn(i, 0, N-1)  {
        cin >> A[i];
        if (i == 0 || lis.back() < A[i]) lis.PB(A[i]);
        else {
            int lb = lower_bound(all(lis), A[i]) - lis.begin();
            lis[lb] = A[i];
        }
    }
    cout << lis.size();

    return 0;
}

알고리즘 분류: 이분 탐색, 가장 긴 증가하는 부분 수열: o(n log n)

현 시점 난이도: 골드 II

14003번: 가장 긴 증가하는 부분 수열 5

https://www.acmicpc.net/problem/14003

14003번: 가장 긴 증가하는 부분 수열 5

O(nlogn) LIS 역추적 문제입니다. 배열의 i번째 원소가 LIS에서 몇 번째 원소에 해당하는지 인덱스를 따로 저장하고, nlogn 만큼 걸리는 과정이 끝난 뒤 시간을 추가로 n만큼 들여 역추적하면 되겠습니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> len(N);
    vector<int> lis;
    forn(i, 0, N-1)  {
        cin >> A[i];
        if (i == 0 || lis.back() < A[i]) {
            lis.PB(A[i]);
            len[i] = lis.size();
        }
        else {
            int lb = lower_bound(all(lis), A[i]) - lis.begin();
            lis[lb] = A[i];
            len[i] = lb + 1;
        }
    }
    int l = lis.size();
    cout << l << "\n";
    stack<int> st;
    forn(i, 1, N) {
        if (len[N-i] == l) {
            st.push(A[N-i]);
            --l;
        }
    }
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }

    return 0;
}

알고리즘 분류: 이분 탐색, 가장 긴 증가하는 부분 수열: o(n log n)

현 시점 난이도: 플래티넘 V

2565번: 전깃줄

https://www.acmicpc.net/problem/2565

2565번: 전깃줄

대표적인 LIS 응용 문제입니다. 입력을 한 번 정렬하고 나면 풀이 방법이 명확해집니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<pii> L(N);
    forn(i, 0, N-1) cin >> L[i].F >> L[i].S;
    sort(all(L));
    vector<int> lis;
    forn(i, 0, N-1) {
        if (i == 0 || lis.back() < L[i].S) {
            lis.PB(L[i].S);
        } else {
            int lb = lower_bound(all(lis), L[i].S) - lis.begin();
            lis[lb] = L[i].S;
        }
    }
    cout << N - lis.size();

    return 0;
}

알고리즘 분류: 다이나믹 프로그래밍

현 시점 난이도: 골드 V

2568번: 전깃줄 - 2

https://www.acmicpc.net/problem/2568

2568번: 전깃줄 - 2

전깃줄 문제의 입력이 커지고 역추적이 들어가는 문제.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<pii> L(N);
    forn(i, 0, N-1) cin >> L[i].F >> L[i].S;
    sort(all(L));
    vector<int> len(N);
    vector<int> lis;
    forn(i, 0, N-1) {
        if (i == 0 || lis.back() < L[i].S) {
            lis.PB(L[i].S);
            len[i] = lis.size();
        } else {
            int lb = lower_bound(all(lis), L[i].S) - lis.begin();
            lis[lb] = L[i].S;
            len[i] = lb + 1;
        }
    }
    int l = lis.size();
    cout << N - l << "\n";
    stack<int> st;
    forn(i, 1, N) {
        if (len[N-i] == l) --l;
        else st.push(L[N-i].F);
    }
    while (!st.empty()) {
        cout << st.top() << "\n";
        st.pop();
    }

    return 0;
}

알고리즘 분류: 가장 긴 증가하는 부분 수열: o(n log n)

현 시점 난이도: 플래티넘 V

9251번: LCS

https://www.acmicpc.net/problem/9251

9251번: LCS

이번에는 최장 공통 부분 수열(Longest Common Subsequence, LCS) 문제입니다.

기초적인 개념은 검색을 통해 익힌 후 구현은 직접 해보았습니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string A, B;
    cin >> A >> B;
    int N = A.size();
    int M = B.size();
    vector<vector<int>> len(N, vector<int>(M));
    forn(i, 0, N-1) {
        forn(j, 0, M-1) {
            if (A[i] != B[j]) {
                int x, y;
                x = i > 0 ? len[i-1][j] : 0;
                y = j > 0 ? len[i][j-1] : 0;
                len[i][j] = max(x, y);
            } else {
                if (i == 0 || j == 0) len[i][j] = 1;
                else len[i][j] = len[i-1][j-1] + 1;
            }
        }
    }
    cout << len[N-1][M-1];

    return 0;
}

알고리즘 분류: 다이나믹 프로그래밍, 문자열

현 시점 난이도: 골드 V

9252번: LCS 2

https://www.acmicpc.net/problem/9252

9252번: LCS 2

앞 LCS 문제에 역추적이 포함된 문제입니다. 역추적의 아이디어는 쉽지만 구현이 조금 까다로울 수 있습니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string A, B;
    cin >> A >> B;
    int N = A.size();
    int M = B.size();
    vector<vector<int>> len(N, vector<int>(M));
    forn(i, 0, N-1) {
        forn(j, 0, M-1) {
            if (A[i] != B[j]) {
                int x, y;
                x = i > 0 ? len[i-1][j] : 0;
                y = j > 0 ? len[i][j-1] : 0;
                len[i][j] = max(x, y);
            } else {
                if (i == 0 || j == 0) len[i][j] = 1;
                else len[i][j] = len[i-1][j-1] + 1;
            }
        }
    }
    cout << len[N-1][M-1] << "\n";
    stack<char> st;
    int i = N-1, j = M-1;
    while (i >= 0 && j >= 0 && len[i][j] > 0) {
        if (i > 0 && len[i][j] == len[i-1][j]) --i;
        else if (j > 0 && len[i][j] == len[i][j-1]) --j;
        else {
            st.push(A[i]);
            --i;
            --j;
        }
    }
    while (!st.empty()) {
        cout << st.top();
        st.pop();
    }

    return 0;
}

알고리즘 분류: 다이나믹 프로그래밍

현 시점 난이도: 골드 IV

12865번: 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

냅색(Knapsack) 기본 문제에 속합니다.

2차원 테이블을 사용해서 풀면 비교적 직관적이고, 저는 1차원 테이블을 사용하였습니다. 1차원 테이블을 사용하는 경우 값을 큰 경우부터 작은 경우의 순서로 계산하는 트릭이 필요합니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    vector<pii> item(N);
    int max_weight = 0;
    forn(i, 0, N-1) {
        cin >> item[i].F >> item[i].S;
        max_weight += item[i].F;
    }
    vector<int> max_value(max_weight+1);
    int ans = 0;
    forn(i, 0, N-1) {
        for (int x = max_weight - item[i].F; x >= 0; --x) {
            if (max_value[x+item[i].F] < max_value[x] + item[i].S) {
                max_value[x+item[i].F] = max_value[x] + item[i].S;
            }
            if (x+item[i].F <= K) {
                ans = max(ans, max_value[x+item[i].F]);
            }
        }
    }
    cout << ans;

    return 0;
}

알고리즘 분류: 다이나믹 프로그래밍, 배낭 문제

현 시점 난이도: 골드 V

9084번: 동전

https://www.acmicpc.net/problem/9084

9084번: 동전

냅색 문제의 응용인데, 1차원 배열만으로도 앞서 언급한 트릭 없이 해결이 가능합니다.

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<int> coin(N);
        forn(i, 0, N-1) {
            cin >> coin[i];
        }
        int M;
        cin >> M;
        vector<int> ans(M+1);
        ans[0] = 1;
        forn(i, 0, N-1) {
            forn(x, 0, M-coin[i]) {
                ans[x + coin[i]] += ans[x];
            }
        }
        cout << ans[M] << "\n";
    }

    return 0;
}

알고리즘 분류: 다이나믹 프로그래밍, 배낭 문제

현 시점 난이도: 골드 V

---

너무 피곤한 관계로 오늘은 여기까지...