11053번 - 가장 긴 증가하는 부분 수열 (LIS)

가장 긴 증가하는 부분 수열을 탐색하는 문제입니다.
이 문제는 이분 탐색과 DP 두 가지 방법으로 풀이할 수 있으나 저는 DP 연습중이므로 DP로 풀겠습니다.

알고리즘 분석

DP로 풀이하는 방법은 다음과 같습니다.

위와 같이 생긴 리스트와 DP가 존재한다면

이러한 씩으로 현재 조사값 이전 값들 중에서 작은 값들이 존재한다면 해당 작은 값들의 DP값들 중에서 제일 큰 DP + 1을 현재 조사값 DP에 넣어주는 씩으로 코딩하면 됩니다.

코딩

N = int(input())
lst = list(map(int,input().split()))
dp = [1]*len(lst)

먼저 수열의 최소 길이는 1이므로 1을 len(lst)만큼 만들어줍니다.

for i in range(len(lst)):
    maximum = 0
    for j in range(i):

현재 조사값은 lst[i], 이전 값들 조사는 lst[j]로 맡겠습니다.

        if lst[j] < lst[i]:
            if maximum < dp[j]:
                maximum = dp[j]
            dp[i] = maximum + 1      

만약 현재 조사값보다 이전 조사값이 더 작다면, 이전 조사값들 중 제일 큰 DP를 maximum에 넣어주고 maximum + 1을 현재 조사값의 DP에 기록하겠습니다.

print(max(dp))

그중에서 가장 큰 값을 출력하면 됩니다.

11722번 - 가장 긴 감소하는 부분 수열

원리만 알면 거의 보너스 문제라고 할 수 있습니다.
마찬가지로 현재 조사 값 이전 값들 중에서 큰 게 존재한다면 이전 값들 max(DP) + 1을 현재 조사값 DP에 대입시켜주면 되는 방식입니다.

N = int(input())
lst = list(map(int,input().split()))
dp = [1]*len(lst)

for i in range(len(lst)):
    maximum = 0
    for j in range(i):
        if lst[i] < lst[j]:
            if maximum < dp[j]:
                maximum = dp[j]
            dp[i] = maximum + 1

print(max(dp)) 

오답 풀이중

15686번 - 치킨 배달

거의 다 푼거 같은데 안풀리는 문제입니다.
지난번 풀이 후 질문을 올려봤는데


라고 친절히 답변해주셔서 저 문제를 살펴봤습니다.

? ㅋㅋㅋㅋㅋㅋ
이게 어떤 말씀하시는지는 감이 잡히는데 (조합 코드 작성할 때 visited를 쓰지 말고 count 변수 증가 형식으로 재귀를 돌려서 백트래킹 부분 시간복잡도를 줄여라? 이런 느낌인 것 같습니다)

정말 한 5시간동안 고민해도 결국 못풀었습니다. 다른 문제 좀 더 살펴보다가 풀어야 할 것 같습니다.