Selection Problem 선택 알고리즘
Selection Problem 선택 알고리즘 Q. n개의 원소 중 k번째로 큰 숫자는 무엇인가? {45, 33, 21, 5, 6, 8, 63, 54, 76, 82} 선택 알고리즘이란 다음과 같은 문제가 주어졌을 때, O(n) 시간 복잡도를 가지는 풀이법이다. 선택 알고리즘을 설명하기에 앞서, 다른 방식으로 문제를 해결할 때의 시간 복잡도를 확인해보자. 방법1. 가장 큰 숫자를 찾고, 그 숫자를 제외한 나머지에서 가장 큰 숫자를 찾고, ... 이를 반복하는 방법. - k번째 큰 숫자를 찾을 때? 1번째 큰 수는 n번의 비교, 2번째 큰 수는 n-1번의 비교, ... k번째 큰 수는 n-(k-1)번 비교 => 따라서, O(kn) - k=1번째 큰 수는 O(n) - k=n번째 큰 수는 O(n^2) 방법2. ..
2018. 11. 7.
