문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 30, 50} 이고, 길이는 4이다.

www.acmicpc.net/problem/11053

  • 입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

  • 출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

과정

처음 생각한 방법은 수열을 처음부터 탐색하면서 [수열의 길이, 해당 수열의 최대값]을 아래 표와 같이 기록해나가는 것이었다.

수열 dp
10 [1, 10]
20 [2, 20]
10 [2, 20], [1, 10]
30 [3, 30], [1, 10]
20 [3, 30], [2, 20]
50 [4, 50], [2. 20]

이 경우에는 10, 20, 30, 50 순으로 부분수열의 길이 4가 제대로 구해진다. 이것을 코드로 구현하면 아래와 같다.

N = int(input())
A = list(map(int, input().split()))
dp = [[1, A[0]]]

for i in range(1, N):
    flag = 0
    for l in dp:
        if l[1] < A[i]:
            l[0] += 1
            l[1] = A[i]
            flag = 1
            break
    if flag == 0:
        dp.append([1, A[i]])
    dp.sort(reverse = True)

print(dp[0][0])

하지만 이 방법은 10 20 30 40 11 12 13 14 15 < 이러한 수열의 경우에 가장 긴 증가하는 부분 수열을 ‘11 12 13 14 15’로 구해버려서 답이 6이 아닌 5로 출력하는 문제가 있었다.

최종 코드

수열 10 20 10 30 20 50
길이 1 a[0]+1 = 2 1 a[1]+1 = 3 a[0]+1 = 2 a[3]+1 = 4

수열의 처음부터 숫자를 탐색해서 자신보다 작은 숫자들 중 가장 큰 길이를 구하고 그 길이에 1을 더하는 방법을 사용하면 쉽게 풀 수 있었다.

N = int(input())
A = list(map(int, input().split()))
dp = [0]*N
dp[0] = 1

for i in range(1, N):
    for j in range(i):
        if A[i]>A[j] and dp[i]<dp[j]:
            dp[i] = dp[j]
    #dp 값의 정확한 비교를 위해 1 증가는 마지막에 진행한다!!
    dp[i] += 1

print(max(dp))

접근 방법은 비슷하지만 이러한 코드도 있었다. 주어진 순열의 증가하는 부분 순열이 여러가지가 있는데, 그 부분 순열을 계속해서 업데이트 하면서 가장 긴 순열의 길이를 찾는 방식이다. 코드를 보면 더 이해하기 쉬울 것이다.

n = input()
# 입력받기
n_list = list(map(int,input().split()))

# 순열중 가장 좌측값을 ans에 넣는다.
ans = [n_list[0]]

# n_list의 1번째 ~ 마지막 인덱스
for i in range(1,len(n_list)):

  # ans의 마지막값보다 n_list[i] 값이 크면 ans에 넣는다.
  if ans[-1] < n_list[i]:  
    ans.append(n_list[i])
  # ans의 마지막값보다 n_list[i]값이 작은 경우...
    else:
      # n_list[i]가 이미 ans에 있다면 pass
      if n_list[i] in ans:
        continue

      ans_len = len(ans)

      # ans를 순회한다.
      for j in range(0,ans_len):
        # ans를 순회하다가 n_list[i]보다 큰값이 나오면
        # n_list[i]와 바꿔치기 하고 순회종료
        if ans[j] > n_list[i]:
          ans[j] = n_list[i] break

print(len(ans))

참고 사이트