취미로 코딩하기

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

이번에 볼 문제는 백준 18171번 문제인 ABB이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/18171

문제를 간단히 요약하면, 입력으로 첫 줄에 1 이상 40만 이하의 정수 N을 주고, 둘째 줄에 알파벳 소문자로 이루어진 길이 N의 문자열 s를 줄 때, s의 뒤에 최소 몇 글자를 더 이어 써야 s를 팰린드롬(palindrome; 회문) 문자열으로 만들 수 있는지를 구하는 문제이다.

따라서, 문자열의 앞에서부터 각 문자(또는 두 문자)를 중심으로 하는 가장 긴 팰린드롬 문자열 길이를 구해나가다가, 마지막 문자를 포함하는 팰린드롬 문자열을 만나면 원래의 문자열 길이에서 해당 팰린드롬의 길이를 뺀 값을 출력하고 팰린드롬 탐색을 중단하면 된다.

문자열의 길이가 최대 40만으로 꽤 기므로, Manacher's Algorithm을 이용해 회문을 탐색하자.

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

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

string s; int len;
string str = " #";
int A[800002];
int main()
{
    cin >> len >> s;
    for (int i = 0;i < len;i++) {
        str += s[i];
        str += '#';
    }
    int center = 0, boundary = 0;
    int strlen = str.length();
    for (int i = 1;i < strlen;i++) {
        if (i > boundary) A[i] = 0;
        else A[i] = min(A[2*center - i], boundary - i);
        while ((i-A[i]-1>0) and (i+A[i]+1<strlen)) {
            if (str[i - A[i] - 1] == str[i + A[i] + 1]) A[i]++;
            else break;
        }
        if (boundary < i + A[i]) {
            boundary = i + A[i];
            center = i;
            if (boundary == strlen - 1) {
                cout << len - A[i];
                break;
            }
        }
    }
    return 0;
}

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

이번에 볼 문제는 백준 11046번 문제인 팰린드롬??이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11046

이 문제는 전에 쓴 10942번 문제(measurezero.tistory.com/69)와 같은 문제이나, 주어지는 수열의 길이가 2000이 아닌 1000000이라는 차이점이 있다.

따라서, 이전에 사용한 풀이로 이 문제를 풀 수는 없고, 시간복잡도가 더 적은 Manacher's Algorithm을 이용하는 것이 좋다.

Manacher's Algorithm은 현재 index가 이미 한번 팰린드롬 문자열 탐색 때 살펴본 범위(boundary) 안에 있다면, 그 범위에 닿았던 중심(center)에 대칭인 index를 중심으로 하는 팰린드롬 문자열 길이만큼 boundary 안쪽에서는 다시 탐색할 필요가 없다는 점을 이용한다. 팰린드롬 문자열의 특징상 그만큼은 이전에 조사한 대로 팰린드롬 문자열임을 알고 있기 때문이다.

Manacher's Algorithm은 그냥 사용하면 각 index가 중심인, 홀수 길이의 팰린드롬만을 구할 수 있기 때문에, 문자열에 끼어있을 수 없는 다른 문자 하나를 각 문자 양옆에 하나씩 삽입해 짝수 길이의 팰린드롬 또한 구할 수 있게 변형해줄 수 있다.

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

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

int nums[2000002];
int A[2000002];

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

    int len; cin >> len;
    len = 2 * len + 2; // 짝수길이 팰린드롬을 구하기 위한 조작
    int temp;
    for (int i = 1;i < len;i++) {
        if (i & 1) nums[i] = -1;
        else {
            cin >> temp;
            nums[i] = temp;
        }
    }
    int boundary = 0, center = 0; // Manacher's Algorithm
    for (int i = 1;i < len;i++) {
        if (i > boundary) A[i] = 0;
        else A[i] = min(A[2 * center - i], boundary - i);
        while ((i-A[i]-1>0) and ((i+A[i]+1)<len)) {
            if (nums[i - A[i] - 1] == nums[i + A[i] + 1]) A[i]++;
            else break;
        }
        if (i + A[i] > boundary) {
            boundary = i + A[i];
            center = i;
        }
    }
    int N; cin >> N; // 쿼리 처리
    int s, e;
    for (int i = 0;i < N;i++) {
        cin >> s >> e;
        if (A[s + e] > e - s) cout << 1 << '\n';
        else cout << 0 << '\n';
    }
    return 0;
}

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

