취미로 코딩하기

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

이번에 볼 문제는 백준 11403번 문제인 경로 찾기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11403

이 문제는 주어진 인접행렬(adjacency matrix)을 보고 각 node가 연결되어있는지 아닌지를 확인하는 문제이다.

node의 수가 충분히 적으므로, 단순하게 행렬을 제곱하는 방식으로 풀어보았다. (이 방법이 가장 빠른 방법인 것은 아니다.)

adjacency matrix를 transpose하고 n제곱한 뒤 다시 transpose를 해 얻을 수 있는 행렬의 i행 j열 성분은 i번째 node에서 j번째 node로 가는 길이 n인 경로의 경우의 수와 같다. 이 값이 0이 아니라면 n번만에 node i에서 node j로 가는 경로이 있다는 것이므로 이에 대응되는 답안의 출력을 1로 한다.

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

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

int mat[100][100];
int expmat[100][100];
int tmp[100][100];
int ans[100][100];

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

    int N;
    cin >> N;

    int x;

    for (int i = 0;i < N;i++) {
        for (int j = 0;j < N;j++) {
            cin >> x;
            mat[j][i] = x; // adjacency matrix의 transpose를 저장
            if (i == j) expmat[i][j] = 1; // identity matrix
        }
    }

    for (int _ = 0;_ < N;_++) {
        for (int i = 0;i < N;i++) {
            for (int j = 0;j < N;j++) {
                for (int k = 0;k < N;k++) {
                    tmp[i][j] += mat[i][k] * expmat[k][j];
                }
            }
        }
        for (int i = 0;i < N;i++) {
            for (int j = 0;j < N;j++) {
                expmat[i][j] = tmp[i][j];
                if (tmp[i][j] != 0) { // N번만에 i에서 j로 가는 경로가 있다면
                    ans[i][j] = 1; // 일단 저장
                }
                tmp[i][j] = 0;
            }
        }

    }
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < N;j++) {
            cout << ans[j][i] << ' '; // adjacency matrix는 다시 transpose해줘야 한다.
        }
        cout << '\n';
    }

    return 0;
}

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

이번에 볼 문제는 백준 1992번 문제인 쿼드트리이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1992

이 문제는 문제에 주어진, 단순한 상황에서 쿼드트리(quadtree)를 구현하는 문제이다.

쿼드트리는 2차원 데이터를 압축, 저장할 수 있는 대표적인 자료구조이다. 쿼드트리는 leaf node를 제외한 각 node에서 이 node가 가리키는 2차원 데이터를 4등분한 데이터를 담고있는 node 4개를 가진다. leaf node에 저장된 값은 조각난 조각을 대표하는 값으로 볼 수 있다.

(출처: en.wikipedia.org/wiki/Quadtree)

이 문제에서는 0과 1로 이루어진 흑백이미지를 쿼드트리를 이용하여 압축하는 것을 구현해본다.

만약 조각에 다른 숫자가 끼어있다면, 조각을 4등분하고 각 나뉜 부분조각들에 대해서 이를 반복하면 된다.

각 조각에 들어있는 숫자의 총합을 이용하면 이 조각에 다른 숫자가 들어있는지 쉽게 판단할 수 있다.

n by n 조각이 1로 가득 차있다면 각 성분의 총합은 n*n일 것이고, 0으로 가득 차있다면 0일 것이기 때문이다.

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

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

int screen[64][64];

void func(int n, int x, int y) {
    int num = 0;
    for (int i = x; i < x + n;i++) { // 각 조각의 모든 성분의 합
        for (int j = y;j < y + n;j++) {
            num += screen[i][j];
        }
    }
    if (num == 0) cout << 0; // 조각 성분 합이 0이면 0으로 가득 찬 것
    else if (num == n * n) cout << 1; // 조각 성분 합이 n*n이면 1으로 가득 찬 것
    else {
        n /= 2;
        cout << '(';
        func(n, x, y); // 왼쪽 위 조각
        func(n, x, y + n); // 오른쪽 위 조각
        func(n, x + n, y); // 왼쪽 아래 조각
        func(n, x + n, y + n); // 오른쪽 아래 조각
        cout << ')';
    }
}

