이진 검색 (binary search)

• 시간복잡도
  • 이분 탐색 : O(logN)
• 정의
  • 항목들을 두 그룹으로 나누고 각 요소를 비교하는 단계를 거치면서 한 쪽 그룹은 다음 고려 대상에서 제외하는 방법
• 특징
  • 오름차순이나 알파벳 순 등으로 이미 정렬되어 있어야 함
  • 분할 정복(Divide and Conquer) 전략의 예
  • 각 단계마다 남아있는 항목이 절반이 됨
  • 작업의 양이 데이터의 양이 증가하는 것에 비해 천천히 증가함
• 구성
  • 단계의 수(비교 횟수)
    • 전체 항목 크기를 2로 나눠 항목 크기가 1에 도달하게 되는 횟수
  • 2를 거듭지곱했을 때 전체 항목의 수가 되도록 하는 지수
• 사례
  • 로그 : 어떤 수를 2로 나눠 1에 도달하기 까지의 횟수 or 2를 거듭제곱해서 그 수까지 도달하기 까지의 횟수
  • 스포츠 경기의 단계별 토너먼트
  <aside> 💡 [예] 약 2만개의 이름이 포함된 전화번호가 있을 때, 20,000은 $2^{14}$(16,384) 와 $2^{15}$(32,768)의 사이에 있기 때문에 14~15번 사이에 특정 전화번호를 찾을 수 있다.
• </aside>

더 알아보기 (요약)

• 설명
  • 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식
  • 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.
• 장점
  • 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다.
• 단점
  • 검색 원리상 정렬된 리스트에만 사용할 수 있다.
• 의사코드

BinarySearch(A[0..N-1], value, low, high) {
  **if** (high < low)
    **return** -1 *// not found*  
	mid = (low + high) / 2
  **if** (A[mid] > value)
    **return** BinarySearch(A, value, low, mid-1)
  **else** **if** (A[mid] < value)
    **return** BinarySearch(A, value, mid+1, high)
  **else**
    **return** mid *// found*
}

• high와 low를 지정

binarySearch(A[0..N-1], value) {*//k*  
	low = 0
  high = N - 1
  **while** (low <= high) {
      mid = (low + high) / 2
      **if** (A[mid] > value)
          high = mid - 1
      **else** **if** (A[mid] < value)
          low = mid + 1
      **else** 
          **return** mid *// found k*  
	}
  **return** -1 *// not found k*
}

분할 정복(Divide and conquer)

• 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법
• 예) 퀵정렬 (quick sort), 병합 정렬 (merge sort), 고속 푸리어 변환 (FFT) 문제 등
• 대표적인 사례: 하노이의 탑

장점

• 어려운 문제를 간단하게 해결할 수 있다.

단점

• 스택에 많은 데이터를 담고 있어 스택 오버플로가 발생하거나 메모리를 과하게 사용하게 된다.
• 재귀적으로 많은 함수호출이 이루어지면 오버헤드가 발생할 수 있다.
• 문제를 쪼개는 방법 자체가 상당히 어려울 수 있다.

재귀함수로의 표현

function F(x):
  if F(x)의 문제가 간단 then:
    return F(x)을 직접 계산한 값
  else:
    x를 y1, y2로 분할
    F(y1)과 F(y2)를 호출
    return F(y1), F(y2)로부터 F(x)를 구한 값

빠른 실행이나 문제 해결 순서 선택을 위해, 재귀호출을 사용하지 않고 스택, 큐 등의 자료구조로 분할 정복법을 구현할 수 있다.

참고자료

• Branch and Bound - Binary Search
• 이진 검색 알고리즘
• 분할 정복 알고리즘
• 분할 정복

동적 계획법 (Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제들로 나누어 풀고, 그 결과를 저장해 재사용하여 주어진 문제를 최적화하는 방법이다.

이는 '분할 정복' 알고리즘의 기본적인 원리를 따르지만, 동적 계획법은 각 하위 문제들이 중첩되어 있는 경우에 특히 효과적이다. 그래서, 동적 계획법은 공통의 하위 문제들을 여러 번 다시 풀지 않도록 이를 메모이제이션 (memoization)하여, 알고리즘의 계산 효율성을 대폭 향상시킨다.

동적 계획법은 일반적으로 두 가지 기본 단계를 거친다.

1. 하향식 접근법(Top-down): 문제를 하위 문제로 나눈다. 만약 하위 문제가 이미 해결되었다면, 저장된 결과를 사용한다. 아니라면, 문제를 해결하고 결과를 저장한다.
2. 상향식 접근법(Bottom-up): 가장 작은 하위 문제부터 시작하여, 작은 하위 문제들의 해결을 바탕으로 큰 문제의 해결책을 구성해 나간다.

동적 계획법은 최단 경로 문제, 0-1 배낭 문제, 피보나치 수열 등 다양한 문제에 적용될 수 있다. 그러나 동적 계획법이 모든 최적화 문제에 효과적인 것은 아니다. '최적 부분 구조(Optimal Substructure)'와 '중복된 하위 문제(Overlapping Subproblems)' 조건을 만족하는 문제에 대해서만 동적 계획법을 적용할 수 있다.

public class Main {
    public static long fib(int n) {
        long[] dp = new long[n+1];
        dp[0] = 0;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fib(10)); // 10 번째 피보나치 수를 출력
    }
}

dp라는 이름의 long형 배열은 메모이제이션을 위한 저장 공간으로 사용된다. 각 n에 대한 피보나치 결과가 이 배열에 저장된다. 이미 계산된 결과를 재사용할 수 있게 되어 중복 계산을 피하고 효율성을 높일 수 있다.

큐(Queue)는 컴퓨터 과학에서 사용되는 기본적인 자료 구조 중 하나이다. 큐는 '선입선출'(FIFO, First-In-First-Out) 원칙을 따르는 것으로 알려져 있다. 즉, 큐에 먼저 들어간 항목이 먼저 나오게 된다. 이는 실생활에서 줄을 서는 것과 비슷한 개념이다.

큐에서는 주로 다음 네 가지 기본 연산이 사용된다.

1. Enqueue: 큐의 뒤쪽에 항목을 추가한다.
2. Dequeue: 큐의 앞쪽에 있는 항목을 제거하고 반환한다. 이 연산을 수행하면, 큐에서 항목이 제거된다.
3. Front: 큐의 앞쪽에 있는 항목을 확인한다.
4. IsEmpty: 큐가 비어 있는지 확인한다.

큐는 다양한 분야에서 사용된다. 예를 들어, 운영 체제에서는 프로세스 스케줄링에 큐를 사용하고, 네트워크에서 패킷 전송을 위한 버퍼로서 큐를 사용한다. 또한, 너비 우선 탐색(BFS)와 같은 알고리즘에서도 큐는 핵심적인 역할을 한다.

import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(1);
        queue.add(2);
        queue.add(3);
        System.out.println("Queue: " + queue);

        int removedElement = queue.remove();
        System.out.println("Dequeued element: " + removedElement);
        System.out.println("Queue after dequeue operation: " + queue);

        int frontElement = queue.peek();
        System.out.println("Front element: " + frontElement);
        System.out.println("Queue after peek operation: " + queue);

        boolean isEmpty = queue.isEmpty();
        System.out.println("Is queue empty? " + isEmpty);
    }
}

Integer 타입의 Queue 객체를 생성하고, add 메소드를 사용하여 큐에 원소를 추가하고, remove 메소드를 사용하여 가장 앞의 원소를 제거하고, peek 메소드를 사용하여 가장 앞의 원소를 확인하며, isEmpty 메소드를 사용하여 큐가 비어 있는지 확인한다.