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

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

LIS Algorithm LIS 알고리즘 (Longest Increasing Subsequence Algorithm) 은 최장증가수열 알고리즘으로 증가하는 원소들의 가장 긴 부분집합을 찾는 알고리즘이다. 다음과 같이 7개의 숫자가 나열되어있을때 여기서 LIS는 위와같이 20 40 50 80 으로 최대길이는 4이다. 물론 아래와 같은 경우도 모두 LIS에 속한다. (LIS알고리즘에서 최대길이를 구성하는 모든 원소들을 구할경우 아래와같이 가능한 경우의 수가 여려개 일수 있기때문에 백준저지에서는 스페셜 저지로 채점을 한다.) + 주의할점은 항상 이전에 선택한 원소보다 커야하기때문에 같은원소역시 연속으로 선택할수 없다. 1. DP(Dynamic Programming) 를 이용한 알고리즘 첫번째로 알아볼 알고리즘..