20210628 Algorithm 03 : 동적 계획법(Dynamic Programming), 분할정복(Divide and Conquer), 퀵 정렬(Quick sort), 병합정렬(Merge sort)

Algorithm 03

동적 계획법 (Dynamic Programming)과 분할 정복(Divide and Conquer)

동적 계획법 (DP)

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

분할 정복

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

공통점과 차이점

• 공통점 : 문제를 잘게 쪼개서, 가장 작은 단위로 분할
• 차이점 :
  • 동적 계획법
    • 부분 문제는 중복되어, 상위 문제 해결시 재활용
    • Memoization 기법 사용 (부분 문제 해답을 저장하여 재활용 하는 최적화 기법으로 사용)
  • 분할 정복
    • 부분 문제는 중복X
    • Memoization을 사용X

X	동적 계획법	분할 정복
공통점	문제를 잘게 쪼개서, 가장 작은 단위로 분할
부분 문제 중복, 재활용	O	X
Memoization 사용	O	X

동적 계획법 알고리즘 이해 : 피보나치 수열

• 피보나치 수열

  • f(0) = 0, f(1) = 1 , f(n>1) = f(n-1) + f(n-2)
  • 2 이상의 값을 넣는 경우, 해당 값을 얻기 위해서는 연속되는 하위 2개의 값을 알아야 함
  • 즉, 큰 문제를 풀려면 경우에 작은 문제를 풀어 값을 알아야 함

• 패턴

  • f(6) -> f(5), f(4)

    • f(5) -> f(4), f(3)
      • f(4) -> f(3), f(2)
        • …
      • f(3) -> f(2), f(1)
        • …
    • f(4) -> f(3), f(2)
      • f(3) -> f(2), f(1)
        • f(2) -> f(1), f(0)
      • f(2) -> f(1), f(0)

  • 위와 같은 패턴으로, 작은 문제들이 여러번 중복되어 활용되는 경우가 생기는데, 굳이 다시 문제를 풀필요 없이 memoization에 저장된 값을 활용함

Recursive call(재귀용법) 활용

• 재귀 용법을 사용하는 경우 중복된 연산을 막을 수 없음

def fibo(n):
  if n <= 1:
    return n
  return fibo(n-1) + fibo(n-2)

# TEST
fibo(4)
# fibo(3) + fibo(2)

# fibo(3) = fibo(2) + fibo(1)
  # fibo(2) = fibo(1) + fibo(0)
# fibo(2) = fibo(1) + fibo(0)
# fibo(2), fibo(1), fibo(0)가 중복되어 계산됨

Dynamic Programming(동적 계획법) 활용

• 애초에, 연산한 값을 저장할 수 있는 캐시를 만들어 활용함
• 이를 활용하여 연산된 값들을 바로 참조 할 수 있게 함
  • 배열의 index가 n의 역할을 하고, 배열 index n에 해당하는 값이 연산된 값으로 되어 있음
  • 그래서, 이미 연산된 값은 다시 연산하지 않음

def fibo_dp(n):
  cache = [0 for i in range(n + 1)]
  cache[0] = 0
  cache[1] = 1

  for i in range(2, n+1):
    cache[i] = cache[i-1] + cache[i-2]
  return cache[n]

# 예시
fibo_dp(6)
# 0, 1에 대한 값 설정
# [0, 0, 0, 0, 0, 0]
# [0, 1, 0, 0, 0, 0]

# 2 부터에 대한 값 설정
# [0, 1, 1, 0, 0, 0]
# [0, 1, 1, 2, 0, 0]
# [0, 1, 1, 2, 3, 0]
# [0, 1, 1, 2, 3, 5]
# return 5

Quick sort (퀵 정렬)

• 정렬 알고리즘의 꽃
• 분할 정복기법을 사용하는 알고리즘
• 기준점(Pivot)을 정해서, 기준점 보다 작은 데이터는 왼쪽(Left), 큰 데이터는 오르쪽(Right)로 모으는 함수를 작성함
• 각 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함
• 함수는 Left + Pivot + right을 리턴함
• 즉, 기준점을 기준으로 계속 좌우로 분리 해 나가면, 모두 정렬이 된 상태로 찢어지게 되는데 이를 모두 합쳐서 가져오면 정렬된 데이터가 됨
  • 재귀 함수를 사용함

패턴

• [49, 97, 53, 5, 33, 65, 62, 51]
• [5, 33] [49] [97, 53, 65, 62, 51]
• [5] [33] [49] [97, 53, 65, 62, 51]
• [5] [33] [49] [53, 65, 62, 51] [97]
• [5] [33] [49] [51] [53] [65, 62] [97]
• [5] [33] [49] [51] [53] [62] [65] [97]
• [5, 33, 49, 51, 53, 62, 65, 97]

