LIS - 최장 증가 부분 수열(Longest Increasing Subsequence) 정리
컴퓨터 공학에서, 최장 증가 부분 수열(Longest Increasing Subsequence) 문제는, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분수열을 찾는 문제이다. 여기서의 부분 수열은 연속적이거나 유일할 필요는 없다. 최장 증가 부분 수열은 알고리즘을 포함한 수학, 랜덤 행렬 이론, 표현론, 그리고 물리학과 관련된 다양한 분야에서 연구되었다.[1] 최장 증가 부분 수열 문제는, 입력 수열의 길이가 n일 때 O(nlogn)의 시간에 풀이가 가능하다.[2] 출처: 위키피디아 4.1. 정렬 문제[편집] 사람들이 각각 번호를 가지고 있고 그 번호 순서에 맞춰서 일렬로 정렬하려고 한다. 이때 움직인 사람들의 총 수를 최소로 하고 싶다면 어떻게 해야 하는가? (단, 초기에 사람들은 무작위로 일렬로 섞..