[Java] 코딩 테스트 대비 유형 정리

Data Structure

• 배열과 리스트
  • 사용 단서 : 연속 공간에 값을 채울 경우

// 배열
public class ArrayExample {
    public static void main(String[] args) {
        int[] array = new int[3]; // 크기가 3인 배열 생성
        array[0] = 1; // 첫 번째 요소에 값 1 할당
        array[1] = 2; // 두 번째 요소에 값 2 할당
        array[2] = 3; // 세 번째 요소에 값 3 할당
        
        // 배열 값 출력
        System.out.println("배열의 값들:");
        for (int i = 0; i < array.length; i++) {
            System.out.println("array[" + i + "] = " + array[i]);
        }

        // 값 변경 (삭제는 배열에서 직접 불가능)
        array[1] = 0; // 두 번째 값을 0으로 초기화하여 "삭제"처럼 동작
        System.out.println("\n두 번째 값을 0으로 초기화 후:");
        for (int i = 0; i < array.length; i++) {
            System.out.println("array[" + i + "] = " + array[i]);
        }
    }
}

/*
출력 결과:
배열의 값들:
array[0] = 1
array[1] = 2
array[2] = 3

두 번째 값을 0으로 초기화 후:
array[0] = 1
array[1] = 0
array[2] = 3
*/

// 리스트
public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(); // 빈 리스트 생성

        // 리스트에 값 추가
        list.add(1); // 첫 번째 값 추가
        list.add(2); // 두 번째 값 추가
        list.add(3); // 세 번째 값 추가
        
        // 리스트 값 출력
        System.out.println("리스트의 값들:");
        for (int i = 0; i < list.size(); i++) {
            System.out.println("list[" + i + "] = " + list.get(i));
        }

        // 값 제거
        list.remove(1); // 두 번째 값을 삭제 (인덱스 1)

        System.out.println("\n두 번째 값을 삭제 후:");
        for (int i = 0; i < list.size(); i++) {
            System.out.println("list[" + i + "] = " + list.get(i));
        }
    }
}

/*
출력 결과:
리스트의 값들:
list[0] = 1
list[1] = 2
list[2] = 3

두 번째 값을 삭제 후:
list[0] = 1
list[1] = 3
*/

• 해시 맵
  • 사용 단서 : key-value 쌍으로 저장하는 경우

// 해시 맵
public class HashMapExample {
    public static void main(String[] args) {
        // 해시맵 생성 (키는 Integer, 값은 String)
        HashMap<Integer, String> map = new HashMap<>();

        // 값 추가
        map.put(1, "사과");   // 키 1에 "사과" 값 추가
        map.put(2, "바나나"); // 키 2에 "바나나" 값 추가
        map.put(3, "체리");   // 키 3에 "체리" 값 추가

        // 값 출력
        System.out.println("해시맵의 값들:");
        for (Integer key : map.keySet()) {
            System.out.println("키: " + key + ", 값: " + map.get(key));
        }

        // 특정 값 가져오기 (키 2에 해당하는 값)
        String value = map.get(2); 
        System.out.println("\n키 2에 해당하는 값: " + value); // "바나나" 출력

        // 값 삭제 (키 2에 해당하는 값 제거)
        map.remove(2);

        // 값 삭제 후 출력
        System.out.println("\n키 2 제거 후 해시맵의 값들:");
        for (Integer key : map.keySet()) {
            System.out.println("키: " + key + ", 값: " + map.get(key));
        }

        // 값 업데이트 (키 1에 새로운 값 할당)
        map.put(1, "포도");

        // 값 업데이트 후 출력
        System.out.println("\n키 1에 값을 업데이트한 후:");
        for (Integer key : map.keySet()) {
            System.out.println("키: " + key + ", 값: " + map.get(key));
        }
    }
}

/*
출력 결과:
해시맵의 값들:
키: 1, 값: 사과
키: 2, 값: 바나나
키: 3, 값: 체리

키 2에 해당하는 값: 바나나

키 2 제거 후 해시맵의 값들:
키: 1, 값: 사과
키: 3, 값: 체리

키 1에 값을 업데이트한 후:
키: 1, 값: 포도
키: 3, 값: 체리
*/

• 스택과 큐
  
  • 사용 단서 : 스택은 후입 선출 / DFS 탐색, 큐는 선입 선출 / BFS 탐색하는 경우

// 스택
public class StackExample {
    public static void main(String[] args) {
        // 스택 생성
        Stack<Integer> stack = new Stack<>();

        // 스택에 값 추가 (push)
        stack.push(1); // 1 추가
        stack.push(2); // 2 추가
        stack.push(3); // 3 추가

        // 스택의 값 출력
        System.out.println("스택의 값들:");
        for (Integer value : stack) {
            System.out.println(value);
        }

        // 스택에서 값 제거 (pop)
        int removedValue = stack.pop(); // 마지막에 추가된 값 3 제거
        System.out.println("\n제거된 값: " + removedValue);

        // 값 제거 후 스택 출력
        System.out.println("\n스택에서 값 제거 후:");
        for (Integer value : stack) {
            System.out.println(value);
        }

        // 스택의 마지막 값 확인 (peek)
        int topValue = stack.peek();
        System.out.println("\n스택의 마지막 값 (peek): " + topValue);
    }
}

/*
출력 결과:
스택의 값들:
1
2
3

제거된 값: 3

스택에서 값 제거 후:
1
2

스택의 마지막 값 (peek): 2
*/

// 큐
public class QueueExample {
    public static void main(String[] args) {
        // 큐 생성
        Queue<Integer> queue = new LinkedList<>();

        // 큐에 값 추가 (offer)
        queue.offer(1); // 1 추가
        queue.offer(2); // 2 추가
        queue.offer(3); // 3 추가

        // 큐의 값 출력
        System.out.println("큐의 값들:");
        for (Integer value : queue) {
            System.out.println(value);
        }

        // 큐에서 값 제거 (poll)
        int removedValue = queue.poll(); // 첫 번째로 추가된 값 1 제거
        System.out.println("\n제거된 값: " + removedValue);

        // 값 제거 후 큐 출력
        System.out.println("\n큐에서 값 제거 후:");
        for (Integer value : queue) {
            System.out.println(value);
        }

        // 큐의 첫 번째 값 확인 (peek)
        int frontValue = queue.peek();
        System.out.println("\n큐의 첫 번째 값 (peek): " + frontValue);
    }
}

/*
출력 결과:
큐의 값들:
1
2
3

제거된 값: 1

큐에서 값 제거 후:
2
3

큐의 첫 번째 값 (peek): 2
*/

