딩코딩 : Computer Science 블로그

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

트라이의 성질을 이용하여 트리구조를 구현해야한다.

이때 출력은 사전순으로 해야하기 때문에

자바로 문제를 푸는 경우엔 TreeMap을 활용하면 key값을 기준으로 알아서 정렬이 된다.

출력은 정렬된 TreeMap을 활용해 하위 노드들을 중위순회로 돌면 된다.

//package org.example;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    class Trie {
        TreeMap<String, Trie> child = new TreeMap<>();
    }
    //출력용
    private StringBuilder sb = new StringBuilder();
    public void print(Trie root, int depth) {
        Set keys = root.child.keySet();

        for (Object key : keys) {
            for (int i = 0; i < depth; i++) {
                sb.append("--");
            }
            sb.append(key).append("\n");
            print(root.child.get(key), depth + 1);
        }
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Trie root = new Trie();

        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int K = Integer.parseInt(st.nextToken());

            Trie cur = root;
            //Trie 생성
            for (int j = 0; j < K; j++) {
                String str = st.nextToken();
                if (!cur.child.containsKey(str)) {
                    cur.child.put(str, new Trie());
                }
                cur = cur.child.get(str);
            }
        }
        print(root, 0);
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    final int GO_MX = 10;

    class Trie {
        Trie[] go;
        boolean output;
        boolean hasChild;

        public Trie() {
            go = new Trie[GO_MX];
            Arrays.fill(go, null);
            output = hasChild = false;
        }

        public void insert(String str, int level) {
            if (level == str.length()) {
                output = true;
                return;
            }
            int next = str.charAt(level) - '0';

            if (go[next] == null) go[next] = new Trie();
            hasChild = true;

            go[next].insert(str, level + 1);
        }

        public boolean consistent() {
            if (this.hasChild && this.output) return false;

            for (int i = 0; i < GO_MX; i++) {
                if (go[i] != null && !go[i].consistent()) return false;
            }

            return true;
        }
    }


    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());

            Trie trie = new Trie();
            for (int j = 0; j < n; j++) {
                String str = br.readLine();
                trie.insert(str, 0);
            }


            if (trie.consistent()) {
                sb.append("YES\n");
            } else {
                sb.append("NO\n");
            }
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

select * from emp

-- 커서 사용
declare
empno number;
ename varchar2(100);
cursor rec_cur is select EMPNO, ENAME from emp;

begin
open rec_cur;
dbms_output.put_line('test');

loop
fetch rec_cur into empno, ename;
exit when rec_cur %NOTFOUND;
dbms_output.put_line(empno||'   '||ename);
end loop;

close rec_cur;
end;


create table university1(
    university varchar2(100),
    department varchar2(100),
    student_cnt number
);

select * from university1;

desc university1;

-- 프로시저 사용
create or replace procedure ex_proc
(
    p_department in varchar2,
    p_student_cnt in number
)
is
p_university varchar2(100) := 'seoul';

begin
insert into 
end ex_proc;

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

#include <iostream>
#include <algorithm>

#define MX 100003

typedef long long ll;
using namespace std;

const int mod = 1e9;
ll N, M, unf[MX];
ll sum = 0, ans = 0;

struct Edge {
    int x, y, w;

    bool operator<(const Edge &b) const {
        return w > b.w;
    }
};

Edge edges[MX];


int Find(int x) {
    if (unf[x] < 0) return x;
    return unf[x] = Find(unf[x]);
}

ll Union(int a, int b) {
    ll ret = unf[a] * unf[b];
    if (unf[a] < unf[b]) {
        unf[a] += unf[b];
        unf[b] = a;
    } else {
        unf[b] += unf[a];
        unf[a] = b;
    }
    return ret;
}

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

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        unf[i] = -1;
    }

    for (int i = 0; i < M; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        edges[i] = {x, y, w};
        sum += w;
    }

    sort(edges, edges + M);

    for (int i = 0; i < M; i++) {
        auto [x, y, w] = edges[i];
        x = Find(x);
        y = Find(y);

        if (x != y) {
            ans += sum * Union(x, y);
        }
        ans %= mod;
        sum -= w;
    }
    cout << ans << '\n';
    return 0;
}

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

#include <bits/stdc++.h>

using namespace std;

int N;
//i+j, i-j
bool arr[16], diagonal1[32], diagonal2[55];
int ans = 0;

void backTrack(int L) {
    if (L == N) {
        ans++;
        return;
    }
    for (int i = 0; i < N; i++) {
        if (!arr[i] && !diagonal1[L + i] && !diagonal2[L - i + N]) {
            arr[i] = diagonal1[L + i] = diagonal2[L - i + N] = 1;
            backTrack(L + 1);
            arr[i] = diagonal1[L + i] = diagonal2[L - i + N] = 0;
        }
    }
}


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

    cin >> N;
    backTrack(0);
    cout << ans << '\n';

}

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

1. 문제설명

BFS를 돌면서 모든 노드간 간선의 가중치를 구하고,

