문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
예제 입력
6
10 20 10 30 20 50
예제 출력
4
풀이
가장 앞에 있는 숫자부터 해당 숫자가 가질 수 있는 수열의 최대 길이를 구한다. 그러나 모든 숫자는 중복될 수 있기 때문에 값에 대해 최대 길이를 저장하는 게 아니라, 인덱스에 대해 최대 길이를 저장한다.
i번째 수열의 최대 길이를 구하는 방법은 다음과 같다(i >= 1 기준)
1. 1~i-1번째 값을 순회한다(인덱스 j라 가정)
2. arr[j] < arr[i] 이면서 dp[j]가 가장 큰 값을 찾는다
3. dp[i] = dp[j] + 1 을 해준다
우리가 찾는건 i번째이므로 이중 for문을 사용하여 모든 번째에 대해 동일한 과정을 거친다.
풀이
n = int(input())
arr = list(map(int,input().split()))
dp = [0]* n
dp[0] = arr[0]
for i in range(n):
mx = 0
for j in range(0, i):
if arr[j] < arr[i] and dp[j] > mx:
mx = dp[j]
dp[i] = mx + 1
print(max(dp))다시 풀기
1
처음에 dp 를 생각해서 dp 의 기록 방식을 dic 로 택하고, dp 를 구할 때 나보다 작으면서 가장 많은 수열의 개수를 가진 값을 찾기 위해 딕셔너리를 순회하는 것을 택했었다.
그러나, 딕셔너리는 순서를 보장하지 않기 때문에 딕셔너리에 저장된 key 값들의 순서가 arr 배열의 값들의 순서와 일치하지 않는다. 그러므로 이렇게 하면 안된다.
dp 의 순서를 딕셔너리에 기록하는게 아니라!, dp 의 값만을 dic 에 기록하는게 올바른 선택이다. 따라서 딕셔너리를 사용할 때 순서를 고려하는 것은 잘못된 방향이다.
잘못된 풀이 1
import sys
input = sys.stdin.readline
dic = {}
for v in arr:
max_key = 0
for k in sorted(list(dic.keys())):
if k < v and max_key < k:
max_key = k
if max_key == 0:
dic[v] = 1
else:
dic[v] = dic[max_key] + 1
print(max(dic.values()))그래서 아래와 같이 딕셔너리에는 값을 기록하는 용도로만 사용하였다. 여기서는 따로 dp 배열을 생성하지 않았다. dp 없이 arr 배열을 사용하여 문제를 풀었다.
여기서 핵심은 arr 의 현재 위치 이전까지의 값들 중 가장 큰 값을 고르는게 아니라, 해당 값을 마지막으로 하는 수열 중 가장 긴 수열을 가지는 값을 찾는 것이다.
딕셔너리[val]: val 값을 마지막으로하는 가능한 수열 중 가장 긴 수열의 값의 개수
DP 배열 없이 값 기록을 위한 딕셔너리 사용
n = int(input().strip())
arr = list(map(int,input().split()))
dic = {}
for i in range(0, len(arr)) :
max_v = 0
# arr 을 돌면서 나보다 작은 수 중에
# 가장 긴 수열을 가지는 값을 구함
for j in range(0, j):
if arr[j] < arr[i] and max_v < dic[arr[j]]:
max_v = dic[arr[j]]
dic[i] = max_v + 1
print(max(dic.values()))위에서 dp 배열 없이 입력 배열(arr)과, 값 기록을 위한 딕셔너리를 사용했다면, 아래와 같이 dp 배열을 사용해서 풀 수도 있다. 이 경우에는 arr 배열의 인덱스로 dp 배열에 값을 기록하고 접근하였다.
DP 배열 사용
n = int(input().strip())
arr = list(map(int,input().split()))
dp = [0] * n
for i in range(0,len(arr)):
mx = 0
for j in range(0, i):
# arr 을 돌면서 나보다 작은 수 중에
# 가장 긴 수열(dp의 값이 길이임)을 가지는 값을 구함
if arr[j] < arr[i] and dp[j] > mx:
mx = dp[j]
dp[i] = mx + 1
print(max(dp))2
세번째 푸는건데 왜 이렇게 안풀리는건지,,
아마 일반적인 점화식이긴 하지만, 우리가 일반적으로 푸는 단일 for 문 dp 문제(피보나치, 계단 오르기, 최소 비용 계산 등)랑 다르게 이중 for 문을 사용하는 형태기 때문에 직관적으로 파악하기가 힘들었다.
연속적으로 증가하는 배열이 아니기 때문에, 앞 부분의 인덱스의 dp 값이 뒷 부분의 dp 값보다 클 수 있다.
따라서 현재 인덱스 이전의 인덱스들의 모든 상태를 탐색해야 하기 때문에 이중 for 문이 필수이다.
예를 들어, 10 20 10 30 20 50 인 경우, dp[1] = 2 이고, dp[2] = 1, dp[3] = 3, dp[4] = 2, dp[5] = 4 이다. 이처럼 앞 부분의 dp 값들중에서 조건부(arr[i] > arr[j]) 인 값들에 대해 dp[i] = max(dp[i], dp[j]+1) 을 해줘야 한다.
따라서 dp[i] 는 두번째 for 문(내부)에서 dp[i] 가 가질 수 있는 가장 큰 값을 찾기 때문에 dp[i] 는 두번째 for 문에서 계속 값이 여러번 바뀔 수 있다.
결국 dp[i] = max(dp[i], dp[j]+1)는 i번째 원소를 마지막으로 하는 증가 부분 수열 중 최대 길이를 구하는 과정이다. => dp 배열의 마지막 원소가 문제가 원하는 증가하는 부분 수열들 중 최대 길이가 아니라, dp 배열의 원소들 중 가장 큰 값이 증가하는 부분 수열들 중 최대 길이이다.
n = int(input())
arr = list(map(int,input().split()))
dp = [1 for _ in range(n)]
for i in range(1, len(arr)):
for j in range(0, i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j]+1)
print(max(dp))결론
웬만하면 DP 문제는 DP 배열을 사용해서 푸는게 나은 것 같다.
