백준 알고리즘 No.11053 가장 긴 증가하는 부분 수열

in Study #Algorithm #Python

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.



체감 난이도: ★★★

문제를 이해하는 것부터 어려웠으며, 이번 주 스터디에서 가장 어려운 문제였다.. 사실 지금도 완전히 이해한게 맞는지 스스로에게 의문을 갖는 중…ㅠ

Code

n = int(input())
a = list(map(int, input().split()))

num = [1] * n   # 리스트를 모두 1로 초기화

for i in range(1, n):
    for j in range(i):
        if a[i] > a[j]:
            num[i] = max(num[i], num[j]+1)    # num 값 갱신
            
print(max(num))

Solution

이러한 알고리즘 문제를 LIS(Longest Increasing Subsequence)라고 부른다.


n = int(input())
a = list(map(int, input().split()))

num = [1] * n   # 리스트를 모두 1로 초기화
  • 우선 수열의 개수는 n, 수열은 리스트 a에 입력 받는다.
  • num이라는 리스트에는 증가 부분 수열의 최대 길이를 담는다.
  • num[i] : a[i]를 마지막 값으로 가지는 증가 부분 수열의 최대 길이


for i in range(1, n):
    for j in range(i):
        if a[i] > a[j]:
            num[i] = max(num[i], num[j]+1)
  • 만약 a[i]가 a[j]보다 크다면, num[i]는 잠정적으로 num[j]+1이 된다.
  • 이를 a[i] 이전의 모든 원소들을 순회하면서 num[i] 값을 업데이트한다.
  • 즉, a[i]보다 작은 원소들 중 가장 큰 원소를 a[k]라 했을 때 num[i] = num[k]+1이 될 것이다.

여기에 Dynamic Programming의 원리가 사용되는데, 이는 간단하게 말하면 “답을 재활용하는 것”이다. 자세한 내용은 나무위키 참고..

Another Solution

위의 방법보다 훨씬 빠르게 계산할 수 있는 방법이 있다. 바로 이진탐색을 활용하는 것이다..

✔ Binary Search (이진 탐색)

  • 데이터가 정렬되어 있는 배열에서 특정한 값을 찾거나 삽입하는 효율적인 알고리즘
  • 데이터를 반으로 나누어서 탐색 범위를 좁혀가며 원하는 값을 찾아내는 방식
  • 시간 복잡도: O(log n)

💡 관련 함수: bisect_left(lst, value) & bisect_right(lst, value)

  • 이진 탐색을 사용하여 정렬된 배열 lst에서 원소 value를 삽입할 위치를 반환
  • bisect_left(lst, value): 중복된 값이 있을 때 해당 값의 왼쪽(앞)에 삽입될 위치를 반환
  • bisect_right(lst, value): 중복된 값이 있을 때 해당 값의 오른쪽(뒤)에 삽입될 위치를 반환

Code

코드 출처

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

from bisect import bisect_left

for i in lst:
  k=bisect_left(dp,i)   # 이진 탐색
  print(k)
  if len(dp)<=k:
    dp.append(i)
  else : 
    dp[k]=i

print(len(dp))
  • dp: 최장 증가 부분 수열을 저장하기 위한 리스트
  • bisect_left 함수를 사용하여 dp 리스트에서 i 가 들어갈 위치를 찾는다.
  • 이 위치를 k에 저장한 후에, 만약 dp의 길이보다 k가 크거나 같다면 (현재 원소가 dp의 가장 큰 원소보다 크거나 같다면) dp에 i를 추가

이 방식에 대해 완벽히 이해하기 위해서 각 단계별로 출력해보았다.

from bisect import bisect_left

lst = [10, 20, 10, 30, 20, 50]
dp = []

for i in lst:
    k = bisect_left(dp, i)
    print(f"Current Element: {i}, Insert Index: {k}, Current dp: {dp}")
    if len(dp) <= k:
        dp.append(i)
    else:
        dp[k] = i
    print(f"After Processing: {dp}")

Current Element: 10, Insert Index: 0, Current dp: []
After Processing: [10]
Current Element: 20, Insert Index: 1, Current dp: [10]
After Processing: [10, 20]
Current Element: 10, Insert Index: 0, Current dp: [10, 20]
After Processing: [10, 20]
Current Element: 30, Insert Index: 2, Current dp: [10, 20]
After Processing: [10, 20, 30]
Current Element: 20, Insert Index: 1, Current dp: [10, 20, 30]
After Processing: [10, 20, 30]
Current Element: 50, Insert Index: 3, Current dp: [10, 20, 30]
After Processing: [10, 20, 30, 50]

훨씬 빠르고 간단하다!!


혹시 더 좋은 알고리즘 풀이가 있다면 언제든 댓글로 알려주세요 😃