학습용 공간

골드바흐의 추측과

에라토스테네스의 체를 활용 

위 두 개념은 starmk95.tistory.com/45 링크에서 설명

 

알고리즘) 수학 - 나머지 연산, 최대공약수(GCD), 최소공배수(LCM), 소수, 팩토리얼

1. 나머지 연산  - 덧셈 : (A+B)modM = ((AmodM)+(BmodM))modM  - 곱셍 : (A*B)modM = ((AmodM)*(BmodM))modM  - 뺄셈 : (A-B)modM = ((AmodM)-(BmodM)+M)modM cf) 왜 덧셈, 곱셈과 달리 +M을 해주는가? ex) ((..

starmk95.tistory.com

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<Integer> prime;
    static boolean[] check;
    public static void main(String[] args) {
        prime = new ArrayList<>();
        findPrime();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 테스트 케이스의 개수
        for (int i=0;i<n;i++) {
            int even = sc.nextInt(); // 짝수 입력 받기
            findPartitionNum(even);
        }
    }

    // 먼저 2 이상 1000000 이하의 소수들을 구한다. (입력 범위 내의 소수)
    // 소수들을 구하기 위해서는 에라토스테네스의 체를 사용한다.
    // 약 0.01초보다 덜 걸림
    public static void findPrime() {
        check = new boolean[1000001]; // 에라토스테네스의 체 구현 (true면 지워진 것, false면 지워지지 않은 것)
        for (int i=2;i<=1000000;i++) {
            if (!check[i]) { // 지워지지 않은 가장 작은 값을 구하기
                prime.add(i); // 해당 수는 소수이다. (소수 리스트에 추가)
            }
            for (int j=i*2;j<=1000000;j+=i) {
                // i의 최대값이 1000000이므로 i*i가 int 범위를 넘어가기 때문에 i*2부터 시작
                // i가 백만 이하의 수라면 i*i가 int의 범위 이내이므로 i*i부터 시작
                // i*i부터 시작하는 이유는 i*i보다 작은 i의 배수들은 이미 i보다 작은 소수들의 배수에 의해 처리되었기 때문에
                // 따로 처리할 필요가 없기 때문이다.
                check[j] = true; // 소수의 배수들 지워주기
            }
        }
    }

    public static void findPartitionNum(int even) {
        int cnt = 0; // 골드바흐 파티션의 개수
        for (int x : prime) { // 범위 내 모든 소수들에 대해 확인
            if (x <= even/2) { // 두 소수의 합의 순서만 다른 것은 같은 파티션 취급하므로 짝수의 반보다 같거나 작은 소수들에 대해 판별
                if (!check[even-x]) cnt+=1; // 짝수에서 해당 소수를 뺀 값이 소수라면 파티션 개수 하나 증가
            } else break; // 짝수의 반보다 큰 값에 대해서는 처리할 필요 없음 (중복이거나 소수다 짝수보다 큰 경우임)
        }
        System.out.println(cnt); // 해당 짝수의 골드바흐 파티션의 개수 출력
    }
}

 

문제 출처 : www.acmicpc.net/problem/17103

먼저 A진법 수를 10진법으로 변환하고,

변환된 10진법 수를 B진법으로 변환한다.

import java.util.Scanner;

public class Main {
    static int[] num;
    static int A;
    static int B;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        A = sc.nextInt();
        B = sc.nextInt();
        int m = sc.nextInt();
        num = new int[m];
        for (int i=m-1;i>=0;i--) { // 낮은 자리 수일수록 낮은 인덱스에 저장
            num[i] = sc.nextInt();
        }
        toB(to10());
        System.out.println();
    }
    /*
    1. 먼저 A진법 수를 10진법으로 바꾼다.
    2. 10진법으로 바뀐 수를 B진법으로 바꾼다.
     */

    // A진법 10진법으로 바꾸는 메소드
    public static int to10() {
        int num10 = 0;
        for (int i=0;i<num.length;i++) {
            num10 += num[i]*(int)Math.pow(A, i); // 각 자리에 맞게 A^n값 곱해서 10진수로 바꿔줌
        }
        return num10; // 10진수로 바꾼 값 저장
    }

    // 10진법 B진법으로 바꾸는 메소드
    public static void toB(int n) {
        if (n == 0) return;
        toB(n/B);
        System.out.print(n%B + " ");
    }
}

 

문제 출처 : www.acmicpc.net/problem/11576

일반적인 진수 변환법을 적용해서 푸는데

