[알고리즘] 분할과 정복

분할과 정복

💡 언제 쓸까?

큰 문제를 작은 문제로 나눠도 해결방법은 똑같을 때

• 그냥 문제의 크기만 다르고 해결방법은 똑같을 때

💡 포인트

• 큰 문제를 작은 문제로 나눠서 해결
  • 재귀함수를 통해 분할하여 작은 문제를 각각 해결(분할) 👉 합침(정복)
• 재귀함수 사용
  📌 재귀함수
  • 함수 자기 자신을 호출하는 함수
  • 맨 마지막 부분 처리가 있어야 함(if문)
• 분할하는 함수, 분할한 범위 내에서 필요한 처리를 하는 함수 각각 정의
  📌 분할하는 함수

  def divide(arr):
    if len(arr) <= 1: #범위의 길이가 1이면 더이상 나누지x
      return arr
    
    left = divide(arr[처음~len(arr)/2])
    right = divide(arr[len(arr)/2~끝])
    return process(left, right) #처리 함수의 결과값(array)을 return

  • left=재귀함수, right=재귀함수
  • if(배열길이1) return 배열
    • 이 조건문에 걸릴때 비로소 함수 호출이 멈추고, left=길이1인 배열, right=길이1인 배열 로 계산 시작 가능
  • 처리함수의 결과값(배열)을 return
  📌 처리 함수

  def process(left, right):
  		result = []
  		#left, right 가지고 필요한 처리를 함
  		return result

💡 예시 : Merge Sort

📌 분할하는 함수

def merge_sort(arr):
	if len(arr) <= 1:
	  return arr
	left = merge_sort(arr[:len(arr)//2])
	right = merge_sort(arr[len(arr)//2:])
	return merge_array(left, right)

📌 처리 함수

def merge_array(a, b):
	result = []
	i = 0; j = 0
	while i < len(a) and j < len(b):
	  if a[i] < b[j]:
	    result.append(a[i])
	    i += 1
	  else:
		result.append(b[j])
		j += 1
	while i < len(a):
	  result.append(a[i])
	  i += 1
	while j < len(b):
	  result.append(b[j])
	  j += 1
	return result