[알고리즘]고급 알고리즘: 분할 정복, 정렬, 슬라이딩 윈도우 🚀🪓

반응형

고급 알고리즘은 복잡한 문제를 간단하고 효율적으로 해결할 수 있는 열쇠예요. 오늘은 다양한 고급 알고리즘들을 탐험하며, 활용 사례와 구현 방법을 재미있게 알아보아요! ✨

---

1. 분할 정복 🪓

분할 정복은 큰 문제를 작은 문제로 나누어 해결하고, 결과를 합쳐 최종 답을 구하는 알고리즘 설계 기법이에요. 이 기법은 문제를 재귀적으로 나누고 합치는 과정에서 효율성을 극대화합니다.

대표 알고리즘 🌟

병합 정렬 (Merge Sort)

병합 정렬은 배열을 절반으로 나누고, 각각을 정렬한 뒤 합치는 정렬 알고리즘이에요.

public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

private void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int[] L = new int[n1];
    int[] R = new int[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

핵심 포인트:

• 시간 복잡도: O(n log n) (항상 일정!)
• 장점: 안정적인 정렬이며, 대규모 데이터를 처리하는 데 적합합니다.
• 단점: 추가적인 메모리가 필요하므로, 공간 효율성이 떨어질 수 있어요.

활용 사례:

• 데이터 정렬: 데이터베이스나 대규모 로그 파일에서 데이터를 정렬할 때.
• 다중 병합: 여러 정렬된 파일을 하나로 병합할 때.

이분 탐색 (Binary Search)

이분 탐색은 정렬된 배열에서 특정 값을 빠르게 찾는 알고리즘이에요.

public 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;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

주의할 점:

• 입력 배열이 반드시 정렬되어 있어야 해요.
• 정수 오버플로를 방지하기 위해 int mid = left + (right - left) / 2;를 사용하세요.

활용 사례:

• 데이터 검색: 대규모 정렬된 데이터베이스에서 특정 키 찾기.
• 조건 만족 판별: 특정 값 이상의 첫 위치 찾기.

---

2. 슬라이딩 윈도우 🚪

슬라이딩 윈도우는 배열이나 문자열에서 일정 범위의 데이터를 효율적으로 처리하는 기법이에요. 특정 구간 내의 값을 빠르게 계산하거나 갱신할 때 유용합니다.

최대/최소 구간합 계산

public int maxSubarraySum(int[] arr, int k) {
    int maxSum = 0, windowSum = 0;
    for (int i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    for (int i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, windowSum);
    }
    return maxSum;
}

핵심 포인트:

• 시간 복잡도: O(n) (반복문 한 번으로 해결!)
• 장점: 메모리와 연산을 최소화하여 빠르게 처리할 수 있어요.
• 단점: 특정 조건이 추가되면 구현이 복잡해질 수 있어요.

활용 사례:

• 금융 데이터 분석: 연속된 기간의 최대 수익 계산.
• 문자열 처리: 특정 길이의 부분 문자열 중 최대/최소 값 찾기.

투 포인터 활용

투 포인터는 두 개의 포인터를 사용해 문제를 효율적으로 푸는 방식이에요.

public boolean hasPairWithSum(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) return true;
        else if (sum < target) left++;
        else right--;
    }
    return false;
}

활용 사례:

• 중복된 데이터 처리: 중복 원소의 집합에서 특정 합을 만드는 쌍 찾기.
• 특정 조건 만족 여부 확인: 주어진 조건에 맞는 두 요소 찾기.

---

3. 유니온 파인드 ✨

유니온 파인드는 그래프에서 연결 요소를 관리하거나 사이클을 판별할 때 사용돼요. 주로 네트워크 분석과 관련된 문제에서 활용됩니다.

구현 예시

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[rootY] = rootX;
        }
    }
}

핵심 포인트:

• 경로 압축(Path Compression)을 통해 탐색 속도를 향상시킬 수 있어요.
• 시간 복잡도: 거의 O(1) (상수 시간에 가까움).

활용 사례:

• 네트워크 연결 분석: 컴퓨터 네트워크에서 연결 여부 판단.
• 최소 신장 트리(MST): 크루스칼 알고리즘 구현.
• 사이클 검출: 무방향 그래프에서 사이클 존재 여부 확인.

---

4. 세그먼트 트리와 펜윅 트리 🌳

구간 연산을 효율적으로 수행할 수 있는 고급 자료구조예요. 대규모 데이터에서 특정 구간에 대한 질의를 빠르게 처리하는 데 적합합니다.

세그먼트 트리

세그먼트 트리는 배열에서 구간 합 또는 최댓값 같은 쿼리를 빠르게 처리해요.

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

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

    private void buildTree(int[] arr, int start, int end, int node) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = start + (end - start) / 2;
        buildTree(arr, start, mid, 2 * node + 1);
        buildTree(arr, mid + 1, end, 2 * node + 2);
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }

    public int query(int l, int r) {
        return query(0, n - 1, l, r, 0);
    }

    private int query(int start, int end, int l, int r, int node) {
        if (start > r || end < l) return 0;
        if (start >= l && end <= r) return tree[node];
        int mid = start + (end - start) / 2;
        return query(start, mid, l, r, 2 * node + 1) +
               query(mid + 1, end, l, r, 2 * node + 2);
    }
}

핵심 포인트:

• 시간 복잡도: O(log n) (구간 쿼리와 업데이트).
• 장점: 동적 데이터 업데이트와 쿼리가 빠릅니다.
• 단점: 구현이 다소 복잡하고, 초기 설정에 추가 메모리가 필요합니다.

활용 사례:

• 구간 합 계산: 대규모 데이터의 특정 범위 합 계산.
• 구간 최댓값: 배열의 특정 구간에서 최댓값 찾기.
• 데이터 분석: 실시간 업데이트와 집계.

---

마무리 🎉

고급 알고리즘은 복잡한 문제를 단순화하고 효율적인 해결책을 제공해요. 분할 정복, 슬라이딩 윈도우, 유니온 파인드, 세그먼트 트리와 같은 알고리즘을 이해하고 활용한다면 한층 더 강력한 문제 해결 능력을 가질 수 있을 거예요! 🌟 이제 여러분의 코드에 멋진 알고리즘을 더해 보세요!