Jiyeon Kang

It’s my CV

13 minute read


분할 정복(Divide and Conquer)과 기본 알고리즘

Divide and Conquer 개념 및 Top-Down 방식

[ 분할정복법 ]

문제를 더 작은 하위 문제로 나누고, 각 하위 문제를 독립적으로 해결한 뒤, 그 결과를 합쳐 원래 문제의 해답을 구하는 알고리즘 설계 기법
• Divide (분할): 문제를 더 작은 하위 문제로 나눔
• Conquer (정복): 하위 문제를 재귀적으로 해결
• Combine (결합): 하위 문제의 해를 이용해 전체 문제의 해를 구성


[ top-down 방식 ]

• 하나의 문제 인스턴스를 두 개 이상의 더 작은 인스턴스로 나눔
• 더 작은 인스턴스들의 해답을 쉽게 구할 수 있으면, 이 해답을 결합하여 원래 문제의 해답을 얻을 수 있음

참고 bottop-up 방식
• 가장 작은 문제부터 시작해서 차례대로 큰 문제를 해결
• 작은 문제의 결과를 저장하고 재사용 (동적 계획법에서 자주 사용)
• 반복문을 이용해 구현됨
• 예: 동적 계획법(Dynamic Programming), 피보나치 수열의 DP 구현



Binary Search (이진 탐색) - 재귀적

[ Binary Search 문제 ]
정의 정렬된(비감소 순서) 배열에서 키 x의 위치를 찾는 문제

방법 배열의 가운데 항목과 x를 비교함
• 같으면 알고리즘 종료
• 다르면 배열을 두 부분으로 나눔: 가운데 항목의 왼쪽 부분, 가운데 항목의 오른쪽 부분

핵심 단계
• 배열을 절반 크기의 두 부분으로 나눈다: x가 가운데보다 작으면 왼쪽 부분, 크면 오른쪽 부분 선택
• 해당 부분에서 x가 있는지 확인, 크기가 충분히 작지 않으면 재귀 호출 사용
• 해당 부분에서의 결과가 전체 배열에 대한 해답이 됨
• 특이사항 작은 인스턴스로 나누지만, 그들의 출력을 결합하지 않음


[ 이진 탐색 알고리즘 설계 ]
기본 설계 원칙
• 더 작은 인스턴스의 해로부터 원래 문제의 해를 구하는 방법 개발
• 더 작은 인스턴스가 도달하게 될 종료 조건 설정
• 종료 조건에 해당하는 경우의 해 결정

프로그래밍 시 유의사항
• 이 자료에서는 재귀 호출 중 값이 변할 수 있는 변수들만 재귀 루틴의 매개변수로 사용
• 꼬리 재귀(tail-recursion) 사용 요구: 재귀 호출 이후 연산 없음, 꼬리재귀를 반복문 기반 알고리즘으로 전환 시 메모리 효율성 ↑
• 주의 재귀 루틴의 경우, 스택에 쌓이는 activation record 수는 재귀 호출이 도달한 깊이에 따라 결정


[ 예시 ]
문제 정렬된 배열에서 x = 18을 찾는 과정

[10 12 13 14 18 20 25 27 30 35 40 45 47]

- 25와 비교 → x < 25 → 왼쪽 선택
- 13과 비교 → x > 13 → 오른쪽 선택
- 18과 비교 → x = 18 → 탐색 성공

의사코드

/*
problem: 크기가 n인 정렬된 배열에서 x 찾기
input: 정수 n, 정렬된 배열 S[1...n], 탐색 키 x 
output: x가 있는 위치(없으면 0 반환)
*/
index location(index low, index high)
{
    index mid;
    if (low > high)
        return 0;
    else {
        mid = ⌊(low + high) / 2⌋;
        if (x == S[mid])
            return mid;
        else if (x < S[mid])
            return location(low, mid - 1);
        else
            return location(mid + 1, high);
    }
}


