과외 - 알고리즘
-
선택(Select)과외 - 알고리즘/과제 2018. 9. 6. 18:36
SelectContents정렬반을 졸업한 소년 빌게이츠는 정렬과는 다른 새로운 문제를 만났다. 문제는 n개의 원소가 아무런 규칙 없이 저장된 배열에서 i번째 작은 원소를 찾는 것이다. 이러한 문제를 다루는 알고리즘을 선택 알고리즘이라 하는데 평균적으로 선형시간(O(n))이 걸리는 선택 알고리즘은 다음과 같다. select(A[], p, r, i) //배열 A[p..r]에서 i번째를 찾는다.{ if(p == r) return A[p]; q = partition(A, p, r); //QuickSort에서 partition과 같음 k = q - p + 1; if(i k) return select(A, q + 1, r, i -..
-
정렬(Sort)과외 - 알고리즘/과제 2018. 9. 6. 18:35
Selection-SortContents소년 빌게이츠는 학원에서 알고리즘 수업에서 선택정렬을 배웠다. 학원 선생님이 말하길 제일 큰 원소를 찾아서 뒤로 옮기면 정렬이 된다고 했다. 학원 선생님이 전수해준 비기는 다음과 같다. 1. A[1..k]중 가장 큰 원소를 찾는다. 2. 가장 큰 원소를 A[k]와 바꾼다. (매번의 반복 마다 swap은 한번만 일어나야한다.) 3. 배열의 크기가 n이라고 할 때, k = n 부터 k = 2 까지 위 과정을 반복한다. 소년 빌게이츠는 수행 시간을 측정하기 위해 1번에서 최대값을 찾기 위해 수행하는 비교 횟수를 다음의 조건에 따라 측정하기로 했다. 여러분이 해야하는 일은 소년 빌게이츠를 도와 선택정렬의 비교 회수를 출력하면 된다. 선택정렬은 소년 빌게이츠가 배운대로 구현..