Algorithm Intermediate

TaeWoo Lee / Kris·2022년 4월 6일
0

분할정복

  • 분할정복
    • 한 문제를 비슷한 여러 하위 문제로 나누어서 재귀적으로 해결하고 이를 합쳐서 원래 문제를 해결
  • 퀵소트, 머지소트
  • 분할(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]
  1. 정복 (분할)
  • [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]
  • 이 두파트를 재귀적으로 분할하여 정렬한다.
    • 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제
  1. 결합
  • 아무것도 하지 않으면서 결합

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

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

병합정렬

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

0개의 댓글