1. 기본적인 $O(n^{2})$ 알고리즘 기본 알고리즘을 다시 한번 생각해보자. 수열 s를 처음부터 순회하면서, i번째 원소를 읽었을때, 0~i번째 원소까지 최장 증가 부분수열의 길이는... i보다 작은 인덱스 j에 대하여, dp배열의 0~j까지 모두 순회해서, j번째 숫자가 i번째 숫자보다 작다면, 그러한 j번째 숫자가 만드는 최장 증가 부분수열에 i번째 숫자를 포함시키면 된다 이렇게 찾은 최장증가부분수열의 길이들의 최댓값이 i번째 원소가 들어가는 최장 증가 부분수열의 길이였다 다익스트라 알고리즘에서 최단거리를 역추적하듯이 생각해보면 아주 심플하다 역추적을 위한 배열 p를 생각해서 현재 i번째 원소에 대한 dp값이 1이라면.. 최장 길이가 1이라는 뜻이니까 자기 자신이 최장 증가 수열의 시작점이니 p..
1. 문제 어떤 수열이 왼쪽에서 오른쪽으로 순서대로 나열된다. 3,2,6,4,5,1.... 만약 이러한 나열된 순서를 유지하면서, 크기가 점진적으로 커지면서, 가장 긴 부분수열은 어떻게 찾을 수 있을까 이러한 부분수열은 연속적으로 고를 필요는 없다. 예를 들어 위 수열에서 3,4,5는 크기가 점점 커지는 부분수열이다. 2. 완전 검색 단순하게 완전 탐색을 수행해서 찾아낼 수도 있다 주어진 수열의 모든 부분집합을 구한다. 부분집합의 원소들이 증가하는 수열인지 검사한다. 증가하는 수열일때, 부분수열의 길이의 최댓값을 갱신한다. 당연히, 부분집합의 크기가 긴 것부터 조사하면, 처음으로 찾게되는 증가수열이 가장 긴 증가수열일 것이다. #완전탐색으로 최장증가 부분수열 찾기 s = [3,2,6,4,5,1] n = ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