음수/음수의 경우 발생하는 예외를 처리해주어야한다.

주석 참고

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        if (num == 0) {
            System.out.println(0);
        } else {
            convert(num);
            System.out.println();
        }
    }

    /*
    진수 변환법
    2진수일 때,
    10 = 2*5 + 0
    5 = 2*2 + 1
    2 = 2*1 + 0
    1 = 2*0 + 1
    이에 따라, 10을 2진수로 표현하면 1010이된다.

    -2진수도 위와 같은 진수 변환법을 사용하면 된다.
    다만 주의할 점은 음수/음수인 경우의 처리이다.
    이 경우에만 나머지가 -1이 나오기 때문에 다르게 처리해주어야 한다.
    (나머지를 1로 만들기 위해서는 몫이 1만큼 커져야함)
    -13 = (-2)*7 + 1 이다.
    그러나 -13/-2의 결과는 6이 나온다.
    그러므로 -13-1/-2 처리를 해주어야 정상적인 7 값이 나온다.
    -13 = -2*(7) + 1
    7 = -2*(-3) + 1
    -3 = -2*(2) + 1
    2 = -2*(-1) + 0
    -1 = -2*(1) + 1
    1 = -2*(0) + 1
     */

    public static void convert(int n) {
        if (n == 0) return; // n이 0이면 변환 끝난 것임
        if (n%2 == 0) { // n이 짝수이면
            convert(n/-2);
            System.out.print(0); // 2로 나누어 떨어지므로 0
        } else { // n이 홀수이면
            if (n>0) convert(n/-2);
            else convert((n-1)/-2); // 음수/음수인 경우 -> 처리 필요
            System.out.print(1); // 2로 나누어 떨어지지 않으므로 1
        }
    }

}

 

문제 출처 : www.acmicpc.net/problem/2089

그래프의 정점의 집합을 둘로 분할하여,

각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때,

그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

dfs로 정점들을 탐색하며 간선으로 연결된 정점들은 다른 집합에 속하도록 한다.

check[x] == 1 또는 2 // 집합 1 또는 2에 넣기 (0이면 방문 안한 정점)

 

입력 예제는 성공했지만 계속 4초에서 3초로 넘어가는 중에 실패처리가 나와서 의문이였는데

그래프가 2개 이상의 연결요소로 구성된 경우를 처리하지 않았기 때문이라는 것을 깨달았다.

(그래프의 모든 정점들이 연결되어 있지 않고 섬처럼 떨어져 있을 수도 있다는 것)

 