알고리즘 구현

• 재귀함수를 통해서 정렬하고 다시 합침
• 재귀 함수를 통하기 때문에 각 함수마다 left, right가 새로 만들어 지기 때문에 다른 것과 중복되진 않음
• python에서 제공하는 list 합치기 기능을 통해서 구현

def qsort(data):
  if len(data) <= 1:
    return data

  left, right = list(), list()
  pivot = data[0]

  for index in range(1, len(data)):
    if pivot > data[index]:
      left.append(data[index])
    else:
      right.append(data[index])

  return qsort(left) + [pivot] + qsort(right)

# TEST
import random
data_list = random.sample(range(100), 10)
print(qsort(data_list))
# [2, 20, 35, 39, 49, 51, 57, 74, 82, 94]

List Comprehension을 사용하여 정리하는 경우

• List Comprehension을 통하면, list를 채울때 더 깔끔하게 채울 수 있음 또한, 조건문을 사용할 수 도 있음

# List Comprehension 을 사용하는 경우
def qsort(data):
  if len(data) <= 1:
    return data

  pivot = data[0]

  left = [item for item in data[1:] if pivot > item]
  right = [item for item in data[1:] if pivot <= item]
  return qsort(left) + [pivot] + qsort(right)

퀵정렬의 시간 복잡도

• 병합정렬과 유사, 시간 복잡도는 O(n log n)
  • 예상되는 평균적인 상태는, pivot에 의해서 left, right가 반반 정도 나누어 지는 형태
  • n개를 돌며 확인 -> n/2 , n/2개 각각 돌며 확인 -> n/2^2, n/2^2, n/2^2, n/2^2 -> …
    • 전체 log n번의 턴이 생기고, 각 턴마다, 리스트는 2^N 씩 늘어나지만, 리스트의 원소 개수는 2^N 줄어 들음
    • 각턴(N회) : 원래 원소의 개수인 n * 2^N / 2^N = O(n)
    • 턴의 개수 : log n 만큼 생김 = O(log n)
    • 결국 , O(nlogn)
  • 최악의 경우, 맨처음 pivot이 가장 크거나, 작은 경우 O(n^2)
    • 모든 데이터를 비교하는 상황이 나옴
    • 한쪽으로 쏠려서 left 또는 right에 1개씩 줄어들게 됨으로 턴의 개수가 n이 됨

Merge sort (병합 정렬)

• 재귀 용법을 활용한 정렬 알고리즘
  • 리스트를 절반으로 잘라 크기가 비슷한 두 부분 리스트로 나눔 -> 반복하면, 하나하나 가 됨
  • 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬함
  • 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병
• 분할 정복 기법을 활용한 알고리즘

패턴

• [1, 9, 3, 2] 의 경우
• 리스트를 각각으로 나눔 (Split)
  • [1, 9] [3, 2]
  • [1] [9] [3] [2]

• 크기 비교 해서 리스트를 합침 (Merge)
  • [1, 9] [2, 3]
  • 같은 리스트의 경우 이미 크기가 비교된 상태라서 다른 리스트 끼리만 비교하면 됨
  • 제일 작은 숫자부터 다른 리스트의 제일 작은 숫자부터 차례대로 비교
  • list index 0(1) vs list index 0(2) -> [1]
  • list index 0(1) vs list index 1(3) -> [1] (어차피 예견 할 수 있는 비교라서 쓸모 없음)
  • list index 1(9) vs list index 0(2) -> [1, 2]
  • list index 1(9) vs list index 1(3) -> [1, 2, 3]
  • 비교 대상이 없으므로 -> [1, 2, 3, 9]

• [49, 97, 53, 5, 33, 65, 62, 51]의 경우
  • [49, 97, 53, 5] [33, 65, 62, 51]
  • [49, 97] [53, 5] [33, 65] [62, 51]
  • [49] [97] [53] [5] [33] [65] [62] [51]
• Merge (작은데이터가 앞, 큰데이터가 뒤)
  • [49, 97] [5, 53] [33, 65] [51, 62]
  • [5, 49, 53, 97] [33, 51, 62, 65]
  • [5, 33, 49, 51, 53, 62, 65, 97]

• 비교 순서 및 경우의 수 (항상 두개의 list를 비교해서 합침, M, N)
  • (0-0) (0-1), (0-…), (0-n)
  • (1-0) (1-1), (1-…), (1-n)
  • (2-0) (2-1), (2-…), (2-n)
  • (m-0) (m-1), (m-…), (m-n)

