ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2517
    알고리즘/acmicpc 2015. 2. 26. 21:54

    처음에 바로 BIT로 풀어야지 했다가 

    정수의 범위가 1000000000까지인걸 단순히 BIT로 접근해선 안되겠음을 깨달았다.


    이전까지 탐색한 정보들을 Heap에 넣어둘까 하다가 최악의 경우가 O(n*n)이라 별 소용이 없음을 생각하고 다른 방법을 강구...


    그러다가 어차피 선수의 수가 500000이하니까 1~1000000000을 1~500000로 좁히는 방법을 생각했다.


    방법은 1~1000000000의 data들을 정렬해서 그 data의 index값을 BIT에 쓰는 방법이다.

    해당 index 값을 찾는 과정은 이진 탐색이니까 O(log(500000))으로 확 준다.


    그러면 BIT에 index값까지의 합을 확인하고 현재까지 탐색한 선수의 수를 빼주고

    그 index에 1만큼 update한다. 이 과정은 O(logN)


    시간복잡도를 O(NlogN)으로 줄일 수 있었다.



    '알고리즘 > acmicpc' 카테고리의 다른 글

    10159  (0) 2015.02.28
    9489  (0) 2015.02.26
    2517  (0) 2015.02.26
    2568  (0) 2015.02.25
    2109  (0) 2015.02.22
    1914  (0) 2015.02.22

    댓글 0

Designed by Tistory.