백준 11053번 – 가장 긴 증가하는 부분 수열 (Python)

🔷 백준 11053번 – 가장 긴 증가하는 부분 수열 (Python)

---

문제설명

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS: Longest Increasing Subsequence)의 길이를 구하는 문제입니다. 부분 수열이란 원소를 연속적이지 않게 선택해도 되지만, 순서는 반드시 유지해야 합니다. 증가하는 부분 수열이란 앞에 있는 원소보다 뒤의 원소가 더 큰 경우만 연결되는 수열을 말합니다.

---

테스트케이스

입력

6
10 20 10 30 20 50

출력

4

---

문제 구체적 설명 (예시 기반)

입력 수열:

10  20  10  30  20  50

가능한 증가 부분 수열 예:

• 10 20 30 50 → 길이 4 ✅ (정답)
• 10 20 50 → 길이 3
• 10 30 50 → 길이 3
• 20 30 50 → 길이 3
• 10 20 30 → 길이 3

왜 10 20 30 50이 최장인가?

• 10 → 20 (증가)
• 20 → 30 (증가)
• 30 → 50 (증가)
• 길이 4로 다른 어떤 증가 부분 수열보다 길이가 깁니다.

---

아이디어

1. 문제의 목적과 접근법

이 문제는 동적계획법이라는 방법을 사용해서 해결합니다. 동적계획법이란, 전체 문제를 작은 문제로 나누고 그 작은 문제들을 하나씩 해결해서 결과를 저장한 후, 이를 바탕으로 최종 답을 구하는 방법입니다.
주어진 수열은 다음과 같습니다.

{10 20 10 30 20 50}

이 수열 중에서 증가하는 부분 수열의 길이를 찾는 문제입니다.
이때 증가하는 수열이란 숫자가 앞에서 뒤로 갈 때 항상 커져야 하는 수열을 말합니다. 숫자가 같거나 작아지면 증가하는 수열이 아닙니다.

---

2. 증가하는 수열과 증가하지 않는 수열의 예시

이 수열에서 증가하는 경우와 증가하지 않는 경우를 명확하게 구분해 보겠습니다.
증가하는 수열인 경우의 예시

• {20, 10} → 20 > 10이므로 증가하지 않습니다.
• {10, 10} → 10 = 10이므로 증가하지 않습니다.
• {30, 20} → 30 > 20이므로 증가하지 않습니다.
• {20, 20} → 20 = 20이므로 증가하지 않습니다.

이렇게 숫자가 뒤로 갈수록 커져야만 증가하는 수열이 되고, 같거나 작아지는 경우는 증가하지 않는 수열입니다.

---

문제 풀이 과정

시작하기 전에 dp 배열의 의미 설명하기

이제 문제를 풀 때는 dp라는 배열을 사용해서 해결합니다.

• dp 배열의 각 값은 그 위치에서 끝나는 가장 긴 증가하는 수열의 길이를 나타냅니다.
• 처음에는 모두 자기 자신 하나로 이루어진 길이 1인 수열을 갖고 있다고 생각합니다. 따라서 모든 dp값을 1로 초기화합니다.

즉 처음 dp 배열은 이렇게 생겼습니다.

dp = {1, 1, 1, 1, 1, 1}

배열을 단계별로 추적하기 (반복, 중복 허용)

처음 원소는 10입니다.
맨 처음에 있는 숫자 10은 그 앞에 아무 것도 없기 때문에, 길이 1짜리 수열입니다. 그래서 dp값은 처음 초기값 그대로 1입니다.

두 번째 원소 20을 봅니다.

{ 10 [20] 10  30  20  50 }
{  1    1   1   1   1   1 }
  ↑

• 이제 20을 가지고 수열을 만드려면 앞에 있는 10보다 커야 합니다.
• 여기서 20은 10보다 크므로, 10과 20으로 이루어진 {10, 20}은 증가하는 수열이 됩니다.

이제 dp 배열을 같이 보여드립니다.

{ 10 [20] 10  30  20  50 }
{  1    2   1   1   1   1 }
  ↑

여기까지 보면, {10, 20}이라는 길이 2의 증가 수열이 만들어졌습니다.

세 번째 원소 10을 봅니다.

{ 10  20 [10]  30  20  50 }
{  1    2    1   1   1   1 }
        ↑

이제 새로운 숫자 10을 확인합니다.

