딩코딩 : Computer Science 블로그

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

1.문제설명

트리의 지름을 구하는 방법은 다음과 같다.

아무 노드 A를 택하고, A노드와 가장 멀리있는 노드 B를 찾는다.(BFS or DFS 아무거나 사용해도 된다)

그리고 노드 B와 가장 멀리 있는 노드 C를 찾아서

노드 B와 노드 C의 거리를 구하면 그게 트리의 지름이 된다.

현재 문제에서 노드간의 거리가 다른데

이 문제는 최단경로를 찾는 문제가 아니므로 다익스트라 알고리즘을 사용할 필요는 없고

BFS로 가장 먼 거리에 있는 노드를 찾아주기만 하면된다.

2.문제풀이코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Pair{
    int node , dist;
    Pair(int node, int dist){
        this.node = node;
        this.dist = dist;
    }
}

public class main {
    static ArrayList<Pair>[] adj;
    static int V;
    static Queue<Pair> Q;

    //start node로 부터 가장 멀리 있는 node와 거리를 구하는 함수
    static Pair bfs(int start){
        int end = 0;
        int dist = 0;
        boolean[] visit = new boolean[V+1];
        visit[start] = true;
        Q.add(new Pair(start, 0));

        while(!Q.isEmpty()){
            Pair cur = Q.poll();
            if(cur.dist > dist){
                end = cur.node;
                dist = cur.dist;
            }

            for(int i=0; i<adj[cur.node].size(); i++){
                int nextNode = adj[cur.node].get(i).node;
                int addDist = adj[cur.node].get(i).dist;

                if(!visit[nextNode]){
                    visit[nextNode] = true;
                    Q.add(new Pair(nextNode, cur.dist + addDist));
                }
            }
        }

        return new Pair(end, dist);
    }



    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        adj = new ArrayList[V+1];
        Q = new LinkedList<>();

        for(int i=1; i<=V; i++){
            adj[i] = new ArrayList<>();
        }

        for(int i=1; i<=V; i++){
            st = new StringTokenizer(br.readLine());
            int curNode = Integer.parseInt(st.nextToken());
            int connectNode = Integer.parseInt(st.nextToken());
            
            while(connectNode!=-1){
                int dist = Integer.parseInt(st.nextToken());
                adj[curNode].add(new Pair(connectNode, dist));
                connectNode = Integer.parseInt(st.nextToken());
            }
        }

        Pair start = bfs(1);
        Pair ans = bfs(start.node);
        bw.write(ans.dist+"");
        bw.flush();
        bw.close();
    }
}

데이터를 순차적으로 정렬해서 저장해야 하는 이유

컴퓨터에서 영속적인 데이터를 보관하기 위해

물리적인 디스크에 정보를 저장한다.

cpu의 관점에서 디스크에서 데이터를 읽어오는 io시간은 굉장히 큰 시간이다.

디스크에서 특정 데이터를 찾는데는 물리적인 rotational delay와 seek time이 필요하기 때문이다.

그렇기 때문에 최대한 디스크에 적게 접근하는 게 중요한 문제이다.

데이터를 저장할 때는 메모리의 output Buffer에 있는 내용을 디스크에 쓰고,

컴퓨터에서 디스크에 있는 정보가 필요해서 불러올 때는 디스크의 블록 단위를 기준으로 메모리에 데이터를 불러온다.

이때 중요한 것중 하나가

컴퓨터에서 특정 데이터가 필요할 때

디스크에 access해서 디스크로부터 메모리로 블록을 읽어와야 한다.

이때 필요한 레코드가 block의 어디에 위치해 있는지 찾는 것이 중요하다.

만약 레코드가 10억개가 존재하는 상황에서 하나의 레코드를 찾아야 한다고 생각해보자

레코드들이 모두 무작위로 위치해 있다면 최악의 경우 레코드를 10억개를 다 찾아보아야 한다.

이 방법은 너무 오래걸린다.

특정 레코드 조회 빨리 하기 위해서 key값을 기준으로 binary search를 한다면

굉장히 빠르게 찾을 수 있다. binary search는 logN 만큼 조회하면 해당 레코드를 찾을 수 있기 때문이다.

