[패스트캠퍼스 :: 코딩테스트 인강] 7주차 ① 동적 계획법, 퀵 정렬, 병합 정렬

알고리즘/기술면접 완전 정복 올인원 패키지 Online

 

동적 계획법과 분할 정복 - 01. 동적 계획법과 분할 정복

고급 정렬 알고리즘 - 01. 퀵 정렬

고급 정렬 알고리즘 - 02. 병합 정렬

 

---

 

2021.04.03

 

 

---

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

 

• 동적 계획법 (DP라고 많이 부름)
  • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
  • 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결괏값을 이용해서 상위 문제를 풀어가는 방식
  • Memoization 기법을 사용함
    • Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
  • 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨
    • 예: 피보나치 수열
• 분할 정복
  • 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
  • 하양식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
    • 일반적으로 재귀 함수로 구현
  • 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음
    • 예: 병합 정렬, 퀵 정렬 등

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

 

 

 

 

 

병합 정렬 (merge sort)

 

 

 

• 알고리즘 분석은 쉽지 않음, 이 부분은 참고로만 알아두자.
  • 다음을 보고 이해해보자
    • 몇 단계 깊이까지 만들어지는지를 depth라고 하고 i로 놓자. 맨 위 단계는 0으로 놓자.
      • 다음 그림에서 n/2222는 2단계 깊이라고 해보자.
      • 각 단계에 있는 하나의 노드 안의 리스트 길이는 n/2222 가 된다.
      • 각 단계에는 2𝑖2i 개의 노드가 있다.
    • 따라서, 각 단계는 항상 2𝑖∗𝑛2𝑖=𝑂(𝑛)2i∗n2i=O(n)
    • 단계는 항상 𝑙𝑜𝑔2𝑛log2n 개 만큼 만들어짐, 시간 복잡도는 결국 O(log n), 2는 역시 상수이므로 삭제
    • 따라서, 단계별 시간 복잡도 O(n) * O(log n) = O(n log n)

 

 

def merge(left, right):
    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


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)

 

 

 

 

퀵 정렬 (quick sort)

 

• 기준점(pivot이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)으로 모으는 함수를 작성함
• 각 왼쪽(left), 오른쪽(right)은 재귀 용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함
• 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right)을 리턴함

 

quicksort 함수 만들기

• 만약 리스트 개수가 한 개이면 해당 리스트 리턴
• 그렇지 않으면, 리스트 맨 앞의 데이터를 기준점(pivot)으로 놓기
• left, right 리스트 변수를 만들고,
• 맨 앞의 데이터를 뺀 나머지 데이터를 기준점과 비교(pivot)
  • 기준점보다 작으면 left.append(해당 데이터)
  • 기준점보다 크면 right.append(해당 데이터)
• return quicksort(left) + pivot + quicksort(right)로 재귀 호출

 

 

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)

 

 

---

 

 

정렬 알고리즘은 정말 많이 활용되는 부분인 만큼 기억해야 할 부분도 많다.

 

 

 

 

 

[패스트캠퍼스 100% 환급 챌린지 미션 중입니다.]

 

 

 

 

 

 

알고리즘 / 기술면접 완전 정복 올인원 패키지 Online. | 패스트캠퍼스