분할정복

• 분할정복
  • 한 문제를 비슷한 여러 하위 문제로 나누어서 재귀적으로 해결하고 이를 합쳐서 원래 문제를 해결
• 퀵소트, 머지소트
• 분할(divide)
  • 원래 문제르 분할하여 비슷한 여러 하위 문제로 나누기
  • 하위 문제 규모가 충분히 작으면 탈출조건을 걸어주기!
• 정복(conquer)
  • 나누어진 하위문제를 정복
  • 정복의 방법으로 재귀 활용
• 합치기(combine)
  • 하위 문제들의 답을 합쳐서 원래 문제를 해결
• 분할정복의 장점
  • 어려운 문제를 작은 문제로 나눔으로써 어려운 문제를 쉽게 해결
  • 작은문제를 분할, 같은 작업을 더 빠르게 처리
• 분할정복의 단점
  • 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생한다.
  • 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용하게 된다.
• 분할정독을 사용하는 알고리즘 설계 방법
  • divide
  • conquer
  • combine

퀵 정렬

• 퀵 정렬은 분할정복 전략을 사용하는 방법 중에서도 중요한 작업은 분할단계에서 일나납니다.

1. 분할

• 피벗 설정하기
  • 배열에서 아무 요소나 골라 분할랍니다.
  • 피벗 설정기준(맨 앞의 값, 맨 뒤의 값, 중간값)
• 파티션하기
  • 배열 안의 요소들을
  • 피벗보다 작거나 같은요소는 피벗의 왼쪽으로 보내고
  • 나머지 요소는 모두 오른쪽으로 보낸다
  • [피벗보다 작은 애들][피벗][피벗보다 큰 애들]
• [9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
• [5, 2, 3][6][9, 7, 11, 12, 14, 10]

2. 정복 (분할)

• [5, 2, 3]
  • [2][3][5]
• [9, 7, 11, 12, 14, 10]
  • [9, 7][10][11, 12, 14]
• [9, 7]
  • [7][9]
• [11, 12, 14]
  • [11, 12][14]
• [11,12]
  • [11][12]
• 이 두파트를 재귀적으로 분할하여 정렬한다.
  • 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제

3. 결합

• 아무것도 하지 않으면서 결합

array = [5, 4, 8 , 9, 1, 3]

• 퀵소트 : 피벗보다 작거나 같은 요서/ 피벗보다 큰 요소를 재귀적으로 정렬하여 정복한다.

병합정렬

• 분할 단계에서는 거의 아무것도 하지 않고 모든 중요한 작업들이 결합단계에서 일어난다.
• 분할
• 정복
  • 입력 배열을 같은 크기의 2개 부분배열로 분할한다.
    • 길이가 1이 될때까지
• 결합 (정복)
  • 정렬된 배열들을 하나의 배열에 병합
  • 정렬된 두 하위 배열을 하나의 정렬된 배열로 결합한다.
• 병합정렬 방법
  • 리스트위 중간 지점을 찾는다
  • 중간값을 기준으로 반으로 나눈다
• 결합(정복)
  • 정렬된 두 하위 배열을 하나의 정렬된 배열로 결합한다.