• 힙
  • 사용 단서 : 우선순위를 활용한 다익스트라 구현

// 최소 힙
public class PriorityQueueExample {
    public static void main(String[] args) {
        // 우선순위 큐 생성 (기본적으로 최소 힙으로 동작, 최대 힙의 경우 Comparator.reverseOrder() 사용)
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 우선순위 큐에 값 추가
        pq.offer(5);
        pq.offer(1);
        pq.offer(3);
        pq.offer(7);
        pq.offer(2);

        // 우선순위 큐에서 값 출력 및 제거
        System.out.println("우선순위 큐에서 값을 하나씩 꺼냅니다 (오름차순):");
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 가장 작은 값부터 출력
        }
    }
}

/*
출력 결과:
우선순위 큐에서 값을 하나씩 꺼냅니다 (오름차순):
1
2
3
5
7
*/

Prefix Sum

• 구간 합
  • 사용 단서 : 합 배열을 이용하여 시간 복잡도를 줄일 경우

// 구간 합
public class PrefixSumExample {
    public static void main(String[] args) {
        // 초기 배열
        int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

        // 누적 합 배열 생성
        int[] prefixSum = new int[array.length + 1];
        for (int i = 1; i <= array.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + array[i - 1];
        }

        // 특정 구간의 합 계산
        int start = 2; // 구간 시작 인덱스 (0 기반)
        int end = 5;   // 구간 끝 인덱스 (0 기반)

        int rangeSum = prefixSum[end + 1] - prefixSum[start];
        
        // 결과 출력
        System.out.println("구간 [" + start + ", " + end + "]의 합: " + rangeSum);
    }
}

/*
출력 결과:
구간 [2, 5]의 합: 18
*/

Two Pointer

• 투 포인터
  • 사용 단서 : 2개의 포인터를 이동하여 합을 구하거나, 연속된 수의 범위를 찾을 경우,           
                         반복문 2개로 풀이할 경우 시간 초과가 발생할 경우

// 투 포인터
public class TwoPointerExample {
    public static void main(String[] args) {
        // 정렬된 배열
        int[] array = {1, 2, 3, 5, 7, 10, 12};
        int target = 9; // 목표 합

        // 투 포인터 초기화
        Arrays.sort(array);
        int left = 0;                 // 배열의 첫 번째 요소
        int right = array.length - 1; // 배열의 마지막 요소

        // 두 포인터를 사용한 탐색
        while (left < right) {
            int sum = array[left] + array[right];

            if (sum == target) {
                // 목표 합을 찾았을 때
                System.out.println("두 수: " + array[left] + " + " + array[right] + " = " + target);
                break;
            } else if (sum < target) {
                // 합이 목표 값보다 작으면 왼쪽 포인터를 오른쪽으로 이동
                left++;
            } else {
                // 합이 목표 값보다 크면 오른쪽 포인터를 왼쪽으로 이동
                right--;
            }
        }
    }
}

/*
출력 결과:
두 수: 2 + 7 = 9
*/

• 슬라이딩 윈도우
  • 사용 단서 : 2개의 포인터로 범위를 지정하여 다음 범위를 유지한 채로 이동하면서 찾을 경우

// 슬라이딩 윈도우
public class SlidingWindowExample {
    public static void main(String[] args) {
        int[] array = {2, 1, 5, 2, 3, 2};
        int targetSum = 7;
        int minLength = findMinSubArray(array, targetSum);

        // 결과 출력
        System.out.println("합이 " + targetSum + " 이상인 최소 길이의 부분 배열: " + minLength);
    }

    public static int findMinSubArray(int[] array, int S) {
        int windowSum = 0;  // 현재 윈도우 내의 합
        int minLength = Integer.MAX_VALUE;  // 최소 길이 초기화
        int windowStart = 0;  // 윈도우의 시작점

        for (int windowEnd = 0; windowEnd < array.length; windowEnd++) {
            windowSum += array[windowEnd];  // 윈도우에 새로운 값 추가

            // 현재 윈도우 합이 S 이상인 경우
            while (windowSum >= S) {
                minLength = Math.min(minLength, windowEnd - windowStart + 1);  // 최소 길이 업데이트
                windowSum -= array[windowStart];  // 윈도우 시작점 이동
                windowStart++;
            }
        }

        // 결과 반환 (최소 길이를 찾지 못한 경우 0 반환)
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}

/*
출력 결과:
합이 7 이상인 최소 길이의 부분 배열: 2
*/

Graph Traversal

• 깊이 우선 탐색 (DFS)
  • 사용 단서 : 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색하며 그래프를 순회하는 경우

// 깊이 우선 탐색
     0
    / \
   1   2
  / \
 3   4
 
public class DepthFirstSearchExample {
    // 그래프를 인접 리스트로 표현
    private static List<List<Integer>> graph = new ArrayList<>();
    private static boolean[] visited;

    public static void main(String[] args) {
        // 그래프 초기화
        int numberOfNodes = 5;
        visited = new boolean[numberOfNodes];
        
        for (int i = 0; i < numberOfNodes; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프의 각 노드 연결 (간선 추가)
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(1, 3);
        addEdge(1, 4);

        System.out.println("DFS 탐색 순서:");
        dfs(0); // 0번 노드부터 탐색 시작
    }

    // 간선 추가 함수
    public static void addEdge(int node1, int node2) {
        graph.get(node1).add(node2);
        graph.get(node2).add(node1); // 무방향 그래프이므로 양방향 연결
    }

    // DFS 함수
    public static void dfs(int node) {
        visited[node] = true; // 현재 노드를 방문 처리
        System.out.print(node + " "); // 방문한 노드 출력

        // 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
    }
}

/*
출력 결과:
DFS 탐색 순서:
0 1 3 4 2
*/

• 너비 우선 탐색 (BFS)
  
  • 사용 단서 : 시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 탐색하며 그래프를 순회하는 경우

// 너비 우선 탐색
     0
    / \
   1   2
  / \
 3   4
 
public class BreadthFirstSearchExample {
    // 그래프를 인접 리스트로 표현
    private static List<List<Integer>> graph = new ArrayList<>();
    private static boolean[] visited;

