🍀 Knowledge/알고리즘
[알고리즘] 분할 정복 - Selection, Closest Pair 문제 해결
* 공부를 하며 정리한 글입니다. 수정할 점이 있다면 댓글 남겨주세요. 선택(Selection) 문제 주어진 수들 중 k 번째로 작은 수를 찾아야 하는 문제는 꽤나 자주 등장한다. 실제로 이러한 문제를 해결하는 알고리즘도 간단한 것이 많다. 예를 들어 최소 숫자를 k번 찾는 방법, 숫자를 정렬하고 k번째 숫자를 찾는 방법 등이 있다. 하지만, 앞서 말한 알고리즘의 시간 복잡도를 고려해보자. 각각 최악의 경우 O(kn)과 O(nlogn)이 소요된다. 그렇다면 이보다 더 효율적인 시간으로 k 번째 작은 수를 찾을 수 있을까? 여기에 있어 우리는 "Selection" 알고리즘을 사용할 수 있다. 미리 말하자면 선택(Selection) 알고리즘은 이진 탐색 알고리즘과 매우 유사하다. 이진 탐색은 원하는 수를 찾..
