목록백준12015 (1)

프로그래밍에 대한 고찰 및 생각

[2][LIS : 최장증가수열 알고리즘] - Lower Bound 를 이용한 알고리즘 (Longest Increasing Subsequence Algorithm)

2. Lower Bound 를 이용한 알고리즘 두번째로 알아볼 알고리즘은 Lower Bound를 이용한 알고리즘이다. 시작하기에 앞서 Lower Bound란 정렬된 배열에서 찾고자 하는 값 이상이 처음으로 나타나는 위치를 말한다. 다음과 같은 배열에서 35의 lower bound는 40 이다. 위의 정의대로 처음으로 나타나는 자신보다 큰값 이라고 생각해도 되고 자신보다 큰 값들중 가장 작은 값 으로 생각해도 된다. 이 lower bound 알고리즘을 이분탐색으로 구현하게 될텐데 여기서는 lis[] 배열을 만들어서 사용할것이다. lis[i] 의 정의는 (i+1)의 길이를 갖는 최대증가수열을 만들때, 가능한 가장 작은 수를 의미한다. 먼저 전체코드는 다음과 같다 int lis_lowerbound(int n)..
알고리즘/LIS 알고리즘 (최장증가수열 알고리즘) 2020. 2. 20. 21:13
이전 Prev 1 Next 다음