MODE::CREATIVE

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.참고교재: 쉽게 배우는 알고리즘(문병로)선택 알고리즘 1.선형 시간 선택 알고리즘(QuickSelect)2.최악의 경우 선형 시간 선택 알고리즘 최악의 경우 선형 시간 선택 알고리즘앞서 주어진 리스트에서 k번째로 작은(또는 큰) 요소를 찾는 선택 알고리즘을 구현했습니다.하지만 최악의 경우, 선택한 기준 원소가 항상 최솟값이나 최댓값이 되어, 분할이 매우 불균형하게 이루어지면 재귀 호출이 깊어져 Θ(n²) 시간이 걸립니다. 이를 해결하기 위해서 Median of Medians 알고리즘을 적용해 Θ(n)의 시간 복잡도를 보장할 수 있습니다. Median of Medians 알고리즘 단계그룹화:주어진 배열을 5개씩의 그룹으로 나눕니다. 마지막 ..

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.참고교재: 쉽게 배우는 알고리즘(문병로)선택 알고리즘 1.선형 시간 선택 알고리즘(QuickSelect)2.최악의 경우 선형 시간 선택 알고리즘 선택 알고리즘이란  선택 알고리즘은 주어진 리스트에서 k번째로 작은(또는 큰) 요소를 찾는 알고리즘을 의미합니다. 이 알고리즘은 다양한 방법으로 구현될 수 있습니다. 선형 시간 선택 알고리즘은 최악의 경우에도 O(n)의 시간 복잡도를 가지는 알고리즘입니다. 이 알고리즘의 대표적인 예는 QuickSelect입니다. QuickSelect는 QuickSort 알고리즘을 기반으로 하며, 분할-정복 방식을 사용합니다. 피벗을 선정하고 이를 기준으로 리스트를 두 부분으로 나눈 후, k가 어느 부분에 있는지에 ..