서로 다른 8개의 값에서 두 번째로 큰 값을 항상 찾기 위해 최악의 경… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 알고리즘] 26년 1회차
서로 다른 8개의 값에서 두 번째로 큰 값을 항상 찾기 위해 최악의 경우 필요한 최소 비교 횟수로 가장 옳은 것은?
1
8
2
9
3
13
4
24
해설
최악의 경우 필요한 최소 비교 횟수는 , 즉 9회다.
토너먼트 방식으로 최댓값을 찾는 데 회가 들고, 두 번째로 큰 값은 반드시 최댓값에게 직접 진 값 가운데 있다.
최댓값은 번 비교에 참여했으므로, 그 3개 중 최댓값을 고르는 데 2회가 더 든다.
- 8회: 최댓값을 찾는 7회에 1회만 더한 값으로, 후보 3개를 가리기에 부족하다.
- 13회: 최댓값을 찾은 뒤 나머지 7개를 순차 비교한 회로, 최소 횟수가 아니다.
오류나 개정된 내용이 보이면 알려주세요