Repository

문제를 보면 모든 노드들은 연결이 되어있고, 모든 노드들을 돌아볼 때 가장 적은 종류의 비행기( 간선 정보 )를 타고 움직이는 수를 알아내야하는 것이 문제의 의도 입니다.

이때 우리는 모든 노드가 연결되어있고, 최소한의 경로로 모든 노드를 방문해야한다는 조건에서 최소신장 트리를 떠올릴 수 있어야 합니다.

최소신장 트리의 모든 노드를 연결하면서 가중치의 합을 구하면 되겠는데, 이때 값은 N - 1로써 가장 간단하게 구할 수 있습니다.

(N은 노드 수입니다.)

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

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

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

        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            for (int i = 0; i < m; i++) {
                br.readLine();
            }
            sb.append(n - 1).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        br.close();
        bw.close();
    }

}

• 시간복잡도: O(1)
• 공간복잡도: O(1)

1. Mysql 접속

기본적으로 데이터베이스 작업을 하거나 테이블 작업을 하려면 설치한 mysql에 접속해야합니다.

만약 처음 설치하였다면 기본적으로 root라는 계정을 할당해주고, 해당 계정은 초기 설치할 때 설정한 비밀번호로 설정이 되게 됩니다. 

mysql -u root -p

2. Database

2-1. 생성

CREATE DATABASE 데이터베이스명;

2-2. 목록 확인

SHOW DATABASES;

2-3. 데이터베이스 선택

USE 데이터베이스명;

2-4. 데이터베이스 삭제

DROP DATABASE 데이터베이스명;

3. 사용자 및 권한 설정

3-1. 사용자 생성

CREATE USER '사용자명'@'호스트' IDENTIFIED BY '비밀번호';

호스트: 접속할 수 있는 정보로 로컬만 허용할 경우 localhost, 모두 허용할 경우 %로 지정

3-2. 권한 부여

GRANT 권한종류 ON 데이터베이스명.* TO '사용자명'@'호스트';
FLUSH PRIVILEGES;

권한 종류: ALL PRIVILEGES, SELECT, INSERT, UPDATE, DELETE, CREATE, DROP

3 - 2. 권한 확인

SHOW GRANTS FOR '사용자명'@'호스트';

3-3. 사용자 삭제

DROP USER '사용자명'@'호스트';

개요

개발을 하거나 면접을 보게 되면 Spring Data Jpa관련 단골 질문으로 가장 많이 나오는 내용이라 생각합니다.

그럼 도대체 OSIV가 뭐길래 JPA에서 계속 말이 나오게 되는 걸까? 한번 알아보도록 하겠습니다.

OSIV란

OSIV란 Open Session In View의 약자로써 사실 JPA가 도입되면서 Open EntityManager In View로 개념이 확립되었으나 편의상 지금까지 OSIV라고 부르고 있습니다.

말 그대로 OSIV는 View까지 EntityManager를 열어두는 것을 의미합니다.

그럼 JPA에서 EntityManager이라 함은 무엇일까요?

바로 영속성 컨텍스트를 의미합니다.

영속성 컨텍스트는 요청이 들어오면 생성되고 사라지는 휘발성 콘텍스트입니다.

해당 콘텍스트는 기본적으로 요청이 들어오면 생성되고, 요청이 끝나면 사라지게끔 되어있는데, 이는 OSIV 설정이 기본으로 True로 설정되어 있어 가능한 일입니다.

만약 OSIV가 False로 설정되어 있다면 영속성 콘텍스트는 Transaction범위에 따라 생성되고 Transaction이 끝날 시 사라지게 됩니다.

이로써 OSIV가 어떤 설정인지 알았으니 해당 설정이 기능과 성능에 미치는 영향에 대해 알아보겠습니다.

OSIV가 미치는 영향

OSIV 설정은 아래 그림으로 한 번에 확인할 수 있습니다.

위와 같이 데이터를 생성, 수정, 삭제 기능들은 트랜잭션 범위 내에서 작업이 가능합니다.

다만 읽기 기능의 경우 영속성 콘텍스트 범위 내에 있을 경우 읽기가 가능한데,

OSIV는 영속성 콘텍스트를 view까지 늘려 트랜잭션이 아닌 요청의 생존 범위까지 늘리는 것을 의미합니다.

즉 생성, 수정, 삭제는 OSIV의 목적은 아니고, 읽기 범위를 늘리는 것이 주목적이라고 보시면 됩니다.

