딩코딩 : Computer Science 블로그

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

1. 문제설명

25명의 학생 중 7명을 뽑아보는 백트래킹을 진행하면서

7명 중 4명이상이 S인지 확인하고,

7명이 모두 인접해있는지 BFS 탐색을 해서

옳으면 경우의 수를 추가해주면 된다.

2. 문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

int ans = 0;
string arr[5];
bool student[25];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

bool check() {
    int num = 0;
    int x, y;
    
    for (int i = 0; i < 25; i++) {
        if (student[i]) {
            int row = i / 5;
            int col = i % 5;

            if (arr[row][col] == 'S') {
                num++;
                x = row;
                y = col;
            }

        }
    }
    if (num < 4) return false;
    
    queue<pair<int, int> > Q;
    Q.push({x, y});
    int cnt = 1;

    bool vis[5][5] = {0};
    vis[x][y] = 1;

    while (!Q.empty()) {
        int curx = Q.front().first;
        int cury = Q.front().second;
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = curx + dx[i];
            int ny = cury + dy[i];

            if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5)continue;
            if (vis[nx][ny]) continue;
            if (!student[nx * 5 + ny]) continue;

            vis[nx][ny] = 1;
            Q.push({nx, ny});
            cnt++;
        }
    }


    return cnt == 7;
}


void DFS(int idx, int num) {
    if (num == 7) {
        if (check()) {
            ans++;
        }
        return;
    }

    for (int i = idx; i < 25; i++) {
        student[i] = 1;
        DFS(i + 1, num + 1);
        student[i] = 0;
    }
}

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

    for (int i = 0; i < 5; i++) {
        cin >> arr[i];
    }

    DFS(0, 0);
    cout << ans << '\n';

    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;
const int mod =1'000'000;
struct Fibo{
    long long arr[2][2] = {{1, 1}, {1,0}};

    Fibo(){
        arr[0][0] = 1;
        arr[0][1] = 1;
        arr[1][0] = 1;
        arr[1][1] = 0;
    };

    Fibo mutiple(Fibo b){
        long long tmp[2][2] = {{0, 0}, {0, 0}};
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                for(int k=0; k<2; k++){
                    tmp[i][k] += (arr[i][j] * b.arr[j][k])%mod;
                    tmp[i][k] %= mod;
                }
            }
        }

        Fibo ret = Fibo();
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                ret.arr[i][j] = tmp[i][j];
            }
        }

        return ret;
    }

    void baseMultiple(){
        long long res[2][2] = {{0,0}, {0, 0}};
        long long tmp[2][2] = {{1, 1}, {1,0}};
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                for(int k=0; k<2; k++){
                    res[i][k] += (arr[i][j] * tmp[j][k])%mod;
                    res[i][k] %= mod;
                }
            }
        }

        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                arr[i][j] = res[i][j];
            }
        }
    }
};

int cnt = 0;
long long N;
Fibo doubleSquare(Fibo cur, long long n){
    if(n==1){
        return cur;
    }

    Fibo tmp = doubleSquare(cur, n/2);
    Fibo ret = tmp.mutiple(tmp);

    if(n%2){
        ret.baseMultiple();
    }
    return ret;
}

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

    cin >> N;

    Fibo st = Fibo();

    Fibo fb = doubleSquare(st, N);

    cout << fb.arr[1][0] << '\n';
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    char *fname;
    char fntmp[BUFSIZ];
    char template[32];

    fname = tmpnam(NULL);
    printf("1. TMP File Name(tmpnam) : %s\n", fname);

    tmpnam(fntmp);
    printf("2. TMP File Name(tmpnam) : %s\n", fntmp);

    fname = tempnam("/tmp", "hanbit");
    printf("3. TMP File Name(tempnam) : %s\n", fname);

    strcpy(template, "/tmp/hanbitXXXXXX");
    fname = mktemp(template);
    printf("4. TMP File Name(mktemp) : %s\n", fname);


    return 0;
}

1. 문제설명

보석에는 무게와 가격이 존재하고,

각 가방마다 챙길 수 있는 최대 무게가 존재합니다.

그리고 각 가방에는 최대 하나의 보석만 넣을 수 있습니다.

이러한 조건이 있을 때 도둑이 여러 개의 가방을 통해 챙길 수 있는 보석들의 가격의 최대 합을 구해야합니다.

우선 각 가방마다 챙길 수 있는 보석의 최대 무게가 다른 조건을 생각해보면,

가방의 최대 무게가 크면 여러개의 보석을 선택할 수 있고,

가방의 최대 무게가 작으면 선택할 수 있는 보석이 줄어듭니다.

이를 바탕으로 최대 무게가 작은 가방부터 보석을 선택해나가면 됩니다.

그리고 각 가방이 챙길 수 있는 최대 무게의 보석을 챙겨야 합니다.

이를 위해서 현재 가방의 최대 무게를 바탕으로

현재 가방에 담을 수 있는 보석을 우선순위 큐에 넣고,

더이상 담을 수 있는 보석이 없다면 우선순위 큐에서 가격이 가장 큰 보석을 꺼내서 선택하는 방식으로 문제를 해결할 수 있습니다.

정리하면

배낭을 최대 무게를 바탕으로 오름차순으로 정렬하고,

보석을 무게를 바탕으로 오름차순으로 정렬해서

배낭의 무게를 작은 값부터 돌면서

무게가 작은 보석부터 넣을 수 있는 보석을 우선순위 큐에 넣고,