log(10억)은 30에 가깝다.

위에서 데이터가 무작위로 위치해있을 땐 최악의 경우 10억번을 봐야했는데,

데이터가 정렬되어 있다면 30번만 보면 디스크에서 원하는 데이터를 찾을 수 있다!

즉 데이터가 일정하게 정렬되어 있는 화일을 sequential한 파일, 순차화일이라 부르는데

화일이 순차화일로 존재한다면 데이터 조회를 굉장히 빠르게 할 수 있는 것이다.

트랜잭션 화일과 마스터 화일 

위에서 처럼 화일에서 데이터를 순차적으로 저장해야 조회를 빠르게 할 수 있다.

그런데 단순히 화일을 순차적으로 저장하면 문제가 발생한다.

데이터에 특정 레코드가 삽입된다면

모든 데이터를 다시 써야하는 문제가 발생하기 때문이다.

예를 들어서

데이터 레코드가 총 10억개 정도 있다고 생각하자.

10억개 데이터는 모두 정렬되어 있다.

이때 화일에 데이터를 하나 삽입해야한다.

그런데 5억개 데이터와 5억개 데이터 사이에 새로운 데이터가 하나 추가되어야 된다고 생각해보자.

그렇다면 새로운 화일을 만들어

기존 5억개 데이터를 그대로 쓰고, 새로운 데이터를 하나 추가하고

다시 또 5억개 데이터를 써야한다.

즉, 순차적인 화일 구조를 유지하기 위해서 데이터가 갱신될 때마다 엄청난 양의 데이터를 다시 써야한다.

이런 구조는 실제로 사용할 수 없다. 데이터 조회는 빨리 할 수 있지만 조회를 빨리 하기 위해서 화일을 다시 쓰는 시간이 너무 오래걸린다.

이러한 문제를 개선하려면

순차 화일 구조를 유지하되, 데이터 갱신하는 횟수를 줄여야한다.

이를 해결하기 위한 방법이 마스터 순차화일을 하나 유지하고,

데이터 갱신 요청을 기록해주는 트랜잭션 화일을 하나 더 만들어서,

일정 간격마다 트랜잭션 화일에서 마스터화일로 데이터를 merge해주면 된다.

이전에는 데이터 갱신이 될때마다 화일을 다시 써야 했다면,

이제는 데이터 갱신 기록을 트랜잭션 화일에 쭉 저장해두었다가, 정해둔 간격마다 마스터 화일에 저장하면 된다.

이렇게 하면 마스터 화일에서 데이터를 빠르게 조회할 수 있고,

순차화일에서 데이터를 갱신하는 문제도 해결할 수 있다.

다만 이도 완벽할 수 없는게 데이터 갱신을 일정 주기마다 하기 때문에

트랜잭션 파일에 저장되었지만 마스터 파일에 저장되지 않았다면 데이터 조회를 할 수 없다.

그래서 비즈니스 로직에 따라 일정한 간격을 정하는 것이 굉장히 중요하다.

Java Fast IO 코드 템플릿

import java.io.*;
import java.util.StringTokenizer;

public class main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        while(st.hasMoreTokens()){
            bw.write(Integer.parseInt(st.nextToken()) + " ");
        }
        
        //problem solve

        bw.flush();
        bw.close();
    }
}

java로 알고리즘 문제를 풀 때

입력의 개수가 엄청 많은 경우 Scanner을 사용하면 시간이 오래 걸려서

알고리즘을 잘 구현했더라도 시간 초과로 틀릴 수 있다.

java에서는 이를 해결하기 위해

BufferedReader, BufferedWriter을 이용하여 입력과 출력을 더 빠르게 할 수 있다.

이 방법이 Scanner을 이용해 입출력하는 것보다 빠른 이유는 다음과 같다.

Scanner을 이용하여 입출력할 때는 바로바로 입출력을 해서 io가 빈번하게 발생하는데,

Buffered 방식을 이용하면 입출력을 즉시 하는 것이 아니라 Buffered에 저장했다가 필요할 때 io를 실시하기 때문에

보다 적은 io횟수로 입출력을 할 수 있어서 보다 빠르게 작업을 수행할 수 있다.

