본문 바로가기

엄숙한 분위기의 스터디 공간/알고리즘

Quick Sort, Approximately medium, Selection Problem

퀵 소트

    • 최악의 경우, 평균의 경우는 pivot의 위치에 따라 다르게 발생함.
      • selection을 이용하여 피봇을 중간쯤~ 의 것으로 설정해 주면 됨. (작은 문제)
      • 배열에서 k번째로 큰 수를 구할 수 있는가? (큰 문제)
  •  
  • 어떻게 할 수 있을까?
    • O(nlogn)에 풀 수 있음은 명백하다. 그보다 더 짧은 시간에 구할 수 있는 방법을 알아보자. (O(n) < .. < O(nlogn) 이 될 것이다. O(n)보다는 작아질 수 없다.) (O(n)보다 작은 경우를 생각해 보자면, 다 보지 않은 경우이다. 그렇다면 다 보지 않고도 k번째의 값을 가질 수 있는가? 예를들어 1 2 3 □ 5를 보았다고 해보자. 4라면 happy하겠지만, 6이라면? 장담할 수 없다. 즉 모든 n을 한번씩이라도 다 보지 못했을 경우에는 절대 성립될 수 없다. )
    • maximum구하는 것처럼, 메모리 공간을 두 자리로 만들어서 최대 하나, 그 다음거 하나로 구성한다.
      • k번째를 구하려면 결국에는 O(n^2)이 된다. O(nlogn)보다 작지 않으므로 개선된 것이 없다.
    • 토너먼트 방식으로!
      • 토너먼트 방식으로 진행 > 1등에게 패배한 후보 중에서 가장 큰 것을 고르면? > 2등이 구해진다!
      • 시간 복잡도를 구해보면, 2등 → n + log n. 3등 → n + log n + log n-1, 4등 → n + log n + log n-1 + log n-2 ….. 그렇다면 k번째는? 너무 복잡해진다.
    • 다른 문제로 가보자. (딴 길로 새보자. 딴 길로 새는 것은 보통 좋지 않은 상황이지만 … 이렇게 한 번 가보자!)

Approximately medium

  • 출발 아이디어 : 퀵 소트에서 100퍼센트 미디엄 값은 필요 없다. 중간 근처면 괜찮다!
  • 그 원하는 중간 범위를 비율로 잡아보자 → r (ex r = 0.3)
  • [rn ~ (1-r)n] 등수를 구하고 싶다! → 이와 같이 비율로 다루는 것에 익숙해져야한다!!
  • 그럼 어떻게 구하나 ? Bark at the moon … Bark at the moon … (문 밖에 문…) 어려운 문제다.
  • 지금의 목표를 다시 정의하자. (제목 때문에 헷갈릴 위험이 농후하다.)
  1. Select(n) : n번째의 값을 알아내자.
  2. A(n) : Approximately medium. 배열의 대~강의 중간값을 찾자. (r = 0.3이라고 하자)
    • 다시 시작해보자. n 번째의 값을 구하고 싶었더니, 대강 중간의 값을 구하라고 한다. 대강 중간의 값을 구하는 방법을 살펴보자. (말 자체에서 문 밖에 문 느낌이 많이 난다.)
    • 왜인지는 모르겠지만, 5개씩 나누어서 sort해보자!
      • 5개씩 모인 집합들의 중간값들을 모아보자! (n/5개)
      • 그 중간값들을 sort해 놓았다고 해보자.
      • 수평으로 중간값들을 sort 해 놓았을 때, 그 중앙값들의 집합들을 수직으로 배열해보자.
      • 그렇다면, 중앙값들의 중앙에 있는 값(중값이라 칭하자)을 기준으로 분할해보자.
      • 오른쪽
        • 중앙값 수평 배열 위로는 모두 명백하게 중값보다 작은 값들이다. (아래로는 확실하지 않음)
        • 이 부분은 전체의 몇 비율인가? >> n * (1/2) * (60%) >> n의 30퍼센트!
      • 왼쪽
        • 중앙값 수평 배열 아래로는 모두 명백하게 중값보다 큰 값들이다. (위로는 확실하지 않음)
        • 이 부분은 전체의 몇 비율인가? >> n * (1/2) * (60%) >> n의 30퍼센트!
      • 확실하게 작거나 큰 값들을 모두 제외했을때 (잘라냈을때)의 비율은?
        • 전체의 70퍼센트!
    • 우리는 앞 또는 뒤로 30% 를 잘라낸 어림잡아 중간(Approximately medium) 부분을 구해냈다!
      • 결국 A(n)은 n (5개로 잘라내어 정렬. 5개 안에서 정렬하는 시간은 O(1)이므로 무시가능하다! ) + S(0.2n)(5개씩 정렬 후 중앙값을 모아둔 곳에서 일어나는 일. n의 (1/5)) 이므로 으로 나누어진다.
    •  
    • S(n)은 A(n)을 하고 난 뒤에는
      • n> 피봇 기준으로 잘라내기. 좌우 구별 (기존 quick sort의 과정 수행)
      • S(0.7n) 으로 다시 >> 0.3. 0.3 잘라낸 다음에, 가장 최악의 경우는? 중간값 범위들 사이에서 끝쪽 값을 선택하는 것. 즉, 0.7n인 경우 >> 0.7n을 다시 선택 정렬
        • S(0.7n) = A(0.7)n + 0.7n + S(0.49n)…
        • 계산해보자!
          • S(n) = S(0.2n) + S(0.7n) + cn + d
          • 이 식은 MASTER THEOREM으로 해결할 수 있다!
          • GUESS 방법으로 해결해 보면, 되네 ?!?! 존재하네 ?!?! a랑 b의 항등식이 ?!
        •  

잠깐 … 우리가 이걸 왜 하던거였지?

: 머지 소트 VS 퀵 소트

- 머지 소트는 안전하게 O(nlogn). 퀵 소트는 O(nlogn) 에서 O(n^2)까지 갈 수도 있음. 그런데도 퀵을 쓰는 이유는?? >> 돌려보니까 더 빨랐기 때문! (머지는 추가 메모리를 쓰기 때문에)

- 퀵 소트의 변동성을 줄이기 위해 좋은 pivot을 선택하고자 함. 그래서 selection을 진행한 것.

그런데 이렇게 복잡해지면 … 안 쓴다!

결론.. 

'엄숙한 분위기의 스터디 공간 > 알고리즘' 카테고리의 다른 글

Convex Hull  (1) 2023.10.19
Deadline Scheduling  (1) 2023.10.19
shortest path : 다익스트라.  (1) 2023.10.19
MST : Prim 증명  (1) 2023.10.19
selection sort 증명  (1) 2023.10.19