import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph; // 인접리스트로 그래프 구현
    static int[] check; // 각 정점의 방문여부와 소속 집합을 기록 (0:방문안함, 1:집합1, 2:집합2)

    static void dfs(int x, int prevGroup) {
        if (prevGroup == 1) check[x] = 2;
        else if (prevGroup == 2) check[x] = 1;
        for (int y : graph[x]) {
            if (check[y] == 0) { // 방문 안한 정점이면
                dfs(y, check[x]);
            }
        }
    }

    static String checkBipartite(int vertex) {
        for (int i=1;i<=vertex;i++) { // 모든 정점과 연결된 정점들에 대해 확인
            for (int x : graph[i]) { // (모든 간선을 확인)
                if (check[i] == check[x]) { // 간선으로 연결된 간선이 같은 집합에 속하면
                    return "NO"; // 이분 그래프가 아님
                }
            }
        }
        return "YES"; // 위 루프를 모두 통과하면 이분 그래프가 맞음
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cases = sc.nextInt(); // 테스트 케이스 개수
        for (int i=0;i<cases;i++) {
            int n = sc.nextInt(); // 정점의 개수
            int m = sc.nextInt(); // 간선의 개수
            graph = (ArrayList<Integer>[]) new ArrayList[n+1]; // 정점의 개수만큼 리스트를 원소로 갖는 배열 생성
            for (int j=1;j<=n;j++){
                graph[j] = new ArrayList<Integer>(); // 각 정점마다 리스트 생성
            }
            for (int j=0;j<m;j++) { // 간선 저장
                int u = sc.nextInt();
                int v = sc.nextInt();
                graph[u].add(v);
                graph[v].add(u);
            }
            check = new int[n+1]; // 각 정점에 대한 방문 여부와 집합 기록 배열 생성
            // 그래프를 구성하는 연결요소가 2개 이상일 수도 있기 때문에
            // dfs 수행하고도 방문하지 않은 정점이 있는지 확인해야 함
            for (int j=1; j<=n; j++) {
                if (check[j] == 0) {
                    dfs(j, 1);
                }
            }
            System.out.println(checkBipartite(n));
        }
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1707

그래프의 연결 요소를 확인하는 방법은

임의의 정점에서 DFS 또는 BFS 탐색을 수행한 후에도 

방문하지 않은 정점이 남아있다면, 

다른 연결요소가 있다는 특성을 이용한 것이다.

 

모든 정점들에 대하여 각 정점을 방문했는지 확인하고, 

방문하지 않은 정점이 있다면 연결요소의 개수를 1개 추가하고

해당 정점에서 다시 탐색을 수행한다.

 

import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph; // 인접 리스트로 그래프 구현
    static boolean[] check; // 정점 방문 여부 확인하는 배열

    static void dfs(int x) {
        if (check[x]) return; // 이미 방문한 정점이면 해당 정점에서는 탐색 안함
        check[x] = true; // 정점 방문 체크
        for (int y : graph[x]) {
            if (!check[y]) { // x와 연결된 정점 y를 방문하지 않았으면
                dfs(y); // 정점 y 방문해서 탐색 수행
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // n = 정점의 개수
        int m = sc.nextInt(); // m = 간선의 개수
        // 그래프 구현
        graph = (ArrayList<Integer>[]) new ArrayList[n+1];
        for (int i=1;i<=n;i++) graph[i] = new ArrayList<Integer>();
        for (int i=0;i<m;i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }
        boolean flag = true; // 모든 연결요소 확인했으면 true, 아니면 false
        int compNum = 0; // 연결 요소의 개수
        // 정점 방문 여부 초기화
        check = new boolean[n+1];
        for (int i=1;i<=n;i++) { // 모든 정점에 대해 반복문 돌림
            if (!check[i]) { // 방문 안한 정점이 있다는 것은 확인 안한 연결요소가 있다는 것
                compNum+=1; // 연결요소 수 추가
                dfs(i); // 해당 연결요소 탐색 수행
            }
        } // 모든 정점이 방문 처리되었으면 모든 연결요소를 확인한 것임
        // 확인된 연결요소의 개수 출력
        System.out.println(compNum);
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/11724

리스트(그래프)의 원소(정점) 접근은 for each문을 사용하여 처리한다.

(for문과 get()메소드로 인덱스를 사용해 접근하는 것보다 빠르기 때문)

위의 이유에 대해서는 하단 링크 참고

https://starmk95.tistory.com/110 

 

JAVA) 리스트에는 for문 대신 for each 문을 사용하자

ArrayList 자료구조를 예시로 들어 설명하면 ArrayList.get(인덱스) 메소드를 실행하면 내부적으로 해당 인덱스를 찾기 위해 루프가 돌게 된다고 한다. 그렇기 때문에 리스트의 원소에 접근할 때, for ea

starmk95.tistory.com

인접 리스트를 사용해 그래프를 구현했고

DFS는 재귀, BFS는 Queue를 통해 구현했다.

import java.util.*;

public class Main {

    static ArrayList<Integer>[] graph; // 인접리스트 방식으로 그래프 저장
    static boolean[] check; // 정점 방문 여부를 확인하는 배열
    // 리스트(그래프)의 원소(정점) 접근은 for each문을 사용하여 처리
    // (for문과 get()메소드로 인덱스를 사용해 접근하는 것보다 빠르기 때문)

    static void dfs(int x) {
        if (check[x]) return; // 이미 방문한 적이 있는 정점이라면 해당 정점 탐색하지 않음
        check[x]= true; // 방문한 정점 체크
        System.out.print(x + " "); // 정점 방문하면 출력
        for (int y : graph[x]) { // 각 정점에 연결되어 있는 정점들 모두에 대해 확인 (리스트에도 for each문 적용 가능)
            if (!check[y]) { // 방문한 적이 없는 정점이라면
                dfs(y); // 해당 정점을 방문하고 그 정점에서 dfs 수행
            }
        }
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(start); // 처음으로 bfs 탐색을 시작할 정점을 큐에 추가
        check[start] = true; // 정점 방문 체크
        while (!queue.isEmpty()) { // 큐가 비면 모든 탐색을 완료한 것임
            int x = queue.remove(); // bfs 탐색을 수행할 현재 정점
            System.out.print(x + " "); // 정점 방문하면 출력
            for (int y : graph[x]) { // bfs를 수행하는 정점에 연결된 모든 정점들 확인
                if (!check[y]) { // 정점을 방문하지 않았다면
                    queue.add(y); // 정점 방문
                    check[y] = true; // 정점 방문 체크
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int v = sc.nextInt();
        int e = sc.nextInt();
        int start = sc.nextInt();
        graph = (ArrayList<Integer>[]) new ArrayList[v+1];
        for (int i=1;i<=v;i++) { // 각 배열의 원소(정점)에 대해 리스트 생성
            graph[i] = new ArrayList<Integer>();
        }
        // 각 배열의 원소는 각 정점에 해당한 정점들을 저장하는 리스트로 구성된다.
        for (int i=0;i<e;i++) {
            int temp1 = sc.nextInt();
            int temp2 = sc.nextInt();
            // 양 정점 모두에 add 해주어야 함 (undirected edge이기 때문)
            graph[temp1].add(temp2);
            graph[temp2].add(temp1);
        }
        // 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하는 조건을 충족하기 위한 정렬
        for (int i=1;i<=v;i++) Collections.sort(graph[i]);

        check = new boolean[v+1]; // dfs 수행 전에 정점 방문 여부 배열 초기화
        dfs(start);
        System.out.println();
        check = new boolean[v+1]; // bfs 수행 전에 정점 방문 여부 배열 초기화
        bfs(start);
        
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1260

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String temp;
        while ((temp = br.readLine()) != null) { // eof 처리
            int upper = 0;
            int lower = 0;
            int num = 0;
            int space = 0;
            for (int i=0;i<temp.length();i++){
                char c = temp.charAt(i);
                if (Character.isUpperCase(c)) upper+=1;
                else if (Character.isLowerCase(c)) lower+=1;
                else if (Character.isDigit(c)) num+=1;
                else if (Character.isSpaceChar(c)) space+=1;
            }
            System.out.printf("%d %d %d %d\n", lower, upper, num, space);
        }
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/10820

문제가 쉬워보이는데 오답률이 높길래 의아해서 풀었다가 나도 틀려서 당황한 문제

문제의 요구사항(조건)을 잘 확인해야 한다는 것을 느낄 수 있는 문제였다.

 

문제의 포인트는 알맞는 자료형을 사용하는 것

 

문제에서 주어지는 4개의 자연수의 각 최대 값은 1,000,000

A와 B를 이어붙인 수는 10,000,001,000,000이 되는데, 이는 int 자료형의 범위를 넘어간다.

그러므로 long 자료형을 사용해서 A, B와 C, D가 이어진 수와 그 합을 처리해줘야한다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String A = sc.next();
        String B = sc.next();
        String C = sc.next();
        String D = sc.next();

        String AB = A + B;
        String CD = C + D;

        long sum = Long.parseLong(AB) + Long.parseLong(CD);
        System.out.println(sum);
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/10824

해당 문제를 해결하기 위해

괄호에 의한 우선 순위 뿐만 아니라

사칙연산의 연산자들 간의 우선 순위도 고려해야 한다.

(괄호) > *, / (곱셈, 나눗셈)  > +, - (덧셈, 뺄셈)

 

# 알고리즘

모든 수식의 입력들 처리할 때까지 반복

1. 입력이 피연산자(알파벳)이면

바로 출력문에 append()

2. 입력이 열린 괄호 "("이면

바로 출력문에 append()

3. 입력이 + 또는 - 이면 

   1) 스택이 비어있다면 바로 push()

   2) 스택이 비어있지 않다면 계속 pop()하고 append()

      a) 스택이 비면 중지

      b) 열린 괄호 "("를 만나면 중지

      a 또는 b 과정 끝나면 입력된 연산자 push

4. 입력이 * 또는 / 이면

   1) 스택이 비어있다면 바로 push()

   2) 스택이 비어있지 않다면 계속 pop()하고 append()

      a) 스택이 비면 중지

      b) 열린 괄호 "("를 만나면 중지

      c) 우선순위 낮은 연산자 + 또는 - 를 만나면 중지

      a 또는 b 또는 c 과정 끝나면 입력된 연산자 push

