[SWEA] 분할 정복(Divide and Conquer)

본 글은 [SW Expert Academy]의 파이썬 SW문제 해결 응용-구현2 분할 정복 강의를 보고 정리한 글입니다

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYFsQq11kDFAVT 

SW Expert Academy

분할 정복(Divide and Conquer)

목차

01 분할 정복 기법

02 병합 정렬

03 퀵 정렬

04 이진 검색

05 분할 정복 사례

 

 

01 분할 정복 기법

---

분할 정복(DnQ)이란?

탑다운 접근(Top-down approac)으로, 문제의 크기가 n인 경우 분할을 통해 크기가 n/2인 부분문제로 나누고 각각의 해를 구해 정복한 후 전체 문제의 해를 구하는 통합과정을 거친다

분할(Divide)	정복(Conquer)	통합(Combine)
해결할 문제를 여러 개의 작은 부분 문제들로 분할	나눈 작은 문제를 각각 해결	필요 시 해결된 해답을 모음

 

예시: 거듭제곱

1) 반복(Iterative) 알고리즘: $O(n)$

C의 거듭제곱 = 1에 거듭제곱 값만큼 C를 곱하는 방법으로 연산 수행

def IterativE_Power(C,n): # return C power of n
	result = 1
    for _ in range(n):
    	result *= C
    return result

2) 분할 정복 기반의 알고리즘: $O(logn)$

거듭제곱을 반씩 나누어서 곱해 나가는 방법으로 풀이

def Recursive_Power(C,n):
	if n == 1:
    	return C
    elif n % 2 == 0: # even
    	y = Recursive_Power(C, n/2)
        return y*y
    else: # odd
    	y = Recursive_Pwer(C,(n-1)/2)
        return y*y*C

 

 

02-03 병합정렬&퀵정렬

---

1) 병합정렬(Merge sort): $O(nlogn)$

자세한 내용은 아래 게시글을 참고해주세요

https://codingsmu.tistory.com/133?category=871719 

파이썬으로 구현하는 병합정렬(Merge Sort)

 

2) 퀵 정렬(Quick sort): $O(nlogn)$

자세한 내용은 아래 게시글을 참고해주세요

https://codingsmu.tistory.com/134

파이썬으로 구현하는 퀵 정렬(Qucik Sort)

 

04 이진 검색

---

이진 검색(Binary Search)이란?

정렬된 리스트에서 특정 값을 찾아내는 방법으로, 가운데에 있는 항목의 키 값과 비교하여 해당 값보다 작은 경우 왼쪽에서 이진 검색을, 큰 경우에는 오른쪽에서 이진 검색을, 같은 경우 해당 값을 반환하게 된다.

 

구현 코드

1) 반복(Iterative) 구조:

def binarySearch(a, key):
    s, e = 0, len(a)-1
    
    while s <= e:
    	mid = s + (e-s) // 2
        if key == a[mid]:
            return mid
        elif key < a[mid]:
            e = mid - 1
        else:
            s = mid + 1
    return -1

2) 재귀(Recursive) 구조:

def binarySearch(a, low, high, key):
	if low > high:
    	return -1
    else:
    	mid = (low+high) // 2
        if key == a[mid]:
        	return mide
        elif key < a[mid]:
        	return binarySearch(a, low, mid-1, key)
        else:
        	return binarySearch(a, mid+1, high, key)

 

05 분할 정복 사례

---

	개념 요약	활용 예시
병합 정렬	외부 정렬의 기본이 되는 정렬 알고리즘	멀티 코어 CPU나 다수 프로세서에서 정렬 알고리즘 병렬화에 활용
퀵 정렬	매우 큰 입력 데이터에 대해서 좋은 성능을 보이는 알고리즘	생물 정보 공학에서 특정 유전자를 효율적으로 찾는데 접미어 배열과 함께 사용
최근접 점의 쌍 문제	2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제	컴퓨터 그래픽스, 컴퓨터 비전, 지리 정보 시스템, 항공 트래픽 제어, 마케팅 등의 분야