Q&A

• 중간이 홈워크보다 쉽다!

• Partition 알고리즘은 유용한 알고리즘! → 다양한 곳에 쓰인다.

  • pivot을 활용한 알고리즘

• 6주차 q&a6 2번 풀이, 6번 풀이

  • 6번풀이 : n/4이므로, 25 : 75로 나뉨

  

  → O(nlogn)

• 9번 풀이

  • 퀵정렬을 재귀적으로 하다가 나머지가 적당한 값이 남았을때, 삽입정렬을 해주면 러닝타임을 개선할 수 있다.
  • k개가 남을 때까지 퀵정렬해주고 → 각 k 에 대해 삽입정렬 실행
    • n/2^i = k ⇒ i = logn/k
    • 가장 말단의 k개가 n/k개 있으므로 → 삽입정렬 시복 : n/kO(k^2) = O(nk) 선형적
    • 전체 시간복잡도 : O(nk + nlgn/k)

• 10번 풀이

  • median - of - 3 method : 3개를 랜덤으로 골라서 3개중 중간값
    • 이걸 pivot으로 설정하면, 1.5배 나은 성능을 보여준다.

  Q&A7

  • 1번 풀이

    • heapsort와 quicksort는 stable하지 않다(중복된 숫자들의 최초 포지션이 유지되지 않음)
      • Insertion sort, Merge sort, Counting sort, radix sort는 stable!

  • 4번 풀이

    • Radix sort를 이용
      • n^6까지 이므로 counting sort를 6번 부르면됌 O(6(n+n)) = O(n)
        • 차수가 6까지 이므로 6번으로 나눠서 부르면된다

  • 6번 풀이

    

    • c가 정답
      • 숫자의 i번째 자릿수를 알아내는 방법!

  • 8번 풀이

    • stable 특성이 유지가 안되어 중복된 숫자들의 순서가 바뀐다.
    • 바뀌는 건 그것뿐 나머지는 정상적으로 작동한다.

  • 9번 풀이

    • median을 피벗으로 사용하면 시간복잡도?
      • 똑같이 O(nlgn) why? 밸런싱된 서브어레이는 모두 O(nlgn)

  • 10번 풀이

  • 시험범위는 6주차강의까지 + 7주차 Q&A까지(Hashtable x)+ HW

  • 시험 답안 모두 영어로 + 키워드 잘적기

  • Cheating paper A4 한페이지만!(앞면)