[Java] 기본 문법 정리 - 이진 탐색, DFS & BFS, 동적 프로그래밍(DP)

✅ 11. 이진 탐색 (Binary Search)

이진 탐색은 정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘으로, 시간 복잡도는 O(log N).
자바에서는 Arrays.binarySearch() 또는 직접 구현할 수 있음.

---

📍 1) Arrays.binarySearch() 활용

• 배열이 정렬되어 있어야 사용 가능
• 값이 존재하면 인덱스 반환, 없으면 음수 반환

  

    
    
    
    
  
import java.util.Arrays;

public class BinarySearchExample {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9}; // 반드시 정렬된 상태여야 함!
        
        int index = Arrays.binarySearch(arr, 5); // 5의 위치 찾기
        
        if (index >= 0) {
            System.out.println("값 찾음: 인덱스 " + index);
        } else {
            System.out.println("값 없음");
        }
    }
}

📌 정렬되지 않은 배열에서 실행하면 잘못된 결과가 나옴!

---

📍 2) 직접 구현하는 이진 탐색

  

    
    
    
    
  
public class BinarySearchCustom {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;

            if (arr[mid] == target) return mid;
            else if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        
        return -1; // 값이 없으면 -1 반환
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int index = binarySearch(arr, 7);
        System.out.println(index); // 3 (인덱스 반환)
    }
}

📌 탐색할 값이 없으면 -1 반환
📌 시간 복잡도: O(log N) → 데이터가 많을수록 선형 탐색보다 훨씬 빠름

---

✅ 12. DFS & BFS (깊이 우선 탐색 & 너비 우선 탐색)

DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)은 그래프 탐색 알고리즘.

📍 1) DFS (깊이 우선 탐색)

• 스택(Stack) 또는 재귀(Recursion)로 구현
• 한 방향으로 끝까지 탐색 후 돌아옴 (깊이 우선)
• 백트래킹, 순열, 조합 문제에서 자주 사용됨

DFS 예제 (재귀 방식)

  

    
    
    
    
  
import java.util.*;

public class DFSExample {
    static boolean[] visited = new boolean[7]; // 방문 체크
    static List<List<Integer>> graph = new ArrayList<>();
    
    public static void dfs(int node) {
        visited[node] = true;
        System.out.print(node + " ");
        
        for (int next : graph.get(node)) {
            if (!visited[next]) dfs(next);
        }
    }
    
    public static void main(String[] args) {
        for (int i = 0; i < 7; i++) graph.add(new ArrayList<>());
        
        graph.get(1).addAll(Arrays.asList(2, 3));
        graph.get(2).addAll(Arrays.asList(4, 5));
        graph.get(3).addAll(Arrays.asList(6));
        
        dfs(1);
    }
}

📌 출력 예시: 1 2 4 5 3 6
📌 깊이 우선 탐색이라 한쪽 끝까지 내려간 후 탐색을 이어감

---

📍 2) BFS (너비 우선 탐색)

• 큐(Queue)로 구현
• 한 레벨씩 좌우로 탐색 (너비 우선)
• 최단 경로 문제에서 자주 사용됨

BFS 예제 (큐 사용)

  

    
    
    
    
  
import java.util.*;

public class BFSExample {
    static boolean[] visited = new boolean[7];
    static List<List<Integer>> graph = new ArrayList<>();
    
    public static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");
            
            for (int next : graph.get(node)) {
                if (!visited[next]) {
                    queue.offer(next);
                    visited[next] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 7; i++) graph.add(new ArrayList<>());

        graph.get(1).addAll(Arrays.asList(2, 3));
        graph.get(2).addAll(Arrays.asList(4, 5));
        graph.get(3).addAll(Arrays.asList(6));

        bfs(1);
    }
}

📌 출력 예시: 1 2 3 4 5 6
📌 BFS는 가까운 노드부터 탐색하므로 계층적으로 퍼져나감

---

✅ DFS vs BFS 비교

기준 DFS (깊이 우선 탐색) BFS (너비 우선 탐색)

자료구조	스택 (Stack) 또는 재귀	큐 (Queue)
탐색 방식	깊이 우선	너비 우선
사용 예	백트래킹, 순열/조합	최단 경로 탐색
속도	깊은 탐색에서 유리	얕은 탐색에서 유리

---

✅ 13. 동적 프로그래밍 (DP)

DP(Dynamic Programming)는 이전 결과를 저장하여 중복 계산을 줄이는 기법.
피보나치 수열, 배낭 문제, 최대 부분합 문제 같은 문제에서 활용됨.

📍 1) 피보나치 수열 (기본 재귀)

  

    
    
    
    
  
public class FibonacciRecursive {
    public static int fib(int n) {
        if (n <= 1) return n;
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(fib(10)); // 55
    }
}

📌 문제점: 중복 계산이 많아 O(2^N)으로 비효율적

---

📍 2) DP를 이용한 피보나치 (메모이제이션)

  

    
    
    
    
  
public class FibonacciDP {
    static int[] dp = new int[100];

    public static int fib(int n) {
        if (n <= 1) return n;
        if (dp[n] != 0) return dp[n]; // 이미 계산된 값이면 반환
        return dp[n] = fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(fib(10)); // 55
    }
}

📌 시간 복잡도 O(N) → 중복 계산 없이 빠르게 동작! 🚀

---