1. 분할정복을 활용한 알고리즘

분할정복(Divide and Conquer) 방법

• 복잡하거나 큰 문제를 여러 개의 서브문제로 나눠서 해결하는 방법
  • 병렬적으로 문제 해결 가능
• 재귀호출과 분할정복 간의 차이
  • 재귀호출: 같은 함수코드를 재호출 = 같은 함수코드 재사용
  • 분할정복: 비슷한 작업을 재진행 → 같은 코드가 아닐 수도 있음
    • 비슷한 크기로 문제를 분할하고, 해결된 문제를 제외하여 동일한 크기로 문제를 다시 분할
• 아래 코드에서 step 1 → 5까지 divide
• sum([5])를 conquer하고, 이후 개별적으로 conquer하고 merge를 해서 sum([1,2,3,4,5])를 해결

# 주어진 숫자에 대해서 덧셈을 실행하는 경우(문제에 따라 분할하는 정도가 다를 수 있다.)
[1, 2, 3, 4, 5]

# step 1
sum([1,2,3,4,5]) = sum([1]) + sum([2,3,4,5])     # Divide

# step 2
sum([2,3,4,5]) = sum([2]) + sum([3,4,5])         # Divide

# step 3
sum([3,4,5]) = sum([3]) + sum([4,5])             # Divide

# step 4
sum([4,5]) = sum([4]) + sum([5])                 # Divide

# step 5
sum([5]) = 5                                     # Conquer

-> 서브문제 sum([5])에 대한 답이 나왔고, 나머지 서브문제 sum([4]), sum([3]) 등에 대한 문제들도 Conquer를 진행
-> 개별적으로 Conquer 후 Merge

• 문제를 분할하지 못하거나 그럴 필요가 없는 경우에는 답을 구함

• 조건

  • 서브 문제로 분할 가능한지 = divide
  • 서브문제의 답을 병합하여 본 문제의 답을 구하는 게 효율적인지 = conquer&merge

• 동일한 문제를 재귀로 해결할 때 vs 분할정복으로 해결할 때

# 재귀 : 1부터 10까지의 합

def func(num):
  if num < 1:
    return 0
  else:
    return num + func(num-1)

func(10)

# 분할정복 : 1부터 10까지의 합

def func(num):
  if num == 1:
      return 1
  if num % 2 == 1:
      return func(num - 1) + num
  else:
      return func(num / 2) * 2 + (num / 2) * (num / 2)

func(10)

2. 퀵정렬과 병합정렬

• 퀵정렬: 전체 탐색할 때 좌우로 나눠서 재귀적으로 수행하므로 병합정렬보다는 빠름

  • 불안정 정렬
  • 시간복잡도
    • 평균적으로 O(nlogn)
    • 최악의 경우 O(n^2)
  • 사용하는 이유:
    • 피벗이라는 별도의 노드를 지정하고 재귀적으로 수행하므로 상대적으로 더 빠름
    • 한정적인 범위 내에서 데이터를 정렬하기 때문에 캐시를 덜 활용함 → HW면에서 더 효율적

• 병합 정렬: divide and conquer 로직으로 인해 처음과 끝을 계속해서 탐색하므로 상대적으로 느림

  • 안정 정렬: 동일 값에 대해 기존 순서가 유지됨
  • 시간복잡도: 항상 O(nlogn)
  • 사용되는 이유:
    • 안정 정렬이라 데이터가 중복되어도 영향을 덜 받음
    • 퀵정렬은 성능이 우수함에도 성능 편차가 크고, 노드(피벗) 설정 등 다루기 어려운 점으로 인해 실무에서 활용되기 어렵

퀵정렬 Quick Sort