int main()
{
    int n;
    cin >> n;
    string s;
    for (int i = 0;i < n;i++) {
        cin >> s;
        for (int j = 0;j < n;j++) {
            if (s[j] == '0') {
                screen[i][j] = 0;
            }
            else screen[i][j] = 1;
        }
    }
    func(n, 0, 0);

    return 0;
}

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

이번에 볼 문제는 백준 1963번 문제인 소수 경로이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1963

소수판정과 BFS를 한번에 해야 하는 문제이다.

구현력이 좋지 않다면 구현력을 높이는 데에 도움이 되는 문제인 것 같다.

글쓴이가 이 문제를 푼 방법은 다음과 같다.

1) 네 자리의 소수를 모두 찾아둔다. 이 때, Sieve of Eratosthenes(에라토스테네스의 체)를 이용하면 빠르게 소수를 찾을 수 있다.

2) 각 네 자리 소수들을 그래프의 node로 생각하자. 그리고 두 네 자리 소수가 딱 한자리만 차이날 때, 두 node 사이에 edge가 있다고 생각하자. 그러면 이 문제는 그래프 위에서 주어진 두 node 사이의 거리를 구하는 문제로 볼 수 있다.

3) 이 그래프는 weight가 없으므로, BFS를 이용하여 두 node사이 거리를 구하고, 출력한다.

이 문제를 풀면서 글쓴이는 코드가 반복되는 부분을 반복문이 아닌 코드를 복사-붙여넣기하여 해결하려는 경향이 강하다고 느꼈다.

아마 코드는 길어져도 직관적이기 때문이 아닐까 싶다.

그래도 반복 횟수가 정해져있지 않거나 큰 경우 이 방법은 사용하기 어려우니 반복문을 사용하는 습관을 길러야겠다.

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

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

bool sieve[10000];


int main()
{
    for (int i = 2;i < 10000;i++) { // 10000 이하의 소수 탐색
        sieve[i] = true;
    }
    for (int i = 2;i < 100;i++) {
        if (sieve[i]) {
            for (int j = i * i;j < 10000;j += i) {
                sieve[j] = false;
            }
        }
    }
    int T;
    cin >> T;
    for (int i = 0;i < T;i++) { // BFS
        queue<int> que;
        bool visited[10000];
        int dist[10000];
        for (int i = 0;i < 10000;i++) {
            visited[i] = false;
            dist[i] = 0;
        }
        int x, target;
        cin >> x >> target;
        que.push(x);
        visited[x] = true;
        bool chk = false;
        while (!que.empty()) {
            int current = que.front();
            que.pop();
            int digit1 = current % 10; // 1의자리
            int digit2 = current % 100 - digit1; // 10의자리*10
            int digit3 = current % 1000 - digit2 - digit1; // 100의자리*100
            int digit4 = current - digit3 - digit2 - digit1; // 1000의자리*1000
            for (int i = 0;i < 10;i++) { // 1의자리가 다른 소수
                int num = i + digit2 + digit3 + digit4;
                if (!visited[num] and sieve[num]) {
                    que.push(num);
                    visited[num] = true;
                    dist[num] = dist[current] + 1;
                    if (num == target) chk = true;
                }
            }
            if (chk) break;
            for (int i = 0;i < 10;i++) { // 10의자리가 다른 소수
                int num = digit1 + 10 * i + digit3 + digit4;
                if (!visited[num] and sieve[num]) {
                    que.push(num);
                    visited[num] = true;
                    dist[num] = dist[current] + 1;
                    if (num == target) chk = true;
                }
            }
            if (chk) break;
            for (int i = 0;i < 10;i++) { // 100의자리가 다른 소수
                int num = digit1 + digit2 + 100 * i + digit4;
                if (!visited[num] and sieve[num]) {
                    que.push(num);
                    visited[num] = true;
                    dist[num] = dist[current] + 1;
                    if (num == target) chk = true;
                }
            }
            if (chk) break;
            for (int i = 1;i < 10;i++) { // 1000의자리가 다른 소수: 1000의자리가 0이 되면 안됨에 유의
                int num = digit1 + digit2 + digit3 + 1000 * i;
                if (!visited[num] and sieve[num]) {
                    que.push(num);
                    visited[num] = true;
                    dist[num] = dist[current] + 1;
                    if (num == target) chk = true;
                }
            }
            if (chk) break;
        }
        cout << dist[target]<<'\n';
    }

    return 0;
}

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