그럼 왜! 읽기 범위를 늘리는 것인가?

이는 Lazy Loading과 밀접한 관련이 있습니다.

Lazy Loading이란 지연 읽기 기능인데, 처음 데이터베이스에서 조회하는 것이 아닌 추후 해당 데이터를 사용할 때 조회하는 기능입니다.

해당 기능을 사용할 때, 영속성 콘텍스트의 생존범위 내에서 로딩하는지가 중요한데 이를 어디까지 허용할 것인지를 조절할 수 있다고 보시면 좋을 것 같습니다.

그럼 해당 기능이 왜 성능 향상에 기여할 수 있는가? 영속성 콘텍스트를 유지하는 것 또한 많은 자원을 소모하게 됩니다.

이를 View까지 유지하지 않고 트랜잭션 범위에 맞춰 종료하게 되면 OSIV가 TRUE인 상태보다 좀 더 효율적으로 자원을 사용할 수 있게 됩니다.

해당 옵션은 위에서 말했듯 default True인 옵션입니다.

만약 애플리케이션 성능 향상에 있어 관심이 많다면 테스트해보시길 바랍니다.

Reference

https://docs.spring.io/spring-boot/reference/data/sql.html#data.sql.jpa-and-spring-data.open-entity-manager-in-view

입력 예제를 확인해보면 N개의 노드와 N - 1개의 간선 정보가 주어지는 것을 확인해 볼 수 있습니다.

그림으로 표현하면 위와 같이 표현할 수 있으며, 해당 정보를 통해 2번부터 N번 까지 노드들의 부모정보를 출력하면 되는 문제입니다.

즉 2번의 부모 4, 3번의 부모 6, 4번의 부모 1, 5번의 부모 3, 6번의 부모 1, 7번의 부모 4번 해서 결과는 4, 6, 1, 3, 1, 4가 나오면 되는 것 입니다.

여기서 주의해야하는 점은 해당 트리는 자식 노드가 최대 2개가 주어진다는 말이 없으니 일반 트리이며, 자식 노드는 N개가 될 수 있다는 말입니다.

문제 풀이는 생각보다 간단합니다. 

문제에서 트리의 루트를 1번으로 잡는다 하였으니, 1번의 자식들의 부모를 Bfs 탐색을 통해 확인한 다음 2번노드 부터 부모 번호를 출력해주면 됩니다.

public class Main {

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

