분할정복 알고리즘

분할정복

• n개의 입력을 가진 문제를 k개의 부분 문제로 쪼개서 문제를 해결하는 전략
• 재귀적으로 정의된 문제에 적합
• 분할정복의 3단계
  • 분할: 주어진 문제(problem)를 부분 문제(subproblem)로 쪼개는 것
  • 정복: 부분 문제의 해를 구하는 것 (재귀적 과정)
  • 결합: 부분 문제의 해를 결합해 원래 문제의 해를 구하는 것
    • 결합을 요구하지 않는 경우도 있음 (쾌속 정렬)
• 분할정복의 예시: 쾌속정렬, 합병정렬, 정수 곱하기, 행렬 곱하기, 이진탐색, 중간값 찾기 등

기본 구조

• 대부분의 분할정복 알고리즘은 재귀호출을 통해서 구현됨
• 지나친 Recursive Call(재귀호출)의 문제 → 메모리 낭비, Stack Overflow

기본 코드 구조 예시

global n, A (1:n);
DnC (int p, int q) {
    int m;
    if (SMALL (p, q))
        return G (p, q);
    
    m ← DIVIDE (p, q);
    return COMBINE ( DnC (p, m), DnC (m+1, q));
}

• 문제(DnC): (p ~ q)까지의 크기를 가진 배열에서 문제를 해결
• 입력: (p ~ q)까지의 크기를 가진 배열
• 분할(Divide): (p ~ q)의 배열을 (p ~ m), (m+1 ~ q)의 부분 배열로 나눔
• 정복(DnC): (p ~ m), (m+1 ~ q) 크기의 부분 배열에서 문제를 해결
• 결합(Combine): (p ~ m), (m+1 ~ q) 크기의 부분 배열에서 얻은 답을 결합
• 예외 처리(Degenerate Case): 문제 크기가 분할정복을 시도할 정도로 크지 않으면 바로 문제를 풀 것

분할정복의 특징

• 재귀적 호출의 특징
• Same Format: 문제를 분할하여 자기 자신을 호출하는 방식이 같은 형식을 따라야 함
• Reduced Problem Size: 문제를 분할할 때마다 문제의 크기가 감소해야 함
• Degenerate Case: 문제를 분할할 필요가 없을 정도로 작은 문제는 직접 문제를 해결해야 함

---

이진탐색

• Binary Search
• 입력: 오름차순으로 정렬된 숫자들로 구성된 리스트, 내가 찾는 원소 x
• 출력: 원소 x가 리스트에 있으면 x의 index를 리턴, 없으면 NULL(-1)을 리턴

기본 구조

int *A;
int binary_search (int s, int e, int x) {
    if (s == e)		// degenerate case
        if (A[s] == x))
            return s;
        else
            return NULL;
    m ← (s+e)/2;	// divide
    if (A[m] ==x)	// conquer
        return m;
    else if (A[m] > x)
        return binary_search (s, m-1, x);
    else
        return binary_search (m+1, e, x);
}

• 문제(Binary Search): (s~e)까지의 크기를 가진 배열에서 x가 있는지 찾기
• 입력: (s~e)까지의 크기를 가진 배열과 x, 처음에는 s=0, e=n-1 (n: 배열의 크기)
• 분할: m = (s+e)/2
• 정복: (s, m-1), (m+1, e)에 대해서 Binary Search는 두 부분 배열 중 하나만 호출하는 독특한 분할정복
• 결합: Binary Search는 결합을 요구하지 않는 독특한 분할정복
• 예외 처리: 배열의 크기가 충분히 작으면 → 배열의 크기가 1이면 → s == e이면 바로 문제를 해결

---

토너먼트

• 승자는 올라가고 패자는 남는 형태의 경기
• 토너먼트를 진행할수록 참가하는 팀의 수 감소
  • 전체 팀의 수를 n으로 설정
  • 현재 진행할 팀의 수는 i
  • team[0 ~ (i-1)] → win[0 ~ (i/2 - 1)]

int tournament (int n, int *team) {
    int i, j;
    for (i=n; i>1; i/=2) {
        /* do the matches */
        for (j=0; j<i; j+=2)
            win[j/2] = winner(team[j], team[j+1]);
        copy(team, win);
    }
    return win[0];
}

분할정복을 이용한 토너먼트 구현

• 토너먼트의 새로운 이해: Bottom-up → Top-down
• 문제: 8개 팀 중에서 챔피언을 찾기
  • 부분 문제: 4개 팀 중에서 챔피언을 찾은 다음 이 둘의 대결
• Champion8() → Champion4() → Champion2()

int Champion8({CRO, BRA, NET, ARG, MOR, POR, ENG, FRA}) {
    Lwinner = Champion4({CRO, BRA, NET, ARG});
    Rwinner = Champion4({MOR, POR, ENG, FRA});
    
    return Winner (Lwinner, Rwinner);
}

int Champion4({CRO, BRA, NET, ARG}) {
    Lwinner = Champion4({CRO, BRA});
    Rwinner = Champion4({NET, ARG});
    
    return Winner (Lwinner, Rwinner);
}

int Champion2({CRO, BRA}) {
    /* 분할 과정 필요 없음 */
    return Winner (CRO, BRA);
}