Jonyo Programming

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

LIS(Longest Increasing Subsequence) 알고리즘은 '가장 긴 증가하는 부분 수열' 알고리즘으로도 불린다. 주로 그리디 알고리즘이나 다이나믹 프로그래밍의 예시로 등장한다. LIS는 수열 내 증가하는 부분 수열 중 가장 긴 수열을 말한다. 예를들어 아래와 같은 수열이 존재할때 3 1 5 2 4 2 이때 가장 긴 증가하는 부분 수열은 {1,2,4}이며 길이는 3이다. 3 1 5 2 4 2 아래의 예시에서는 가장 긴 증가하는 부분 수열은 {10,20,30,50} 이며 길이는 4가 된다. 10 20 10 30 20 50 이제 이 알고리즘을 이용하는 문제를 해결해 보자. BOJ : 11053 가장 긴 증가하는 부분 수열 이 문제를 어떻게 풀어야할까? 이 문제는 동적계획법을 이용하여 O(N²..