BLOG

정리해야함 코드도 내용도

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

[JAVA]

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n, m, k;
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        long a[] = new long[n];
        int h = (int) Math.ceil(Math.log10(n) / Math.log10(2));
        int tree_size = (1 << (h + 1));
        long tree[] = new long[tree_size];
        m += k;
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(br.readLine());
        }
        init(a, tree, 1, 0, n - 1);

        StringBuilder sb = new StringBuilder();
        while (m-- > 0) {
            int t1, t2, t3;
            st = new StringTokenizer(br.readLine());
            t1 = Integer.parseInt(st.nextToken());
            if (t1 == 1) {
                long t4;
                t2 = Integer.parseInt(st.nextToken());
                t4 = Long.parseLong(st.nextToken());
                t2 -= 1;
                long diff = t4 - a[t2];
                a[t2] = t4;
                update(tree, 1, 0, n - 1, t2, diff);
            } else if (t1 == 2) {
                t2 = Integer.parseInt(st.nextToken());
                t3 = Integer.parseInt(st.nextToken());
                sb.append(sum(tree, 1, 0, n - 1, t2 - 1, t3 - 1) + "\n");
            }
        }
        System.out.println(sb);
        br.close();
    }

    static long init(long[] a, long[] tree, int node, int start, int end) {
        if (start == end)
            return tree[node] = a[start];
        else
            return tree[node] = init(a, tree, node * 2, start, (start + end) / 2)
                    + init(a, tree, node * 2 + 1, (start + end) / 2 + 1, end);
    }

    static void update(long[] tree, int node, int start, int end, int index, long diff) {
        if (index < start || index > end)
            return;
        tree[node] = tree[node] + diff;
        if (start != end) {
            update(tree, node * 2, start, (start + end) / 2, index, diff);
            update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, diff);
        }
    }

    static long sum(long[] tree, int node, int start, int end, int left, int right) {
        if (left > end || right < start)
            return 0;
        if (left <= start && end <= right)
            return tree[node];
        return sum(tree, node * 2, start, (start + end) / 2, left, right)
                + sum(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right);
    }

}

https://murra.tistory.com/70

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

public class Main {
    static char[][] arr = new char[5][5];
    static int[] dy = { -1, 0, 0, 1 }, dx = { 0, -1, 1, 0 };
    static boolean[] b = new boolean[25];
    static int ret = 0;

    static boolean find(int y, int x) {
        boolean[][] check = new boolean[5][5];
        Queue<int[]> q = new LinkedList<>();
        check[y][x] = true;
        int vcnt = 1;
        q.offer(new int[] { y, x });
        while (!q.isEmpty()) {
            int[] s = q.poll();

            for (int i = 0; i < 4; i++) {
                int yy = s[0] + dy[i];
                int xx = s[1] + dx[i];
                if (0 <= yy && yy < 5 && 0 <= xx && xx < 5 && !check[yy][xx] && b[yy * 5 + xx]) {
                    vcnt += 1;
                    check[yy][xx] = true;
                    q.offer(new int[] { yy, xx });
                }
            }
        }
        return vcnt == 7 ? true : false;
    }

    static void dfs(int n, int pick, int sc) {
        sc += arr[n / 5][n % 5] == 'S' ? 1 : 0;
        b[n] = true;
        if (pick == 7) {
            if (sc >= 4) {
                if (find(n / 5, n % 5)) {
                    ret += 1;
                }
            }
        } else {
            for (int i = n + 1; i < 25; i++) {
                if (!b[i])
                    dfs(i, pick + 1, sc);
            }
        }
        b[n] = false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < 5; i++) {
            String in = br.readLine();
            for (int j = 0; j < 5; j++) {
                arr[i][j] = in.charAt(j);
            }
        }

        for (int i = 0; i < 25; i++) {
            dfs(i, 1, 0);
        }

        System.out.println(ret);

        br.close();
    }
}

[C++]

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

char arr[5][5];
bool b[25];
bool check[5][5];
int ret;
queue<pair<int, int>> q;
int dy[]{-1, 0, 0, 1}, dx[]{0, -1, 1, 0};

