3개의 댓글이 있습니다.
-
-
amok -
이진 탐색 트리를 이용할 때, 트리 안에 특정 원소 a보다 큰 원소가 몇 개 있는지 세고, 그 이후에 다시 a를 트리 안에 집어넣고, 이걸 반복하는 식으로 푸셨죠? 세그먼트 트리로도 같은 방법으로 푸시면 됩니다. 구간의 합을 O(log n)에 계산하고, 값의 업데이트를 O(log n)에 처리하는 세그먼트 트리를 구현하신 후, a를 정렬된 부분에 삽입할 때 a라는 인덱스에 해당하는 값을 1 증가시키고, a보다 큰 원소가 몇 개 있는 지 구할 때 a부터 구간의 끝까지의 합을 구하면 됩니다. 소스는 특별히 필요 없을 것 같습니다.
8년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
정용진
이진탐색트리로 문제를 해결했습니다.
처음에 이진탐색트리를 적용하지않고 세그먼트트리를 적용해서 해결하고자 했었는데요.
세그먼트트리를 어떤식으로 적용해야 할지를 몰라서 며칠을 고민하다가 방법을 찾지못해 다른방도를 찾다가 이진탐색트리를 적용해 풀게 되었습니다.
세그먼트트리를 적용한다면 어떤식으로 적용가능할지 적용된 소스를 구할수있을까요?
korea80san@naver.com 로 부탁드립니다.
감사합니다.
8년 전