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