Data Structures and Algorithms (7)

Data Structure and Algorithms (7) : Dynamic programming(동적 계획법) & Divide and Conquer (분할정복)

1. Dynamic Programming (동적 계획법)

동적 계획법
1) 입력크기가 작은 부분 문제들을 해결한 후 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
2) 상향식 접근법으로 가장 최하위 해답을 구한 후 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
3) Memoization기법을 사용함

-> Memoization (메모이제이션)이란? : 프로그램 실행시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행속도를 빠르게 하는 기술 / 문제를 잘게 쪼갤 때 부분문제는 중복되어 재활용됨 ex) 피보나치 수열

Recursive Call

def fibo (num);
if num <= 1;
  return num
return fibo(num-1) + fibo(num-2)

동적 계획법 활용

def fibo_dp (num):
cache = [0 for index in range(num+1)]
cache[0] = 0
cache[1] = 1
ㅤ
for index in range(2, num+1)
  cache[index] = cache[index-1] + cache[index-2]
return cache[num]

ㅤ
ㅤ
ㅤ

ㅤ
ㅤ

2. Divide and Conquer (분할정복)

Quick Sort (퀵 정렬)
병합정렬보다 빠른건 아니지만 일반적으로 빠름
정렬에서는 가장 빠르다고 보면 됨

1) pivot (기준점)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽에 놓는 것
2) 왼쪽 오른쪽 은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복
3) 함수는 왼쪽 + 기준점 + 오른쪽을 리턴

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)
ㅤ
------------------------------------------------
ㅤ
Import random
data_list = random.sample(range(100), 10)
qsort(data_list)

시간복잡도 : : O (n log n) = 병합정렬과 동일
but 최악의 경우 pivot기준이 순서대로라면 O(n^2) – 한 단계마다 n번의 계산이 일어나기 때문에 (특이한 경우이기 때문에 적용 X)

Merge Sort (병합 정렬)
재귀용법을 활용한 정렬 알고리즘

1) 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다
2) 각 부분 리스트를 재귀적으로 합병 정렬이용해 정렬
3) 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병

총 필요한 함수
1. 나누는 함수
2. 병합하는 함수

나누는 함수

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

병합하는 함수

def merge(left, rigth):
  merged = list()
  left_point, right_point = 0, 0
ㅤ
  #case1 : 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:
      merged.append(left[left_point])
      left_point += 1
ㅤ
  #case2 : left만 남아있을 때
  while len(left) > left_point:
    merged.append(left[left_point])
    left_point += 1
ㅤ
  #case3 : right만 남아있을 때
  while len(right) > right_point:
    merged.append(right[right_point])
    right_point += 1
ㅤ
  return merged

적용

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

시간복잡도
각 단계는 항상 2^i X n/2^i = n
단계는 항상 log2n 이 만들어지기 때문에
O(n log n)

---

공통점
문제를 잘게 쪼개서 가장 작은 단위로 분할

차이점
1) 동적계획법 : 부분문제는 중복되어 상위문제 해결시 재활용됨 / Memoization 기법 사용(부분 문제의 해답을 지정해서 재활용하는 최적화 기법으로 사용)
2) 분할정복 : 부분문제는 서로 중복되지 않음 / Memoization 기법 사용 안함

---

본 게시글은 fastcampus 이준희강사 수업을 듣고 개인적으로 정리한 내용임을 밝힘.