더이상 넣을 수 없다면 우선순위 큐에서 가격이 가장 큰 보석을 꺼내서 답에 더해주는 것을 반복하면 됩니다.

이렇게 하면

항상 가방은 해당 가방이 선택할 수 있는 보석의 최대 가격을 선택하게 됩니다.

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

int n, k;

struct Jew{
    int m, v;
    bool operator<(const Jew& a) const {
        return v < a.v;
    }
};

vector<pair<int,int> > jew;
vector<int> backpack;

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

    cin >> n >> k;
    long long ans = 0;

    for(int i=0; i<n; i++){
        int m, v;
        cin >> m >> v;

        jew.push_back({m,v});
    }

    for(int i=0; i<k; i++){
        int c;
        cin >> c;
        backpack.push_back(c);
    }

    sort(jew.begin(), jew.end());
    sort(backpack.begin(), backpack.end());

    int ptr = 0;

    priority_queue<Jew> pq;

    for(int i=0; i<k; i++){

        while(ptr<n && jew[ptr].first <= backpack[i]){
            pq.push({jew[ptr].first, jew[ptr].second});
            ptr++;
        }

        if(!pq.empty()){
            ans += pq.top().v;
            pq.pop();
        }

    }


    cout << ans << '\n';
    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

long long N, B;

struct Matrix {
    int arr[6][6] = {0};
};

Matrix multiple(Matrix m1, Matrix m2) {
    Matrix tmp;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                tmp.arr[i][k] += (m1.arr[i][j] * m2.arr[j][k]) % 1000;
                tmp.arr[i][k] %= 1000;
            }
        }
    }
    return tmp;
}

Matrix power(Matrix A, long long b) {
    if (b == 1) return A;

    Matrix powered = power(A, b / 2);
    Matrix ret = multiple(powered, powered);
    if (b % 2 == 1) {
        ret = multiple(ret, A);
    }
    return ret;
}


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

    cin >> N >> B;

    Matrix matrix, ans;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> matrix.arr[i][j];
        }
    }

    ans = power(matrix, B);

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cout << ans.arr[i][j] % 1000 << ' ';
        }
        cout << '\n';
    }


    return 0;
}

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

숫자 범위가 굉장히 크다.

하나씩 다 따져보다간 시간이 너무 오래 걸린다.

바운더리 컨디션을 생각해보면서 이분탐색을 시행해야 문제를 해결 할 수 있다.

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

int n, k;

int main() {

    cin >> n >> k;

    int st = 1, en = k , ans;

    while(st <= en){
        int mid = (st + en)/2;

        int cnt = 0;
        for(int i=1; i<=n; i++){
            cnt += min(n, mid/i);
        }

        if(cnt >= k){
            ans = mid;
            en = mid - 1;
        }
        else{
            st = mid + 1;
        }
    }

    cout << ans << '\n';


    return 0;
}

1. Server

#include <stdio.h>
#include <unistd.h>
#include <sys/times.h>
#include <limits.h>
#include <stdlib.h>
#include <time.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <string.h>
#include <fcntl.h>

int main() {
    int pd, n;
    char msg[] = "Hello, FIFO";

    printf("Server =====\n");

    if(mkfifo("./HAN-FIFO", 0666) == -1){
        perror("mkfifo");
        exit(1);
    }

    if((pd = open("./HAN-FIFO", O_WRONLY)) == -1){
        perror("open");
        exit(1);
    }


    printf("To Client : %s\n", msg);

    n = write(pd, msg, strlen(msg)+1);
    if(n==-1){
        perror("write");
        exit(1);
    }
    close(pd);





    return 0;
}

2. client

#include <stdio.h>
#include <unistd.h>
#include <sys/times.h>
#include <limits.h>
#include <stdlib.h>
#include <time.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <string.h>
#include <fcntl.h>

int main() {
    int pd, n;
    char inmsg[80];

    if((pd = open("./HAN-FIFO", O_RDONLY)) == -1){
        perror("open");
        exit(1);
    }

    printf("Client ====\n");
    write(1, "From Server :", 13);

    while((n=read(pd, inmsg, 80)) > 0)
        write(1, inmsg, n);

    if(n==-1){
        perror("read");
        exit(1);
    }

    write(1, "\n", 1);
    close(pd);

    return 0;
}

#include <stdio.h>
#include <unistd.h>
#include <sys/times.h>
#include <limits.h>
#include <stdlib.h>
#include <time.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <string.h>

int main() {
    int fd1[2], fd2[2];
    pid_t pid;
    char buf[257];
    int len, status;

    if(pipe(fd1)== -1){
        perror("pipe");
        exit(1);
    }


    if(pipe(fd2)==-1){
        perror("pipe");
        exit(1);
    }

    switch(pid = fork()){
        case -1 :
            perror("fork");
            exit(1);
            break;

        case 0:
            close(fd1[1]);
            close(fd2[0]);
            write(1, "Child Process:", 15);
            len = read(fd1[0], buf, 256);
            write(1, buf, len);

            strcpy(buf, "Good\n");
            write(fd2[1], buf, strlen(buf));
            break;
        default:
            close(fd1[0]);
            close(fd2[1]);
            buf[0] = '\0';
            write(fd1[1], "Hello\n", 6);

            write(1, "Parent Process:", 15);
            len = read(fd2[0], buf, 256);
            write(1, buf, len);
            waitpid(pid, &status, 0);
            break;
    }

    return 0;
}