Young Tableau: 삽입 정렬형 격자, LIS

Young Tableau, 영 태블로, Young diagram

정의

Young Tableau 는 왼쪽/위쪽 원소가 항상 아래/오른쪽 원소보다 작은 정수 격자입니다. RSK correspondence (Robinson-Schensted-Knuth) 로 순열 <-> Young tableau 쌍이 일대일 대응됩니다.

LIS 응용

수열의 Longest Increasing Subsequence 길이 = RSK 로 얻은 tableau 의 첫 행 길이.

input: [3 1 4 1 5 9 2 6]

insert 3:  [3]
insert 1:  [1] , bump 3
           [3]
insert 4:  [1 4]
           [3]
insert 1:  [1 1] , bump 4
           [3 4]
...

참고

• LIS
• 순열