• 앞의 숫자 10과 같습니다. 숫자가 같으면 증가하지 않습니다. {10,10}은 증가하지 않습니다.
• 10은 그 앞의 20보다 작으므로 {20, 10} 역시 증가하지 않습니다.

dp 배열 상태를 다시 보면:

{ 10  20 [10]  30  20  50 }
{  1    2    1   1   1   1 }
        ↑

• 10은 앞의 숫자들과 비교했을 때 증가하는 관계를 전혀 이루지 못했기 때문에 dp값은 여전히 1로 유지됩니다. (자기 혼자만 수열)

네 번째 원소 30을 봅니다.

{ 10  20  10 [30]  20  50 }
{  1    2    1    3   1   1 }
            ↑

• 30은 앞의 첫 번째 숫자 10보다 크므로 {10, 30}이라는 증가수열을 만들 수 있습니다. → 증가
• 30은 앞의 두 번째 숫자 20보다 크므로 {10, 20, 30}도 가능합니다. → 증가
• 30은 앞의 세 번째 숫자 10보다 크므로 {10, 30} 가능 → 증가

dp를 업데이트합니다:

• 첫 번째 10의 dp값은 1, 여기에 30이 붙으면 2입니다. (현재 dp=2)
• 두 번째 20의 dp값은 2, 여기에 30을 붙이면 길이가 3이 됩니다. (현재 dp=3)
• 세 번째 10의 dp값은 1, 붙이면 길이 2라서 더 커지지 않습니다.

dp 배열 업데이트 후:

{ 10  20  10 [30]  20  50 }
{  1    2    1    3   1   1 }
            ↑

현재까지 가장 긴 증가 수열은 {10, 20, 30}으로 길이 3입니다.
이런 식으로, 앞에서부터 하나하나 반복해서 비교하고, 배열을 중복해서 보여드립니다. 이 방식을 끝까지 반복하면 최종적으로 dp 배열에 저장된 값이 최장 증가 수열의 길이가 됩니다.

---

이런 식으로 전체 배열의 끝까지 똑같이 할 수 있습니다.

배열의 마지막까지 위에서 본 방식과 동일하게 각 숫자별로 앞의 모든 숫자와 비교하고,

• 증가하면 앞의 dp값에서 +1을 해줍니다.
• 증가하지 않으면 dp값을 업데이트하지 않습니다.

이 과정을 끝까지 반복하면,

• 최종 dp 배열은 {1, 2, 1, 3, 2, 4}가 됩니다.
• 이 중 가장 큰 값이 최장 증가 부분 수열의 길이입니다.
• 여기서는 최종적으로 4가 답입니다. {10, 20, 30, 50} 수열입니다.

이렇게 하면 각 과정에서 증가하는 수열과 증가하지 않는 수열을 명확히 구분하고, 배열 상태를 중복적으로 반복해서 확인하면서 최종 답을 얻을 수 있습니다.

---

전체코드

N=int(input())

arr=list(map(int,input().split()))
dp = [1 for _ in range(N)]
for i in range(1,N):
    max_k=0
    for j in range(i-1,-1,-1):
        if arr[i]>arr[j] and dp[j]>max_k:
            max_k=dp[j]
    dp[i]=max_k+1

print(max(dp))

---

개별코드 설명

1. 입력 & 초기화

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

모든 원소는 자기 자신만으로도 길이가 1인 LIS를 형성합니다.

2. 중첩 반복문

for i in range(1,N):
    max_k=0
    for j in range(i-1,-1,-1):
        if arr[i]>arr[j] and dp[j]>max_k:
            max_k=dp[j]
    dp[i]=max_k+1

• i번째 원소를 끝으로 하는 LIS를 찾기 위해 i 이전의 모든 j를 역순으로 확인합니다.
• arr[i] > arr[j]이고 dp[j]가 현재 max_k보다 크면, max_k를 dp[j]로 갱신합니다.
• dp[i]는 max_k + 1로 설정하여, 현재 원소를 포함하는 가장 긴 증가 부분 수열의 길이를 저장합니다.

3. 최대 길이 출력

print(max(dp))

전체 dp 배열 중 최댓값이 LIS 길이입니다.

---

결론

• 이 문제는 전형적인 O(N²) DP로 해결할 수 있습니다.
• 핵심은 "이전 원소 중 arr[j] < arr[i]인 경우의 dp[j] + 1 중 최댓값"을 찾는 것입니다.
• N이 최대 1000이므로 N²(100만) 연산은 충분히 1초 안에 동작합니다.