    public static void main(String[] args) {
        // 그래프 초기화
        int numberOfNodes = 5;
        visited = new boolean[numberOfNodes];
        
        for (int i = 0; i < numberOfNodes; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프의 각 노드 연결 (간선 추가)
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(1, 3);
        addEdge(1, 4);

        System.out.println("BFS 탐색 순서:");
        bfs(0); // 0번 노드부터 탐색 시작
    }

    // 간선 추가 함수
    public static void addEdge(int node1, int node2) {
        graph.get(node1).add(node2);
        graph.get(node2).add(node1); // 무방향 그래프이므로 양방향 연결
    }

    // BFS 함수
    public static void bfs(int startNode) {
        Queue<Integer> queue = new LinkedList<>(); // BFS에 사용할 큐
        visited[startNode] = true; // 시작 노드를 방문 처리
        queue.offer(startNode); // 시작 노드를 큐에 추가

        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            int node = queue.poll(); // 큐에서 노드를 꺼냄
            System.out.print(node + " "); // 방문한 노드 출력

            // 현재 노드에 연결된 모든 인접 노드를 확인
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true; // 방문하지 않은 노드를 방문 처리
                    queue.offer(neighbor); // 큐에 인접 노드 추가
                }
            }
        }
    }
}

/*
출력 결과:
BFS 탐색 순서:
0 1 2 3 4
*/

• 집합 (Union, Find)
  • 사용 단서 : 여러 노드가 있을 때 특정 2개의 노드가 같은 집합에 속하는지 확인하고 연결해 1개의 집합으로 묶는 경우

// 집합 (유니온 파인드)
public class UnionFindExample {
    private int[] parent; // 부모 노드

    public UnionFindExample(int size) {
        parent = new int[size];

        // 각 노드의 부모를 자기 자신으로 초기화 (즉, 모든 노드는 독립된 집합에 속함)
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    // Find 연산: 경로 압축을 사용하여 부모를 찾는 함수
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 경로 압축
        }
        return parent[x];
    }

    // Union 연산: 두 집합을 합치는 함수 (랭크를 고려하여 더 효율적으로 합침)
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            parent[rootX] = rootY; // x의 루트 부모를 y의 루트 부모로 변경
        }
    }

    // 두 원소가 같은 집합에 속하는지 확인하는 함수
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }

    public static void main(String[] args) {
        // 5개의 원소가 있는 유니온 파인드 집합 생성
        UnionFindExample uf = new UnionFindExample(5);

        // 원소 0과 1을 같은 집합으로 합침
        uf.union(0, 1);
        System.out.println("0과 1이 같은 집합에 속하는가? " + uf.isConnected(0, 1)); // true 출력

        // 원소 1과 2를 같은 집합으로 합침
        uf.union(1, 2);
        System.out.println("0과 2가 같은 집합에 속하는가? " + uf.isConnected(0, 2)); // true 출력

        // 원소 3과 4는 아직 합치지 않았으므로 false
        System.out.println("3과 4가 같은 집합에 속하는가? " + uf.isConnected(3, 4)); // false 출력

        // 원소 2와 3을 같은 집합으로 합침
        uf.union(2, 3);
        System.out.println("0과 3이 같은 집합에 속하는가? " + uf.isConnected(0, 3)); // true 출력
    }
}

• 이진 탐색
  • 사용 단서 : 순차적인 배열 탐색으로는 시간 초과가 발생하는 경우

// 이진 탐색
public class BinarySearchExample {
    
    // 이진 탐색 함수: target이 배열에 있으면 인덱스를 반환, 없으면 -1 반환
    public static int binarySearch(int[] array, int target) {
        int left = 0;               // 탐색 범위의 시작
        int right = array.length - 1; // 탐색 범위의 끝

        while (left <= right) {
            int mid = left + (right - left) / 2; // 중간 인덱스 계산

            if (array[mid] == target) {
                return mid; // target을 찾으면 해당 인덱스 반환
            } else if (array[mid] < target) {
                left = mid + 1; // target이 중간 값보다 크면 오른쪽 부분 탐색
            } else {
                right = mid - 1; // target이 중간 값보다 작으면 왼쪽 부분 탐색
            }
        }
        return -1; // target을 찾지 못한 경우
    }

    public static void main(String[] args) {
        // 정렬된 배열
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15};

        // 찾고자 하는 값
        int target = 7;

        // 이진 탐색 수행
        int result = binarySearch(sortedArray, target);

        // 결과 출력
        if (result != -1) {
            System.out.println("값 " + target + "은 배열의 인덱스 " + result + "에 있습니다.");
        } else {
            System.out.println("값 " + target + "은 배열에 없습니다.");
        }
    }
}

/*
값 7은 배열의 인덱스 3에 있습니다.
*/

• 위상 정렬
  • 사용 단서 : 사이클이 없는 방향 그래프에서 노드 순서를 찾는 경우

// 위상 정렬
public class TopologicalSortExample {
    
