Algorithm - LIS(Longest Increasing Subsequence) 코딩테스트 문제를 풀다보면 자주 마주치는 문제 알고리즘 유형에 대해 정리해보려고 한다. 첫번째로 정리할 내용은 **LIS(Longest Increasing Subsequence)**이다. LIS(최장 증가 부분 수열) 문제는 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다. LIS 란 LIS라는것은 한국말로 번역하면 최장 증가 부분수열이라고 할 수 있다. 말로만 하면 제대로 이해가 안될 수 있다. 예를 들어 설명하도록 하겠다. 아래와 같이 임의의 수열이 주어졌다고 하자. 위 수열에서 숫자 몇 개를 제거해서 아래와 같이 부분 수열을 만들 수 있다. 2 6 8 3 3 4 5 1 2 3 4 5 등등.. 위와 같은 수열들..