5. 입력이 닫힌 괄호 ")"이면

스택에서 열린 괄호 "("가 나올 때까지 pop()하고 append()

 

모든 수식의 입력들을 처리한 후에

스택에 남아있는 연산자가 있다면 모두 pop()하고 append()

 

완성된 출력문 출력

 

아래는 문제를 해결하는 코드이다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        Scanner sc = new Scanner(System.in);
        String inorder = sc.next();
        String[] each = inorder.split("");
        StringBuilder sb = new StringBuilder();
        for (String x : each) {
            if (x.equals(")")) { // 닫힌 괄호가 들어오면 stack에 열린 괄호가 나올 때까지 pop하고 식에 append 해줌
                while (!stack.peek().equals("(")) {
                    sb.append(stack.pop());
                }
                stack.pop(); // "(" stack에서 제거
            } else if (x.equals("+") || x.equals("-")) {
                // +,-연산자가 들어올 때
                // stack이 비거나 열린 괄호가 나오거나
                // stack에 있는 우선 순위가 같은 +, - 연산자들은 append 해준다. (stack에는 열린 괄호와 연산자만 들어감)
                if (stack.empty()) {
                    // stack이 비어있으면
                    stack.push(x);
                } else {
                    // stack이 비어있지 않으면
                    while (!stack.empty()) {
                        // 열린 괄호를 만나면 pop과 append 중지
                        if (stack.peek().equals("(")) break;
                        // 아니라면 stack이 빌때까지 pop하고 append
                        sb.append(stack.pop());
                    }
                    stack.push(x);
                }
            } else if (x.equals("*") || x.equals("/")) {
                if (stack.empty()) {
                    // stack이 비어있으면
                    stack.push(x);
                } else {
                    // stack이 비어있지 않으면
                    while (!stack.empty()) {
                        // 열린 괄호를 만나면 pop과 append 중지
                        if (stack.peek().equals("(")) break;
                        // *, /보다 우선 순위가 낮은 +, - 연산자를 만나면 pop과 append 중지
                        else if (stack.peek().equals("+") || stack.peek().equals("-")) break;
                        // 아니라면 pop하고 append
                        sb.append(stack.pop());
                    }
                    stack.push(x);
                }
            } else if (x.equals("(")) {
                // 열린 괄호가 들어와도 stack에 넣어준다.
                stack.push(x);
            } else {
                // 피연산자가 들어오면 바로 append
                sb.append(x);
            }
        }
        // 반복문을 다 돌고도 stack에 남아있는 연산자가 있다면
        // -> 열림 괄호 없이 들어온 연산자가 있었을 경우 처리
        while (!stack.empty()) sb.append(stack.pop());

        System.out.print(sb);
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1918

