분할 정복 알고리즘

분할 정복(divide and conquer) 알고리즘

개념

• 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 기법이다.
• 재귀적으로 구현한다.
• 대표적인 예시로는 병합 정렬(Merge Sort), 이진 검색(Binary Search), 거듭 제곱(Exponentiation), 퀵 정렬(Quick Sort)이 있다.
  • 이 외로는 행렬 곱셈(Matrix Multiplication), 최대 부분 합(Maximum Subarray)이 있다.

설계

1) Divide(분할): 주어진 문제를 분할한다. 단, 문제를 적절한 크기로 분할하는 것이 중요하다. (최소 2개 이상)

2) Conquer(정복): 각 하위 문제들을 재귀적으로 해결한다. 나눌 수 없으면 탈출 조건을 설정하고, 문제를 해결한다.

3) Combine(결합): 하위 문제들을 결합하여 주어진 문제의 답을 구한다.

---

병합 정렬(Merge Sort)

동작 과정

• Divide : 주어진 배열을 절반으로 분할한다.
• Conquer : 각각의 배열을 재귀적으로 병합 정렬한다.
• Combine : 정렬된 배열을 병합하여 전체 배열을 정렬한다.

예시 코드

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    res = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1

    if i < len(left):
        res.extend(left[i:])

    if j < len(right):
        res.extend(right[j:])

    return res

코드 설명

• 리스트 중간을 기준으로 left 와 right 를 나눈다.
• i 와 j 는 각각 left 와 right 의 인덱스를 나타낸다.
• 각 원소를 순서대로 비교하면서 작은 값을 res 에 추가한다.
• 두 리스트 중 하나가 추가 되었다면 남은 리스트의 원소들을 순서대로 res 에 추가한 후, 반환한다.

---

이진 검색(Binary Search)

동작 과정

• Divide : 배열을 중간 인덱스를 기준으로 2개의 부분 배열로 나눈다.
• Couquer : 찾으려는 값과 중간 값을 비교하여 적절한 부분 배열에서 탐색한다.
• Combine : 값이 찾아질 때까지 분할과 정복을 반복한다.

예시 코드

def binary_search(arr, target):
    if not arr:
        return -1

    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

코드 설명

• 리스트가 비어있다면 -1을 반환하고, 그렇지 않다면 left 와 right 변수를 초기화 한다.
• while 문을 통해 left 가 right 보다 작거나 같은 동안 반복하고, 이 때 중앙값은 left 와 right 의 합을 2로 나눈 몫으로 설정한다.
• mid 변수에 저장한 중앙값과 찾으려는 값인 target 을 비교하여 같으면 mid 를 반환한다.
• target 보다 값이 작으면 left 를 mid + 1 로 갱신하고, 크면 right 를 mid - 1 로 갱신한다.
• 찾으려는 값이 리스트에 없면 -1을 반환한다.

---

거듭 제곱(Exponentiation)

동작 과정

• Divide : 지수를 2로 나눈다.
• Conquer : 지수의 절반에 해당하는 값을 구한다.
• Combine : 구한 값을 제곱하여 다음 지수의 값으로 사용한다.

예시 코드

def exponentiation(base, exp):
    if exp == 0:
        return 1

    if exp % 2 == 0:
        subproblem = exponentiation(base, exp // 2)
        return subproblem * subproblem
    else:
        subproblem = exponentiation(base, (exp - 1) // 2)
        return subproblem * subproblem * base

코드 설명

• 함수의 입력으로 밑(base)과 지수(exp)가 주어진다.
• 지수가 0이면 밑의 0승은 항상 1이기에 1을 반환한다.
• 지수가 짝수인 경우 재귀적으로 함수를 호출하고, subproblem * subproblem 을 통해 밑의 지수를 계산한다.
• 홀수인 경우 지수 - 1을 반으로 나눈 값을 이용하여 함수를 호출한다.
• subproblem * subproblem * base 연산을 통해 밑의 지수를 계산하다.

---

퀵 정렬(Quick Sort)

동작 과정

• Divide : 주어진 배열에서 피벗(pivot)을 선택한다.
  • 피벗은 배열에서 임의의 위치를 선택하거나, 배열의 첫 번째 원소, 마지막 원소, 중간 원소 등으로 선택할 수 있다.
  • 피벗을 기준으로 작은 값들과 큰 값들을 나누어 2개의 부분 배열로 분할한다.
• Conquer : 각 부분 배열에 대해 재귀적으로 퀵 정렬을 수행한다.
• Combine : 부분 배열들이 정렬된 결과를 결합하여 전체 배열을 정렬한다.

예시 코드

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left, right, equal = [], [], []

    for num in arr:
        if num < pivot:
            left.append(num)
        elif num > pivot:
            right.append(num)
        else:
            equal.append(num)

    return quick_sort(left) + equal + quick_sort(right)

코드 설명

• 피벗을 중간 원소로 선택한다.
• for문을 통해 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누어 분할한다.
• 피벗과 같은 값은 equal 리스트에 추가하고, 결합 단계에서 추가한다.

---

분할 정복을 공부하면서 풀기 좋은 백준 문제를 추천합니다.

2630번: 색종이 만들기

2630번: 색종이 만들기

 

더보기를 누르면 참고한 블로그가 있습니다! chatGPT와 아래 블로그를 참고 했습니다 ㅎㅎ
보다 더 자세하게 알고 싶다면 더보기를 통해 확인해주세요.

https://velog.io/@turtle601/%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5

분할정복(Divide and conquer)이란?

https://velog.io/@nk590/%EB%B6%84%ED%95%A0-%EC%A0%95%EB%B3%B5-Divide-and-Conquer

분할 정복 (Divide and Conquer)

https://loosie.tistory.com/237

[알고리즘] 분할정복 알고리즘 정리 (합병 정렬, 퀵 정렬, 이진 탐색) (Java)

https://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Divide-and-Conquer-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5

[알고리즘] Divide and Conquer (분할정복)