[알고리즘] BOJ 11722번 - 가장 긴 감소하는 부분 수열(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

5 / 50

 

탐색

5 / 50

 

기초 동적 프로그래밍

6 / 50(NEW!)

 

투포인터

0 / 10

---

문제

11722번: 가장 긴 감소하는 부분 수열 (acmicpc.net)

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

→ solved.ac 기준 실버 2

---

문제 해결 아이디어

가장 긴 증가/감소하는 부분 수열은 대표적인 DP 문제

→ 수열 A에서 감소하는 부분 수열의 길이를 미리 저장해두자.

보기에서처럼 A = [10, 30, 10, 20, 20, 10]이라고 가정

cache[0] = 1(10)

cache[1] = 1(30)

cache[2]  = 2(30, 10) = cache[1] + 1

cache[3] = 2(30, 20) = cache[1] + 1

cache[4] = 2(30, 20) = cache[3] = cache[1] + 1

cache[5] = 3(30, 20, 10) = cache[4] + 1

...

cache[i]는 A[i]보다 작은 A의 0부터 i-1 중

캐시에 저장된 값이 가장 큰 값에 + 1을 해준다.

 

예를 들어 위에서 cache[5]와 같은 경우

인덱스의 0부터 4까지 탐색했을 때 자신보다 큰 값은 30, 20, 20이 있다.

30, 20, 20의 인덱스는 각각 1, 3, 4인데

cache[1], cache[3], cache[4] 중 가장 큰 값에 +1을 해준다는 뜻.

 

만약 A[i]보다 작은 값이 없다면 혼자만 되므로 cache[i]는 1이 된다.

---

구현

내 풀이

import sys
input = sys.stdin.readline

n = int(input())
array = list(map(int, input().split()))
cache = [1 for _ in range(n)]

for i in range(1, n):
  value = array[0]
  for j in range(i):
    if array[i] < array[j]:
      cache[i] = max(cache[i], cache[j] + 1)

print(max(cache))

---

메모

• 걸린 시간: 45분

---

마치며

가장 긴 감소하는 부분 수열이 뭔 말인지 순간 헷갈려서

이해를 위해 찾아보다가 DP에서 흔한 문제라는 걸 알게 됐다.

가장 긴 증가하는 부분 수열은 이미 푼 적이 있더라..ㄷㄷ

 

찾다보니 위와 같은 부분 수열은

시간 복잡도를 따졌을 때 내가 제출한 알고리즘은 베스트가 아니었다.

이분 탐색으로 이중 for문을 돌지 않고도 하는 방법이 있는데,

나중에 관련 문제도 다 풀어봐야겠땅

 

+ LIS 관련 백준 문제들:

• 11053번. 가장 긴 증가하는 부분 수열
• 11054번. 가장 긴 바이토닉 부분 수열
• 11055번. 가장 큰 증가하는 부분 수열
• 11722번. 가장 긴 감소하는 부분 수열
• 12738번. 가장 긴 증가하는 부분 수열 3
• 14002번. 가장 긴 증가하는 부분 수열 4
• 14003번. 가장 긴 증가하는 부분 수열 5