백준 11053번 - 가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열 문제 바로 가기

풀이 날짜: 2026-02-15

baekjoon 알고리즘 문제 풀이

풀이 코드


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

dp = [1] * (n+1)

for i in range(n):
    for j in range(i):
        if data[j] < data[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

문제 접근

처음에는 단순히 배열을 정렬하고 서로 다른 숫자의 개수를 세는 방식으로 접근했다. 하지만 이 문제는 정렬과는 전혀 관계가 없다는 것을 깨달았다. 핵심은 원래의 순서를 유지하면서 증가하는 부분 수열 중 가장 긴 길이를 구하는 것이다. 즉, 값이 작은 것부터 나열하는 문제가 아니라, “앞에 있는 숫자보다 뒤의 숫자가 큰 경우”를 이용해 길이를 확장해 나가는 문제이다.

핵심 개념: dp[i]

dp[i]는 i번째 숫자를 마지막으로 하는 증가하는 부분 수열의 최대 길이를 뜻한다. 처음에는 이 의미가 잘 와닿지 않았지만, “전체 최댓값을 바로 구하려는 게 아니라, 각 위치에서 끝나는 최댓값을 기록하는 것”이라는 관점으로 보니 이해가 되었다. 모든 위치에 대해 이 값을 계산해두고, 마지막에 그 중 최댓값을 구하면 된다.

핵심 코드: 이중 for문

다음과 같은 의미를 가진다.

i번째 숫자를 마지막 원소로 가정한다.
그 원소보다 앞에 있는 모든 j번째 숫자를 확인한다.
만약 data[j] < data[i]라면, j에서 끝나는 증가 수열 뒤에 i를 붙일 수 있다.
따라서 dp[j]+1이 새로운 후보 길이가 된다.
그 중에서 가장 큰 값을 dp[i]에 저장ㅇ한다. 즉, “i보다 작은 앞 숫자들 중에서 가장 긴 증가 수열을 찾고, 거기에 i를 붙이는 것”이다.

왜 모든 j를 확인해야 하는가

처음에는 왜 굳이 앞의 모든 숫자를 다 확인해야 하는지 이해되지 않았다. 하지만 i를 마지막으로 하는 증가 수열은 여러 경로에서 만들어질 수 있다. 예를 들어, 어떤 경우에는 바로 앞 숫자를 이어붙이는 것이 최적이 아닐 수도 있다. 따라서 i 앞의 모든 j를 확인하면서, 그 중 가장 긴 수열을 찾아야 한다. 그래서 이중 반복문 구조가 필요하다.

내가 깨달은 점.

이 문제는 단순 구현 문제가 아니라, “부분 문제를 정의하는 사고”가 중요한 문제였다. 처음에는 전체 최장 길이를 바로 구하려고 했지만, 실제로는 각 위치에서 끝나는 최대 길이를 저장해두는 방식으로 접근해야 했다. LIS는 동적 계획법(DP)의 대표적인 예시이며, 이후 다양한 최적화 문제에서도 비슷한 구조로 등장할 수 있다는 점을 알게 되었다.

Vienna sausage