[알고리즘] LIS : Longest Increasing Subsequnce 알고리즘 - DP 활용(최장 증가 부분 수열)
LIS (최장 증가 부분 수열)란, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 의미한다. 예를 들어, 아래의 그림처럼 수열 {10, 50, 20, 30, 10, 60} 이 있을 때,만들 수 있는 증가하는 수열은 { 10, 50, 60 } 그리고 { 10, 20, 30, 60 } 이다. (이때, 꼭 등차수열이거나 순서가 연속적일 필요는 없다.)이때, 가장 긴 증가하는 부분 수열(LIS)은 { 10, 20, 30, 60 } 임을 알 수 있다. 백준 11053번의 가장 긴 증가하는 부분 수열 의 예시로 알고리즘을 설명하겠다. https://www.acmicpc.net/problem/11053 1. DP 테이블 정의하기수열의 크기가 n인 배열이 입력으로 주어지면, 우리는 i 번째 원소의 LIS..
2024. 8. 28.
