[코딩 테스트] 14일차: 분할 정복

분할 정복 (Divide and Conquer)

분할 정복은 문제를 더 작은 하위 문제로 나누어 해결하고, 그 결과를 합쳐서 원래 문제를 해결하는 알고리즘 기법입니다. 분할 정복의 핵심은 문제를 나누고(Divide), 정복하며(Conquer), 합치는(Combine) 단계로 이루어집니다.

분할 정복의 주요 개념

• 분할(Divide): 문제를 더 작은 하위 문제로 나눕니다.
• 정복(Conquer): 하위 문제를 재귀적으로 해결합니다.
• 합치기(Combine): 하위 문제의 결과를 합쳐 원래 문제의 해를 구합니다.

합병 정렬 (Merge Sort)

합병 정렬은 분할 정복 알고리즘의 대표적인 예제로, 배열을 반으로 나누어 각각을 정렬한 후 병합하여 정렬된 배열을 만듭니다. 시간 복잡도는 O(n log n)입니다.

 

예제: 합병 정렬 구현

JavaScript

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

let arr = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(arr)); // [3, 9, 10, 27, 38, 43, 82]

Python

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):
    result = []
    left_index = 0
    right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] < right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1

    result.extend(left[left_index:])
    result.extend(right[right_index:])
    return result

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr)) # [3, 9, 10, 27, 38, 43, 82]

퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복 알고리즘의 또 다른 예제로, 피벗을 선택하여 배열을 분할하고, 각 부분을 정렬한 후 병합하여 정렬된 배열을 만듭니다. 평균 시간 복잡도는 O(n log n)입니다.

예제: 퀵 정렬 구현

JavaScript

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

let arr = [10, 7, 8, 9, 1, 5];
console.log(quickSort(arr)); // [1, 5, 7, 8, 9, 10]

Python

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

    pivot = arr[-1]
    left = []
    right = []

    for x in arr[:-1]:
        if x < pivot:
            left.append(x)
        else:
            right.append(x)

    return quick_sort(left) + [pivot] + quick_sort(right)

arr = [10, 7, 8, 9, 1, 5]
print(quick_sort(arr)) # [1, 5, 7, 8, 9, 10]

분할 정복의 대표적인 예제

예제 1: 최대 서브어레이 합 (분할 정복)

주어진 배열에서 연속된 부분 배열의 합 중에서 가장 큰 합을 분할 정복을 이용하여 구하세요.

JavaScript

function maxSubArraySum(arr, left = 0, right = arr.length - 1) {
  if (left === right) {
    return arr[left];
  }

  const mid = Math.floor((left + right) / 2);

  const leftMax = maxSubArraySum(arr, left, mid);
  const rightMax = maxSubArraySum(arr, mid + 1, right);
  const crossMax = maxCrossingSum(arr, left, mid, right);

  return Math.max(leftMax, rightMax, crossMax);
}

function maxCrossingSum(arr, left, mid, right) {
  let sum = 0;
  let leftSum = -Infinity;

  for (let i = mid; i >= left; i--) {
    sum += arr[i];
    if (sum > leftSum) {
      leftSum = sum;
    }
  }

  sum = 0;
  let rightSum = -Infinity;

  for (let i = mid + 1; i <= right; i++) {
    sum += arr[i];
    if (sum > rightSum) {
      rightSum = sum;
    }
  }

  return leftSum + rightSum;
}

let arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArraySum(arr)); // 6

Python

def max_sub_array_sum(arr, left=0, right=None):
    if right is None:
        right = len(arr) - 1

    if left == right:
        return arr[left]

    mid = (left + right) // 2

    left_max = max_sub_array_sum(arr, left, mid)
    right_max = max_sub_array_sum(arr, mid + 1, right)
    cross_max = max_crossing_sum(arr, left, mid, right)

    return max(left_max, right_max, cross_max)

def max_crossing_sum(arr, left, mid, right):
    sum = 0
    left_sum = float('-inf')

    for i in range(mid, left - 1, -1):
        sum += arr[i]
        if sum > left_sum:
            left_sum = sum

    sum = 0
    right_sum = float('-inf')

    for i in range(mid + 1, right + 1):
        sum += arr[i]
        if sum > right_sum:
            right_sum = sum

    return left_sum + right_sum

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_sub_array_sum(arr)) # 6

 