bool isFriends(int n)
{
    int y = n / 5;
    int x = n % 5;

    for (int i = 0; i < 5; i++)
    {
        fill(check[i], check[i] + 5, false);
    }
    int cnt = 1;
    check[y][x] = true;
    q.push(make_pair(y, x));
    while (!q.empty())
    {
        pair<int, int> p = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            y = p.first + dy[i];
            x = p.second + dx[i];
            if (0 <= y && y < 5 && 0 <= x && x < 5 && b[5 * y + x] && !check[y][x])
            {
                cnt++;
                check[y][x] = true;
                q.push(make_pair(y, x));
            }
        }
    }
    return cnt == 7 ? true : false;
}

void combine(int n, int pick, int s)
{
    b[n] = true;
    s += arr[n / 5][n % 5] == 'S' ? 1 : 0;
    if (pick == 7)
    {
        if (s >= 4 && isFriends(n))
            ret++;
    }
    else
    {
        for (int i = n + 1; i < 25; i++)
            combine(i, pick + 1, s);
    }
    b[n] = false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            cin >> arr[i][j];

    for (int i = 0; i < 25; i++)
        combine(i, 1, 0);

    cout << ret;
    return 0;
}

조합을 통해서 7명을 뽑고 이다솜(S)파가 4명이상일 경우에만 7명이 인접해있는지 확인한다.

처음 풀때는 DFS를 통해서 7명을 찾을려고 해서 풀지 못했다. 옆 행렬인 경우 (2,1)에서 시작해서 (4,2)와 (4,5)를 포함하는 경우의 수가 존재한다. (4,5) 경우에는 DFS로 탐색이 가능하지만 (4,2) 경로를 포함한 경우는 (2,2) 좌표에서 십자가모양으로 퍼지기 때문에 DFS로 탐색할 수 없다. 

그래서 조합을 통해서 25개의 좌표 중에서 7개를 먼저 선택하는 방식으로 문제를 풀 수 있었다.

SCC ( Strongly Connected Component )

강한 연결 요소, 집합 내에서 서로 왕복 가능한 최대 집합의 크기

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

1. 방향 그래프, 역방향 그래프, 스택을 준비한다.
2. 방향 그래프를 사용하여 dfs를 수행하고, 끝나는 순서대로 스택에 push한다. (단, 모든 정점에 대해서 수행)
3. 스택을 비울 때까지 pop을 하면서, 역방향 그래프를 사용하여 dfs를 수행하고 모든 정점들을 같은 SCC로 묶는다.

[ JAVA ]

class Main {
    static ArrayList<Integer> graph[];
    static ArrayList<Integer> reverse[];
    static boolean visited[];
    static Stack<Integer> st = new Stack<>();
    // Result
    static ArrayList<ArrayList<Integer>> a = new ArrayList<>();

    static void dfs(int now) {
        for (int a : graph[now]) {
            if (visited[a] == false) {
                visited[a] = true;
                dfs(a);
            }
        }
        st.push(now);
    }

    static void rdfs(int base, ArrayList<Integer> temp) {
        temp.add(base);
        for (int a : reverse[base]) {
            if (!visited[a]) {
                visited[a] = true;
                rdfs(a, temp);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        int m = Integer.parseInt(stk.nextToken());

        graph = new ArrayList[n + 1];
        reverse = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
            reverse[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            stk = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(stk.nextToken());
            int to = Integer.parseInt(stk.nextToken());
            graph[from].add(to);
            reverse[to].add(from);
        }

        // stack
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i);
            }
        }

        Arrays.fill(visited, false);

        while (!st.isEmpty()) {
            int base = st.pop();
            if (!visited[base]) {
                visited[base] = true;
                ArrayList<Integer> temp = new ArrayList<>();
                rdfs(base, temp);
                Collections.sort(temp);
                temp.add(-1);
                a.add(temp);
            }
        }

        Collections.sort(a, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                return Integer.compare(o1.get(0), o2.get(0));
            }
        });

        StringBuilder sb = new StringBuilder();
        sb.append(a.size()).append("\n");
        for (int i = 0; i < a.size(); i++) {
            int size = a.get(i).size();
            for (int j = 0; j < size; j++) {
                sb.append(a.get(i).get(j)).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);

        br.close();
    }
}

