동적계획법과 분할 정복

정의

동적계획법

동적 계획법 소개 

• 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
  • 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
  • 메모제이션 기법을 이용한다.
    • 메모제이션 : 프로그램 실행시 이전 계산 값을 저장해, 다시 계산을 방지해 전체 실행 속도를 빠르게 한다.
  • 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용 된다.
    • 예. 피보나치 수열

---

분할 정복

• 문제를 나눌 수 없을 때까지 나눠 각각을 풀면서 다시 합병해 문제의 답을 얻는 알고리즘
• 하향식 접근법으로 상위의 해답을 수하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식
  • 일반적으로 재귀 함수로 구현한다.
• 문제를 잘게 쪼갤 때, 부분문제들은 서로 중복되지 않는다.
  • 예. 병합정렬, 퀵 정렬 등

병합정렬

합병 정렬

def merge_sort(list):
	if len(list)<=1:
    	return list
  	mid = len(list)//2
    leftList = list[:mid]
    rightList  = list[mid:]
    leftList = merge_sort(leftList)
    rightList = merge_Sort(rightList)
    return merge(leftList, rightList)
    
def merge(left, right):
	result =[]
    while len(left)>0 or len(right)>0:
    	if len(left)>0 and len(right)>0:
        	if left[0] <= right[0]:
            	result.append(left[0])
                left = left[1:]
            else:
            	result.append(right[0])
                right = right[1:]
         elif len(left)>0:
         	result.append(left[0])
            left= left[1:]
         elif len(right)>0:
         	result.append(right[0])
            right = right[1:]
     return result

퀵정렬

퀵 정렬

퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. ( 나보다 어린애 숙여!!!! , 어우 형님 죄송합니다.)

def quick_sort(ARRAY):
	ARRAY_LENGTH = len(ARRAY)
    if ARRAY_LENGTH <=1:
    	return ARRAY
    else:
    	PIVOT = ARRAY[0]
        GREATER = [ element for element in ARRAY[1:] if element > PIVOT ]
        LESSER =  [ element for element in ARRAY[1:] if element <= PIVOT]
        return quick_sort(LESSER) +[PIVOT] + quick_sort(GREATER)

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

참고 문헌

ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

https://www.fun-coding.org/Chapter14-dp_divide.html

퀵 소트, 머지소트 참고

ratsgo.github.io/data%20structure&algorithm/2017/09/28/quicksort/

ratsgo.github.io/data%20structure&algorithm/2017/10/03/mergesort/