분할정복 - Divide and Conquer (3.0 Introduction)

3. Divide & Conquer

3.0 Introduction

3.1 Recurrence relation

3.2 Multiplication

3.3 Sorting

3.4 Medians

3.5 Matrix multiplication

 

 

3.0 Introduction

Divid & Conquer의 핵심 (3단계)

• Divid - 쪼개기
• Conquer – 쪼갠 부분을 재귀적으로 해결하기
• Combine(optional) – 쪼갠 것을 합치는 것은 선택적인 사항임 필수가 아니다

 

3.0 Introduction의 예제

Tournament

#Tournament

elit8 = ['URG', 'FRA', 'BRA', 'BEA', 'SWE', 'ENG', 'RUS', 'CRO']

def Champion(s, e):

    if (s == e): #Degenerate case
        return s

    m = (s+e)//2 #Divide

    Lwinner = Champion(s,m) # Conquer
    Rwinner = Champion(m+1,e) # Conquer

    return Lwinner,Rwinner # Combine
print(Champion(0,7))

>>> (((0, 1), (2, 3)), ((4, 5), (6, 7)))

n개의 문제를 k개의 subsets으로 만들어서 문제를 푸는 것을 Divide Conquer라고 할 수 있다.

 

<Comparison>

	degenerate case	divide	Conquer	Combine	Performance
Tournament	n = 1 (s = e)	n = 1 (s = e)	champ (s,m); champ (m+1,e);	win (LW, RW);	2T(n/2) + O(1) = O(n)

 

Divid & Conquer Three check point

• Same format  -> 재귀 사용이 이에 해당
• Reduced problem size -> 문제의 개수를 쪼개서 푸는 가가 이에 해당
• Degenerate case -> 문제 상황에서 break 시킬 수 있는 조건문을 넣은 것이 이에 해당

 

Bruteforce search (linear search) / 순차 검색을 브루트포스 알고리즘으로 작성한 코드 예시

# Bruteforce search (linear search)

def linear_search(s,e,array,x): #시작값 끝값 찾을 배열 찾을 수
    for i in range(len(array)):
        #찾는 값이 있을 경우 i번째에 있다는 index를 보내준다.
        if array[i] == x:
            return i
    return False

a = [1,2,3,5,9,7,6]
n= int(input("찾고자하는 값을 입력해주세요. "))

if linear_search(0,6,a,n) == False:
    print("찾는 값이 존재하지 않습니다.")
else:
    print(f"찾고자 하는 값 {n}을(를) {linear_search(0,6,a,n)}번째에서 찾았습니다!")

순차 검색 : 하나씩 차례대로 배열에 들어가 있는 요소들을 하나씩 확인하며 검색하는 알고리즘이다.

 

 

Binary search (Divide & Conquer) / 이진 검색을 분할정복 알고리즘으로 작성한 코드 예시

# Binary search (Divide & Conquer)

def binary_search(s,e,array,x): #시작값 끝값 찾을 배열 찾을 수
    for i in range(len(array)):
        #첫값과 끝값이 같다면 그대로 return
        if s == e:
            if array[s] == x:
                return s

        m = (s+e)//2 #중간값을 통해서 왼쪽 오른쪽 나누기 위함
        
        if array[m] == x: #중간 자리에 있는 값이 찾는 값일 경우
            return m
        elif array[m] > x:
            return binary_search(s,m-1,array,x)
        else:
            return binary_search(m+1,e,array,x)
        

a = [1,2,3,5,9,7,6]
n= int(input("찾고자하는 값을 입력해주세요. "))

if binary_search(0,6,a,n) == False:
    print("찾는 값이 존재하지 않습니다.")
else:
    print(f"찾고자 하는 값 {n}을(를) {binary_search(0,6,a,n)}번째에서 찾았습니다!")

<Comparison>

	degenerate case	divide	Conquer	Combine	Performance
Tournament	n = 1 (s = e)	n = 1 (s = e)	champ (s,m); champ (m+1,e);	win (LW, RW);	2T(n/2) + O(1) = O(n)
binary search	n = 1 (s = e)	m = (s+e)/2	bs (s, m-1); or bs (m+1, e);	-	T(n/2) + O(1) = O(log n)

 

정리.

 

Divide & conquer의 모든 문제는 divide, conquer, combine의 3 단계를 모두 수행하지 않아도 해결 가능하다. combine의 경우엔 옵션이기 때문에 필요할 때만 사용하면 된다.

 

Divide & conquer에는 degenerate case를 무조건 고려해주어야 한다. 그래야 문제의 끝을 낼 수 있기 때문이다.