크루스칼을 시행하면된다.

이렇게 풀 수 있는 이유는 복제 로봇이 시작점, 키가 있는 곳에서 무한으로 복제가 가능하기 때문에

모든 노드를 이어놓고 최소스패닝트리를 구하면 답이 되기 때문이다.

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

int N, M;
string arr[51];
int maze[51][51];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

struct Edge {
    int from, to, weight;
    bool operator<(const Edge &b) const {
        return weight < b.weight;
    }

};


vector<pair<int, int> > vertex;
vector<Edge> edge;

bool BFS(int num) {
    int x = vertex[num].first;
    int y = vertex[num].second;

    int check[51][51];
    memset(check, 0, sizeof(check));

    check[x][y] = 1;
    queue<pair<int, int> > Q;
    Q.push({x, y});

    while (!Q.empty()) {
        auto cur = Q.front();
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (check[nx][ny] || maze[nx][ny] == -1) continue;
            check[nx][ny] = check[cur.first][cur.second] + 1;
            Q.push({nx, ny});
        }
    }

    for (int i = num + 1; i < vertex.size(); i++) {
        int nx = vertex[i].first;
        int ny = vertex[i].second;

        if (check[nx][ny] == 0) {
            return false;
        }
        edge.push_back({num, i, check[nx][ny] - 1});
    }


    return true;
}


//kruskal
int unf[3000];

int Find(int a) {
    if (unf[a] < 0) return a;
    return unf[a] = Find(unf[a]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a == b) return;
    if (unf[a] > unf[b]) {
        unf[b] += unf[a];
        unf[a] = b;
    } else {
        unf[a] += unf[b];
        unf[b] = a;
    }
}


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

    cin >> N >> M;

    int kidx = 2;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == '1') {
                maze[i][j] = -1;
            } else if (arr[i][j] == 'S') {
                maze[i][j] = 1;
                vertex.push_back({i, j});
            } else if (arr[i][j] == 'K') {
                maze[i][j] = kidx++;
                vertex.push_back({i, j});
            }
        }
    }


    //각 노드간 edge 생성
    for (int i = 0; i < vertex.size() - 1; i++) {
        if (!BFS(i)) {
            //연결되지 않은 vertex 존재할 경우
            cout << -1 << '\n';
            return 0;
        }
    }


    //크루스칼
    int ans = 0;
    memset(unf, -1, sizeof(unf));
    sort(edge.begin(), edge.end());

    for (auto e: edge) {
        auto [a, b, c] = e;
        a = Find(a);
        b = Find(b);

        if (a != b) {
            Union(a, b);
            ans += c;
        }
    }
    cout << ans << '\n';
    
    return 0;
}

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

#include <bits/stdc++.h>

#define MX 10001
using namespace std;

int N, P;

struct Edge {
    int from, to, weight;

    bool operator<(const Edge &b) const {
        return weight < b.weight;
    }
};

int countryCost[MX], unf[MX];
vector<Edge> realEdges;

int Find(int a) {
    if (unf[a] < 0) {
        return a;
    }
    return unf[a] = Find(unf[a]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if (a == b) return;
    if (unf[a] > unf[b]) {
        unf[b] += unf[a];
        unf[a] = b;
    } else {
        unf[a] += unf[b];
        unf[b] = a;
    }
}


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

    cin >> N >> P;

    memset(unf, -1, sizeof(unf));

    int minCountry = 1e9;
    for (int i = 1; i <= N; i++) {
        cin >> countryCost[i];
        minCountry = min(minCountry, countryCost[i]);
    }

    for (int i = 1; i <= P; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        realEdges.push_back({a, b, 2 * c + countryCost[a] + countryCost[b]});
    }

    sort(realEdges.begin(), realEdges.end());

    int ans = 0;

    for (auto edge: realEdges) {
        auto [a, b, c] = edge;
        int aa = Find(a);
        int bb = Find(b);

        if (aa != bb) {
            Union(aa, bb);
            ans += c;
        }
    }


    cout << ans + minCountry << '\n';

    return 0;
}

넌블록킹과 블록킹

분류기준 대기

블록킹 → 대기 , read하거나 write 할 때, 완료될 때까지 대기, 함수가 반환할 때, 성광과 실패를 알 수 있다.

넌블럭킹 → 대기 안함, 어떤 요청을 하면, 성공이든 실패든 일단 즉시 처리 후 반환한다. 함수가 반환되면 성공, 실패, 부분성공의 상태가 존재 가능

동기와 비동기

분류 기준은 순서

동기 → 순서대로 처리 보장

비동기 → 순서대로 처리를 보장하지 않음(out-of-order)

일반적인 시스템 프로그래밍의 입출력 함수는 모두 ‘동기’ 모델이다.

비동기식은 시그널, AIO, 스레드(Task 단위로는 비동기, Task 내의 기능들은 동기 → 스레드의 동기/비동기 여부는 기준 관점에 따라 다를 수 있다.)