재귀_동적_프로그래밍

swexpertacademy.com/main/learn/course/lectureHtmlViewer.do#none

SW Expert Academy

문제2) Merge Sort, 크기 n인 배열을 입력으로 받아,

배열을 절반으로 두 개로 나눈 후, 각작은 배열을 재귀적으로 정렬하고, 그 결과를 Merge 한다.

 

-------

merge mergeSort(A):

  if len(A) == 1:

    return A

  else:

    mid = len(A)//2  # 몫

    mergeSort(A[0 : mid])   # 앞부분 합병

    mergeSort(A[mid : len(A)])  # 뒷부분 합병

    merge()    # 합병

 

 

--------

def mergesort(lis):
    if len(lis) == 1:
        return lis
    else:
        tmp = list()
        mid = len(lis)//2
        ls1 = mergesort(lis[0:mid])
        ls2 = mergesort(lis[mid:len(lis)])

        part1 = 0
        part2 = 0

        while (part1 < len(ls1) and part2 < len(ls2)):
            if ls1[part1] <= ls2[part2]:
                tmp.append(ls1[part1])
                part1 += 1
            else:
                tmp.append(ls2[part2])
                part2 += 1
        
        tmp = tmp + ls1[part1:len(ls1)]
        tmp = tmp + ls2[part2:len(ls2)]

        
        return tmp

lis = [10, 2, 50 ,32 ,22 ,4,19, 1, 26, 9]
lis2 = [10, 2, 6, 5]
print(mergesort(lis))

 가정 : mergeSort를 호출하면 F(n)이 return 됨을 알 수 있다.

(1) lis의 길이가 1 일 때

첫문장에서 바로 자기 자신이 리턴됨을 알 수 있다.

 

(2) lis의 길이가 k 일 때

 

 

시간복잡도

T(n) = 1                              if n = 1

T(n) = T(n/2) + T(n/2) + n       if n > 1

 

 

문제 3 : 다음 소팅 알고리즘이 실제로 소팅에 항상 성공한다는 것을 증명하라.

 

문제 4 : 위의 소팅 알고리즘에서 수행하는 Swap의 횟수는 최대 몇번인가?

 

문제 5 : 어떤 배열 A[1..n]에 (음수포함) 정수 값이 증가하는 순서로 저장되어 있다. A[i] = i가 되는 인덱스 i가 존재하는지 찾는 알고리즘을 수도코드 수준으로 작성하고 정확성 증명 및 시간 복잡도 계산을 수행하라. 동일한 문제이지만, 저장된 값이 자연수로 제한되면 어떻게 풀 수 있는가?

 

문제 6 : 루트 있는 트리를 입력으로 받아 아래와 같이 출력하는 알고리즘을 작성하라. 트리의 각 노드에는 1,000 미만의 자연수가 저장되어 있다. 트리의 노드 연결 관계는 다음과 같이 표현해야 한다. 아래 출력에서 루트에는 자식이 3개 있고 그 자식들 중 하나는 더 이상 자식이 없는 것임을 알 수 있을 것이다.

 

문제 7 : (어려움) 무한한 크기의 물통이 3개 있다. 초기에 각 물통에는 자연수리터 만큼의 물이 들어 있다. 가능한 작업은 두개의 물통을 잡아서 그중 많거나 같은양의 물이 들어 있는 곳에서 작은 쪽으로 물을 부어서 작은 쪽의 물의 양을 두배로 만드는 것이다. 즉, 4리터, 3리터를 잡았다면 1리터, 6리터가 될 것이다. 입력으로 초기 물의 양을 받아서 한 물통에 들어 있는 물의 양을 0리터로 만들고 싶다. (실행 시간이 많이 걸려도 좋으니) 그렇게 만드는 과정을 계산하는 알고리즘을 작성하라.