세그먼트 트리, 펜윅 트리, 이진 검색 트리등을 이용하면 앞에 있는 값들 중 기준값보다 큰 값이 몇 개 있는지 O(log n)에 셀 수 있습니다. 단순한 방법으로 센다면 O(n)의 사간이 걸리게 되고, 이는 정렬을 하는 것과 같은 시간복잡도이므로 그렇게는 해결할 수 없습니다.
답변감사합니다. 제가 능력이 부족해서 그런데요.
이진탐색등을 이용하고자 하면 기본적인 전제가 정렬이되어있어야 하지않나요?. 세그먼트트리도 기본적으로 정렬된 데이터를 미리계산해서 검색시 빠르게 검색하고자 하는거 같은데요. 이러면 결국 정렬에 대한 시간이 들어서 문제를 풀수없지 않는가요? std::map을 이용해서 정렬후 데이터를 조회하게도 했었는데 시간초과가 발생했습니다.
제가 어디서 잘못한걸까요? 아 머리가 굳어서그런지 생각이 안나네요;;
정용진
정렬이 답이 아닌거같아 삽입정렬이 이뤄지는 원리가
기준값에서 앞에있는 값들중 기준값보다
큰수의 갯수만큼 이동하는거라 생각되어
정렬을 하지않고 기준값기준 카운트만 계산했습니다.
하지만 시간초과가 뜨네요.
어떻게 해야할지 방향을 못잡고 있습니다.
힌트하나만 투척해주세요~
9년 전