이번에 볼 문제는 백준 9020번 문제인 수열과 헌팅이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/9020

골드바흐의 추측은 유명한 미해결문제로, 2를 제외한 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 내용을 담고 있다. 적당히 큰 수의 범위 내에서는 모든 짝수가 두 소수의 합으로 나타내짐이 알려져있다. 이 문제에서는 10000 이하의 (2가 아닌) 짝수를 두 "차이가 가장 적은" 소수의 합으로 나타내야 한다.

차이가 가장 적은 소수의 쌍을 찾기 위해 주어진 짝수의 절반값서부터 탐색해나가자.

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

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

bool sieve[10001];

int main()
{
    for (int i = 2;i < 10001;i++) {
        sieve[i] = true;
    }
    for (int i = 2;i <= 100;i++) {
        if (sieve[i]) {
            for (int j = i * i;j < 10001;j += i) {
                sieve[j] = false;
            }
        }
    }

    int n;
    cin >> n;
    int x, pt;

    for (int i = 0;i < n;i++) {
        cin >> x;
        x /= 2;
        pt = 0;
        while (!sieve[x + pt] or !sieve[x - pt]) {
            pt++;
        }
        cout << x - pt << ' ' << x + pt << "\n";
    }

    return 0;
}

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

이번에 볼 문제는 백준 20495번 문제인 수열과 헌팅이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/20495

문제풀이의 아이디어는 간단하다.

주어진 범위 내에서 정해진 수가 있을 수 있는 index의 범위를 구하는 것이므로,

가장 낮은 index가 나올 경우는 구하는 수는 범위에서 최솟값을 갖고 나머지 수들은 범위에서 각각 최댓값을 가지는 경우에 발생할 것이고,

가장 큰 index가 나올 경우는 구하는 수는 범위에서 최댓값을 갖고 나머지 수들은 범위에서 각각 최솟값을 가지는 경우에 발생할 것이다.

그러므로 미리 가장 낮은 index끼리 정렬을 해두고, 가장 큰 index끼리 정렬을 해둔 뒤 각 구간의 최댓값 최솟값을 binary search로 각 배열에서 bound를 찾아 문제를 해결할 수 있다.

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

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

int arrx[500000];
int arry[500000];
int sortarrx[500000];
int sortarry[500000];

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

    int n;
    cin >> n;
    int x, y;
    for (int i = 0;i < n;i++) {
        cin >> x >> y;
        arrx[i] = x-y;
        sortarrx[i] = x-y;
        arry[i] = x+y;
        sortarry[i] = x+y;
    }

    sort(sortarrx, sortarrx + n);
    sort(sortarry, sortarry + n);

    int temp;
    for (int i = 0;i < n;i++) { 
        int left = 0, right = n - 1;
        x = arrx[i];
        y = arry[i];
        while (left <= right) { // 작은 index
            int mid = (left + right) / 2;
            if (sortarry[mid] >= x) {
                right = mid - 1;
            }
            else left = mid + 1;
        }
        cout << left+1 << ' ';
        left = 0, right = n - 1; // 큰 index
        while (left <= right) {
            int mid = (left + right) / 2;
            if (sortarrx[mid] <= y) {
                left = mid + 1;
            }
            else right = mid - 1;
        }
        cout << right+1 << '\n';
    }

    return 0;
}

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

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

www.acmicpc.net/problem/20494

이 문제에서 셰프는 결국 각 사람들이 먹을 스시를 전부 만들어야한다.

각 사람들이 먹을 스시는 문자열으로 들어오는데, 그 길이를 전부 합하면 셰프가 만들어야하는 스시의 최소 개수를 알 수 있다.

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

#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::string;
int main()
{
    string s;
    int n;
    int ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++) { // 문자열 길이 총합 = 만들어야하는 최소 스시개수
        cin >> s;
        ans += s.length();
    }
    cout << ans;

    return 0;
}