[ 최악의 시간 복잡도 분석 ]

$W(n) = W(n/2) + 1$
• $W(n/2)$: 재귀호출에서의 비교
• $1$: top level에서의 비교

👉 $t_n = \log_2 n + 1 \quad$ 몇 개의 값을 통해 확인
$t_2 = t_{2/2} + 1 = t_1 + 1 = 1 + 1 = 2$
$t_4 = t_{4/2} + 1 = t_2 + 1 = 2 + 1 = 3$
$t_8 = t_{8/2} + 1 = t_4 + 1 = 3 + 1 = 4$
$t_{16} = t_{16/2} + 1 = t_8 + 1 = 4 + 1 = 5$

귀납법 적용
귀납 기초 (Induction base) $t_1 = 1 = \log 1 + 1$
귀납 단계 (Induction step) when $2n$
• (재귀는 2의 거듭제곱에 대해서만 정의됨)
• $t_{2n} = \log 2n + 1$
증명 과정 $t_{2n} = t_{2n/2} + 1 = t_n + 1$
$= \log n + 1 + 1$
$= \log n + \log 2 + 1$
$= \log(2n) + 1$



Merge Sort (합병 정렬)

[ 예시 ]


[ 의사코드: not in-place ]
예시 1 - mergesort

// 문제: n개의 키를 비감소(non-decreasing) 순서로 정렬하라
// 입력: 양의 정수 n, 인덱스 1부터 n까지의 키 배열 S
// 출력: 비감소 순서로 정렬된 키들을 포함하는 배열 S
void mergesort (int n, keytype S[]) {
    if (n > 1) {
        const int h = ⌊n/2⌋, m = n - h;
        keytype U[1..h], V[1..m];

        // S를 절반씩 나누어 각각 U와 V로 복사
        copy S[1] through S[h] to U[1] through U[h];
        copy S[h+1] through S[n] to V[1] through V[m];

        // 각각 재귀적으로 정렬
        mergesort(h, U);
        mergesort(m, V);

        // 정렬된 두 배열을 병합
        merge(h, m, U, V, S);
    }
}

예시 2 - merge

// 문제: 정렬된 두 배열을 하나의 정렬된 배열로 병합하라
// 입력: 양의 정수 h, m
//      인덱스 1부터 h까지의 정렬된 배열 U
//      인덱스 1부터 m까지의 정렬된 배열 V
// 출력: 인덱스 1부터 h + m까지의 정렬된 배열 S, U와 V의 모든 원소 포함

/*
inplace sort가 아니다
→ 정렬 과정에서 새로운 배열(U, V)을 계속 만들어서 공간을 추가로 사용함
→ 특히, 재귀 호출 중마다 메모리가 쌓이므로 활성 스택도 증가
*/
void merge (int h, int m, const keytype U[], const keytype V[], keytype S[]) {
    index i, j, k;
    i = 1; j = 1; k = 1;

    while (i <= h && j <= m) {
        if (U[i] < V[j]) {
            S[k] = U[i];
            i++;
        } else {
            S[k] = V[j];
            j++;
        }
        k++;
    }

    // 남은 요소 복사
    if (i > h)
        copy V[j] through V[m] to S[k] through S[h+m];
    else
        copy U[i] through U[h] to S[k] through S[h+m];
}


[ 의사코드: in-place ]
예시 1 - Mergesort 2

/*
문제: n개의 키를 비감소(non-decreasing) 순서로 정렬하라
입력: 양의 정수 n, 인덱스 1부터 n까지의 키 배열 S
출력: 정렬된 상태의 배열 S
*/

void mergesort2(index low, index high) {
    index mid;
    if (low < high) {
        mid = ⌊(low + high)/2⌋;
        mergesort2(low, mid);
        mergesort2(mid + 1, high);
        merge2(low, mid, high);
    }
}

예시 2 - Merge 2

