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

 

• 분할 정복 - 주어진 문제를 더이상 나눌 수 없을 때까지 나누고, 나누어진 문제를 각각 풀어 답을 얻는 알고리즘
  • 규칙은 정해져있지 않고 개발자의 창의력, 독창성, 경험에 달려있다
•  분할 정복 알고리즘을 설계하는 요령
  • 분할 - 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보다 작다