더불어 내가 해야할 일 중 입력은 엄청 많은데 출력이 적은 경우

입력만 BufferedReader로 받고 출력을 System.out.println으로 간편하게 해도 되지 않나 하는 의문이 들었다.

입력과 출력을 완전히 분리해서 사용하면 크게 문제가 되지 않는 것 같다.

예를 들어 입력은 모두 BufferedReader을 사용해서 받고

출력은 System.out.println으로만 하면 정상적으로 작동한다.

하지만 만약에 System.out.println 과 bw.write()를 하나의 프로그램에서 둘다 사용한다면

내가 예상한 코드대로 동작하지 않는 경우가 생긴다.

즉 입력을 받을 때도 한가지 메소드를 이용해야하고,

출력을 할 때도 한가지 메소드만 출력해서 이용해야 두가지 메소드가 서로 얽히지 않는다.

System.out.println, BufferedWriter.write 소요시간 비교

실제로 두 방법의 소요시간 차이를 측정해보았다.

환경은 인텔리제이에서 돌리고, 숫자 100만개를 출력하는 속도를 비교해보았다.

먼저 BufferedWriter을 이용한 코드이다.

import java.io.*;
import java.util.StringTokenizer;

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

        //bw 사용
        long start = System.currentTimeMillis();
        for (int i=0; i<1000000; i++) {
            bw.write(i + " ");
        }
        bw.flush();
        long finish = System.currentTimeMillis();
        long bwTime = finish - start;
        bw.write("---------\n");
        bw.write("Buffered write 소요 시간 "+ bwTime);
        bw.close();
    }
}

이번엔 System.out.println 을 이용한 코드이다

import java.io.*;
import java.util.StringTokenizer;

public class main {
    public static void main(String[] args) throws IOException {
        //bw 사용
        long start = System.currentTimeMillis();
        int count = 0;
        for (int i=0; i<1000000; i++) {
            System.out.print(i + " ");
        }
        long finish = System.currentTimeMillis();
        long sysTime = finish - start;

        System.out.println("---------\n");
        System.out.println("System out 소요 시간 "+ sysTime);

    }
}

같은 출력을 할 때

Buffered 방식을 이용하면 85ms,

System.out.print 방식을 이용하면 1171ms가 소요된 것을 알 수 있다.

입출력하는 데이터의 크기가 더 커질수록 두 방식의 시간차이는 더 커질 것이다.

반드시 Fastio로 문제를 풀어야 하는가?

하지만 꼭 모든 알고리즘 문제에 fastio를 적용해야하는 건 아니다.

입출력의 개수가 작은 편이라면

대부분 System 방식을 사용해서 간편하게 문제를 풀어도 해결할 수 있다.

이는 정확히 측정한 것이 아니고 문제마다 걸려있는 시간 제한에 따라 다르지만

내 개인적인 체감 상 데이터의 크기 N이 10,000개 이하정도라면

Buffered까지 사용하지 않고 System만을 이용해서도 문제를 해결할 수 있는 것 같다.

다만 Buffered를 이용해서 푼거에 비해 소요 시간이 많게 나올 수 있다.

알고리즘 문제를 푸는데 자바 입출력 속도를 위해 Buffered와 StringTokenizer 을 써서 코드를 여러줄 쓴다는 게

꽤 귀찮게 느껴지는 일이긴 하다.

상황에 따라 유동적으로 쓸 수 있도록 훈련하면 좋을 것 같다.

var season = 3
    when(season){
        1 -> println("Spring")
        2 -> println("Summer")
        3 -> {
            println("Fall")
            println("Autumn")
        }
        4 -> println("Winter")
    }

    var month = 1
    when(month) {
        in 3..5 -> println("Spring")
        in 6..8 -> println("Summer")
        in 9..11 -> println("Fall")
        12,1,2 -> println("Winter")
        else -> println("Invalid Season")
    }

    var age = 30
    when(age){
        !in 0..20 -> println("now you may drink in the US")
        in 18..20 -> println("you may vote now")
        16,17 -> println("you may drive now")
        else -> println("you're too young")
    }

    var x : Any = "13.37f"
    when(x){
        is Int -> println("$x is an Int")
        is Double -> println("$x is not a Double")
        is String -> println("$x is a String")
        else -> println("$x is none of the above")
    }

