LIS 란?
LIS(Longest Inceasing Sequence)란? LIS는 Longest Increasing Subsequence의 약자로 최장 증가 수열 또는 최장 증가 부분수열이라고 합니다. LIS를 이해하기 위해서는 먼저 Increasing Subsequence 한글로 증가 부분수열을 알아야 합니다. 증가 부분수열을 말 그대로 증가하고 있는 부분 수열을 나타냅니다. 가령 [5, 1, 9, 2, 7, 3, 8, 4, 6] 이라는 리스트가 존재할때 여기서 증가하는 부분 수열을 찾아 보겠습니다. [5, 9], [5, 7, 8], [1, 2, 7, 8] 등등 다양한 증가하는 부분수열이 존재합니다. 이중 가장 길이가 큰 최장 증가 부분 수열은 [1, 2, 3, 4, 6]이 됩니다. 이 최장 증가 부분 수열을 찾는..
2023. 9. 21.
Inversion Counting 알고리즘
Inversion Counting 이란? Inversion Counting 이란 역순으로 되어 있는 순서쌍의 개수를 세는 유명한 알고리즘 입니다. 쉽게 예를 들면 아래와 같은 숫자가 있습니다. 3 2 5 4 1 이렇게 5개의 숫자가 있습니다. 하나씩 비교해보면 (3, 2)는 3이 더 크기 때문에 역순으로 되어 있습니다. (3, 5)는 역순이 아닙니다. (3, 4) 역시 역순이 아닙니다. (3, 1)은 역순으로 되어 있습니다. 이런식으로 모든 순서쌍을 비교해보면 아래와 같은 순서쌍을 찾을 수 있습니다. (3, 2), (3, 1), (2, 1), (5, 4), (5, 1), (4, 1) 이렇게 6개의 순서쌍을 찾을 수 있습니다. 이것은 버블 정렬을 진행할 때 몇 번이나 교환을 진행하는지의 숫자와 같습니다. ..
2023. 9. 11.
