이진탐색

"정렬된 배열"에서 "특정 값"을 찾는 알고리즘을 의미

• 이진탐색은 "탐색 범위를 절반씩 줄여" 나가기 때문에 선형탐색에 비해 빠른 속도를 보장
  하지만 "배열이 정렬되어 있어야 한다는 조건"이 필요하기 때문에 배열이 정렬되어있지 않는 경우에는 정렬 작업이 필요하다

주요 특징:

탐색 범위를 절반씩 줄여 나가기 때문에 선형탐색보다 빠름
배열이 반드시 정렬되어 있어야 함
시간 복잡도: O(log n)

선형탐색 : 배열이나 리스트와 같은 데이터 구조에서 특정한 값을 찾는 알고리즘 중 하나

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            }
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;  // 찾는 값이 없을 때
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(binarySearch(arr, 7));  // 출력: 6
    }
}

동적 프로그래밍 (Dynamic Programming, DP)

동적 프로그래밍은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법입니다.
주요 특징:

큰 문제를 작은 하위 문제로 나눔
중복되는 계산을 피하기 위해 이미 계산한 결과를 저장 (메모이제이션)
주로 최적화 문제나 카운팅 문제에 사용됨

import java.util.HashMap;

public class FibonacciDP {
    private static HashMap<Integer, Integer> memo = new HashMap<>();

    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        int result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }

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

이 DP 구현에서는:

작은 문제의 결과를 memo HashMap에 저장합니다.
이미 계산한 값은 다시 계산하지 않고 저장된 값을 사용합니다.
이를 통해 중복 계산을 피하고 실행 시간을 크게 줄일 수 있습니다.

이진탐색과 동적 프로그래밍은 모두 효율적인 알고리즘 설계 기법으로, 적절한 상황에서 사용하면 프로그램의 성능을 크게 향상시킬 수 있습니다.