[알고리즘] 5. 분할정복

KOCW에서 제공하는 고려대학교 유용재 교수 알고리즘 강의를 듣고 정리한 글 입니다.

5주차 분할정복의 뜻과 문제 해결에의 적용 

 

---

 

5주차. 분할 정복의 뜻과 문제 해결에의 적용

 

1.  재귀적 접근 원리와 실제

1) 재귀란?

: 함수의 정의부에서, 함수 자기 자신을 재귀적으로 호출할 수 있음

재귀호출은 분할 정복 패러다임 구현을 위한 도구로 활용됨

 

2) 상향식 / 하향식 접근법

• 문재 해결을 위한 접근법은 상향식(Bottom-up)과 하향식(Top-down)으로 구분 가능
• 재귀 호출은 일반적으로 하향식(Top-down) 접근법에 해당

 

3) 재귀호출을 이용한 문제 해결 사례

피보나치 수열

def ex_func(N):
	if (N == 1) OR (N == 2):
    	return 1
    return ex_func(N-1) + ex_func(N-2)

ex_func 가 ex_func를 호출하는 형태.

문제의 최상단에서 시작하는 top-down 알고리즘.

ex_func 함수가 가지는 시간복잡도? => TC(N) = TC(N-1) + TC(N-2) => θ(1.618^n) (피보나치 수열 일반항)

 

2. 분할정복의 이해

1) 분할 정복이란?

아래 절차를 거쳐 문제를 해결하는 알고리즘 패러다임

• 문제를 보다 작은 크기의 문제로 계속해서 분할
• 쉽게 풀 수 있을 정도로 문제의 크기가 작아진 경우 이를 정복
• 작은 개별문제들에 대한 해를 통합하는 과정을 거듭하여 최종 해 도출
• * 문제에 따라 통합 과정 불필요할 수도 있음 ex) 이진 탐색

 

2) 문제 예시

거듭 제곱 계산 

자연수 x와 음이 아닌 정수 n을 인자로 받아, x^n의 값을 반환하는 함수 exp?

def exp(x, n):
	if (n==0):
    	return 1
    elif (n%2)==0:
    	return exp(x, n//2) ** 2
    else:
    	return (exp(x, n//2) ** 2) * x

'''
exp(5, 4)
= exp(5,2) ** 2
=(exp(5,1) **2) ** 2
=(((exp(5,0) ** 2) * 5) ** 2) ** 2
=(((1**2) * 5) ** 2) **2)
= (5**2)**2
= 25 ** 2
= 625
'''

단계 거듭할 수록 밑 1/2배됨 -> log N 

단계당 연산  1 or 2 번

=> 2 log N

=> θ(log N)

 

 

3. 분할정복을 이용한 정렬

1) 병합 정렬 Merge Sort

• 수열이 주어질 때, 수열을 절반으로 쪼개는 과정 반복
• 더 이상 수열을 쪼갤 수 없는 경우, 이미 쪼개진 수열들을 순서에 맞게 합치는 과정 반복

 

시간복잡도

분할 : 미미함. 

합병 : 길이 X인 수열 2개가 합치는 경우

최선 X회, 최악 2X회 비교

단계에 원소 N개라면 합병에 θ(N)

-> θ(N)

* 쪼개는 단계 (높이) 수 => log N

=>  θ(N log N)

 

# Week 5

# Merge Sort

def merge_sort(num_list):
  if len(num_list) <= 1:
    return num_list
  
  mid = len(num_list) // 2
  
  left_list = merge_sort(num_list[:mid])
  right_list = merge_sort(num_list[mid:])
  
  return_array = list()
  
  while True:
    if len(left_list) == 0:
      return_array = return_array + right_list
      break
    if len(right_list) == 0:
      return_array = return_array + left_list
      break
    if (left_list[0] <= right_list[0]):
      return_array.append(left_list[0])
      del(left_list[0])
    else:
      return_array.append(right_list[0])
      del(right_list[0])
    
  return return_array
  
num_list = [800, 32, 4, 122, 766, 12, 98, 772, 8]

print(merge_sort(num_list))

# result
# [4, 8, 12, 32, 98, 122, 766, 772, 800]

 

2) 퀵 정렬 Quick Sort

(1) 퀵 정렬

 

시간 복잡도

• 최선 : 수열의 중앙 인근에서 분할이 이루어지는 것이 최선 -> 시간복잡도  θ(N log N) (병합 정렬과 유사)
• 최악 : 수열의 끝에서 분항리 이루어 지는 것이 최악 -> 층수는 n ->  θ(N^2)

 

연습 문제

다음 원소들을을 오름차순 배열하려고한다.

퀵 정렬을 이용하여 정렬한다고 할 때, 정렬이 완료된 시점에서 원소간 총 비교 횟수는?

(기준 원소는 항상 마지막 원소를 사용한다)

[15, 30, 60, 5, 35, 18]