[ C++ ]

#include <stdio.h>
#include <memory.h>
#include <algorithm>
#include <vector>
using namespace std;

typedef vector<int> vi;
const int v_ = 1e4 + 1;

int v, e, cnt, pos, stk[v_];
bool vst[v_];
vi gp1[v_], gp2[v_];
vector<vi> res;

void dfs(int now)
{
    vst[now] = true;
    for (int nxt : gp1[now])
        if (!vst[nxt])
            dfs(nxt);
    stk[pos++] = now;
}

void scc(int now)
{
    vst[now] = true;
    res[cnt].push_back(now);
    for (int nxt : gp2[now])
        if (!vst[nxt])
            scc(nxt);
}

int main()
{
    int i;
    scanf("%d %d", &v, &e);
    for (i = 1; i <= e; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        gp1[a].push_back(b);
        gp2[b].push_back(a);
    }

    for (i = 1; i <= v; i++)
        if (!vst[i])
            dfs(i);

    memset(vst, 0, sizeof(vst));
    while (pos)
    {
        int top = stk[--pos];
        if (vst[top])
            continue;
        res.push_back(vi());
        scc(top);
        cnt++;
    }

    for (i = 0; i < cnt; i++)
        sort(res[i].begin(), res[i].end());
    sort(res.begin(), res.end(), [](const vi &i, const vi &j) { return i[0] < j[0]; });

    printf("%d\n", res.size());

    for (auto &i : res)
    {
        for (auto j : i)
            printf("%d ", j);
        puts("-1");
    }
    return 0;
}

https://jason9319.tistory.com/98

가장 왼쪽부터 폰트가 설정되고, 적용되지 않는 폰트가 있으면 오른쪽으로 적용

이어지는 간선들을 하나의 집합으로 분류하고 서로소 집합들을 만드는 알고리즘이다. 

Disjoint Set이라고도 부른다.

핵심 함수

• find 함수 : 노드들의 부모를 찾는 과정, 어떤 집합에 포함되있는지 찾는다.
• union 함수 : 두 노드를 하나의 집합으로 묶는다.

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

public class Main {
    static int n, m, parent[];
 
    static int find(int x) {
        if (parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }
 
    static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        parent[y] = x;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        parent = new int[n + 1];
 
        for (int i = 0; i <= n; i++)
            parent[i] = i;
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0, t, x, y; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            t = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            if (t == 0) {
                union(x, y);
            } else {
                sb.append(find(x) == find(y) ? "YES" : "NO").append("\n");
            }
        }
 
        System.out.println(sb);
 
        br.close();
    }
}

간과했던 부분 ( line : 38 )

두 노드가 같은 집합인지 확인할 때, find 함수를 통해 찾는다면 재귀를 다시 사용해야 했기 떄문에 불필요하다고 생각했고, parent 배열을 확인하여 O(1) 만에 같은 집합인지 알 수 있을 것이라고 생각했다. 

3 3
0 2 3
0 1 2
1 1 3

하지만 이러한 반례의 경우, 3의 부모는 2가 될 것이고, 2의 부모는 1이 될 것이다. 노드 1, 2, 3은 같은 집합이지만 1과 3노드가 같은 집합인지 확인할 경우 parent 배열에 다른 값이 들어 가있는 상태이고, 같은 집합임에 불구하고 NO를 출력했던 것이다. 따라서 같은 집합인지 확인하기 전 find를 호출하여 다시 루트노드까지 가는 과정을 통해 parent 배열을 최신화해주는 것을 통해 해결할 수 있었다.

입출력

#include <bits/c++io.h>
#include <stdio.h>
#include <cstdio>
int n;
int main() {
    scanf("%d",&n);
    printf("hello C++! %d",n);
}

#include <iostream>
using namespace std;
int n;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(nullptr);
    cin >> n;
    cout << "hello C++! " << n;
}

endl  ,  \n  

endl은 출력 후 버퍼를 비우는 역할을 수행하기 때문에 많이 느리다.

using namespace std 에 대해서

배열 미리 최대범위까지 선언하는것과  배열 범위 입력받고 선언하는법

string 사용법 

https://webnautes.tistory.com/1158