예제 2: 행렬 곱셈 (Strassen's Algorithm)

분할 정복을 이용하여 행렬 곱셈을 효율적으로 계산하는 Strassen's Algorithm을 구현하세요.

JavaScript

function strassenMultiply(A, B) {
  const n = A.length;

  if (n === 1) {
    return [[A[0][0] * B[0][0]]];
  }

  const half = Math.floor(n / 2);
  const a = splitMatrix(A, 0, 0, half);
  const b = splitMatrix(A, 0, half, half);
  const c = splitMatrix(A, half, 0, half);
  const d = splitMatrix(A, half, half, half);
  const e = splitMatrix(B, 0, 0, half);
  const f = splitMatrix(B, 0, half, half);
  const g = splitMatrix(B, half, 0, half);
  const h = splitMatrix(B, half, half, half);

  const p1 = strassenMultiply(a, subtractMatrix(f, h));
  const p2 = strassenMultiply(addMatrix(a, b), h);
  const p3 = strassenMultiply(addMatrix(c, d), e);
  const p4 = str

assenMultiply(d, subtractMatrix(g, e));
  const p5 = strassenMultiply(addMatrix(a, d), addMatrix(e, h));
  const p6 = strassenMultiply(subtractMatrix(b, d), addMatrix(g, h));
  const p7 = strassenMultiply(subtractMatrix(a, c), addMatrix(e, f));

  const C11 = addMatrix(subtractMatrix(addMatrix(p5, p4), p2), p6);
  const C12 = addMatrix(p1, p2);
  const C21 = addMatrix(p3, p4);
  const C22 = subtractMatrix(subtractMatrix(addMatrix(p5, p1), p3), p7);

  return combineMatrix(C11, C12, C21, C22);
}

function splitMatrix(matrix, row, col, size) {
  const result = [];
  for (let i = 0; i < size; i++) {
    result[i] = [];
    for (let j = 0; j < size; j++) {
      result[i][j] = matrix[row + i][col + j];
    }
  }
  return result;
}

function addMatrix(A, B) {
  const n = A.length;
  const result = [];
  for (let i = 0; i < n; i++) {
    result[i] = [];
    for (let j = 0; j < n; j++) {
      result[i][j] = A[i][j] + B[i][j];
    }
  }
  return result;
}

function subtractMatrix(A, B) {
  const n = A.length;
  const result = [];
  for (let i = 0; i < n; i++) {
    result[i] = [];
    for (let j = 0; j < n; j++) {
      result[i][j] = A[i][j] - B[i][j];
    }
  }
  return result;
}

function combineMatrix(C11, C12, C21, C22) {
  const n = C11.length;
  const result = [];
  for (let i = 0; i < 2 * n; i++) {
    result[i] = [];
    for (let j = 0; j < 2 * n; j++) {
      if (i < n && j < n) {
        result[i][j] = C11[i][j];
      } else if (i < n && j >= n) {
        result[i][j] = C12[i][j - n];
      } else if (i >= n && j < n) {
        result[i][j] = C21[i - n][j];
      } else {
        result[i][j] = C22[i - n][j - n];
      }
    }
  }
  return result;
}

const A = [
  [1, 2],
  [3, 4]
];

const B = [
  [5, 6],
  [7, 8]
];

console.log(strassenMultiply(A, B));

Python

import numpy as np

def strassen_multiply(A, B):
    n = A.shape[0]

    if n == 1:
        return A * B

    half = n // 2
    a = A[:half, :half]
    b = A[:half, half:]
    c = A[half:, :half]
    d = A[half:, half:]
    e = B[:half, :half]
    f = B[:half, half:]
    g = B[half:, :half]
    h = B[half:, half:]

    p1 = strassen_multiply(a, f - h)
    p2 = strassen_multiply(a + b, h)
    p3 = strassen_multiply(c + d, e)
    p4 = strassen_multiply(d, g - e)
    p5 = strassen_multiply(a + d, e + h)
    p6 = strassen_multiply(b - d, g + h)
    p7 = strassen_multiply(a - c, e + f)

    C11 = p5 + p4 - p2 + p6
    C12 = p1 + p2
    C21 = p3 + p4
    C22 = p5 + p1 - p3 - p7

    C = np.zeros((n, n))
    C[:half, :half] = C11
    C[:half, half:] = C12
    C[half:, :half] = C21
    C[half:, half:] = C22

    return C

A = np.array([
    [1, 2],
    [3, 4]
])

B = np.array([
    [5, 6],
    [7, 8]
])

print(strassen_multiply(A, B))

결론

이번 글에서는 코딩 테스트 준비를 위해 분할 정복에 대해 배웠습니다. 이를 통해 분할 정복의 개념, 합병 정렬과 퀵 정렬의 구현 방법, 그리고 최대 서브어레이 합과 Strassen's Algorithm을 익힐 수 있었습니다. 다음 글에서는 그리디 알고리즘에 대해 알아보겠습니다.

다음 글에서 만나요!