# Foundation/알고리즘
가장 긴 증가하는 부분 수열 (LIS - Longest Increasing Subsequence) 알고리즘
가장 긴 증가하는 부분 수열 (LIS)최장 증가 부분 수열 문제란, 주어진 수열에서 오름차순으로 되어있는 가장 긴 부분수열을 찾는 문제이다. 이 때, 부분수열은 반드시 연속적일 필요는 없으며,필요하다면 중간을 건너뛰는 것도 가능하다. 예를 들어, 수열 A = {10, 20, 60, 50, 30, 40, 20} 에서,가장 긴 증가하는 부분 수열은 A = {10, 20, 60, 50, 30, 40, 20} 이고, 길이는 4 이다. 대표적인 동적 계획법(Dynamic Programming) 문제이며,이 게시글에서 설명할 주제는 다음과 같다.LIS의 특성N^2 문제풀이N*logN 문제풀이경로 역추적 (백트래킹) LIS의 특성어떤 수열에 대해 적절히 n개를 삭제하여 최대한 긴 증가 부분 수열을 만드는 것이므로,이..
2019. 6. 30. 16:25
# Foundation/알고리즘
동적 계획법(Dynamic Programming) 알고리즘
동적 계획법 이름의 유래수학, 컴퓨터 공학, 경제학에서 사용되는 문제풀이 방법. 리처드 벨만이 처음 이 단어를 사용했으며,그의 자서전 '태풍의 눈'에서 다음과 같이 설명했다. 어떤 문제가 다단계로 이루어져 있으며, // sub-structure시간에 대해 가변적이고, // time-varying동적이다. // dynamic 시간에 대해 가변적이라는 특성은, 특히 경제학에서 주로 다뤄지는 것 같다. 동적 계획법이란?하나의 복잡한 문제를, 동일한 구조의 간단한 문제들의 합으로 푸는 방법. 하나의 문제를, 그것과 동일한 형태의 작은 문제들로 나눈 뒤.작은 문제들을 풀어내어 최종적인 문제에 접근하는 것이 그 목적이다. 또한 어떤 문제를 푸는 도중에, 작은 문제들의 결과값이 필요하다면,작은 문제를 푸는 과정으로 ..
2019. 6. 25. 16:16