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 특정 범위의 Array 의 Sum을 빠르게 하기 위해 만들어진 기법이다. 만약 [3,5,8,1,3,9] 라고 하는 Array가 주어 졌다고 생각해 보자. 이를 Tree로 만들면 다음과 같다. 이 Tree에서 주의해서 봐야할 점은 우측에 '0' 이다. 반듯이 Tree의 Balance를 맞춰줘야 한다. 이렇게 Tree가 만들어지면 다음과 같이 Query가 가능하다. [3,5,8,1,3,9] 에서 0 ~ 5까지의 Sum은? 상기와 같이 Index 0과 5 즉 Left Index < Right Index인 관계에서 Left Index가 짝수이면 상위 노드로 올라간다. Right Index 가 홀수이면 상위 노드로 올라간다 라는 개념을 만들 수 있다. 그런데 상위 노드의 Index는 몇인가..

Create Sorted Array through Instructions 문제 내용 빈 Array nums[]가 있고 이곳에 입력할 값 Array 인 instructions가 있다고 할때 instructions Array의 왼쪽에서 오른쪽으로 nums[] Array에 값을 추가해 나간다. 단, nums[]의 Array는 정렬이 되어야 한다. 정렬을 위한 cost는 다음과 같이 정의한다. Min( 현재 있는 nums 중 insturction[i] 보다 작은 숫자의 갯수, 현재 있는 nums 중 instruction[i]보다 큰 숫자의 갯수 ) 예를 들자면 [1,2,3,4,5]의 nums가 주어졌을 때 3을 넣기 위한 최소의 cost 값은 1,2 => 2개, 4,5 => 2개 min(2,2) 임으로 cost..