[BOJ] 2631번: 줄세우기 (LIS) / LIS 알고리즘 문제

 

LIS 유형 암기 !! (LCS랑 다름 주의)

 

문제 링크

https://www.acmicpc.net/problem/2631

 

완전 똑같은 문제 유형

• 12015번: https://www.acmicpc.net/problem/12015
• 12738번: https://www.acmicpc.net/problem/12738
• 2352번: https://www.acmicpc.net/problem/2352
• 14003번: https://www.acmicpc.net/problem/14003

 

TIL

• LIS(Longest Increasing Subsequence)는 언제 사용하면 좋을까?
  • 배열의 일부 원소를 유지하면서 순서를 정렬해야 할 때
  • 최소한의 이동, 제거, 삽입을 통해 정렬된 부분 수열을 만들 때
  • 데이터를 정렬된 상태로 유지하는 최적의 방법을 찾을 때

[ 문제 접근 방법 ]

1. 이동하지 않고 그대로 둬도 되는 아이들을 찾는다.
   • 이는 현재 줄 서 있는 아이들 중에서 가장 긴 증가하는 부분 수열(LIS)에 해당하는 아이들이다.
   • LIS에 포함된 숫자는 제자리에 그대로 두면 된다.
2. 나머지 아이들을 최소한으로 이동한다.
   • 전체 아이 수(N)에서 LIS의 길이를 빼면 최소한으로 이동해야 하는 아이들의 수가 된다.

• LIS의 길이를 구하는 방법 >> bisect 사용 !!!!!
• 주의할 것 : bisect은 "길이"만을 구하는 거고, 실제 배열을 구하지는 못함 !! 그럴거면 DP를 사용 or 역추적 추가 (O(N^2)) 

 

• bisect는 이진 탐색을 이용해 정렬된 배열에서 빠르게 원소를 삽입하거나 위치를 찾는 Python 표준 라이브러리 모듈
  • 시간 복잡도: O(log N) (이진 탐색 사용)
  • 주로 사용되는 함수:
    • bisect.bisect_left(arr, x): 정렬된 배열 arr에서 x를 삽입할 수 있는 가장 왼쪽 위치를 찾음
    • bisect.bisect_right(arr, x): x를 삽입할 수 있는 가장 오른쪽 위치를 찾음
    • bisect.insort_left(arr, x): x를 정렬된 위치에 삽입 (왼쪽 기준)
    • bisect.insort_right(arr, x): x를 정렬된 위치에 삽입 (오른쪽 기준)
    • 음수도 지원 !! 

LIS vs. LCS

• "배열에서 정렬된 부분을 유지하면서 최장 길이 찾기" → LIS
• "두 개의 문자열에서 공통된 순서를 유지하면서 최장 길이 찾기" → LCS
• 따라서 LIS는 정렬 문제와 관련이 많고, LCS는 문자열 비교 문제에서 주로 사용됩니다

 

 

 

[ 처음 코드 ] - LIS를 구현하려고 나름 노력함

n = int(input())

def solution():

    children = [int(input()) for _ in range(n)]
    lis = []

    cnt = 0
    for i in range(n):
        pivot = children[i]
        for j in range(i+1, n):
            if pivot < children[j]:
                cnt += 1
                pivot = children[j]
        lis.append(cnt)
        cnt = 0

    return n-max(lis)

if __name__=="__main__":
    solution()

• 코드의 문제점
  • 제대로 된 LIS를 찾아낼 수 없음
  • 3 7 5 2 6 1 4 인 경우, {3 7} 찾고 끝나버림 ( {3 5 6} 이 더 김)

 

 

Code

import bisect

n = int(input())
children = [int(input()) for _ in range(n)]
lis = []

for i in range(n):
    pos = bisect.bisect_left(lis, children[i])
    if pos == len(lis):
        lis.append(children[i])
    else:
        lis[pos] = children[i]

print(n-len(lis))