이번에 볼 문제는 백준 10942번 문제인 팰린드롬?이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/10942

팰린드롬(palindrome; 회문)이란 앞에서부터 읽을 때랑 뒤에서부터 읽을 때 같게 읽히는 문자열을 의미한다.

이 문제에서는 미리 주어진 한자리 수로 이루어진 수열에서 두 수 s, e(단, s<=e)를 입력받아 s번째 숫자부터 e번째 숫자까지의 수열이 팰린드롬을 이루는지 확인해야한다.

여러 s와 e를 받아 처리하다보면 중복된 확인이 빈번히 일어나게 되는데, 이러한 중복을 줄이는 것이 이 문제를 푸는 것의 핵심이다.

어떤 수열이 팰린드롬을 이룬다면, 이 수열의 첫 항과 마지막 항을 제거한 나머지 또한 팰린드롬을 이룬다.

역으로, 어떤 수열이 첫항과 마지막 항이 같고, 첫 항과 마지막 항을 제거한 나머지 수열이 팰린드롬을 이룬다면 이 수열은 팰린드롬을 이룬다.

따라서, 주어진 수열에서, 가운데로 사용할 수 있는 길이 1, 2짜리 수열에서부터 각각의 수열을 (수열의 범위가 넘어가지 않을 때까지) 앞뒤로 숫자를 하나씩 붙여가면서 모든 가능한 팰린드롬 문자열의 시작점 및 끝점을 2차원 배열의 성분으로 하여 모든 부분문자열(substring)이 팰린드롬인지 아닌지 미리 저장할 수 있다.

이 배열이 있다면 이 문제에서 들어오는 10만개의 질문의 답을 바로 배열에서 꺼내 답할 수 있으므로, 문제를 해결할 수 있다.

그러나, 같은 상황에서 수열의 길이가 100만까지 커질 수 있는 11046번 문제(팰린드롬??)은 이 방법으로 해결할 수 없다.

수열의 길이가 더 길어진다면, Manacher's Algorithm을 이용해 모든 팰린드롬 부분문자열을 구하는 것이 좋다.

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

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

int nums[2001]; // 수열을 저장
bool isPal[2001][2001]; // s번째 숫자부터 e번째 숫자까지가 팰린드롬을 이루는지 저장

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

    int N; cin >> N;
    int x;
    for (int i = 1;i <= N;i++) {
        cin >> x; nums[i] = x;
    }
    int l, r;
    for (int i = 1;i <= N;i++) {
        l = i, r = i; // 홀수 길이 수열 판단
        while (l > 0 and r <= N) {
            if (nums[l] == nums[r]) isPal[l][r] = 1;
            else break;
            l--; r++;
        }
        l = i, r = i + 1;
        while (l > 0 and r <= N) { // 짝수 길이 수열 판단
            if (nums[l] == nums[r]) isPal[l][r] = 1;
            else break;
            l--; r++;
        }
    }
    int M; cin >> M;
    int s, e;
    for (int i = 0;i < M;i++) {
        cin >> s >> e;
        cout << isPal[s][e] << '\n';
    }
}

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

이번에 볼 문제는 백준 1655번 문제인 가운데를 말해요이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1655

이 문제에서는 매번 목록에 새로운 수가 하나씩 추가될 때, 그 목록의 크기순으로 중간번째인 수를 출력해야 한다. 만약 숫자가 짝수라면, 가운데에서 작은 수를 골라 출력해야 한다. 예를 들면 8개의 수 가운데 4번째로 작은 수를 출력해야 한다.

이 문제를 풀기 위해서는 다른 위치에 상관 없이 크기순으로 중간에 있는 값에만 빠르게 접근하면 되므로, 목록을 출력해야하는 중간번째를 기준으로 나눠서 중간번째보다 큰 수를 보관하는 우선순위 큐(priority queue)와 작은 수를 보관하는 우선순위 큐를 만드는 전략이 유효하다.