// U는 정렬을 위한 임시 배열 (in-place라 하더라도 공간은 일부 사용)
// 최종적으로 U의 내용을 다시 S로 복사 → 원본 배열이 정렬됨
/*
문제: Mergesort 2에서 생성된 두 정렬된 부분 배열을 병합하라
입력: 인덱스 low, mid, high
     배열 S[low..high] (두 부분 [low..mid], [mid+1..high]는 각각 정렬된 상태)
출력: 전체 범위 S[low..high]가 정렬된 상태로 병합됨
*/

void merge2(index low, index mid, index high) {
    index i, j, k;
    keytype U[low..high]; // 병합을 위한 임시 배열

    i = low; j = mid + 1; k = low;

    while (i <= mid && j <= high) {
        if (S[i] < S[j]) {
            U[k] = S[i];
            i++;
        } else {
            U[k] = S[j];
            j++;
        }
        k++;
    }

    if (i > mid) {
        move S[j] through S[high] to U[k] through U[high];
    } else {
        move S[i] through S[mid] to U[k] through U[high];
    }

    move U[low] through U[high] to S[low] through S[high];
}



Quick Sort (퀵 정렬)

[ 퀵 정렬 ]

피벗을 기준으로 나누고, 각각 정렬하는 방식


[ 예시 ]

//배열을 분할: 피벗 항목보다 작은 모든 항목은 왼쪽에, 큰 항목은 오른쪽에 오도록 배열을 나눈다
//서브 배열 정렬

    [15 22 13 27 12 10 20 25]
            /         |         \
    [10 13 12]     [15]    [22 27 20 25]
        /                      \
    [10]                  [20] [22] [27 25]
        \                             \
    [12 13]                         [25 27]
배열내부 설명
15 22 13 27 12 10 20 25 처음
10 13 12 [15] 22 27 20 25 피벗(15)을 기준으로 배열 나누기
• 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽
10 13 12 → 10 12 13,
22 27 20 25 → 20 22 25 27		 두 부분 배열 각각 정렬
15 22 13 27 12 10 20 25 정렬


[ 시간 복잡도 ]
Partition의 시간복잡도
입력 배열의 크기에 따라 $T(n) = n - 1$ (피벗 빼고 나머지 비교)

최악의 경우 시간 복잡도

피벗이 항상 가장 작거나, 가장 큰 값일 경우
• 정렬이 한쪽으로만 이루어짐
• 왼쪽 서브배열(0개), 오른쪽 서브배열(n-1개)

👉 $W(n) = T(0) + T(n-1) + (n-1)$
$W(n)$: 원소 n개를 정렬하는 데 걸리는 최악의 경우 시간
$T(0)$: 왼쪽 부분 배열 정렬 시간 (비어있음 → 0)
$T(n-1)$: 오른쪽 배열 정렬 시간 (피벗 제외 나머지 모두)
$n-1$: 파티션 비용

👉 재귀적 방정식
$T(n) = T(n - 1) + n - 1, (for n > 0)$
$T(0) = 0$
solution: $T(n) = n(n-1)/2$ > $O(n^2)$ 시간복잡도

평균의 경우 시간 복잡도

모든 위치가 피벗이 될 확률이 동일($p = 1/n$)하다고 가정할 때, A(n)
$A(n) = \sum_{p=1}^{n} \frac{1}{n} \left[ A(p-1) + A(n-p) \right] + (n - 1)$
• 앞부분: 피벗 위치 p에 따라 양쪽 서브배열을 정렬하는 평균 시간
• 뒤의 (n - 1)은 파티션하는 데 걸리는 시간

• 근사화하면
$A(n) \approx (n + 1) \cdot 2 \ln n \approx 1.38(n + 1)\log n \in \Theta(n \log n)$
• 평균적으로 매우 효율적인 정렬 알고리즘


[ 의사코드 ]