    // 위상 정렬 함수
    public static List<Integer> topologicalSort(int numVertices, List<List<Integer>> adjList) {
        List<Integer> result = new ArrayList<>();
        int[] inDegree = new int[numVertices];
        Queue<Integer> queue = new LinkedList<>();

        // 모든 노드의 진입 차수 계산
        for (int u = 0; u < numVertices; u++) {
            for (int v : adjList.get(u)) {
                inDegree[v]++;
            }
        }

        // 진입 차수가 0인 노드를 큐에 추가
        for (int i = 0; i < numVertices; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 큐에서 노드를 꺼내며 위상 정렬
        while (!queue.isEmpty()) {
            int u = queue.poll();
            result.add(u);

            for (int v : adjList.get(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int numVertices = 6; // 정점의 개수

        // 그래프의 인접 리스트 표현
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numVertices; i++) {
            adjList.add(new ArrayList<>());
        }
        
        // 간선 추가: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3, 2 -> 4, 4 -> 5
        adjList.get(0).add(1);
        adjList.get(0).add(2);
        adjList.get(1).add(3);
        adjList.get(2).add(3);
        adjList.get(2).add(4);
        adjList.get(4).add(5);

        // 위상 정렬 수행
        List<Integer> sortedOrder = topologicalSort(numVertices, adjList);

        // 결과 출력
        System.out.println("위상 정렬 결과:");
        for (int vertex : sortedOrder) {
            System.out.print(vertex + " ");
        }
    }
}

/*
위상 정렬 결과:
0 1 2 4 3 5 
*/

• 다익스트라
  • 사용 단서 : 그래프에서 출발 노드와 모든 노드 간의 최단 경로를 구하는 경우 (엣지가 모두 양수)

// 다익스트라
public class DijkstraExample {
    
    // 다익스트라 알고리즘 함수
    public static int[] dijkstra(int numVertices, List<List<int[]>> adjList, int start) {
        int[] dist = new int[numVertices];
        boolean[] visited = new boolean[numVertices];
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

        // 초기화
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        pq.offer(new int[]{start, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];
            int currentDist = current[1];

            if (visited[u]) continue;
            visited[u] = true;

            // 인접 정점에 대한 거리 업데이트
            for (int[] neighbor : adjList.get(u)) {
                int v = neighbor[0];
                int weight = neighbor[1];
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new int[]{v, dist[v]});
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int numVertices = 5; // 정점의 개수

        // 그래프의 인접 리스트 표현 (각 정점의 인접 정점과 간선의 가중치)
        List<List<int[]>> adjList = new ArrayList<>();
        for (int i = 0; i < numVertices; i++) {
            adjList.add(new ArrayList<>());
        }
        
        // 간선 추가: u -> (v, weight)
        adjList.get(0).add(new int[]{1, 10});
        adjList.get(0).add(new int[]{2, 3});
        adjList.get(1).add(new int[]{2, 1});
        adjList.get(1).add(new int[]{3, 2});
        adjList.get(2).add(new int[]{1, 4});
        adjList.get(2).add(new int[]{3, 8});
        adjList.get(2).add(new int[]{4, 2});
        adjList.get(3).add(new int[]{4, 7});
        adjList.get(4).add(new int[]{3, 9});

        int start = 0; // 출발 정점

        // 다익스트라 알고리즘 수행
        int[] distances = dijkstra(numVertices, adjList, start);

        // 결과 출력
        System.out.println("출발 정점 " + start + "에서 각 정점까지의 최단 거리:");
        for (int i = 0; i < numVertices; i++) {
            System.out.println("정점 " + i + ": " + (distances[i] == Integer.MAX_VALUE ? "무한" : distances[i]));
        }
    }
}

/*
출발 정점 0에서 각 정점까지의 최단 거리:
정점 0: 0
정점 1: 7
정점 2: 3
정점 3: 15
정점 4: 5
*/

• 벨만-포드
  • 사용 단서 : 그래프에서 출발 노드와 모든 노드 간의 최단 경로를 구하는 경우 (엣지가 음수여도 수행할 수 있음)

// 벨만 포드
public class BellmanFordExample {
    
    // 벨만-포드 알고리즘 함수
    public static int[] bellmanFord(int numVertices, List<int[]> edges, int start) {
        int[] dist = new int[numVertices];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        // Relaxation 과정: 모든 간선에 대해 (numVertices - 1)번 반복
        for (int i = 1; i < numVertices; i++) {
            for (int[] edge : edges) {
                int u = edge[0];
                int v = edge[1];
                int weight = edge[2];
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
            }
        }

        // 음수 사이클 감지
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                System.out.println("그래프에 음수 사이클이 있습니다.");
                return null;
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int numVertices = 5; // 정점의 개수

        // 간선 추가: (u, v, weight)
        List<int[]> edges = new ArrayList<>();
        edges.add(new int[]{0, 1, 10});
        edges.add(new int[]{0, 2, 3});
        edges.add(new int[]{1, 2, 1});
        edges.add(new int[]{1, 3, 2});
        edges.add(new int[]{2, 1, 4});
        edges.add(new int[]{2, 3, 8});
        edges.add(new int[]{2, 4, 2});
        edges.add(new int[]{4, 3, 7});
        edges.add(new int[]{3, 4, -9}); // 음수 가중치 간선

        int start = 0; // 출발 정점

        // 벨만-포드 알고리즘 수행
        int[] distances = bellmanFord(numVertices, edges, start);

        // 결과 출력
        if (distances != null) {
            System.out.println("출발 정점 " + start + "에서 각 정점까지의 최단 거리:");
            for (int i = 0; i < numVertices; i++) {
                System.out.println("정점 " + i + ": " + (distances[i] == Integer.MAX_VALUE ? "무한" : distances[i]));
            }
        }
    }
}

/*
출발 정점 0에서 각 정점까지의 최단 거리:
정점 0: 0
정점 1: 7
정점 2: 3
정점 3: -2
정점 4: 5
*/

• 플로이드-워셜
  • 사용 단서 : 그래프에서 모든 노드 간에 최단 경로를 구하는 경우

// 플로이드 워셜
public class FloydWarshallExample {
    
    // 플로이드-워셜 알고리즘 함수
    public static void floydWarshall(int numVertices, int[][] graph) {
        // 거리 배열 초기화
        int[][] dist = new int[numVertices][numVertices];
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                } else if (graph[i][j] != 0) {
                    dist[i][j] = graph[i][j];
                } else {
                    dist[i][j] = Integer.MAX_VALUE; // 무한대
                }
            }
        }

        // 플로이드-워셜 알고리즘 수행
        for (int k = 0; k < numVertices; k++) {
            for (int i = 0; i < numVertices; i++) {
                for (int j = 0; j < numVertices; j++) {
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }

        // 결과 출력
        System.out.println("모든 정점 쌍 사이의 최단 거리:");
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                if (dist[i][j] == Integer.MAX_VALUE) {
                    System.out.print("무한\t");
                } else {
                    System.out.print(dist[i][j] + "\t");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int numVertices = 4; // 정점의 개수

        // 그래프의 인접 행렬 표현 (가중치가 없는 경우 0으로 표현, 무한대는 Integer.MAX_VALUE로 표현)
        int[][] graph = {
            {0, 3, 0, 7},
            {8, 0, 2, 0},
            {5, 0, 0, 1},
            {2, 0, 0, 0}
        };

        // 플로이드-워셜 알고리즘 수행
        floydWarshall(numVertices, graph);
    }
}

/*
모든 정점 쌍 사이의 최단 거리:
0	3	5	6	
8	0	2	3	
5	8	0	1	
2	5	7	0	
*/

• 최소 신장 트리
  
  • 사용 단서 : 그래프에서 모든 노드를 연결할 때 사용된 엣지들의 가중치(비용)의 합을 최소로 구하는 경우

// 최소 신장 트리 (크루스칼)
public class KruskalExample {
    // Union-Find 클래스
    static class UnionFind {
        private int[] parent;

        public UnionFind(int size) {
            parent = new int[size];
            for (int i = 0; i < size; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]); // 경로 압축
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);

            if (rootX != rootY) {
                parent[rootX] = rootY;
            }
        }
    }

    public static void kruskal(int numVertices, int[][] edges) {
        // 간선을 가중치 기준으로 오름차순 정렬
        Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));

        UnionFind uf = new UnionFind(numVertices);
        List<int[]> mst = new ArrayList<>();

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int weight = edge[2];

            if (uf.find(u) != uf.find(v)) {
                uf.union(u, v);
                mst.add(edge);
            }
        }

