[Python Algorithm] Ch4. 축소 정복 기법

4.0 축소 정복

축소정복이란?

문제를 해결하기 위해 해당 문제와 더 작은 문제간의 관계를 이용하여 주어진 문제를 해결하는 전략

• 하향식 축소 정복 기법: 순환구조 사용(재귀)
• 상향식 축소 정봅 기법: 반복구조 사용

축소정복 기법의 문제의 크기

문제의 크기가 줄어드는 방식에 따라 세 가지로 나뉨

• 고정 크기 축소
• 고정 비율 축소
• 가변 크기 축소

4.1 삽입 정렬

삽입정렬이란?

임의의 데이터를 정렬이 된 구간의 맨 앞부터 비교해나가면서 정렬하는 방법

삽입 정렬 알고리즘

def insertion_sort(A):
    n = len(A)

    for i in range(1, n):   # 키를 잡는 과정
        key = A[i]
        j = i - 1

        # 왼쪽으로 나아가면서 정렬 -> key값이 A[j]보다 적을 시 종료
        while (j >= 0 and A[j] > key):
            A[j + 1] = A[j]     # 한 칸 우측으로 이동
            j -= 1
        A[j + 1] = key


data = [5, 3, 8, 4, 9, 1, 6, 2, 7]

• 삽입정렬 알고리즘의 복잡도(최악)는 O(n^2)

4.2 위상 정렬

위상 정렬이란?

방향 그래프와 연관, 정점들을 순서에 맞게 나열하는 것

• 그래프에 사이클 존재 시 정렬 불가능

DFS 기반 알고리즘

4.3 이진 탐색

4.4 거듭제곱 문제

4.5 k번째 작은 수 찾기

4.6 축소 정복 기법의 추가적인 예