[Java] 기본 문법 정리 - 추가

✅ 19. 트리 (Tree, Binary Tree, Binary Search Tree)

트리는 계층 구조를 가지는 자료구조로, 탐색과 정렬에 자주 사용됨.
대표적인 트리 구조는 이진 트리(Binary Tree), 이진 탐색 트리(BST).

---

📍 1) 이진 트리 (Binary Tree)

• 각 노드가 최대 2개의 자식을 가짐 (왼쪽, 오른쪽)
• DFS, BFS 탐색에 사용됨

이진 트리 기본 클래스

class Node {
    int data;
    Node left, right;

    public Node(int data) {
        this.data = data;
        this.left = this.right = null;
    }
}

public class BinaryTreeExample {
    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        
        System.out.println("루트 값: " + root.data); // 1
        System.out.println("왼쪽 자식: " + root.left.data); // 2
    }
}

---

📍 2) 이진 탐색 트리 (Binary Search Tree, BST)

• 모든 왼쪽 자식 < 부모 < 모든 오른쪽 자식 규칙을 가짐
• 탐색, 삽입, 삭제 연산이 평균 O(log N)
• 중위 순회하면 오름차순 정렬된 결과 출력

이진 탐색 트리 삽입 & 탐색

class BST {
    Node root;

    public void insert(int key) {
        root = insertRec(root, key);
    }

    private Node insertRec(Node root, int key) {
        if (root == null) return new Node(key);

        if (key < root.data) root.left = insertRec(root.left, key);
        else if (key > root.data) root.right = insertRec(root.right, key);

        return root;
    }

    public boolean search(int key) {
        return searchRec(root, key) != null;
    }

    private Node searchRec(Node root, int key) {
        if (root == null || root.data == key) return root;
        return key < root.data ? searchRec(root.left, key) : searchRec(root.right, key);
    }
}

public class BSTExample {
    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(50);
        tree.insert(30);
        tree.insert(70);
        tree.insert(20);
        tree.insert(40);

        System.out.println("70 존재? " + tree.search(70)); // true
        System.out.println("25 존재? " + tree.search(25)); // false
    }
}

📌 이진 탐색 트리(BST)는 O(log N)의 탐색 속도를 보장하지만, 불균형할 경우 O(N)까지 증가할 수 있음!
📌 균형 트리(Red-Black Tree, AVL Tree)를 사용하면 최적의 탐색 성능 유지 가능!

---

✅ 20. 힙 (Heap)

힙은 최댓값 또는 최솟값을 빠르게 찾기 위한 자료구조.
자바에서는 우선순위 큐(PriorityQueue)가 힙을 구현한 클래스.

---

📍 1) 최소 힙 (Min Heap)

• 가장 작은 값이 항상 루트 노드에 위치
• 자바의 PriorityQueue는 기본적으로 최소 힙

최소 힙 구현 (PriorityQueue)

import java.util.PriorityQueue;

public class MinHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.offer(10);
        pq.offer(20);
        pq.offer(5);

        System.out.println(pq.poll()); // 5 (최소값)
        System.out.println(pq.poll()); // 10
    }
}

---

📍 2) 최대 힙 (Max Heap)

• 가장 큰 값이 루트 노드에 위치
• 자바에서는 PriorityQueue를 Collections.reverseOrder()로 설정

최대 힙 구현

import java.util.Collections;
import java.util.PriorityQueue;

public class MaxHeapExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        maxHeap.offer(10);
        maxHeap.offer(20);
        maxHeap.offer(5);

        System.out.println(maxHeap.poll()); // 20 (최대값)
        System.out.println(maxHeap.poll()); // 10
    }
}

📌 힙은 "정렬된 데이터를 유지"하는 것이 아니라, "최댓값 또는 최솟값을 빠르게 찾는" 것이 목적!

---

✅ 21. 그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘은 각 단계에서 가장 최적인 선택을 하는 방식.
대표적인 예시: 동전 거스름돈 문제, 회의실 배정 문제

---

📍 1) 예제: 동전 거스름돈 문제

• 가장 큰 단위의 동전부터 거슬러 주면 최소 개수로 해결 가능

public class GreedyCoinChange {
    public static void main(String[] args) {
        int[] coins = {500, 100, 50, 10}; // 큰 동전부터 정렬
        int amount = 1260;
        int count = 0;

        for (int coin : coins) {
            count += amount / coin;
            amount %= coin;
        }

        System.out.println("최소 동전 개수: " + count); // 6
    }
}

---

✅ 22. 백트래킹 (Backtracking)

백트래킹은 모든 경우를 탐색하면서 조건이 맞지 않으면 가지치기(Pruning)하는 방식.
대표적인 문제: N-Queen, 순열(Next Permutation), 부분집합

---

📍 1) 예제: N-Queen 문제

public class NQueen {
    static int N = 4;
    static int[] board = new int[N];
    static int count = 0;

    public static void main(String[] args) {
        solve(0);
        System.out.println("N-Queen 해답 개수: " + count);
    }

    static void solve(int row) {
        if (row == N) {
            count++;
            return;
        }

        for (int col = 0; col < N; col++) {
            board[row] = col;
            if (isSafe(row)) solve(row + 1);
        }
    }

    static boolean isSafe(int row) {
        for (int i = 0; i < row; i++) {
            if (board[i] == board[row] || Math.abs(board[i] - board[row]) == row - i) return false;
        }
        return true;
    }
}

📌 백트래킹을 사용하면 "불가능한 경로를 미리 차단"해서 탐색 속도를 높일 수 있음!

---

🎯 최종 정리

자바 코딩 테스트 필수 문법! 🚀
✅ 기본 문법 (자료형, 연산자, 조건문, 반복문)
✅ 자료 구조 (List, Set, Map, Stack, Queue, Deque, PriorityQueue)
✅ 탐색 & 정렬 (Binary Search, DFS, BFS, Sorting)
✅ 트리 & 그래프 (Tree, BST, Heap, Graph)
✅ 알고리즘 (DP, 그리디, 백트래킹)