코딩테스트
최장 증가 수열(LIS), 최장 공통 문자열(LCS)
lis는 10, 20, 10, 30, 20, 50 이런 길이 5의 수열중 10, 20 ,30 ,50 과 같이 계속해서 증가하는 수열들 중, 가장 긴 수열을 찾는 문제다. 우선 lcs는 푸는 방식이 정말 다양한데, 전부 시간 복잡도가 다르다. dp를 통해서 풀게되면 O(N^2) 이고, lower_bound를 통해서 풀게 되면 O(NlogN) 의 시간 복잡도가 발생한다. lis 문제는 시간초과를 가지고 장난을 많이 치기에 lower_bound 방식만 가지고 문제를 풀어보겠다. 자세한건 아래 문제를 보면서 알아보자..! 1.lis 의 길이는? lis의 길이를 구하는 문제로, 위 의 입력의 경우 10,20,30,50 이기에 4가 정답입니다. 흔히 전깃줄 문제로 응용 됩니다. 자세한 건 아래 문제를 확인 해봅시다..
