백준 - LIS 알고리즘 관련 문제들 (Python)

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4#s-3.2

최장 증가 부분 수열 - 나무위키

 

LIS 알고리즘 관련된 문제를 쭉 풀어보았다. 생소하고 어려워서 시간은 좀 걸렸지만 이제는 익숙해졌다.

크게 두 가지 방법이 있다. 간단하게 정리하자면,

​

1. O(n2)의 해결 방법

dp로 해결한다. 시작점부터 끝점까지, 끝점을 한 칸씩 옮겨가며 만약 탐색하다가 탐색하는 점이 도착한 점보다 작으면 탐색하려는 점의 dp 값을 기존에 있던 값과 출발한 점+1 중 더 큰 것으로 바꾼다.

이 방법대로라면 어떤 수열이 증가하는 수열인지 파악할 수 있는 것이 장점이다.

11053번이 이 방법대로 풀 수 있는 문제이다. 주어진 값의 개수가 1000개이고 제한시간이 1초이기 때문이다.

​

백준 11053

2. O(n log n)의 해결 방법

길이만을 파악할 때 사용하기 적절한 방법으로, 이분 탐색을 활용한다.

오름차순으로 리스트를 만들어둔 후, 원 리스트의 제일 앞 값을 하나씩 오름차순 리스트에 넣는다.

이때 오름차순 리스트의 가장 큰 값보다 a에서 뺀 값이 더 크다면 그대로 넣는다.

그렇지 않다면, 넣을 수 있는 위치를 찾아 그 값으로 바꿔준다.

12015번이 이 방법대로 풀 수 있는 문제이다. 주어진 값의 개수가 백만 개이고, 제한 시간이 1초이기 때문이다.

​

백준 12015

​

몇 가지 바리에이션 문제가 있었다.

​

백준 11722

Q. 그러면 감소하는 수열은 어떻게 구하나요?

A. 리스트를 거꾸로 돌리기.

​

백준 11055

Q2. 가장 합이 큰 증가하는 부분 수열은 어떻게 구하나요?

A2. 기존 O(n2)풀이에서 lis[i]를 dp에 저장했던 것과 달리 최대 값을 저장.

​

백준 14002

Q3. 어떤 수열이 가장 긴 증가 부분 수열인지는 어떻게 아나요?

A3. 기본적으로 O(n2) 방식의 풀이에서는 dp를 통해 해당 위치에서의 가장 긴 LIS 길이를 기록한다.

이렇게 구한 후 어느 것이 가장 긴 지 알기 위해서는 앞에서부터 보면 안 된다.

예를 들어 1 2 2 3 1 4 2 3 과 같은 식으로 저장되어 있는 dp에서 4는 4 전의 3, 2, 1이 무엇인지를 알 수 있는 단서가 전혀 없다.

그러나 역순으로 가장 큰 수부터 하나씩 내려오면 그것이 '감소하는' 수열임은 틀림없다.

그래서 이 문제도 어느 감소하는 수열인지는 관심을 두지 않는 것이다.

​

백준 12378 (12015와 동일한 코드)

Q4. LIS 알고리즘은 음수가 섞여도 이용할 수 있나요?

A4. LIS 알고리즘뿐만 아니라 이분 탐색 기반 알고리즘은 index를 이용하기에 음/양과 무관하다.

굳이 불안하다면 최소의 음수를 더해 양수로 만들어주자.

​

백준 11054

응용 문제이다. 증가하는 수열과 감소하는 수열이 한 수를 기점으로 맞닿은 경우 이를 바이토닉 수열이라고 한다.

이 때 바이토닉 수열의 길이가 최대가 되려면 어떻게 하면 될까?

생각보다 단순하다. 수의 개수가 1000개이니 다 해보면 된다.

여기까지는 동일하다.

간단하다. a_1, a_2는 아까처럼 수열을 받은 뒤에 a_1을 기점으로 쪼개고 a_2는 거꾸로 뒤집은 것이다.

두 개를 더해 가장 큰 길이를 저장한다.

다만 자꾸 오류가 떠서 반례를 생각해보니, 1 2 2 1처럼 두개가 대칭이면 답은 3이지만 4가 뜬다.

그래서 쪼갠 기점, 즉 a_1[-1]과 a_2[0]이 같은 경우 개수를 하나 빼 준 것이다.

​

백준 14003

마지막 응용 문제는 O( n log n)으로 풀면 LIS가 무엇인지 알 수 있는가에 대한 문제였다.

개수가 1,000,000개이니 n log n으로만 풀 수 있으나, 3초로 더 많은 시간이 주어지니 백트래킹을 추가한다.

이진 탐색은 동일하게 진행하니 이진 탐색 함수는 생략한다.

기존에 이용한 b 리스트에 더해서 dp 리스트를 만든다.

이 dp리스트의 역할은 O(n2)에서의 dp 리스트와 그 역할이 유사하다.

즉 해당 위치에서 가장 큰 LIS의 길이를 기록해두는 것이다.

이렇게 dp 리스트를 만든 후, 뒤집어서 큰 수부터 하나씩 취하면 LIS를 찾을 수 있다.