풀이
증가하는 부분 수열이라는 말을 보고 LIS(최장 증가 부분 수열)알고리즘이 떠올라야합니다.
LIS
배열 내에서 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그러한 부분 수열 중 길이가 가장 긴 수열을 LIS(최장 증가 부분 수열)라고 합니다.
해당 문제에서는 {10, 20, 30, 50}이 LIS입니다.
참고: https://chanhuiseok.github.io/posts/algo-49/
문제의 이해
해당 문제가 LIS 자체를 찾는 것이라면 조금 더 문제가 복잡해질 수 있지만 이 문제의 경우는 LIS의 길이를 물어보고 있습니다.
일반적으로 LIS의 길이를 구하는 것은 dp와 이분탐색이 있습니다. 하지만 이 문제에서는 dp로 풀 경우 시간초과가 나므로 이분탐색으로 푸는 것이 좋겠습니다.
LIS를 구성할 res에는 당연히 오름차순으로 숫자가 들어가야할 것입니다.
문제의 핵심은 LIS의 길이를 물어보고 있다는 점입니다. LIS가 엉망이어도 상관이 없습니다.
- res에 배열의 첫번째 값을 넣어줍니다.
- for문으로 배열의 끝까지 검사를 하게 되는데
2-1. res에서 가장 큰 값보다 arr[i]가 더 크다면 그대로 res에 append해줍니다.
2-2. 아니라면 res 배열에서 해당하는 숫자가 있는지 이분탐색으로 찾아보고 res[index]에 arr[i]를 넣어줍니다. - res의 길이를 출력합니다.
문제는 LIS의 길이를 묻는 것이다.
여기서 2번에서 많은 생각이 들기 시작합니다. LIS는 각 원소가 이전 원소보다 크다는 조건을 만족하고 그 순서를 무시하면 안되는데 for문을 돌리다가 res의 최댓값보다 작은 수가 뒤에 나왔는데 res에 해당하는 숫자를 업데이트를 해주니까 말이죠.
하지만 이것은 LIS의 길이를 구하는 문제이기 때문에 상관이 없습니다.
res에 k개의 숫자가 들어가있다고 가정하면 우리는 가장 큰 res[k]만 신경쓰면 됩니다. res의 길이가 길어지기 위해선 res[k]보다 큰 수가 들어와야하니까요.
그래서 res[0]~res[k-1]까지의 숫자는 바뀌어도 정답에는 영향이 없습니다.
예를 들어 입력 값으로
7
10 20 10 30 20 5 50
을 넣게 되면 LIS는 {10, 20, 30, 50}입니다.
하지만 실제 위에 있는대로 문제를 풀게 되면 {5, 20, 30, 50}이 res에 담겨있습니다.
n = int(input())
arr = list(map(int,input().split(" ")))
def binary_search(start,end,target):
if start > end:
return start
mid = (start+end) // 2
if res[mid] > target:
return binary_search(start,mid-1,target)
elif res[mid] == target:
return mid
else:
return binary_search(mid+1,end,target)
res = [arr[0]]
for i in range(1,len(arr)):
if res[-1] < arr[i]:
res.append(arr[i])
else:
res[binary_search(0,len(res)-1,arr[i])] = arr[i]
print(len(res))