log/Memo
최소 맨해튼 거리, 배열에서 K번째 원소 찾기
ycs1m1yk
2022. 7. 26. 18:26
14400번: 편의점 2
영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고
www.acmicpc.net
맨해튼 거리
- 각 축의 거리는 독립적이다.
- 최소 맨해튼 거리를 갖는 점은 중간점이다 (medoid?)
선택 알고리즘을 잊지말자
배열에서 k번째 원소를 찾을 때
- 정렬 후 k번째 원소 찾기
: 최선 $O(n)$, 평균 $O(nlogn)$ (Tim sort를 사용하는 V8 엔진 기준) - 선택 알고리즘으로 k번째 원소 구하기
: $O(n)$