최대 증가 부분 수열
최대 증가 부분 수열(LIS)이 뭘까요? 최대 증가 부분 수열(Longest Increasing Sequence)은 오름 차순으로 증가하는 부분 수열 중 가장 긴 부분 수열을 의미합니다.하나의 예시를 통해서 알아보겠습니다.10 20 30 10 40 50 오름 차순으로 증가 하는 부분 수열 중 가장 긴 부분 수열은 어떻게 될까요? 10 20 30 20 40 50 [10,20,30,40,50]이 됩니다. 중간에 20이 있는데 오름 차순으로 증가하는 부분 수열이 아니지 않나요?10 20 30 20 40 50 [10,20]도 오름 차순으로 증가하는 부분 수열입니다. 어떤 부분 수열 배열이 최대 증가 부분 수열일까요? [10,20,30,40,50]은 길이가 5인 부분 수열이고, [10,20]은 길이가 2인 부분..
2025. 2. 22.