// 제자리 파티셔닝 방식이라 별도 배열 안 씀
// 선형 시간 복잡도
/*
문제: Quicksort를 위해 배열 S를 파티션(partition)하라
입력: 두 인덱스: low와 high, 배열 S[low ... high] (부분 배열)
출력: pivotpoint: 정렬 후 피벗이 위치하게 되는 인덱스
*/
void partition(index low, index high, index& pivotpoint) {
    index i, j;
    keytype pivotitem;

    // 피벗 항목을 배열의 첫 번째 원소로 선택
    pivotitem = S[low];
    j = low;

    // low+1부터 high까지 반복하며 파티션 수행
    for (i = low + 1; i <= high; i++) {
        if (S[i] < pivotitem) {
            j++;
            exchange S[i] and S[j]; // 작은 값들을 앞으로 모음
        }
    }

    // 피벗의 최종 위치를 저장
    pivotpoint = j;
    exchange S[low] and S[pivotpoint]; // 피벗을 제자리에 배치
}



Factorial

[ 의사코드 ]

/*
문제: n! = n × (n-1) × (n-2) × ... × 3 × 2 × 1 (단, n ≥ 1), 0! = 1
입력: 음이 아닌 정수 n
출력: n!
*/
int fact(int n) {
    if (n == 0)
        return 1;
    else
        return n * fact(n - 1);
}


[ 팩토리얼 알고리즘의 효율성 ]
1) 곱셈 횟수를 재귀식(recurrence equation) 으로 표현
재귀 방정식: 재현식

$t_n = t_(n-1) + 1$
• $t_n$: 재귀호출 시 곱셈 횟수
• $1$: 최상위 수준에서의 곱셈 1회
→ 함수의 값이 작은 n의 값을 이용해 큰 n의 값을 구함

초기 조건: $t_0 = 0$ (0! = 1이므로 곱셈 없음)
n이 클 때의 $t_n$ 계산 예시
• t₁ = t₀ + 1 = 0 + 1 = 1
• t₂ = t₁ + 1 = 1 + 1 = 2
• t₃ = t₂ + 1 = 2 + 1 = 3
결론: tₙ을 t₀부터 반복 계산하는 건 비효율적이다


2) 곱셈 횟수를 후보 해(candidate solution) 를 통해 구하기
• $t_n$에 대한 명시적 표현(해)을 얻기: $t_n = t_(n-1) + 1$
👉 귀납법으로 해를 찾는 것은 불가능하지만, 후보 해가 맞는지를 확인하는 데는 귀납법을 사용할 수 있음
• 초반 몇 개 값을 확인

t₁ = t₀ + 1 = 0 + 1 = 1
t₂ = t₁ + 1 = 1 + 1 = 2
t₃ = t₂ + 1 = 2 + 1 = 3

• 후보 해 추정: $t_n = n$

3) 후보 해의 정당성 증명
n = 0: $t_0 = 0$
귀납가정(Induction Hypothesis): $t_n = n$
귀납단계(Induction Step): $t(n+1) = n + 1$이 참임을 증명
결론: $t_(n+1) = t_((n+1)-1) + 1 = t_n + 1 = n + 1$




재귀식

재귀식이란

[ 재귀식의 정의 ]

어떤 수열의 다음 항이 이전 항들에 의해 정의되는 식


재귀식(Recurrence)의 종류와 해 구하기

[ 용어정리 ]

용어 설명
재귀식 어떤 수열의 다음 항이 이전 항들에 의해 정의되는 식
선형(Linear) 미지수가 곱해지지 않고, 제곱(제곱근) 같은 비선형 연산이 없고, 각 항이 1차식으로 되어있는 경우
허용되지 않음: $t_{n-i}^2$, $t_{n-i}t_{n-j}$
c가 1이 아닌 양의 상수일 때, 이것도 안 됨: $t_c{n-i}$
동차(Homogeneous) 등식의 오른쪽에 독립된 항(=외부에서 들어온 값, 상수나 함수)이 없다
• 동차: $a_n = 2a_{n-1} + 3a_{n-2}$
• 비동차: $a_n = 2a_{n-1} + 5$
상수계수(Equations with Constant Coefficient) 항 앞의 계수가 변하지 않는 상수
영 함수 (Zero function) $f(n) = 0$
후보해 (Candidate Solution) 문제를 풀기 위해 가설로 세운 해 (검증 필요)
일반해 (General Solution) 재귀식 전체를 만족하는 해, 상수 포함해서 모든 해를 나타내는 형태


