TMI 1. 요즘 다시 FM 시작. 본머스로 하는데 첫 시즌 바로 5위 찍어버렸네. 다음 시즌은 챔스 ㄱ.
TMI 2. 오늘 점심은 버거킹 시켜먹었지롱. 버거킹 어플로 시키니까 배달비는 없는데 최소 주문 금액이 14000원 이더라. 高... 이득인가 아닌가.

어쨌든 오늘도 열심히 코딩이나 하자.

---

LIS

LIS, Longest Increasing Subsequence. 가장 긴 증가하는 부분 수열이라는 뜻.
오늘도 파이썬 코테 문제를 풀다가 이런게 튀어 나왔다.
백준 12015번 : 가장 긴 증가하는 부분 수열 2

푸는 일반적인 방법은 DP를 이용하는 것이다. 그래 C# 기본 강의에서도 이런 문제를 풀었었다.
Do you know DP?

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

dp = [1] + [0 for _ in range(N-1)]

answer = 1
for i in range(1, N):
    temp = 0
    for j in range(i):
        if arr[i] > arr[j]:
            temp = max(temp, dp[j])
    
    dp[i] = temp + 1
    answer = max(answer, dp[i])

print(answer)

이렇게 한번 쓰-윽 작성해보고 채점해본 결과 시간초과. 아니 그 때는 이렇게 해서 하면 된다고 배웠는데 외않됄까 ? 결국 못풀고 즉시 구글링 ㄱㄱ.

구글링 한 결과 DP를 이용하면 시간 복잡도가 O(N^2)이 된다고 하네. 그래서 이를 개선하기 위해서는 이분탐색을 해야한다...? 이분탐색이 왜 거기서 나와...

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
LIS = [0]

for num in arr:

    if LIS[-1] < num:
        LIS.append(num)

    else:
        left = 0
        right = len(LIS)

        while left < right:
            mid = (right + left) // 2

            if LIS[mid] < num:
                left = mid + 1
            else:
                right = mid

        LIS[right] = num

print(len(LIS) - 1)

이분 탐색을 이용하면 시간 복잡도를 O(NlogN)으로 줄일 수 있다고 한다.
하지만 이분 탐색을 통해 LIS를 구하고 그 속을 들여다보면 실제 LIS와는 값이 다르다. 왜냐하면 배열에서 뒤에 있던 원소가 먼저 들어온 원소보다 lower_bound로 탐색된 최적의 위치가 앞에 있을 수도 있기 때문이다.
따라서 배열에 들어있는 값들은 LIS를 이루는 요소와 무관하다는 것이다.

흠.. 그럼 적절한 상황에 맞춰 DP나 이분탐색을 써야겠고만. 알아두자

---

세줄 요약

• 파이썬 공부는 끝이 없다
• 여러가지 구현 방법을 알아놓자 - 상황에 맞게 쓸수 있도록
• 여백의 미