Count of Smaller Numbers After Self 문제 내용 숫자로 이루어진 Array가 주어지고, 각 숫자의 오른쪽에 위치한 숫자중에 현재의 숫자보다 작은 숫자의 갯수를 맞추는 문제 이다. 접근방법 굉장히 다양한 접근이 가능한 문제이다. 가능하다면 모든 경우의 문제를 푸는 것이 좋다고 생각한다. full search segment tree & binary indexed tree insertion sort merge sort full search 모든 경우의 수를 조회하는 방법이다. 예를 들어 보자. $ [5,2,6,1] $ 이 있다고 생각해 보자. 5보다 작은 우측의 수는 2와 1 두개가 있다. 이것을 알기 위해서는 2,6,1을 한번씩 순회하면 된다. 다음은 2일때다. 2일때는 6과 1 ..

앞서 Segment Tree를 알아 보았다. 2021.05.02 - [Problem Solving] - Segment Tree 그런데 생각보다 개발량도 많고 필요할때 바로 만들어서 쓴다는게 쉽지 않다. 그래서 Binary Indexed Tree를 알아보고자 한다. Binary Indexed Tree는 크게 2개의 Array가 필요하다. N+1 Size의 오리지널 Array N+1 Size의 Fenwick Tree Array 오리지널 Array는 입력하고자 하는 Array 그 자체라고 생각하면된다. [1,3,5,7,9,11,13,15] 라는 배열이 있다면 이것을 Original Array = [NA,1,3,5,7,9,11,13,15] 로 유지 하는 것이다. NA가 들어가는 이유는 첫번째 Value를 1이라..