본문 바로가기
휴지통

알고리즘 강의 2주차 - 분할 정복, 합병 정렬

by SOLYI 2021. 10. 8.

 

  • 분할 정복 - 주어진 문제를 더이상 나눌 수 없을 때까지 나누고, 나누어진 문제를 각각 풀어 답을 얻는 알고리즘
    • 규칙은 정해져있지 않고 개발자의 창의력, 독창성, 경험에 달려있다
  •  분할 정복 알고리즘을 설계하는 요령
    • 분할 - 2개이상의 하위문제로 나눈다
    • 정복 - 하위문제가 여전히 분할 가능하다면 하위집합에 대해 분할을 다시 수행, 아니라면 하위 문제를 푼다.
    • 결합 - 위 두 과정에서 정복된 답을 취합한다.
  • 부분문제 - 분할된 입력에 대한 문제
  • 부분해 - 부분 문제의 해
  • 문제해 - 부분해를 취합

 

  • 합병 정렬 Merge Sort
    • n개의 숫자들을 n/2개씩 2개의 부분 문제로 분할
    • 각각의 부분문제를 재귀적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬(정복)
  • 합병 정렬의 시간 복잡도 
    • (층수)xO(n) = log2nxO(n) = O(nlogn) 
  • 선택Selection 문제 : n개의 숫자들중에서 k번째로 작은 숫자를 찾는 문제
    • 이진탐색 - 2분의 1로 나눈 두부분중에서 한부분만 탐색 
    • 선택문제
      • 정렬되어있지않는 값들 중 피봇(기준)을 선택 -> 피봇을 기준으로 Small그룹 Large그룹으로 나눈다.
    • good/bad 분할
      • bad 분할 : 4분의 3보다 크다

good 분할 : 4분의 3보다 작다

반응형