mid 변수에 기존 중간 위치의 값을 저장하자. 새로운 수를 입력받았을 때 이 값이 이전 출력값보다 크거나 같다면 큰 수를 보관하는 우선순위 큐에, 작다면 작은 수를 보관하는 우선순위 큐에 삽입한다. 그리고 두 우선순위 큐의 크기를 비교하면 현재 mid에 보관하고있는 값이 지금도 중간 위치에 있는 수인지 아닌지 알 수 있다.

mid에 보관된 값이 중간위치가 아니게 되었다면, mid를 적절한 우선순위 큐에 다시 넣고, 반대쪽 우선순위 큐에서 mid값을 새로 읽어온다.

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

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

priority_queue<int> smallvalues;
int mid;
priority_queue<int> largevalues;

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    cin >> mid; cout << mid << '\n';
    for (int i = 1;i < N;i++) {
        int current; cin >> current;
        if (current >= mid) largevalues.push(-current);
        else smallvalues.push(current);
        if (largevalues.size() - smallvalues.size() == 2) {
            smallvalues.push(mid);
            mid = -largevalues.top(); largevalues.pop();
        }
        else if (largevalues.size() - smallvalues.size() == -1) {
            largevalues.push(-mid);
            mid = smallvalues.top(); smallvalues.pop();
        }
        cout << mid << '\n';
    }
    return 0;
}

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

이번에 볼 문제는 백준 13975번 문제인 파일 합치기 3이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/13975

이전에 쓴 measurezero.tistory.com/66 이 문제에서 greedy 알고리즘을 적용한 논리와 같은 논리를 적용할 수 있는 문제이다. 차이점이 있다면 이 문제는 합의 형태로 나타난 문제이고, 저 문제는 곱의 형태로 나타난 문제라는 것이다.

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

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

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

    int T;cin >> T;
    for (int t = 0;t < T;t++) {
        priority_queue<long long> pq;
        int K; cin >> K;
        for (int i = 0;i < K;i++) {
            int x; cin >> x;
            pq.push(-x);
        }
        long long ans = 0;
        while (pq.size() > 1) {
            long long temp = 0;
            temp -= pq.top(); pq.pop();
            temp -= pq.top(); pq.pop();
            ans += temp;
            pq.push(-temp);
        }
        cout << ans << '\n';
    }
}

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

이번에 볼 문제는 백준 14698번 문제인 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/14698

이 문제에서 익혀갈 점은

1) 이 문제에서 greedy한 알고리즘이 성립하는 이유를 증명하는 연습과

2) 오버플로우를 일으키지 않게 주의하는 것이다.

  1) 이 문제에서 greedy한 해법이 성립하는 이유 증명하기

이 문제의 슬라임 합성비용을 greedy한 방법으로 구한다면 다음을 반복하여 구해볼 수 있다.

"슬라임이 1마리 남을 때까지 가장 슬라임 에너지가 적은 두 슬라임을 합친다"

결과론적으로, 이렇게 했을 때 가장 적은 슬라임 합성비용을 지불하게 된다.

그렇다면 이 경우에 가장 적은 합성비용을 지불하게 된다는 것을 어떻게 증명할 수 있을까?

처음에 주어진 n마리의 슬라임을 기본 슬라임이라 하고, 기본 슬라임 중 가장 적은 슬라임 에너지를 가진 슬라임을 A, 그 다음으로 적은 슬라임 에너지를 가진 슬라임을 B라 하자.

n=2인 경우, 합치는 방법은 한 가지밖에 없으니 증명은 자명하다.

n>2인 경우, 증명은 다음과 같다.

Step 1) A가 처음 합쳐지는 슬라임이 기본 슬라임인 경우 중 최소비용이 드는 경우가 포함되어 있다.

그 이유는 다른 슬라임들이 합쳐져 만들어진 슬라임과 A를 합치는 경우와, 그 합쳐진 슬라임에 들어있는 기본 슬라임중 하나와 A를 교체해서 그대로 진행하면 사용되는 비용이 더 늘어나지는 않기 때문이다.

