성장하고 개발하는 계란의 이야기

LIS(Longest Increasing Subsequence )개념  주어진 배열에서 가장 긴 증가하는 부분 수열의 길이를 구하는 코드. DP 방식이나 이분 탐색을 이용하여 풀 수 있다.  예를 들어, 배열 [10, 20, 10, 30, 20, 50]가 주어졌을 때, 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50]로 길이는 4가 된다. 문제 풀이 방식동적 프로그래밍(DP) 방식 - 시간 복잡도: O(n^2)이분 탐색을 이용한 최적화 방식 - 시간 복잡도: O(n log n) 풀이 방식(DP)배열을 순서대로 탐색하면서 dp 배열을 갱신해나가는 방식. 각 위치에서 해당 위치까지의 가장 긴 증가하는 부분 수열의 길이를 저장한다.점화식: dp[i]는 i번째 요소까지의 가장 긴 증가하는 부분 수열의..

문제 풀이 고려해야할 점더보기입력 데이터의 수는 100000개 이하로 최악의 경우를 생각하면 O(nlogn)의 시간 복잡도로 문제를 해결해야 한다. 길이만 출력하는 것이 아닌 제거해야 하는 전깃줄의 번호도 출력해야 하기 때문에 각 경우에 제거되는 혹은 남는 전깃줄의 번호를 저장하고 추적해야 한다. 출력하는 것은 A 기둥의 번호이다. 실수로 B기둥의 번호나 임의로 부여한 인덱스를 출력하지 않도록 주의해야 한다.  문제  해결 아이디어더보기겹치지 않는 경우를 찾으려면 왼쪽과 오른쪽 인덱스가 서로 교차하지 않도록 전깃줄을 선택하면 된다. 즉 왼쪽과 오른쪽 모두 증가하는 전깃줄의 경우의 수 중 가장 많은 수의 전깃줄이 배치된 것을 찾으면 된자. (LIS 문제)가장 긴 증가하는 부분수열은 DP와 이분 탐색으로 풀..