[코딩 테스트 스터디 - 5회차 ]

이진 트리 탐색 => 탐색을 효율적으로 할 수 있도록 트리로 구축 (자식 노드가 최대 2)

이진 탐색 트리 구축 방법 -> 특정한걸 찾는거

(탐색 트리의 대상) 데이터가 3 -> 4 -> 2 -> 8 -> 9 -> 7 -> 1 순서로 들어온다고 생각하고 이를 (이진탐색트리) 구축하시요.

이진 탐색 트리는 데이터 크기를 따져서 나열한다.
(왼쪽 자식노드에는 데이터가 작은것, 오른쪽 자식 노드에는 데이터가 큰것) 부모노드 기준!!!

기준 : 3 -> 4 -> 2 -> 8 -> 9 -> 7 -> 1
1. 최초의 데이터는 루트 노드가 된다. 3을 이진트리에 루트 노드에 추가

2. 삽입하는 데이터가 4이다. 루트(부모)노드 보다 크므로 오른쪽
   

이진트리 탐색은 시간 복잡도면에서 효율적이다.
시간 복잡도 문제는 정렬인 경우가 많다.

완전(균형) 이진 탐색 트리 => AVL 트리, 레드-블랙 트리 등으로 구분하여 부른다.

예상 대진표 문제

확률 구하는 문제인듯?? 토너먼트 최종이니 삼각형 모형으로 이진트리로 예측할 수 있다.

N = 1 2 3 4 5 6 7 8
A = 4
B = 7

import java.lang.reflect.Array;
import java.util.*;
class Main {
    public int solution(int n , int a, int b){
        int count = 0;
        while (a != b){
            a = (a/2) + (a % 2);   
            b = (b/2) + (b % 2);
            count++;
        }
        return count;
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n=kb.nextInt();
        int a=kb.nextInt();
        int b=kb.nextInt();
        System.out.print(T.solution(n, a, b));
    }
}

1. a/2 + a%2의 의미
   이 연산은 다음 라운드에서 참가자가 받을 번호를 계산하는 방법이다.

코딩테스트 연습 - 길찾기 게임

이 문제는 전위순회/ 후위순회한 결과를 반환하면된다.
이건 긴말 생략 계속 반복 학습하면서 트리 노드 구하는거 이해해야될것 같다..

import java.util.*;

class Main {
    int[][] result;
    int idx;
    public int[][] solution(int[][] nodeInfo) {
        //노드 배열을 초기화하고 각 노드를 입력받는다.
        Node[] node = new Node[nodeInfo.length];
        for (int i = 0; i < nodeInfo.length; i++) {
            node[i] = new Node(nodeInfo[i][0], nodeInfo[i][1], i+1, null, null);
        }
        // y값 큰 순서대로, y값 같다면 x 값 작은 순서대로 정렬
        // -> 이진트리의 형태 구성하는 문제이기에 y값(높이) 기준으로 내림차순
        // y값이 클수록 해당 노드는 트리에서 상위 레벨에 위치하기 위해
        Arrays.sort(node, new Comparator<Node>() {
            @Override
            public int compare(Node n1, Node n2) {
                if(n1.y == n2. y) return n1.x - n2.x;
                else{
                    return n2.y - n1.y;
                }
            }
        });

        // 트리를 만든다.
        Node root = node[0];
        for (int i = 1; i < node.length; i++) {
            insertNode(root, node[i]);
        }
        result = new int[2][nodeInfo.length];
        idx = 0;
        preorder(root); // 전위 순회
        idx =0;
        postorder(root); // 후위 순회
        return result;
    }

    public void insertNode(Node parent, Node child){
        if(parent.x > child.x){
            // 부모의 x 값이 자식의 x 값보다 크다면 왼쪽 서브트리로 삽입
            if(parent.left == null) parent.left = child;
            else insertNode(parent.left, child); // 왼쪽 서브트리로 재귀 호출
        }else{
            // 부모의 x 값이 자식의 x 값도 크지 않다면 오른쪽 서브트리로 삽입
            if(parent.right == null) parent.right = child;
            else insertNode(parent.right, child); // 오른쪽 서브트리로 재귀 호출
        }
    }
    public void  preorder(Node root){
        if(root != null){
            result[0][idx++] = root.value;
            preorder(root.left);
            preorder(root.right);
        }
    }

    public void postorder(Node root){
        if(root != null){
            postorder(root.left);
            postorder(root.right);
            result[1][idx++] = root.value;
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        int[][] nodeInfo = {
                {5,3},{11,5},{13,3}, {3,5}, {6,1},
                {1,3}, {8,6}, {7,2}, {2,2}
        };
        int[][] resultArrays = T.solution(nodeInfo);
        // solution 메소드 호출
        System.out.println(Arrays.deepToString(resultArrays));
    }
    public class Node{
        int x;
        int y;
        int value;
        Node left;
        Node right;

        public Node(int x, int y, int value, Node left, Node right){
            this.x = x;
            this.y = y;
            this.value = value;
            this.left = left;
            this.right= right;
        }
    }
}

BFS (너비 우선 탐색 => 가까운 노드부터 탐색하는 알고리즘)

(* DFS => 최대한 멀리 있는 노드를 우선으로 탐색하는 방법)

1. 탐색 시작 노드를 큐에 삽입 (비어있는 큐 생성!!!)
2. 큐에서 노드를 꺼내서 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입
3. 위의 2번 과정을 반복적으로 더 이상 수행할 수 없을 때까지 반복한다.
   너비는 인접 모드 다 넣는다!!!
   
   
   

import java.util.ArrayDeque;
import java.util.ArrayList;

public class Solution {
    private static ArrayList<Integer>[] addList;
    private static boolean[] visited;
    private static  ArrayList<Integer>  answer;

    public static void main(String[] args) {

    }
    private static int[] solution(int[][] graph, int start, int n){
    addList = new ArrayList[n + 1];
        for (int i = 0; i < addList.length; i++) {
            addList[i] = new ArrayList<>();
        }
        for (int[] edge: graph) {
            addList[edge[0]].add(edge[1]);
        }

        visited = new boolean[n +1];
        answer = new ArrayList<>();
        bfs(start);

        return  answer.stream().mapToInt(Integer::intValue).toArray();
    }
    private static void bfs(int start){
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        visited[start] = true;
        
        while (!queue.isEmpty()){
            int now = queue.poll();
            answer.add(now);

            for (int next: addList[now] ){
                if(!visited[next]){
                    queue.add(next);
                    visited[next] = true;
                }
            }
        }
    }
}