특히, 다른 슬라임들이 합쳐져 만들어진 슬라임이 만들어지는 과정에는 기본 슬라임 둘을 합치는 과정이 있으므로, 이 과정에 있는 기본 슬라임과 A를 교체하면 비용이 더 적거나 같고 A가 처음 합쳐지는 슬라임이 기본 슬라임인 합치기 과정을 얻을 수 있다.

Step 2) A가 처음 합쳐지는 슬라임이 B인 경우 중 최소 비용이 드는 경우가 포함되어 있다.

최소 비용이 들어가는 합치기 과정에서 A와 처음 합쳐지는 기본 슬라임이 C(단, 슬라임 에너지는 A<B<C)라고 하자. 그러면, 전체 지불 비용에 A의 슬라임에너지가 곱해지는 횟수와 C의 슬라임에너지가 곱해지는 횟수는 x로 같게 된다.

한편, 슬라임을 합치는 최소비용을 얻으려면, 두 슬라임의 에너지가 x < y일 때 전체 지불 비용에 x가 곱해지는 횟수와 y가 곱해지는 횟수 사이에 x>=y라는 관계가 성립해야한다. (그렇지 않다면, 해당 합치기 과정에서 슬라임 에너지가 x와 y인 슬라임이 들어가는 위치를 서로 바꿔 더 적은 비용이 드는 합치기 과정을 얻을 수 있기 때문이다.) 따라서, A와 B와 C 각각의 슬라임 에너지 x, y, z는 모두 같게 되고, 위 최소 비용이 들어가는 합치기 과정에서 B와 C의 슬라임 위치를 서로 바꿔주어도 같은 비용이 들어감을 알 수 있다.

즉, A와 B를 합쳐도 최종 최소비용이 드는 경우를 얻을 수 있다.

따라서, 위의 greedy한 방법으로 비용을 계산해도 최소비용을 이용하여 슬라임을 전부 합칠 수 있다.

위의 증명에서, n=2인 경우를 따로 뗀 이유는 n=2라면 세 슬라임 A B C를 정할 수 없기 때문이다.

위의 증명의 Step 1, 2에 적힌 명제에 "포함되어 있다"와 같은 표현을 이용한 이유는 이것이 최소비용이 들어가게 합치는 유일한 방법은 아닐 수 있기 때문이다. 경우에 따라 다른 다양한 합치는 방법이 있을 수 있다.

2) 오버플로우를 주의하기

문제 조건에 따라 합쳐진 슬라임 에너지는 long long 범위를 넘어가지 않지만, 이 합쳐진 슬라임 에너지를 계속 곱해나가면서 계산하는 "최소 비용"은 long long 범위를 넘어갈 수 있다. 특히, 현재 계산되어있는 "최소 비용" 변수값과 이번에 곱해져야 할 합치는 데 들어가는 에너지(특히 마지막 합성)를 단순히 곱한다면 long long 범위를 가뿐히 넘기는 테스트 케이스가 존재한다. 따라서, 이번에 곱할 에너지를 최소비용에 곱하기 전에 1,000,000,007로 먼저 한번 나눠서 오버플로우를 방지할 수 있다. 1,000,000,007 이하의 두 수의 곱은 long long 범위 내이기 때문이다.

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

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

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

    int T;cin >> T;
    for (int t = 0;t < T;t++) {
        priority_queue<long long> pq; // 항상 가장 작은 두 수를 빠르게 접근하기 좋은 자료구조
        int N; cin >> N;
        for (int i = 0;i < N;i++) {
            long long x; cin >> x;
            pq.push(-x); // stl의 priority queue는 max heap이므로 min heap으로 이용하기 위함
        }
        long long ans = 1;
        while (pq.size() > 1) {
            long long temp = 1;
            temp *= pq.top(); pq.pop(); // 음수 둘의 곱은 양수가 되므로 두 수를바로 곱해도 상관없다
            temp *= pq.top(); pq.pop();
            pq.push(-temp); // pq에는 원래 수를 그대로 넣어야 대소 관계가 깨지지 않는다.
            temp %= 1000000007; // 최소비용 계산에 사용하기 전에 1000000007로 나눈 나머지를 구한다
            ans *= temp;
            ans %= 1000000007;
        }
        cout << ans << '\n';
    }
    return 0;
}