개발일지/Algorithm
백준 - 11053 가장 긴 증가하는 부분 수열 [LIS]
E-room
2023. 10. 18. 17:29
728x90
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
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. 전체 코드
728x90