        // 결과 출력
        System.out.println("최소 신장 트리의 간선들:");
        int totalWeight = 0;
        for (int[] edge : mst) {
            System.out.println("정점 " + edge[0] + " - 정점 " + edge[1] + ": " + edge[2]);
            totalWeight += edge[2];
        }
        System.out.println("최소 신장 트리의 총 가중치: " + totalWeight);
    }

    public static void main(String[] args) {
        int numVertices = 4; // 정점의 개수

        // 간선 추가: (u, v, weight)
        int[][] edges = {
            {0, 1, 10},
            {0, 2, 6},
            {0, 3, 5},
            {1, 3, 15},
            {2, 3, 4}
        };

        // Kruskal의 알고리즘 수행
        kruskal(numVertices, edges);
    }
}

/*
최소 신장 트리의 간선들:
정점 2 - 정점 3: 4
정점 0 - 정점 3: 5
정점 0 - 정점 1: 10
최소 신장 트리의 총 가중치: 19
*/

Greedy

• 그리디
  • 사용 단서 : 부분적인 최적해가 전체적인 최적해가 되는 경우

// 그리디 (최소 개수의 동전으로 주어진 금액 만들기)
public class GreedyExample {

    // 그리디 알고리즘을 사용한 동전 교환 문제 해결 함수
    public static void coinChange(int[] coins, int amount) {
        // 동전 종류를 오름차순으로 정렬 (필요 시)
        Arrays.sort(coins);

        int totalCoins = 0;
        StringBuilder result = new StringBuilder();

        for (int i = coins.length - 1; i >= 0; i--) {
            while (amount >= coins[i]) {
                amount -= coins[i];
                totalCoins++;
                result.append(coins[i]).append(" ");
            }
        }

        if (amount == 0) {
            System.out.println("동전을 사용한 최소 개수: " + totalCoins);
            System.out.println("사용된 동전: " + result.toString().trim());
        } else {
            System.out.println("주어진 금액을 만들 수 없습니다.");
        }
    }

    public static void main(String[] args) {
        int[] coins = {1, 3, 4}; // 동전 종류
        int amount = 6; // 만들 금액

        // 동전 교환 문제 해결
        coinChange(coins, amount);
    }
}

/*
동전을 사용한 최소 개수: 2
사용된 동전: 4 2
*/

• 조합
  • 사용 단서 : n개의 숫자에서 r개를 뽑는 경우의 수를 찾는 경우

// 조합
public class CombinationExample {

    // 조합을 생성하는 재귀 함수
    private static void combine(List<Integer> list, int start, int k, List<Integer> current, List<List<Integer>> result) {
        if (current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i < list.size(); i++) {
            current.add(list.get(i));
            combine(list, i + 1, k, current, result);
            current.remove(current.size() - 1); // 백트래킹
        }
    }

    public static void main(String[] args) {
        List<Integer> list = List.of(1, 2, 3, 4); // 입력 리스트
        int k = 2; // 조합의 개수
        List<List<Integer>> result = new ArrayList<>();

        // 조합 생성
        combine(list, 0, k, new ArrayList<>(), result);

        // 결과 출력
        System.out.println("모든 가능한 조합:");
        for (List<Integer> combination : result) {
            System.out.println(combination);
        }
    }
}

/*
모든 가능한 조합:
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
*/

• 순열
  • 사용 단서 : n개의 숫자 중 r개를 뽑아 순서를 고려해 나열하는 경우의 수를 찾는 경우

// 순열
public class PermutationExample {

    // 순열을 생성하는 재귀 함수
    private static void permute(List<Integer> list, List<Integer> current, boolean[] used, List<List<Integer>> result) {
        if (current.size() == list.size()) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < list.size(); i++) {
            if (used[i]) continue; // 이미 사용된 요소는 건너뜀

            used[i] = true; // 요소 사용
            current.add(list.get(i)); // 요소 추가
            permute(list, current, used, result); // 재귀 호출
            current.remove(current.size() - 1); // 백트래킹: 요소 제거
            used[i] = false; // 요소 미사용 상태로 복원
        }
    }

    public static void main(String[] args) {
        List<Integer> list = List.of(1, 2, 3); // 입력 리스트
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[list.size()]; // 요소 사용 상태 배열

        // 순열 생성
        permute(list, new ArrayList<>(), used, result);

        // 결과 출력
        System.out.println("모든 가능한 순열:");
        for (List<Integer> permutation : result) {
            System.out.println(permutation);
        }
    }
}

/*
모든 가능한 순열:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
*/

Math

• 에라토스테네스의 체
  • 사용 단서 : 소수를 구하는 경우

// 에라토스테네스의 체
public class SieveOfEratosthenesExample {

    // 에라토스테네스의 체를 사용하여 소수를 찾는 함수
    public static void sieveOfEratosthenes(int n) {
        // 소수 여부를 나타내는 배열 초기화 (true로 설정)
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false; // 0은 소수가 아님
        isPrime[1] = false; // 1은 소수가 아님

        // 에라토스테네스의 체 알고리즘
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false; // i의 배수는 소수가 아님
                }
            }
        }

        // 결과 출력
        System.out.println("소수들:");
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                System.out.print(i + " ");
            }
        }
    }

    public static void main(String[] args) {
        int n = 30; // 범위
        sieveOfEratosthenes(n); // 에라토스테네스의 체 실행
    }
}

/*
소수들:
2 3 5 7 11 13 17 19 23 29 
*/

• 오일러피
  • 사용 단서 : 서로소를 구하는 경우

// 오일러 피
public class EulerTotientFunctionExample {

    // 오일러 피 함수 계산
    public static int eulerTotient(int n) {
        int result = n; // 초기값 설정

        // 2부터 √n까지의 모든 소수로 n을 나누어 처리
        for (int p = 2; p * p <= n; p++) {
            if (n % p == 0) { // p는 n의 소인수
                // p로 나누기
                while (n % p == 0) {
                    n /= p;
                }
                // 결과 업데이트
                result -= result / p;
            }
        }

        // n이 1보다 큰 경우, n은 소수임
        if (n > 1) {
            result -= result / n;
        }

        return result;
    }

    public static void main(String[] args) {
        int n = 9; // 예시 입력
        int result = eulerTotient(n); // 오일러 피 함수 계산
        System.out.println("φ(" + n + ") = " + result); // 결과 출력 (1부터 9까지의 정수 중에서 9와 서로소인 수의 개수)
    }
}

