Note
LIS(Longest Increasing Subsequence)를 동적 프로그래밍으로 해결하는 기본 문제입니다.
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
문제 링크: https://www.acmicpc.net/problem/11053
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
예제
예제 입력 1:
6
10 20 10 30 20 50
예제 출력 1:
4
문제 분석
이 문제는 LIS를 구하는 기본 문제입니다.
핵심 포인트
- 부분 수열: 원본 수열에서 일부 원소를 선택하되 원래 순서를 유지
- 증가하는: 각 원소가 이전 원소보다 커야 함
- 가장 긴: 가능한 모든 증가하는 부분 수열 중 길이가 가장 긴 것
해결 방법
동적 프로그래밍을 사용합니다:
dp[i]: i번째 원소를 마지막으로 하는 증가하는 부분 수열의 최대 길이- 점화식:
dp[i] = max(dp[j] + 1)for allj < iwherearr[j] < arr[i] - 초기값: 모든
dp[i] = 1(자기 자신만으로 길이 1)
코드 구현
제공된 코드
import sys
readline = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
dp = [1 for _ in range(n)]
for i in range(n):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))코드 분석
1. 입력 처리
import sys
readline = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))readline을 import했지만input()을 사용 (일관성 개선 가능)- 수열의 크기 N과 수열 A를 입력받음
2. DP 배열 초기화
dp = [1 for _ in range(n)]- 모든 원소를 1로 초기화
- 각 원소는 최소한 자기 자신만으로 길이 1의 부분 수열을 만들 수 있음
3. DP 계산
for i in range(n):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)동작 과정:
- 각 원소 i에 대해 모든 이전 원소 j를 확인
arr[i] > arr[j]이면 (증가 조건)dp[j] + 1과 현재dp[i]중 큰 값을 선택- 이는 j를 마지막으로 하는 부분 수열에 i를 추가할 수 있음을 의미
4. 결과 출력
print(max(dp))- 모든
dp[i]중 최댓값이 LIS의 길이 - 어떤 원소를 마지막으로 하든 가장 긴 부분 수열의 길이
개선된 코드
더 일관성 있게 작성한다면:
import sys
readline = sys.stdin.readline
n = int(readline())
arr = list(map(int, readline().split()))
dp = [1] * n
for i in range(n):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))개선 사항:
input()대신readline()사용 (일관성)[1 for _ in range(n)]대신[1] * n사용 (간결함)
시간 및 공간 복잡도
시간 복잡도
- O(n²): 각 원소 i에 대해 모든 이전 원소 j를 확인
- n ≤ 1,000이므로 충분히 빠름
공간 복잡도
- O(n): dp 배열만 필요
예제 동작 과정
예제 입력: n=6, arr=[10, 20, 10, 30, 20, 50]
단계별 계산:
i=0 (arr[0]=10):
- j 범위: 없음
dp[0] = 1
i=1 (arr[1]=20):
- j=0:
arr[1]=20 > arr[0]=10✓dp[1] = max(1, dp[0] + 1) = max(1, 1 + 1) = 2
dp[1] = 2
i=2 (arr[2]=10):
- j=0:
arr[2]=10 > arr[0]=10✗ - j=1:
arr[2]=10 > arr[1]=20✗ dp[2] = 1
i=3 (arr[3]=30):
- j=0:
arr[3]=30 > arr[0]=10✓dp[3] = max(1, dp[0] + 1) = max(1, 2) = 2
- j=1:
arr[3]=30 > arr[1]=20✓dp[3] = max(2, dp[1] + 1) = max(2, 3) = 3
- j=2:
arr[3]=30 > arr[2]=10✓dp[3] = max(3, dp[2] + 1) = max(3, 2) = 3
dp[3] = 3
i=4 (arr[4]=20):
- j=0:
arr[4]=20 > arr[0]=10✓dp[4] = max(1, dp[0] + 1) = max(1, 2) = 2
- j=1:
arr[4]=20 > arr[1]=20✗ - j=2:
arr[4]=20 > arr[2]=10✓dp[4] = max(2, dp[2] + 1) = max(2, 2) = 2
- j=3:
arr[4]=20 > arr[3]=30✗ dp[4] = 2
i=5 (arr[5]=50):
- j=0:
arr[5]=50 > arr[0]=10✓dp[5] = max(1, dp[0] + 1) = max(1, 2) = 2
- j=1:
arr[5]=50 > arr[1]=20✓dp[5] = max(2, dp[1] + 1) = max(2, 3) = 3
- j=2:
arr[5]=50 > arr[2]=10✓dp[5] = max(3, dp[2] + 1) = max(3, 2) = 3
- j=3:
arr[5]=50 > arr[3]=30✓dp[5] = max(3, dp[3] + 1) = max(3, 4) = 4
- j=4:
arr[5]=50 > arr[4]=20✓dp[5] = max(4, dp[4] + 1) = max(4, 3) = 4
dp[5] = 4
최종 dp 배열: [1, 2, 1, 3, 2, 4]
LIS 길이: max(dp) = 4
실제 LIS: [10, 20, 30, 50] (길이 4)
주의사항
1. 부분 수열의 정의
부분 수열은 원소를 건너뛸 수 있지만, 원래 순서는 유지해야 합니다:
[10, 20, 30, 50]✓ (순서 유지)[20, 10, 30]✗ (순서 위반)
2. 증가 조건
arr[i] > arr[j] 조건이 중요합니다:
arr[i] >= arr[j]가 아님 (같으면 증가하지 않음)arr[i] < arr[j]이면 부분 수열에 추가할 수 없음
3. dp 배열의 의미
dp[i]는 i번째 원소를 포함하는 증가하는 부분 수열의 최대 길이입니다.
따라서 최종 답은 max(dp)입니다.
4. 입력 최적화
코드에서 readline을 import했지만 input()을 사용했습니다. 일관성을 위해 readline()을 사용하는 것이 좋습니다.