        List<Integer>[] arr = new List[N + 1];
        for( int i = 1; i <= N; i++ ) {
            arr[i] = new ArrayList<>();
        }

        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());

            arr[from].add(to);
            arr[to].add(from);
        }

        int[] parent = new int[N + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        parent[1] = 1;

        while (!queue.isEmpty()) {
            int current = queue.poll();
            for(int child: arr[current]){
                if (parent[child] == 0) {
                    parent[child] = current;
                    queue.add(child);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= N; i++) {
            sb.append(parent[i]);
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

• 시간복잡도: O(N)
• 공간복잡도: O(N)

모스 부호 문제입니다.

매우 간단한 문제이며, 우선 시간제한과 메모리 제한을 확인해 보겠습니다.

입력 예제를 보면  N은 최대 100 이하의 개수가 주어진다 합니다.

그럼 이 문제를 접할 때 최악의 경우 모스부호 100개를 문자열로 변환해야 하는 문제라고 볼 수 있습니다.

예제로 준 모스 부호표를 보면 41개를 명시한 표를 통해 답을 만들 수 있습니다.

최악의 경우 100개의 모스 부호를 41개 중 찾기 위해 반복문을 돌린다 하면 4100번 돌려 해결을 할 수 있습니다.

다만, 4100번 돌려 답을 찾는 것은 O(n)의 복잡도를 가지게 되지만 41이란 상수는 빅오표기법상 표기를 안 하니 딱히 효율적인 알고리즘은 아니라 생각합니다.

거기서 우리는 Map이라는 자료구조를 활용하여 O(1) 시간복잡도로 모스 부호를 검색할 수 있는 방법을 떠올릴 수 있습니다.

public class Problem29701 {

    public static Map<String, String> initMorseCodeMap() {
        Map<String, String> morseCodeMap = new HashMap<>();
        morseCodeMap.put(".-", "A");
        morseCodeMap.put("-...", "B");
        morseCodeMap.put("-.-.", "C");
        morseCodeMap.put("-..", "D");
        morseCodeMap.put(".", "E");
        morseCodeMap.put("..-.", "F");
        morseCodeMap.put("--.", "G");
        morseCodeMap.put("....", "H");
        morseCodeMap.put("..", "I");
        morseCodeMap.put(".---", "J");
        morseCodeMap.put("-.-", "K");
        morseCodeMap.put(".-..", "L");
        morseCodeMap.put("--", "M");
        morseCodeMap.put("-.", "N");
        morseCodeMap.put("---", "O");
        morseCodeMap.put(".--.", "P");
        morseCodeMap.put("--.-", "Q");
        morseCodeMap.put(".-.", "R");
        morseCodeMap.put("...", "S");
        morseCodeMap.put("-", "T");
        morseCodeMap.put("..-", "U");
        morseCodeMap.put("...-", "V");
        morseCodeMap.put(".--", "W");
        morseCodeMap.put("-..-", "X");
        morseCodeMap.put("-.--", "Y");
        morseCodeMap.put("--..", "Z");
        morseCodeMap.put(".----", "1");
        morseCodeMap.put("..---", "2");
        morseCodeMap.put("...--", "3");
        morseCodeMap.put("....-", "4");
        morseCodeMap.put(".....", "5");
        morseCodeMap.put("-....", "6");
        morseCodeMap.put("--...", "7");
        morseCodeMap.put("---..", "8");
        morseCodeMap.put("----.", "9");
        morseCodeMap.put("-----", "0");
        morseCodeMap.put("--..--", ",");
        morseCodeMap.put(".-.-.-", ".");
        morseCodeMap.put("..--..", "?");
        morseCodeMap.put("---...", ":");
        morseCodeMap.put("-....-", "-");
        morseCodeMap.put(".--.-.", "@");
        return morseCodeMap;
    }

    public static void main(String[] args) throws IOException {
        Map<String, String> morseCodeMap = initMorseCodeMap();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        StringBuilder sb = new StringBuilder();
        while(N-- > 0) {
            String morseCode = st.nextToken();
            sb.append(morseCodeMap.get(morseCode));
        }
        System.out.println(sb);
    }
}

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)

이번 문제 또한 매우 간단한 문제입니다.

N명의 학생이 존재하고, 3번째 줄부터 N개 나오는 학생들 이름을 가지고 인기도를 측정하여 출력하면 되는 문제입니다.

우선 여기서 봐야 할 점은 인기도 측정 방식과 정렬인데요.

인기도 측정 방식은 그냥 나오는 학생 이름들을 전부 인기도에 반영하면 되는 간단한 문제이고,

정렬은 주어진 조건에 맞춰 정렬하면 됩니다.

정렬의 경우 저는 Stream의 sorted함수를 사용하였는데요. 이때, sort조건을 커스텀함으로써 간단하게 정렬하였습니다.

이후 reduce를 활용하여 StringBuilder에 값들을 담게 했는데요, 이는 String과 달리 StringBuilder는 불변성이 아니어서 메모리 활용 측면에서 훨씬 효율적이라 판단하여 사용하였습니다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<String, Integer> map = new HashMap<>();
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++) {
            map.put(st.nextToken(), 0);
        }

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                String to = st.nextToken();
                map.put(to, map.get(to) + 1);
            }
        }

        StringBuilder answer = map.entrySet().stream().sorted((prev, now) -> {
            if(prev.getValue() != now.getValue()) return now.getValue() - prev.getValue();
            return prev.getKey().compareTo(now.getKey());
        }).reduce(new StringBuilder(),(sb, entry) -> sb.append(entry.getKey()).append(" ").append(entry.getValue()).append("\n"),StringBuilder::append);
        System.out.println(answer);
    }
}

• 시간복잡도: O(n)
•  공간복잡도: O(n)

이번 문제는 고민 했던 것보다 꽤 쉽게 풀어져 가져와보았습니다.

위와 같이 문제가 주어졌습니다.

쉽게 생각해보면 점이 n개 주워졌을 때 x나 y에 평행이 되는 선의 갯수를 구하라는 뜻인데,

여기서 살짝 생각해보면 좋은 점은 x와 y에 평행이 되려면 어떤 조건을 가져야하는가 입니다.

x에 평행이 되려면 두 점의 y좌표는 동일해야할 것이고, y에 평행이 되려면 x좌표가 동일해야할 것 입니다.

즉, x점을 기준으로 묶은 자료와 y점을 기준으로 묶은 자료만 있다면 쉽게 문제를 풀 수 있는 것입니다.

