Min IT's Devlog

전에서 관련 알고리즘을 찾아보고 코딩 문제를 해결했던 것 같은데 오랜만에 다시보니 기억이 나지 않아 이번에 정리해보고자 한다. 언어는 python을 사용해서 진행해보고자 한다. 최장 증가 부분 수열(Longest Increasing Subsequence) 해당 알고리즘은 DP(Dynamic Programming) 문제로 자주 나오고 있으며 O(N^2)의 시간복잡도를 가지고 있는 알고리즘과 O(NLogN)의 시간복잡도를 가지고 있는 알고리즘이 존재한다. [개념] LIS는 어떤 수열에서 만들 수 있는 부분수열 중에서 가장 길면서 오름차순을 유지하는 수열이다. 여기서 부분 수열이란 주어진 수열에서 일부 수를 뽑아내어 만든 수열을 의미한다. 2 5 3 1 4 7 6 예를 든다면 위에 주어진 수열에서 부분 수열은..