# 트리 : 사이클이 없는 연결 그래프

1. 사이클이 없다

2. 연결되어 있다.

3. 그래프이다.

 

트리의 정점의 개수 = V,

트리의 간선의 개수 = V-1

(정점이 N개, 간선이 N개면 사이클이 1개만 존재하게 된다.)

 

cf) 트리라고 무조건 루트가 존재하는 것은 아니다.

루트는 정하기에 따라 달라진다.

 

# 트리에서의 부모(parent), 자식(child), 단말 노드(leaf node)

위 예시에서 

루트 = 노드 1로 정의했을 때,

노드 1의 자식 = 노드 2, 노드 3

노드 2의 부모 = 노드 1

(루트 노드(노드 1)의 부모는 존재하지 않는다.)

해당 트리의 단말 노드 = 노드 4, 5, 6, 7

노드 2의 형제(sibling) 노드 = 노드 3

 

# 깊이(Depth) : 루트로부터 노드의 거리

깊이는 정의마다 값이 다른데 일반적으로

root의 깊이를 0으로 설정하느냐, 1로 설정하느냐에 따라 달라진다

ex) 노드 4의 깊이 = (전자면) 2, (후자면) 3

 

# 높이(Height) : 단말 노드로부터의 거리

높이 역시 단말노드의 높이를 0으로 하느냐 1로 하느냐에 따라 달라진다.

 

# 조상(Ancestor), 후손(Descendent)

위 개념의 가장 큰 특징을 자신을 포함한다는 것이다.

ex) 노드 4의 조상 = 노드 4, 노드 2, 노드 1

노드 3의 후손 = 노드 3, 노드 6, 노드 7

 

 

# 이진 트리 (Binary Tree) : 자식을 최대 2개만 갖는 트리

(위 트리 예시는 이진 트리의 예시이기도 하다.)

 

# 포화 이진 트리 (Full Binary Tree) : 모든 단말 노드에서의 깊이가 동일한 이진 트리

포화 이진 트리의 전체 노드의 개수 = (2^h)-1

(h = 트리의 최대 높이)

위 트리 예시는 포화 이진 트리의 예시이기도 하다.

(단말 노드인 노드 4, 5, 6, 7의 깊이가 모드 3)