[ 재귀식의 종류 ]

종류 설명
동차(동질) 재귀식
(Homogeneous Recurrence)		 재귀식의 오른쪽이 항들의 조합으로만 이루어져 있고, 독립된 상수항이 없는 경우
비동차(비동질) 재귀식
(Nonhomogeneous Recurrence)		 오른쪽에 독립된 항 존재
선형 동차 상수 계수 재귀식 이전 항들의 선형 결합 + 계수가 상수 + 동차
선형 동차 재귀식 각 항이 선형으로 나타나고, 상수항이 없고, 이전 항들의 조합으로 구성된 식
$a_bt_n + a_1t_{n-1} + … + a_Kt_{n-k} = 0$
$k$와 $a_i$는 상수
동차 선형 상수 계수 재귀식 $7t_n - 3t_{n-1} = 0$
$6t_n - 5t_{n-1} + 8t_{n-2} = 0$
$8t_n - 4t_{n-3} = 0$
비동차 선형 재귀식 각 항이 선형으로 나타나며, 오른쪽에 독립된 항(상수나 함수)이 존재하는 재귀식
상수 계수를 갖는 비동차 선형 재귀식 nonhomogeneous linear recurrence equation with constant coefficients
다음 형태의 점화식 $a_0 t_n + a_1 t_{n-1} + \cdots + a_k t_{n-k} = f(n)$
에서 $k$와 $a_i$들은 상수이고 $f(n)$은 0이 아닌 어떤 함수


[ 재귀식을 푸는 법]

• 수학적 귀납법 (Induction): 귀납적 방식으로 일반해가 맞는지 증명
• 특성방정식 (Characteristic Equation): 선형 동차 상수 계수 재귀식에서 일반해를 구함
• 곱셈을 이용한 대입 (Substitution): 식을 반복 대입해 일반항 추정
• 변수 치환 (Change of Variables): 복잡한 식을 단순화하기 위해 변수 변환
• 생성 함수 (Generating Functions): 함수 형태로 수열 표현 후 해석
• 마스터 정리 (Master Theorem): 분할정복 알고리즘의 시간 복잡도 분석용
• 비동차 재귀식 해법: 비동차 항이 있는 경우, 일반항에 비슷한 꼴의 특수해를 추가


[ 정리 ]

정리 B.1 (Theorem B.1)
$a_0t_n + a_1t_{n-1} + … + a_kt_{n-k} = 0$
👉 여기서 $k$와 각 $a_i$들은 상수일 때, 이를 상수 계수로 갖는 동차 선형 재귀식
• 선형(linear)인 이유: 모든 항 $t_1$가 1차로만 등장하기 때문
• 다음 항은 포함하지 않음: $t_{2n-i}, t_{n-1}t{n-j}$
• $c$가 1이 아닌 양의 상수일 경우, 다음 항도 포함하지 않음: $t_{c(n-i)}$
정리 B.2 (Theorem B.2)
• $r$이 상수 계수를 가진 동차 선형 점화식의 특성 방정식의 중복도 $m$을 가진 근이라면,
• $t_n = r^n, t_n = n r^n, t_n = n^2 r^n, t_n = n^3 r^n, \dots, t_n = n^{m-1} r^n$ 는 모두 점화식의 해가 됨
• 그러므로 이러한 해 각각은 점화식의 일반해(정리 B.1에서 제시됨)에 포함
정리 B.3 (Theorem B.3)
• 다음 형태의 비동차 선형 점화식은 다음과 같은 특성 방정식을 갖는 동차 선형 점화식으로 변환할 수 있다
$a_0 t_n + a_1 t_{n-1} + \cdots + a_k t_{n-k} = b^n p(n)$ => $(a_0 r^k + a_1 r^{k-1} + \cdots + a_k)(r - b)^{d+1} = 0$
• 여기서 $d$는 $p(n)$의 차수(Degree)
• 이 특성 방정식은 두 부분으로 이루어진다
(해당 동차 점화식의 특성 방정식, 비동차 항으로부터 유도된 항)
• 만약 오른쪽 항에 $b^n p(n)$ 같은 항이 둘 이상 있다면:
각각의 항이 특성 방정식에 하나의 항을 더하게 된다



