알고리즘 3주차

분할 정복 알고리즘 정의

주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘

분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산
이들의 해를 취합하여 원래 문제의 해를 얻음 그냥 넣어보기!!

부분 문제와 부분 해

분할된 입력에 대한 문제를 부분 문제 (subproblem)
부분 문제의 해를 부분 해
부분 문제는 더 이상 분할할 수 없을 때까지 분할

분할 정복 알고리즘의 분류

분할 정복 알고리즘은 분할되는 부분 문제의 수와 부분 문제의 크기에 따라서 다음과 같이 분류

문제가 a개로 분할되고, 부분 문제의 크기가 1/b로 감소하는 알고리즘

a=b=2인 경우: 합병 정렬, 최근접 점의 쌍 찾기, 공제선문제4
a=3, b=2인 경우: 큰 정수의 곱셈
a=4, b=2인 경우: 큰 정수의 곱셈
a=7, b=2인 경우: 스트라센(Strassen)의 행렬 곱셈 알고리즘

문제가 2개로 분할되고, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

퀵 정렬

문제가 2개로 분할되나, 그 중에 1개의 부분 문제는 고려할 필요가 없으며, 부분 문제의 크기가 1/2로 감소하는 알고리즘

이진 탐색

문제가 2개로 분할되나, 그 중에 1개의 부분 문제는 고려할 필요가 없으며, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

선택 문제 알고리즘

부분 문제의 크기가 1, 2개씩 감소하는 알고리즘

삽입 정렬, 피보나치 수의 계산

합병 정렬

합병 정렬은 입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 1/2로 감소하는 분할 정복 알고리즘

n개의 숫자들을 n/2개씩 2개의 부분 문제로 분할
각각의 부분 문제를 순환으로 합병 정렬
2개의 정렬된 부분을 합병하여 정렬(정복) 합병 과정이 문제를 정복하는 것

합병

2개의 각각 정렬된 숫자들을 1개의 정렬된 숫자로 합치는 것
배열 A: 6 14 18 20 29
배열 B: 1 2 15 25 30 45
⇨ 배열 C: 1 2 6 14 15 18 20 25 29 30 45

알고리즘

MergeSort(A,p,q)
입력: A[p]~A[q]
출력: 정렬된 A[p]~A[q]

if ( p < q ) { // 배열의 원소의 수가 2개 이상이면
k = ⌊(p+q)/2⌋ // k는 중간 원소의 인덱스
MergeSort(A,p,k) // 앞부분 순환 호출
MergeSort(A,k+1,q) // 뒷부분 순환 호출
A[p]~A[k]와 A[k+1]~A[q]를 합병 }

합병 정렬의 단점

대부분의 정렬 알고리즘들은 입력을 위한 메모리 공간과 O(1) 크기의 메모리 공간만을 사용하면서 정렬 수행

O(1) 크기의 메모리 공간이란 입력 크기 n과 상관없는 크기의 공간(예를 들어, 변수, 인덱스 등)을 의미

합병 정렬의 공간 복잡도: O(n)

입력을 위한 메모리 공간 (입력 배열)외에 추가로 입력과 같은 크기의 공간 (임시 배열)이 별도로 필요.
2개의 정렬된 부분을 하나로 합병하기 위해, 합병된 결과를 저장할 곳이 필요하기 때문

요약

합병 정렬은 외부 정렬의 기본이 되는 정렬 알고리즘

연결 리스트에 있는 데이터를 정렬할 때에도 퀵 정렬이나 힙 정렬 보다 훨씬 효율적

멀티코어(Multi-Core) CPU와 다수의 프로세서로 구성된 그래픽 처리 장치(Graphic Processing Unit)의 등장으로 정렬 알고리즘을 병렬화하는 데 에 합병정렬 알고리즘이 활용

import java.util.Arrays;
public class MergeSort {

  public static void main(String[] args) {
      int[] arr = {10, 5, 3, 8, 6, 1, 9, 2, 7, 4}; // 정수를 원소로 갖는 배열을 생성한다.
      System.out.println("Before sorting: " + Arrays.toString(arr));// Arrays.toString(arr) 메서드를 이용하여 'arr' 배열을 출력한다. toString() 메서드는 배열의 원소를 문자열로 변환한다. 
      mergeSort(arr, 0, arr.length - 1);// mergeSort 메서드를 이용하여 배열을 정렬한다. 이때 배열의 첫 인덱스와 마지막 인덱스를 전달한다.
      System.out.println("After sorting: " + Arrays.toString(arr)); 
  }

  public static void mergeSort(int[] A, int p, int q) {
      if (p < q) {
          int k = (p + q) / 2; // 배열의 중간 원소인 k를 계산한다.
          mergeSort(A, p, k); 
          mergeSort(A, k + 1, q); // 앞부분 배열과 뒷부분 배열을 정렬한다. 앞부분 배열은 A[p]에서 A[k] 뒷 부분 배열은 A[k+1]에서 A[q]이다.
          merge(A, p, k, q); // 앞부분과 뒷부분을 병합한다.
      } 
  }


  private static void merge(int[] A, int p, int k, int q) {
      int i = p;
      int j = k + 1;
      int[] temp = new int[q - p + 1];
      int index = 0;
      while (i <= k && j <= q) {
          if (A[i] < A[j]) {
              temp[index++] = A[i++];
          } else {
              temp[index++] = A[j++]; 
          } // arr 배열에서 i와j 위치의 값중 작은 값을 temp에 저장하고, 해당 위치를 k 변수로 업데이트한다.
      }
      while (i <= k) {
          temp[index++] = A[i++];
      }
      while (j <= q) {
          temp[index++] = A[j++];
      }
      for (int m = p; m <= q; m++) {
          A[m] = temp[m - p];
      }
  }
}// temp 배열의 값을 arr 배열에 복사합니다. x는 start부터 end까지 증가하면서, temp[x-start]의 값을 arr[x]에 저장한다.

주어진 입력 배열 A의 p부터 q까지를 Merge Sort하는 mergeSort 함수를 구현합니다. 함수 내부에서는 배열의 길이가 2개 이상일 때만 정렬을 수행하도록 하고, 먼저 중간 원소의 인덱스 k를 계산합니다. 그리고 앞부분(A[p]부터 A[k])과 뒷부분(A[k+1]부터 A[q])을 각각 순환 호출하여 정렬합니다. 마지막으로, 앞부분과 뒷부분을 합병하는 merge 함수를 호출하여 두 부분을 합칩니다.
merge 함수는 앞부분(A[p]부터 A[k])과 뒷부분(A[k+1]부터 A[q])을 병합하는 함수입니다. 두 부분에서 각각 가장 작은 원소부터 비교하여 작은 순서대로 temp 배열에 복사합니다. 그리고 두 부분 중 어느 한 부분의 모든 원소를 다 처리한 경우에는, 나머지 부분의 원소들을 그대로 temp 배열에 복사합니다. 마지막으로, temp 배열에 저장된 정렬된 원소들을 다시 입력 배열 A에 저장합니다.

분할 정복 알고리즘

분할 정복 알고리즘 정의

분할 정복 알고리즘의 분류

합병 정렬

합병

알고리즘

합병 정렬의 단점

요약

CATALOG

FEATURED TAGS

FRIENDS