# 완전 이진 트리 (Complete Binary Tree) : 마지막 level(깊이)에서 오른쪽 leaf 노드의 일부가 없어진 형태

아래는 완전 이진 트리의 예시들이다.

위 그림의 오른쪽 예시에서 노드 7이 추가되어 있다면, 해당 트리는 완전 이진 트리가 아니다.

 

 

# 트리의 구현

- 그래프 구현 방식으로 구현할 수 있다. (트리도 그래프의 일종이기 때문)

- root가 존재한다면, 트리만의 저장 방식을 사용할 수 있다.

1) 부모만 저장하는 방식 - Union Find에 사용

-> 모든 노드들의 부모를 배열에 저장하는 방식으로 구현한다.

(모든 노드는 부모 노드가 1개이고, 부모가 없는 노드는 root 노드 하나만 존재하기 때문에 사용가능한 방식이다.)

위 방식은 부모를 찾는것은 수월하지만 O(1)

자식을 찾는데는 O(노드개수) 만큼의 시간이 걸린다.

2) 완전 이진 트리 - Heap, Segment Tree 구현에 사용한다.

완전 이진 트리의 경우에는 배열을 사용하여 트리를 구현하는 것이 가능하다.

3) 그냥(일반) 이진 트리 

구조체 또는 클래스를 사용하여 구현한다.

 

# 트리의 탐색

트리를 탐색하는데에도 DFS/BFS 방식을 사용할 수 있다.

(트리도 그래프의 일종이기 때문이다.)

1. DFS - 출력 순서 3가지 (노드 방문 처리 시점에 따른 차이)

   1) pre-order

   2) in-order

   3) post-order

 

 

1) pre-order : 그래프의 DFS 방문 순서와 동일하다는 특징이 있다.

순서 :

노드 방문 ->

왼쪽 자식를 루트로 하는 서브 트리의 pre-order 출력 -> 

오른쪽 자식를 루트로 하는 서브 트리의 pre-order 출력

ex) A B D E C F G

2) in-order : Binary Searcj Tree의 삭제를 구현하는데 inorder successor가 사용된다는 특징이 있다.

순서 : 

왼쪽 자식를 루트로 하는 서브 트리의 in-order 출력 ->

노드 방문 ->

오른쪽 자식를 루트로 하는 서브 트리의 in-order 출력

ex) D B E A F C G

3) post-order : 자식의 노드의 정보를 이용하여 현재 노드에 정보를 저장할 때 사용하기 용이하다. (중요)

순서 :

왼쪽 자식를 루트로 하는 서브 트리의 post-order 출력 ->

오른쪽 자식를 루트로 하는 서브 트리의 post-order 출력 ->

노드 방문

ex) D E B F G C A

 

cf) pre-order, post-order 방식은 이진 트리가 아니여도 사용 가능하다.

그러나 in-order 방식에서는 왼쪽, 오른쪽 자식을 구분하는 기준이 없기 때문에 현재 노드를 언제 방문해야하는지 정해지지 않기 때문에 사용할 수 없다.

 

2. BFS - 트리에서의 최단 경로 탐색에 사용될 수 있다.

트리는 사이클이 존재하지 않는 그래프이다.

사이클이 존재하지 않는 그래프에서는 임의의 두 정점 사이에는 경로가 1개만 존재한다.

그렇기 때문에 트리에서의 두 정점 사이의 경로는 1개뿐이므로 해당 경로가 곧 최단 경로이며

BFS 탐색을 통해 이를 구할 수 있다.

 

 

# 트리의 지름

트리에 존재하는 모든 경로 중 가장 긴 경로를 트리의 지름이라고 한다.

구하는 방법 2가지 

1. 탐색 2번으로 구하기

탐색 1 : 임의의 정점 s에서 모든 정점까지의 거리를 구하고 최장 거리에 위치하는 정점을 u로 둔다.

탐색 2 : 탐색 1로 구한 정점 u에서 모든 정점 까지의 거리를 구하고 최장 거리에 위치하는 정점을 v로 둔다.

이 때, 정점 u와 v 사이의 거리가 트리의 지름이 된다.

2. post-order 이용하기

루트 노드를 v라고 할때, 트리의 지름을 v를 통과하는 경우, 통과하지 않는 경우로 총 2가지가 존재한다.

v를 통과하는 경우 : 트리의 지름은 각각의 자식에서 단말 노드까지의 거리 중 가장 긴 경로 2개를 이용하여 만들 수 있다.