/*
φ(9) = 6
*/

• 유클리드 호제법
  • 사용 단서 : 최소 공배수, 최대 공약수를 구하는 경우

// 유클리드 호제법
public class EuclideanAlgorithmExample {

    // 유클리드 호제법을 사용하여 최대 공약수 계산
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    // 최대 공약수를 사용하여 최소 공배수 계산
    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    public static void main(String[] args) {
        int a = 56; // 첫 번째 정수
        int b = 98; // 두 번째 정수

        int gcdResult = gcd(a, b); // 최대 공약수 계산
        int lcmResult = lcm(a, b); // 최소 공배수 계산

        System.out.println("GCD(" + a + ", " + b + ") = " + gcdResult); // 최대 공약수 출력
        System.out.println("LCM(" + a + ", " + b + ") = " + lcmResult); // 최소 공배수 출력
    }
}

/*
GCD(56, 98) = 14
LCM(56, 98) = 392
*/

Tree

• 트리
  • 사용 단서 : 전위, 중위, 후위 순회를 하는 경우, 트리의 루트 노드/높이/너비/서브 트리의 수를 찾는 경우

// 트리
class TreeNode { // 트리 노드 정의
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

public class TreeExample {

    // 전위 순회
    public static void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.value + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 중위 순회
    public static void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.value + " ");
        inOrder(root.right);
    }

    // 후위 순회
    public static void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value + " ");
    }

    // 트리의 높이 계산
    public static int height(TreeNode root) {
        if (root == null) return 0;
        return 1 + Math.max(height(root.left), height(root.right));
    }

    // 트리의 너비 계산 (최대 레벨 너비)
    public static int width(TreeNode root) {
        if (root == null) return 0;
        int maxWidth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            maxWidth = Math.max(maxWidth, levelSize);
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return maxWidth;
    }

    // 서브트리의 수 계산
    public static int countSubtrees(TreeNode root) {
        if (root == null) return 0;
        return 1 + countSubtrees(root.left) + countSubtrees(root.right);
    }

    public static void main(String[] args) {
        // 트리 생성
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        // 전위 순회
        System.out.print("Pre-order: ");
        preOrder(root);
        System.out.println();

        // 중위 순회
        System.out.print("In-order: ");
        inOrder(root);
        System.out.println();

        // 후위 순회
        System.out.print("Post-order: ");
        postOrder(root);
        System.out.println();

        // 트리의 높이
        System.out.println("Height: " + height(root));

        // 트리의 너비
        System.out.println("Width: " + width(root));

        // 서브트리의 수
        System.out.println("Number of subtrees: " + countSubtrees(root));
    }
}

/*
Pre-order: 1 2 4 5 3 6 7 
In-order: 4 2 5 1 6 3 7 
Post-order: 4 5 2 6 7 3 1 
Height: 3
Width: 4
Number of subtrees: 7
*/

• 트라이
  • 사용 단서 : 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 하는 경우

// 트라이
class TrieNode { // 트라이 노드 정의
    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

// 트라이 정의
public class TrieExample {
    private TrieNode root;

    public TrieExample() {
        root = new TrieNode();
    }

    // 단어 삽입
    public void insert(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            current = current.children.computeIfAbsent(c, k -> new TrieNode());
        }
        current.isEndOfWord = true;
    }

    // 단어 검색
    public boolean search(String word) {
        TrieNode current = root;
        for (char c : word.toCharArray()) {
            current = current.children.get(c);
            if (current == null) return false;
        }
        return current.isEndOfWord;
    }

    // 단어 접두사 검색
    public boolean startsWith(String prefix) {
        TrieNode current = root;
        for (char c : prefix.toCharArray()) {
            current = current.children.get(c);
            if (current == null) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        TrieExample trie = new TrieExample();

        // 단어 삽입
        trie.insert("apple");
        trie.insert("app");
        trie.insert("bat");

        // 단어 검색
        System.out.println("Search 'apple': " + trie.search("apple")); // true
        System.out.println("Search 'app': " + trie.search("app")); // true
        System.out.println("Search 'appl': " + trie.search("appl")); // false

        // 단어 접두사 검색
        System.out.println("Starts with 'app': " + trie.startsWith("app")); // true
        System.out.println("Starts with 'bat': " + trie.startsWith("bat")); // true
        System.out.println("Starts with 'bats': " + trie.startsWith("bats")); // false
    }
}

/*
Search 'apple': true
Search 'app': true
Search 'appl': false
Starts with 'app': true
Starts with 'bat': true
Starts with 'bats': false
*/

• 세그먼트 트리
  • 사용 단서 : 구간 합과 데이터 업데이트를 둘 다 수행할 경우

// 세그먼트 트리 (구간 합)
public class SegmentTreeSum {
    private int[] tree;
    private int n;

    // 생성자: 배열을 받아 세그먼트 트리 초기화
    public SegmentTreeSum(int[] array) {
        this.n = array.length;
        this.tree = new int[2 * n];
        build(array);
    }

    // 세그먼트 트리 초기화
    private void build(int[] array) {
        // 리프 노드에 배열 값 복사
        for (int i = 0; i < n; i++) {
            tree[n + i] = array[i];
        }
        // 내부 노드 계산
        for (int i = n - 1; i > 0; i--) {
            tree[i] = tree[i << 1] + tree[i << 1 | 1];
        }
    }

    // 구간 합 쿼리
    public int query(int left, int right) {
        int sum = 0;
        for (left += n, right += n; left <= right; left >>= 1, right >>= 1) {
            if ((left & 1) == 1) sum += tree[left++];
            if ((right & 1) == 0) sum += tree[right--];
        }
        return sum;
    }

    // 값 업데이트
    public void update(int index, int value) {
        index += n;
        tree[index] = value;
        while (index > 1) {
            index >>= 1;
            tree[index] = tree[index << 1] + tree[index << 1 | 1];
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11};
        SegmentTreeSum segmentTree = new SegmentTreeSum(array);
        System.out.println("Sum of range [1, 3]: " + segmentTree.query(1, 3)); // 15
        segmentTree.update(2, 6);
        System.out.println("Sum of range [1, 3] after update: " + segmentTree.query(1, 3)); // 16
    }
}

/*
Sum of range [1, 3]: 15
Sum of range [1, 3] after update: 16
*/

// 세그먼트 트리 (구간 최소값)
public class SegmentTreeMin {
    private int[] tree;
    private int n;