재귀식의 해 구하기 - 귀납법

[ 재귀식 해 구하기 예시 ]
1) 예제 1

구분 내용
주어진 재귀식 $t_n = t_{n/2} + 1$(단, (n > 1), (n)은 2의 거듭제곱)
$t_1 = 1$
점검 (Inspection) $t_2 = t_{2/2} + 1 = t_1 + 1 = 1 + 1 = 2$
$t_4 = t_{4/2} + 1 = t_2 + 1 = 2 + 1 = 3$
$t_8 = t_{8/2} + 1 = t_4 + 1 = 3 + 1 = 4$
$t_{16} = t_{16/2} + 1 = t_8 + 1 = 4 + 1 = 5$
추정 (Estimation) $t_n = \log n + 1$
정당성 증명 (Proof of the correctness) $n = 1$일 때: $t_1 = 1 = \log 1 + 1$
귀납 가정 (Induction hypothesis) $t_n = \log n + 1$
귀납 단계 (Induction step) $2n$을 대입하여 다음을 보여야 함:
$t_{2n} = \log (2n) + 1$
결론 (Conclusion) $t_{2n} = t_{(2n)/2} + 1 = t_n + 1 = \log n + 1 + 1$
$= \log n + \log 2 + 1$
$= \log (2n) + 1$


2) 예제 2

구분 내용
주어진 재귀식 $t_n = 7t_{n/2}$ (단, $n > 1$ ,$n$은 $2$의 거듭제곱)
$t_1 = 1$
점검 $t_2 = 7t_{2/2} = 7t_1 = 7$
$t_4 = 7t_{4/2} = 7t_2 = 7^2$
$t_8 = 7t_{8/2} = 7t_4 = 7^3$
$t_{16} = 7t_{16/2} = 7t_8 = 7^4$
추정 $t_n = 7^{\log n}$
정당성 증명 $n = 1$ 일 때: $t_1 = 1 = 7^0 = 7^{\log 1}$
귀납 가정 $t_n = 7^{\log n}$
귀납 단계 $t_{2n} = 7^{\log (2n)}$
결론 $t_{2n} = 7t_{(2n)/2}
= 7t_n = 7 \times 7^{\log n} = 7^{1 + \log n}
= 7^{\log 2 + \log n} = 7^{\log (2n)}$
$\therefore t_n = n^{\log 7} \approx n^{2.81}$ (왜냐하면 $7^{\log n} = n^{\log 7}$)


3)명확한 후보 해(candidate solution)가 없는 경우

구분 내용
주어진 재귀식 $t_n = 2t_{n/2} + n - 1$ (단, $n > 1, n$은 2의 거듭제곱)
$t_1 = 0$
점검 (Inspection) $t_2 = 2t_{2/2} + 2 - 1 = 2t_1 + 1 = 1$
$t_4 = 2t_{4/2} + 4 - 1 = 2t_2 + 3 = 5$
$t_8 = 2t_{8/2} + 8 - 1 = 2t_4 + 7 = 17$
$t_{16} = 2t_{16/2} + 16 - 1 = 2t_8 + 15 = 49$
추정 (Estimation) ???

You may also enjoy