Jonyo Programming

배열에 [1,3,2,5,7,6] 라는 값이 들어있을 때 자신의 앞에 있는 수 중에 자신보다 크기가 큰 수의 갯수를 찾으려면 어떻게 해야할까? 즉, i A[j] 를 만족하는 갯수를 찾는것이다. 1은 맨 앞에 있으므로 1보다 앞에 있는 수 중 자신보다 큰 수는 없다. 3은 두번째에 위치하지만 앞에 있는 수가 자신보다 작으므로 자신보다 큰 수는 없다. 2는 자신의 앞에 자신보다 큰 3이라는 숫자가 있다. 이런식으로 배열 원소의 각각의 위치에서 자신보다 "앞에 있는" 수 중에 자신보다 "큰" 수를 찾고 싶을때 쓰인다. 쉽게 떠올릴 수 있는 가장 일반적인 방법은 이중for문을 돌면서 각각의 원소마다 자신보다 큰 수의 갯수를 찾으면 될것이다. 그러나 이건 O(N^2)의 시간복잡도를 가지므로..