2.3 알고리즘의 설계

2.3 알고리즘의 설계

 

분할정복

분할 : 현재 문제를 같은 문제를 다루는 다수의 부분 문제로 분할한다.

정복 : 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 충분히 작으면 직접적인 방법으로 푼다.

결합 : 부분 문제의 해를 결합하여 원래 문제의 해가 되도록 만든다.

 

병합정렬

출처 : CLRS

분할정복 시간복잡도

출처 : CLRS

---

 

연습문제

 

2.3-1

2.3-2

def merge_without_sentinels(A, p, q, r):
    nL = q - p + 1  # Length of A[p...q]
    nR = r - q      # Length of A[q+1...r]

    L = [0] * nL    # Initialize arrays L and R
    R = [0] * nR

    for i in range(nL):  # Copy A[p...q] into L
        L[i] = A[p + i]

    for j in range(nR):  # Copy A[q+1...r] into R
        R[j] = A[q + j + 1]

    i = 0  # Index for L
    j = 0  # Index for R
    k = p  # Index for A

    while i < nL and j < nR:
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        k += 1

	# 병합루프 2번
    while i < nL:
        A[k] = L[i]
        i += 1
        k += 1

    while j < nR:
        A[k] = R[j]
        j += 1
        k += 1

# Example usage
A = [3, 5, 8, 10, 2, 6, 7, 9]
merge_without_sentinels(A, 0, 3, 7)
print(A)  # Output: [2, 3, 5, 6, 7, 8, 9, 10]

 

2.3-3

2.3-4

맨끝 요소부터 탐색하면서 더 크면 이동하는식으로 구현

def recursion_insertion_sort(A, n):
    if n > 0:
        recursion_insertion_sort(A, n-1)

        key = A[n]
        j = n - 1
        while j >= 0 and A[j] > key:
            A[j+1] = A[j] # 한칸씩 우측으로 이동시키고
            j -= 1
        A[j+1] = key

A = [5, 2, 4, 6, 1, 3]
recursive_insertion_sort(A, len(A) - 1)
print(A)  # Output: [1, 2, 3, 4, 5, 6]

최악의 경우 시간복잡도 : T(n) = T(n - 1) + Θ(n)

 

 

2.3-5

result = NIL
L = 1
R = n
target = x

while L <= R:
    mid = (L+R) // 2
    if target == mid:
        result = A[mid]
        break
    elif target < mid:
        R = mid - 1
    else:
        L = mid + 1

print(result)

2.3-6

불가능하다. 이진탐색은 검색간격을 반복적으로 절반으로 나누어 이미 정렬된 배열 내에서 요소를 찾는데 사용.

삽입 정렬에 필요한 비교 횟수와 이동 횟수를 줄이는데 효과적이지 않다.

 

2.3-7

S.sort()

L = 1
R = n

result = False
while L <= R:
    if x == A[L] + A[R]:
        result = True
        break
    elif x < A[L] + A[R]:
        R -= 1
    elif x > A[L] + A[R]:
        L += 1

print(result)