v를 통과하지 않는 경우 : 각각의 자식을 루트로 하는 서브트리에서 다시 트리의 지름을 구하는 것으로 지름을 구한다.

# 그래프의 탐색의 목적 

임의의 정점에서 시작하여 연결되어 있는 모든 정점을 1번씩 방문하는 것

(1번 이상 방문하면 그것은 DFS, BFS가 아님)

 

DFS, BFS는 어떤 순서로 정점을 방문하는 것인가에 차이를 갖는다.

 

# DFS (깊이 우선 탐색)

한 정점에서 시작하여 최대한 깊게 탐색(새로운 연결된 정점이 없을 때까지)하고

더 이상 깊게 탐색할 정점이 없으면 탐색해온 경로를 되돌아오면서 다시 탐색한다.

(새로운 정점 : 방문한 적이 없는 정점)

(사람 1명이 탐색을 하는 것이라고 비유할 수 있다.)

 

 

# BFS (너비 우선 탐색)

탐색을 시작한 정점부터 각 정점에서 방문 가능한(연결되어 있는) 모든 새로운 정점들을 1번에 확인하는 방식으로 탐색한다.

(사람이 연결된 정점의 수만큼 복제되면서 탐색하는 것이라고 비유할 수 있다.)

 

# DFS 구현

- Stack 사용 

더 이상 갈 수 있는 정점이 없을 때, 어디로 돌아가야 하는지 알려주는 역할을 한다.

탐색을 수행해오는 경로를 저장하는 기능을 Stack을 통해 구현한다고 할 수 있다.

cf) Stack이 비면, 모든 정점을 방문하고 탐색을 종료하는 시점이 된다.

- 배열 사용

각 정점에 대한 방문 여부를 저장하는 배열로 사용한다.

 

Stack의 자료 구조와 같은 구조로 작동하는 재귀함수의 특징을 이용하여

DFS는 재귀함수로 구현할 수 있다.

 

아래는 인접 행렬로 표현된 그래프에 대한 DFS를 재귀함수로 구현한 코드이다.

void dfs(int x) {
	check[x] = true; // 방문한 정점은 방문했다고 처리
	for (int i=1; i<=n; i++) { // 각 정점마다 모든 정점에 대해서 확인
		if (a[x][i] == 1 && check[i] == false) { // 두 정점 사이의 간선이 있고, 방문한 적 없는 정점이면
			dfs(i); // 탐색 수행
		}
	}
}

아래는 인접 리스트로 표현된 그래프에 대한 DFS 코드이다.

void dfs(int x) {
	check[x] = true;
	for(int i=0;i<a[x].size();i++) { // 각 정점마다 연결되어 있는 차수만큼 검사
		int y = a[x][i];
		if (check[y] == false) { // 방문한 적 없는 정점이라면
			dfs(y);
		}
	}
}

인접 행렬에 대한 DFS의 시간복잡도는 O(V^2)이고

(모든 정점들을 방문(O(V))하며, 각 방문하는 정점마다 모든 정점에 대한 조건 판별을 수행(*O(V))하기 때문)

인접 리스트에 대한 DFS의 시간복잡도는 O(V+E)이다

