백준 - 11053 가장 긴 증가하는 부분 수열 [LIS]

 

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

 

1. 문제 요약

수열 A가 주어졌을 때, 최장 증가 부분 수열의 길이를 구하시오.

 

2. 접근 방법

• 배열을 순회하며,
• 현재 숫자의 이전 인덱스의 숫자들 중,
• 현재 숫자보다 작은 경우,
• 현재 dp와 찾은 숫자의 dp를 비교하여,
• 더 큰 값을 현재 dp에 저장한다.

 

현재 숫자의 이전 숫자가 없는 경우 1을 저장한다.

 

 

2 이전 숫자들 중, 1이 가장 작으므로 데려오며, +1을 해준다.

 

1의 이전 숫자들중, 1보다 작은 숫자가 없으므로 1을 저장한다.

 

 

3 이전의 숫자들 중, 3보다 작고, dp값이 가장 큰 숫자의 dp값을 데려와 +1을 해준다.

 

 

이를 반복한다.

 

 

3. 파이썬

n = int(input())
arr = list(map(int, input().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))

 

4. 자바

int answer = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (arr[i] > arr[j]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }

    answer = Math.max(answer, dp[i]);
}

System.out.print(answer + 1);

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/11053.%E2%80%85%EA%B0%80%EC%9E%A5%E2%80%85%EA%B8%B4%E2%80%85%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94%E2%80%85%EB%B6%80%EB%B6%84%E2%80%85%EC%88%98%EC%97%B4