배경

CI / CD 파이프라인을 구축하여

깃허브에서 코드 푸시를 통해 AWS 클라우드에 배포하는 것 까지 자동화 하기 위해 공부하고 있었다.

자세한 과정은 다음과 같다.

깃허브 master 브랜치에 푸쉬하면

travis.ci에서 해당 코드를 바탕으로 테스팅을 시도하며

테스트를 통과하면 도커 이미지를 생성하고 도커 허브에 레포지토리를 만들고

이를 바탕으로 AWS Elastic Beanstalk과 RDS에 연동되어 서버와 데이터베이스를 띄운다.

그런데 이러한 과정에서

프론트 파일은 제대로 배포에 성공했으나

서버와 데이터베이스 쪽에 문제가 발생했다.

오류는 다음과 같다.

data: {code: 'ER_BAD_DB_ERROR', errno: 1049, sqlMessage: "Unknown database 'myapp'", sqlState: '42000', index: 0, …}

배포과정에서 AWS에서 RDS에 mysql 인스턴스를 생성해서

서버와 연결하여 사용하려는데

위 코드와 사진과 같이 에러가 발생했다.

위에 설명한 것과 같이 여러가지 과정이 혼합되어 있고 다 처음해보는 것이라

어디서 문제인지 한참을 고민했다.

"Unknown database 'myapp'"

그러다가 위와 같은 에러가

서버에서 데이터베이스에 쿼리를 날릴 때 해당 데이터베이스가 존재하지 않아서 발생하는 것임을 확인했고,

RDS에서 돌리고 있는 mysql에 직접 연결해서 데이터베이스를 확인해보니

내가 생성하고자 했던 myapp이라는 데이터베이스가 존재하지 않아서 에러가 발생했다는 것을 알았다.

에러 원인

그동안 깃허브에 푸쉬하고 자동배포가 되면서

mysql에서도 myapp이라는 데이터베이스가 자동적으로 생성될 것이라 생각했다.

개발환경에서는 미리 데이터베이스를 생성하는 코드를 작성해두고 테스팅해서

mysql도 자동배포가 되었는데, 실제로 배포환경에서는 개발환경처럼 mysql을 서버 환경과 같이 두지 않고

Beanstalk과 RDS로 두개로 구분해주어서 생성했기 때문에

내가 만든 환경에서는 RDS를 통해 mysql 인스턴스를 생성하고 쿼리를 통해 초기 세팅을 해주는 작업이 필요했던 것이다.

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

큰 수의 계산을 잘 구현해야 하는 문제이다.

2^100은

10^34 정도 되기 때문에

long long 은 최대 19자리이므로 long long 2개를 붙여쓰면 38자리까지 구현이 가능하다.

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


void _pow(int n){
    long long a = 0, b = 0, mod = 1'000'000'000'000'000'000;
    for(int i=0; i<n; i++){
        b*=2;
        a = 2 * a + 1;
        b += a / mod;
        a %= mod;
    }
    if(b>0) cout << b << a << '\n';
    else cout << a << '\n';
}


//start : 0 , mid:1, end:2
void moveBlock(int start, int end){
    cout << start+1 << ' ' << end+1 << '\n';
}


void hanoi(int n, int start, int mid, int end){
    if(n==0) return;
    hanoi(n-1, start, end, mid);
    //마지막꺼 옮기기
    moveBlock(start, end);
    hanoi(n-1, mid, start, end);
}

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

    int n;
    cin >> n;
    _pow(n);

    if(n<=20) {
        hanoi(n, 0, 1, 2);
    }

    return 0;
}

docker run -d -p 8010:8080 -v /usr/src/app/node_modules -v $(pwd):/usr/src/app 이미지

볼륨을 이용해서 로컬 파일을 Mapping하면

로컬에 있는 파일이 변경되어도

이미지 파일을 새로 빌드할 필요 없이

컨테이너를 껏다가 다시 실행하여 변경사항을 적용할 수 있다.