백준 - 11053번 가장 긴 증가하는 부분 수열 python 문제풀이 [Hellfer]

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

🔷 알고리즘 분류 - 다이내믹프로그래밍, 난이도 - 실버 2

🔶 문제 이해하기 

이 문제는 '가장 긴 증가하는 부분 수열' (LIS, Longest Increasing Subsequence)를 찾는 문제입니다.

부분 수열이란 주어진 수열의 일부를 추출하여 만든 수열을 의미합니다. 이때, 추출된 요소들은 원래 수열에서의 

순서를 유지해야 합니다.

증가하는 부분 수열이란 부분 수열 중에서 각 요소가 이전 요소보다 큰, 즉 수열이 증가하는 형태를 가진 것을 말합니다.

예를 들어, [1, 3, 2, 5, 4]라는 수열에서 증가하는 부분 수열은 [1, 3], [1, 2], [2, 5], [1, 2, 5] 등이 있습니다. 이 중에서 

가장 긴 증가하는 부분 수열은 [1, 2, 5]로, 길이가 3입니다.

문제는 이렇게 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾는 것입니다. 이를 위해 다이내믹 프로그래밍 방법을 사용하게 됩니다.

 

🔶문제풀이 - 다이내믹프로그래밍을 이용한 풀이

# 입력값 N을 정수로 받아옵니다. N은 수열의 길이입니다.
N = int(input()) 

# 수열 arr을 입력받아 정수형으로 변환한 후 리스트로 만듭니다.
arr = list(map(int, input().split())) 

# dp 리스트를 생성하고 모든 요소를 1로 초기화합니다. dp[i]는 i번째 요소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 저장합니다.
dp = [1] * N 

# arr의 두 번째 요소부터 마지막 요소까지 순회합니다. 
for i in range(1, N): 
    # arr[i] 이전의 모든 요소를 확인합니다.
    for j in range(i): 
        # 만약 arr[i]가 arr[j]보다 크다면, arr[i]를 arr[j] 뒤에 붙여 증가하는 부분 수열을 만들 수 있습니다.
        if arr[i] > arr[j]: 
            # 이때, dp[j]에 저장된 부분 수열의 길이에 1을 더한 값과 dp[i]를 비교해, 더 큰 값을 dp[i]에 저장합니다.
            dp[i] = max(dp[i], dp[j] + 1) 

# 모든 요소를 순회한 후, dp의 최댓값을 출력합니다. dp의 최댓값이 가장 긴 증가하는 부분 수열의 길이입니다.
print(max(dp)) 

 

🔶 문제 해결전략

dp를 1로 만들어야 되는 이유??

 

dp 리스트의 각 요소는 해당 인덱스의 숫자를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 의미합니다.

최소한 자기 자신만을 가진 길이 1의 부분 수열은 항상 존재하므로, dp 리스트의 모든 요소를 1로 초기화하는 것입니다.

즉, 각 숫자는 자신 하나로 이루어진 길이가 1인 증가하는 부분 수열을 가집니다. 그래서 dp 리스트는 1로 초기화되어야 합니다.

이후에 알고리즘을 수행하면서, 만약 더 긴 증가하는 부분 수열이 발견되면 그에 따라 dp 리스트의 값을 업데이트

하게 됩니다. 이렇게 dp 리스트는 각 위치에서 만들 수 있는 가장 긴 증가하는 부분 수열의 길이를 저장하게 됩니다.

 

# arr의 두 번째 요소부터 마지막 요소까지 순회합니다. 
for i in range(1, N): 
    # arr[i] 이전의 모든 요소를 확인합니다.
    for j in range(i): 
        # 만약 arr[i]가 arr[j]보다 크다면, arr[i]를 arr[j] 뒤에 붙여 증가하는 부분 수열을 만들 수 있습니다.
        if arr[i] > arr[j]: 
            # 이때, dp[j]에 저장된 부분 수열의 길이에 1을 더한 값과 dp[i]를 비교해, 더 큰 값을 dp[i]에 저장합니다.
            dp[i] = max(dp[i], dp[j] + 1) 

 

 

예를 들어, arr이 [1, 3, 2, 5, 4]라고 가정해 봅시다.

초기에 dp는 [1, 1, 1, 1, 1]로 초기화되어 있습니다.

i가 1일 때, j는 0입니다. arr1은 arr0보다 크므로, dp [1]은 max(dp [1], dp [0] + 1)이 되어 dp [1]은 2가 됩니다.

다음으로 i가 2일 때, j는 0, 1입니다. arr2는 arr0보다 크지만 arr1보다는 작습니다. 따라서 dp [2]는 max(dp [2], dp [0] + 1)이 되어 dp [2]은 2가 됩니다.

i가 3일 때, j는 0, 1, 2입니다. arr3은 arr [0], arr [1], arr [2] 모두보다 크므로, dp [3]은 max(dp [3], dp [0] + 1, dp [1] + 1, dp [2] + 1)이 되어 dp [3]은 3이 됩니다.

마지막으로 i가 4일 때, j는 0, 1, 2, 3입니다. arr4는 arr [0], arr [1], arr [2]보다 크지만 arr [3]보다는 작습니다. 따라서 dp [4]는 max(dp [4], dp [0] + 1, dp [1] + 1, dp [2] + 1)이 되어 dp [4]은 3이 됩니다.

이렇게 모든 위치를 순회하면 dp는 [1, 2, 2, 3, 3]이 됩니다. 이 dp의 최댓값이 가장 긴 증가하는 부분 수열의 길이가 

됩니다. 따라서 이 경우, 가장 긴 증가하는 부분 수열의 길이는 3입니다.

 

🤗파이팅입니다~ 여러분!!🤗