알고리즘 고안

• 하지만, 어차피 한번 비교되어서 넣은 요소가 선택이 되면, 비교 당하는 list의 해당 요소 다음은 의미가 없는 비교임

  • left[m] < right[n] -> left[m] 추가후, 바로 m + 1 로 넘어가서 비교 하면 됨
  • left[m] >= right[n] -> right[n] 추가후, 바로 n + 1로 넘어가서 비교 하면 됨
  • 값이 작아 선택 당한 방향의 list에서 다음 index의 data를 비교함

• 어차피 한번에 split 반복 후 merge 반복 하므로 재귀 함수로 split, merge를 합쳐 사용하면 됨

  • 함수의 경우, 인자가 명확해 져야 해당 함수를 실행하기 때문에, split은 계속 실행되고 나서, split이 닫히는 과정에서 merge의 인자가 명확해 짐으로 merge가 그때 반복되어 실행됨
  • split -> split -> … -> split_return_list -> merge -> … -> merge -> merge

알고리즘 구현

• Split, Merge 함수

def split(data):
  medium = int(len(data)/2)
  left = data[:medium]
  right = data[medium:]
  print(left, right)

# TEST
data_list = [3, 4, 1, 3, 2]
# [3,4] [1, 3, 2]

• 재귀함수를 활용한 Split 반복

def mergeSplit(data):
  if len(data) <= 1:
    return data
  medium = int(len(data)/2)
  left = mergeSplit(data[:medium])
  right = mergeSplit(data[medium:])
  return merge(left, right)

• Merge 함수 만들기

def merge(left, right):
  merged = list()
  left_point, right_point = 0, 0
  # left, right에 데이터가 남아 있는 경우
  while len(left) > left_point and len(right) > right_point:
    if left[left_point] > right[right_point]:
      merged.append(right[right_point])
      right_point += 1
    else:
      marged.append(left[left_point])
      left_point += 1

  # (위에서 이미 걸러졌기 때문에 둘중 하나는 남을 수 있음)
  # left만 남아 있는 경우
  while len(left) > left_point:
    marged.append(left[left_point])
    left_point += 1

  # right만 남아 있는 경우
  while len(right) > right_point:
    merged.append(right[right_point])
    right_point += 1

  return merged

최종 코드 작성

def mergeSplit(data):
  if len(data) <= 1:
    return data
  medium = int(len(data)/2)
  left = mergeSplit(data[:medium])
  right = mergeSplit(data[medium:])
  return merge(left, right)

def merge(left, right):
  merged = list()
  left_point, right_point = 0, 0
  # left, right에 데이터가 남아 있는 경우
  while len(left) > left_point and len(right) > right_point:
    if left[left_point] > right[right_point]:
      merged.append(right[right_point])
      right_point += 1
    else:
      marged.append(left[left_point])
      left_point += 1

  # left만 남아 있는 경우
  while len(left) > left_point:
    marged.append(left[left_point])
    left_point += 1

  # right만 남아 있는 경우
  while len(right) > right_point:
    merged.append(right[right_point])
    right_point += 1

  return merged

# TEST

import random

data_list = random.sample(range(100), 10)

print(mergesplit(data_list))
# [1, 3, 7, 12, 23, 30, 36, 43, 45, 93]

병합 정렬의 시간 복잡도

• split, merge
  • -> 0단계: n개의 원소를 가진 list
  • -> 1단계: n/2 , n/2 (2개)
  • -> 2단계: n/2^2, n/2^2, n/2^2, n/2^2 (2^2개)
  • -> log n단계(각각의 list가 1개만 가지는 경우): n/2^i , n/2^i, n/2^i … (2^i 개)
• 각 단계의 list(노드)의 개수 : 2^i

• 해당 list(노드)를 구성하는 원소의 개수 : n/2^i
• 각 단계의 계산량 : (2^i) * n/(2^i) = O(n)

• 단계의 개수 : log n (노드가 1개만 남을 때 까지 이므로) -> O(log n)
  • 4개의 원소를 가진 list -> 4, 2, 1 -> 2단계
  • 8개의 원소를 가진 list -> 8, 4, 2, 1 -> 3단계
  • 16개의 원소를 가진 list -> 16, 4, 2, 1 -> 4단계
  • n개의 원소를 가진 list -> n, n/2, n/2^2, n/2^3, … n/2^logn -> log n 단계
    • n/2^logn = 1

• O(n) * O(log n) = O(n logn)