Binary Search (이진 탐색) 및 Segment Tree (세그먼트 트리)

이진 탐색(Binary Search) 또는 이분 탐색은 정렬된 배열에서 특정 값을 효율적으로 찾는 알고리즘이다. 탐색 범위를 절반씩 나누면서 원하는 값을 찾기 때문에 시간 복잡도가 O(log N)으로 매우 빠르다.

세그먼트 트리(Segment Tree)는 주로 범위에 대한 질의와 업데이트가 빈번한 상황에서 사용되는 자료 구조이다. 세그먼트 트리를 통해 범위 합, 최소/최대값, 곱 등의 연산을 효율적으로 수행할 수 있다.

이진 탐색(Binary Search)

동작 원리

1. 정렬: 이진 탐색을 수행하기 전에 배열이 정렬되어 있어야 한다.
2. 중앙값 선택: 탐색 범위의 중앙값(mid)을 선택한다.
3. 값 비교: 중앙값과 찾고자 하는 값을 비교한다.

• 찾고자 하는 값이 중앙값과 같으면 탐색을 종료한다.
• 찾고자 하는 값이 중앙값보다 크면, 탐색 범위를 중앙값의 오른쪽 절반으로 줄인다.
• 찾고자 하는 값이 중앙값보다 작으면, 탐색 범위를 중앙값의 왼쪽 절반으로 줄인다.

4. 반복: 위 과정을 탐색 범위가 유효한 동안 반복한다.

시간 복잡도

• 전체 탐색: O(N)
• 이진 탐색: O(log N)

package Study;

import java.util.Arrays;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {2, 13, 6, 5, 12, 15, 23, 17, 19, 10};
        System.out.println(solution(17, arr));
    }

    private static int solution(int target, int[] arr) {
        Arrays.sort(arr);
        int left = 0, right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (target == arr[mid]) {
                System.out.println("Find Target : " + target + ", Value : " + arr[mid]);
                return arr[mid];
            }

            if (target < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }
}

결과

• 찾고자 하는 값을 찾은 경우, 해당 값을 반환하고 찾았다는 메시지를 출력한다.
• 찾지 못한 경우, -1을 반환한다.

세그먼트 트리(Segment Tree)

세그먼트 트리(Segment Tree)는 배열의 구간 합, 구간 최소/최대값 등의 질의를 효율적으로 수행하기 위해 사용하는 자료 구조이다. 배열의 특정 구간에 대한 연산을 빠르게 수행할 수 있다.

동작 원리

1. 트리 구성: 주어진 배열을 기반으로 세그먼트 트리를 구축한다.
2. 구간 질의: 트리를 통해 특정 구간에 대한 질의를 수행한다.
3. 구간 업데이트: 트리를 통해 특정 구간의 값을 업데이트한다.

시간 복잡도

• 구성 시간: O(N)
• 질의 및 업데이트 시간: O(log N)

class SegmentTree {
    private int[] tree;
    private int n;

    public SegmentTree(int[] arr) {
        this.n = arr.length;
        this.tree = new int[4 * n];
        build(arr, 0, n - 1, 1);
    }

    private void build(int[] arr, int start, int end, int node) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, start, mid, 2 * node);
            build(arr, mid + 1, end, 2 * node + 1);
            tree[node] = tree[2 * node] + tree[2 * node + 1]; // 예: 구간 합
        }
    }

    public int query(int left, int right) {
        return query(1, 0, n - 1, left, right);
    }

    private int query(int node, int start, int end, int left, int right) {
        if (right < start || end < left) {
            return 0; // 예: 구간 합, 무시할 값
        }
        if (left <= start && end <= right) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        int leftSum = query(2 * node, start, mid, left, right);
        int rightSum = query(2 * node + 1, mid + 1, end, left, right);
        return leftSum + rightSum;
    }

    public void update(int index, int value) {
        update(1, 0, n - 1, index, value);
    }

    private void update(int node, int start, int end, int index, int value) {
        if (start == end) {
            tree[node] = value;
        } else {
            int mid = (start + end) / 2;
            if (index <= mid) {
                update(2 * node, start, mid, index, value);
            } else {
                update(2 * node + 1, mid + 1, end, index, value);
            }
            tree[node] = tree[2 * node] + tree[2 * node + 1]; // 예: 구간 합
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        SegmentTree segmentTree = new SegmentTree(arr);

        // 구간 합 질의 예제
        System.out.println(segmentTree.query(1, 3)); // 3+5+7 = 15

        // 값 업데이트 예제
        segmentTree.update(1, 10); // arr[1] = 10
        System.out.println(segmentTree.query(1, 3)); // 10+5+7 = 22
    }
}

설명

1. 트리 구성:
   build 함수는 주어진 배열을 기반으로 세그먼트 트리를 구축한다. 트리는 구간 합을 저장하는 구조로 이루어진다.
2. 구간 질의:
   query 함수는 트리를 통해 특정 구간의 합을 구한다. 트리 노드를 재귀적으로 탐색하여 구간 합을 계산한다.
3. 구간 업데이트:
   update 함수는 특정 인덱스의 값을 업데이트하고, 트리의 값을 재계산한다. 트리 노드를 재귀적으로 탐색하여 값을 갱신한다.

결론

이진 탐색은 정렬된 배열에서 특정 값을 빠르게 찾을 수 있는 효율적인 알고리즘이다. 세그먼트 트리는 배열의 구간 질의와 업데이트를 빠르게 수행할 수 있는 자료 구조로, 범위 연산이 빈번한 경우 매우 유용하다. 오늘 학습을 통해 이진 탐색과 세그먼트 트리의 동작 원리와 구현 방법을 이해하고, 이를 실제 코드로 작성해보며 그 효율성을 경험할 수 있었다.