public class Main {

    static Map<Integer, Integer> xLineMap = new HashMap<>();
    static Map<Integer, Integer> yLineMap = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++) {
            String[] strs = br.readLine().split(" ");
            int x = Integer.parseInt(strs[0]);
            int y = Integer.parseInt(strs[1]);
            xLineMap.put(x, xLineMap.getOrDefault(x, 0) + 1);
            yLineMap.put(y, yLineMap.getOrDefault(y, 0) + 1);
        }
        int answer = 0;
        for (int count : xLineMap.values()) {
            if (count > 1) {
                answer++;
            }
        }
        for (int count : yLineMap.values()) {
            if (count > 1) {
                answer++;
            }
        }
        System.out.println(answer);
    }
}

위 문제를 확인해보면 2초의 시간초가 주어지고, n은 최대 100,000이라고 합니다.

이를 통해보면 알고리즘은 O(n)의 성능을 가지고 있도록 작성하는 것이 합리적이라 생각합니다.

위 알고리즘을 보면 n을 받아 n번 반복함으로 O(n)의 시간복잡도를 가지고 있다고 볼 수 있습니다.

또한, n을 받아 사용하는 데이터들을 보면 n개의 데이터들만을 활용하는 것을 볼 수 있어 공간복잡도 또한 O(n) 혹은 O(2n)의 복잡도를 가지고 있습니다.

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)

들어가기에 앞서

해당 글을 작성하기에 앞서 이진트리는 어떤 것인지에 대한 사전 지식이 있어야 이해할 수 있는 글입니다.

만약 이진트리가 무엇인지 모른다면 이 글을 읽고 오시기 바랍니다.

이진 트리 순회

이진 트리를 순회하는 방법에는 어디서부터 확인하느냐로 4가지로 나눌 수 있습니다.

순회 방법에 따라 사용처가 다르게 나오게 되고, 이를 학습함으로써 좀 더 본인이 사용하고자 하는 목적에 알맞은 방법으로 알고리즘을 작성할 수 있습니다.

아래 보이는 이진 트리를 통해 각각의 순회 결과에 대해 알려드리겠습니다.

아래 이진 트리는 이 곳에서 코드로 확인해 보실 수 있습니다.

전위 순회 ( Pre-order Traversal )

전위 순회는 부모 노드 -> 왼쪽 노드 -> 오른쪽 노드 순으로 재귀하며 출력하는 방법입니다.

즉 가장 왼쪽부터 라인부터 탐색하며, 가장 깊은 Level의 오른쪽 노드부터 차근차근 탐색할 수 있게 해줍니다.

public void traversePreOrder(TreeNode<Integer> node) {
    if (node != null) {
        System.out.print(" " + node.getValue());
        traversePreOrder(node.getLeft());
        traversePreOrder(node.getRight());
    }
}

결과

사용처

• DFS 탐색
• 트리 복사

중위 순회 ( In-order Traversal )

중위 순회는 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식노드 순으로 순회하는 방법입니다.

public void traverseInOrder(TreeNode<Integer> node) {
    if (node != null) {
        traverseInOrder(node.getLeft());
        System.out.print(" " + node.getValue());
        traverseInOrder(node.getRight());
    }
}

결과

사용처

• 오름차순 정렬
• 정렬된 데이터 탐색

후위 순회 ( Post-order Traversal )

후위 순회는 왼쪽 자식노드 -> 오른쪽 자식노드 -> 부모 노드 순으로 순회하는 방법입니다.

public void traversePostOrder(TreeNode node) {
    if (node != null) {
        traversePostOrder(node.getLeft());
        traversePostOrder(node.getRight());
        System.out.print(" " + node.getValue());
    }
}

결과

사용처

• 메모리 해제
• 파일 구조 삭제
• 후위 표기법을 통한 연산

레벨 순회 ( Level-order Traveral )

레벨 순회는 root 부터 각 레벨마다 순차적으로 왼쪽부터 오른쪽으로 순회하는 방법입니다.

public void traverseLevelOrder(TreeNode root) {
    if (root == null) return;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(" " + node.getValue());

        if (node.getLeft() != null) queue.add(node.getLeft());
        if (node.getRight() != null) queue.add(node.getRight());
    }
}

결과

사용처

• 최단 경로 탐색
• Bfs 탐색

Reference

https://www.w3schools.com/dsa/dsa_data_binarysearchtrees.php