서로 다른 8개의 값에서 두 번째로 큰 값을 항상 찾기 위해 최악의 경… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
서로 다른 8개의 값에서 두 번째로 큰 값을 항상 찾기 위해 최악의 경우 필요한 최소 비교 횟수로 가장 옳은 것은?
1
8
2
9
3
13
4
24
해설

최악의 경우 필요한 최소 비교 횟수는 n+⌈log⁡2n⌉−2n+\lceil \log_2 n \rceil-2, 즉 9회다.

토너먼트 방식으로 최댓값을 찾는 데 n−1=7n-1=7회가 들고, 두 번째로 큰 값은 반드시 최댓값에게 직접 진 값 가운데 있다.

최댓값은 log⁡28=3\log_2 8=3번 비교에 참여했으므로, 그 3개 중 최댓값을 고르는 데 2회가 더 든다.
7+2=97+2=9

  • 8회: 최댓값을 찾는 7회에 1회만 더한 값으로, 후보 3개를 가리기에 부족하다.
  • 13회: 최댓값을 찾은 뒤 나머지 7개를 순차 비교한 7+67+6회로, 최소 횟수가 아니다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기