    // 생성자: 배열을 받아 세그먼트 트리 초기화
    public SegmentTreeMin(int[] array) {
        this.n = array.length;
        this.tree = new int[2 * n];
        build(array);
    }

    // 세그먼트 트리 초기화
    private void build(int[] array) {
        // 리프 노드에 배열 값 복사
        for (int i = 0; i < n; i++) {
            tree[n + i] = array[i];
        }
        // 내부 노드 계산
        for (int i = n - 1; i > 0; i--) {
            tree[i] = Math.min(tree[i << 1], tree[i << 1 | 1]);
        }
    }

    // 구간 최소값 쿼리
    public int query(int left, int right) {
        int min = Integer.MAX_VALUE;
        for (left += n, right += n; left <= right; left >>= 1, right >>= 1) {
            if ((left & 1) == 1) min = Math.min(min, tree[left++]);
            if ((right & 1) == 0) min = Math.min(min, tree[right--]);
        }
        return min;
    }

    // 값 업데이트
    public void update(int index, int value) {
        index += n;
        tree[index] = value;
        while (index > 1) {
            index >>= 1;
            tree[index] = Math.min(tree[index << 1], tree[index << 1 | 1]);
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11};
        SegmentTreeMin segmentTree = new SegmentTreeMin(array);
        System.out.println("Min of range [1, 3]: " + segmentTree.query(1, 3)); // 3
        segmentTree.update(2, 0);
        System.out.println("Min of range [1, 3] after update: " + segmentTree.query(1, 3)); // 0
    }
}

/*
Min of range [1, 3]: 3
Min of range [1, 3] after update: 0
*/

// 세그먼트 트리 (최대 값)
public class SegmentTreeMax {
    private int[] tree;
    private int n;

    // 생성자: 배열을 받아 세그먼트 트리 초기화
    public SegmentTreeMax(int[] array) {
        this.n = array.length;
        this.tree = new int[2 * n];
        build(array);
    }

    // 세그먼트 트리 초기화
    private void build(int[] array) {
        // 리프 노드에 배열 값 복사
        for (int i = 0; i < n; i++) {
            tree[n + i] = array[i];
        }
        // 내부 노드 계산
        for (int i = n - 1; i > 0; i--) {
            tree[i] = Math.max(tree[i << 1], tree[i << 1 | 1]);
        }
    }

    // 구간 최대값 쿼리
    public int query(int left, int right) {
        int max = Integer.MIN_VALUE;
        for (left += n, right += n; left <= right; left >>= 1, right >>= 1) {
            if ((left & 1) == 1) max = Math.max(max, tree[left++]);
            if ((right & 1) == 0) max = Math.max(max, tree[right--]);
        }
        return max;
    }

    // 값 업데이트
    public void update(int index, int value) {
        index += n;
        tree[index] = value;
        while (index > 1) {
            index >>= 1;
            tree[index] = Math.max(tree[index << 1], tree[index << 1 | 1]);
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11};
        SegmentTreeMax segmentTree = new SegmentTreeMax(array);
        System.out.println("Max of range [1, 3]: " + segmentTree.query(1, 3)); // 7
        segmentTree.update(2, 12);
        System.out.println("Max of range [1, 3] after update: " + segmentTree.query(1, 3)); // 12
    }
}

/*
Max of range [1, 3]: 7
Max of range [1, 3] after update: 12
*/

• 최소 공통 조상
  • 사용 단서 : 트리 그래프에서 임의의 두 노드를 선택했을 때 처음 공통으로 만나게 되는 부모 노드를 찾는 경우

// 최소 공통 조상
public class LCABinaryTreeExample {
    private static final int MAX = 100; // 최대 노드 수
    private List<Integer>[] adj; // 인접 리스트
    private int[] depth; // 각 노드의 깊이
    private int[][] parent; // 부모 배열
    private int log; // 로그 값 (높이)

    // 생성자
    public LCABinaryTree(int n) {
        adj = new ArrayList[n + 1];
        depth = new int[n + 1];
        parent = new int[n + 1][20]; // 2^20 >= 1000000, 따라서 20층
        log = 20;
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
    }

    // 트리 추가
    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);
    }

    // DFS를 사용하여 부모와 깊이 배열 계산
    private void dfs(int node, int par) {
        parent[node][0] = par;
        for (int i = 1; i <= log; i++) {
            if (parent[node][i - 1] != -1) {
                parent[node][i] = parent[parent[node][i - 1]][i - 1];
            }
        }

        for (int neighbor : adj[node]) {
            if (neighbor != par) {
                depth[neighbor] = depth[node] + 1;
                dfs(neighbor, node);
            }
        }
    }

    // LCA 찾기
    public int findLCA(int u, int v) {
        if (depth[u] < depth[v]) {
            int temp = u;
            u = v;
            v = temp;
        }

        // u를 v와 같은 깊이로 만들기
        for (int i = log; i >= 0; i--) {
            if (depth[u] - (1 << i) >= depth[v]) {
                u = parent[u][i];
            }
        }

        if (u == v) return u;

        // 두 노드가 같지 않으면 공통 조상을 찾기
        for (int i = log; i >= 0; i--) {
            if (parent[u][i] != parent[v][i]) {
                u = parent[u][i];
                v = parent[v][i];
            }
        }

        return parent[u][0];
    }

    public static void main(String[] args) {
        int n = 7; // 노드 수
        LCABinaryTree tree = new LCABinaryTree(n);

        // 트리 생성
        tree.addEdge(1, 2);
        tree.addEdge(1, 3);
        tree.addEdge(2, 4);
        tree.addEdge(2, 5);
        tree.addEdge(3, 6);
        tree.addEdge(3, 7);

        // 깊이와 부모 배열 초기화
        Arrays.fill(tree.parent[0], -1);
        tree.depth[1] = 0;
        tree.dfs(1, -1);

        // LCA 쿼리
        System.out.println("LCA of 4 and 5: " + tree.findLCA(4, 5)); // 2
        System.out.println("LCA of 4 and 6: " + tree.findLCA(4, 6)); // 1
        System.out.println("LCA of 3 and 4: " + tree.findLCA(3, 4)); // 1
        System.out.println("LCA of 5 and 6: " + tree.findLCA(5, 6)); // 1
    }
}

/*
LCA of 4 and 5: 2
LCA of 4 and 6: 1
LCA of 3 and 4: 1
LCA of 5 and 6: 1
*/

Dynamic Programming

• 동적 계획법
  • 사용 단서 : 복잡한 문제를 한 번에 해결하는 것이 아닌, 점차적으로 풀이하는 경우

