최장 증가 부분 수열

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

컴퓨터 공학에서, 최장 증가 부분 수열(Longest Increasing Subsequence) 문제는, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제이다. 여기서의 부분 수열은 연속적이거나 유일할 필요는 없다. 최장 증가 부분 수열은 알고리즘을 포함한 수학, 랜덤 행렬 이론, 표현론, 그리고 물리학과 관련된 다양한 분야에서 연구되었다.[1] 최장 증가 부분 수열 문제는, 입력 수열의 길이가 n일 때 O(nlogn) 의 시간에 풀이가 가능하다.[2]

같이 보기[편집]

참고 자료[편집]

  1. Aldous, David; Diaconis, Persi (1999), “Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem”, 《Bulletin of the American Mathematical Society》 36 (04): 413–432, doi:10.1090/S0273-0979-99-00796-X .
  2. Schensted, C. (1961), “Longest increasing and decreasing subsequences”, 《Canadian Journal of Mathematics13: 179–191, doi:10.4153/CJM-1961-015-3, MR 0121305 .