(모든 정점들을 방문하며(O(V)), 각 정점들의 차수만큼 조건 판별을 수행하는데, 각 정점들의 차수의 합은 곧 그래프의 간선의 개수와 같기 때문에 O(E)만큼의 시간이 추가로 걸린다고 할 수 있다.

이 때, 항상 V<=E가 성립하기 때문에 인접 리스트에 대한 DFS의 시간복잡도는 O(E)라고 할 수도 있다.

 

# BFS 구현

- Queue 사용

내가 방문해야할 정점들을 Queue를 사용해서 관리한다.

1. 특정 정점에서 방문할 수 있는 모든 정점들을 Queue에 넣는다.

   Queue에 들어가는 정점들은 방문한 것으로 처리되며, Queue에 들어가는 순간 처리된다.

   (Queue에서 나갈떄 처리되면 정점을 중복 방문할 가능성이 생기기 때문)

2. 방문하고 나간 정점은 Queue에서 pop() 해준다. 

3. Queue가 비면, 모든 정점들을 탐색하고 종료되는 시점이 된다.

- 배열 사용 

DFS와 같이 정점의 방문 여부를 기록하기 위한 배열이 필요하다.

 

BFS 알고리즘은 모든 간선들의 가중치가 1일때, 정점 간의 최단 거리를 구할 수 있다는 점에서 중요하다.

 

사실상 알고리즘이 수행하는 기능은 DFS와 같기 때문에 시간복잡도는 DFS와 동일하다.

(인접 행렬 : O(V^2), 인접 리스트 : O(E))

 

아래 코드는 인접 행렬로 구현된 그래프 대해 BFS를 구현한 코드이다.

queue<int> q;
check[1] = true; q.push(1);
while (!q.empty()) {
	int x = q.front(); q.pop();
	for (int i=1; i<=n; i++) {
		if (a[x][i] == 1 && check[i] == false) {
			check[i] = true;
			q.push(i);
		}
	}
}

 

아래 코드는 인접 리스트로 구현된 그래프에 대해 BFS를 구현한 코드이다.

queue<int> q;
check[1] = true; 
q.push(1);
while (!q.empty()) {
	int x = q.front(); q.pop();
	for (int i=0;i<a[x].size();i++) {
		int y = a[x][i];
		if (check[y] == false) {
			check[y] = true; q.push(y);
		}
	}
}

import java.util.*;
class Edge { // 간접 리스트를 위한 클래스
    int from, to;
    Edge(int from, int to) {
        this.from = from;
        this.to = to;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 사람 수
        int m = sc.nextInt(); // 관계 수

        boolean[][] a = new boolean[n][n]; // 인접 행렬 구현
        ArrayList<Integer>[] g = (ArrayList<Integer>[]) new ArrayList[n]; // 인접 리스트 구현
        ArrayList<Edge> edges = new ArrayList<Edge>(); // 간접 리스트 구현
        for (int i=0;i<n;i++) { // 인접 리스트는 각 정점마다 연결된 간선을 저장하므로
            g[i] = new ArrayList<>(); // 각 정점에 대해 리스트를 할당
        }
        for (int i=0; i<m; i++) {
            // 친구 관계는 양방향 관계이므로 양 방향으로 간선을 배정해야 한다.
            // 간선 리스트에 관계 저장
            int from = sc.nextInt();
            int to = sc.nextInt();
            edges.add(new Edge(from, to));
            edges.add(new Edge(to, from));
            // 인접 행렬에 관계 저장
            a[from][to] = a[to][from] = true;
            // 인접 리스트에 관계 저장
            g[from].add(to);
            g[to].add(from);
        }
        // 관계는 양방향이므로 입력된 관계*2를 해주어야 간선들의 총 개수가 된다.
        m *= 2;
        // 아래는 2개의 간선들에 대한 관계 파악해줌
        for (int i=0;i<m;i++) {
            for (int j=0;j<m;j++) {
                // 간선리스트 사용
                int A = edges.get(i).from;
                int B = edges.get(i).to;
                int C = edges.get(j).from;
                int D = edges.get(j).to;
                // B-C 친구 관계 여부를 간선 리스트로 확인
                // 서로 다른 두 간선이 연결되어 있는지 확인
                // A-B, C-D가 친구일 때 B-C가 친구인지 확인하는 것
                if (A == B || A == C || A == D || B == C || B == D || C == D) {
                    // A==B이면 edges i는 간선이 아님
                    // A==C 또는 A==D는 간선 i와 j가 정점 1개를 공유하는 간선이라는 것이다.
                    // (서로 다른 정점 4개를 연결하는 간선이 아닌 것임)
                    continue; // 위 조건에 해당하면 A-B, C-D가 친구일 때 B-C가 친구인지 확인할 수 없으므로 continue (정점 4개에 대한 관계가 아니게 되기 때문)
                }
                // 인접 행렬 사용
                if (!a[B][C]) continue; // A-B, C-D 에서 B-C 관계도 성립하지 않는다면 continue
                // 인접 리스트 사용
                for (int E : g[D]) { // D 정점과 연결된 정점들이 E로 들어온다.
                    if (A == E || B == E || C == E || D == E) continue;
                    // 연결된 정점이 A, B, C, D와 같다면 이는 중복되는 간선이 들어온 것이므로 continue
                    // (D-E 관계에 해당하지 않는다는 것)
                    // 위 조건들을 모두 통과하면 A-B-C-D-E 관계가 존재한다는 것이다.
                    System.out.println(1);
                    System.exit(0);
                }
            }
        }
        // 위 모든 쌍의 간선들을 확인했음에도 불구하고 모두 조건문에 걸려 continue 처리되어
        // 해당 코드에 다다르면 A-B-C-D-E 관계가 성립하지 않는다는 것이다.
        System.out.println(0);
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/13023