// 동적 계획법 (피보나치 수열)
public class FibonacciDP {
    public static void main(String[] args) {
        int n = 10; // 계산할 피보나치 수열의 항
        
        // DP 배열 초기화
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        
        // DP 배열 채우기
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        // 결과 출력
        System.out.println("Fibonacci(" + n + ") = " + dp[n]);
    }
}

/*
Fibonacci(10) = 55
*/

// 동적 계획법 (최대 무게를 넘지 않으면서 얻을 수 있는 최대 가치)
public class KnapsackProblem {
    public static void main(String[] args) {
        int W = 50; // 배낭의 최대 무게
        int[] weights = {10, 20, 30}; // 물건의 무게
        int[] values = {60, 100, 120}; // 물건의 가치
        int n = values.length; // 물건의 개수

        // DP 배열 초기화
        int[] dp = new int[W + 1];
        
        // DP 배열 채우기
        for (int i = 0; i < n; i++) {
            for (int w = W; w >= weights[i]; w--) {
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
        
        // 결과 출력
        System.out.println("최대 가치: " + dp[W]);
    }
}

/*
최대 가치: 220
*/

// 동적 계획법 (최장 공통 부분 수열)
public class LCS {
    public static void main(String[] args) {
        String s1 = "ABCBDAB";
        String s2 = "BDCAB";
        int m = s1.length();
        int n = s2.length();
        
        // DP 배열 초기화
        int[][] dp = new int[m + 1][n + 1];
        
        // DP 배열 채우기
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // 결과 출력
        System.out.println("최장 공통 부분 수열의 길이: " + dp[m][n]);
    }
}

/*
최장 공통 부분 수열의 길이: 4
*/

• 트리 동적 계획법
  • 사용 단서 : 트리를 재귀적으로 탐색하는 경우

// 트리 동적 계획법 (트리에서 인접하지 않은 노드들의 최대 집합 찾기)
import java.util.ArrayList;
import java.util.List;

public class TreeDP {
    private static class TreeNode {
        int value;
        List<TreeNode> children;
        
        TreeNode(int value) {
            this.value = value;
            this.children = new ArrayList<>();
        }
    }
    
    private static class DP {
        int include; // 현재 노드를 포함할 때 최대 독립 집합의 크기
        int exclude; // 현재 노드를 포함하지 않을 때 최대 독립 집합의 크기
        
        DP() {
            this.include = 0;
            this.exclude = 0;
        }
    }
    
    // 트리에서 DP를 계산하는 함수
    private static DP calculateDP(TreeNode node) {
        DP dp = new DP();
        dp.include = 1; // 현재 노드를 포함할 때의 기본 값
        
        for (TreeNode child : node.children) {
            DP childDP = calculateDP(child);
            dp.exclude += Math.max(childDP.include, childDP.exclude); // 자식 노드를 포함하거나 포함하지 않는 경우 중 최대 값을 선택
            
            // 자식 노드를 포함하는 경우에는 현재 노드를 포함할 수 없으므로 dp.include에 추가
            dp.include += childDP.exclude;
        }
        
        return dp;
    }
    
    public static void main(String[] args) {
        // 트리 생성
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        
        root.children.add(node2);
        root.children.add(node3);
        node2.children.add(node4);
        node2.children.add(node5);
        
        // DP 계산
        DP result = calculateDP(root);
        
        // 결과 출력
        System.out.println("트리의 최대 독립 집합의 크기: " + Math.max(result.include, result.exclude));
    }
}

/*
트리의 최대 독립 집합의 크기: 4
*/

Brute Force / BackTracking

• 완전 탐색 / 백트래킹
  • 사용 단서 : 그래프 탐색, 반복문을 통해 모든 경우를 탐색하는 경우
                         재귀적으로 경우를 탐색하며, 도중 조건을 만족할 수 없다고 판단되면 되돌아가서 다시 탐색하는 경우

// 완전 탐색 (부분 집합 구하기)
import java.util.ArrayList;
import java.util.List;

public class SubsetSum {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3}; // 입력 배열
        int targetSum = 4; // 목표 합

        List<List<Integer>> subsets = new ArrayList<>();
        findSubsets(nums, 0, new ArrayList<>(), subsets);

        // 목표 합이 4인 부분집합 출력
        System.out.println("부분집합 중 합이 " + targetSum + "인 부분집합:");
        for (List<Integer> subset : subsets) {
            if (subset.stream().mapToInt(Integer::intValue).sum() == targetSum) {
                System.out.println(subset);
            }
        }
    }

    private static void findSubsets(int[] nums, int index, List<Integer> current, List<List<Integer>> subsets) {
        if (index == nums.length) {
            subsets.add(new ArrayList<>(current));
            return;
        }

        // 현재 인덱스의 값을 포함하지 않는 경우
        findSubsets(nums, index + 1, current, subsets);

        // 현재 인덱스의 값을 포함하는 경우
        current.add(nums[index]);
        findSubsets(nums, index + 1, current, subsets);
        current.remove(current.size() - 1); // 백트래킹
    }
}

/*
부분집합 중 합이 4인 부분집합:
[1, 3]
[1, 2, 1]
*/

Divide and Conquer

• 분할 정복
  • 사용 단서 : 문제를 작게 분할한 후 각각을 정복하는 경우

// 분할 정복 (병합 정렬)
public class MergeSortExample {
    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("정렬 전 배열:");
        printArray(array);

        mergeSort(array, 0, array.length - 1);

        System.out.println("\n정렬 후 배열:");
        printArray(array);
    }

    private static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;

            // 분할
            mergeSort(array, left, middle);
            mergeSort(array, middle + 1, right);

            // 결합
            merge(array, left, middle, right);
        }
    }

    private static void merge(int[] array, int left, int middle, int right) {
        int n1 = middle - left + 1;
        int n2 = right - middle;

        // 임시 배열 생성
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        // 배열 복사
        System.arraycopy(array, left, leftArray, 0, n1);
        System.arraycopy(array, middle + 1, rightArray, 0, n2);

        // 병합
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                array[k++] = leftArray[i++];
            } else {
                array[k++] = rightArray[j++];
            }
        }

        // 남아있는 요소 복사
        while (i < n1) {
            array[k++] = leftArray[i++];
        }
        while (j < n2) {
            array[k++] = rightArray[j++];
        }
    }

    private static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

/*
정렬 전 배열:
38 27 43 3 9 82 10 

정렬 후 배열:
3 9 10 27 38 43 82 
*/