[Python][SWEA] 3307. 최장 증가 부분 수열 D3

SW Expert Academy

---

 

🗒️ 파이썬 코드 풀이

T = int(input())
for tc in range(1,T+1) :
    N = int(input())
    lst = list(map(int,input().split()))
    dp_lst = [1] * N  # dp 1차원 행렬 생성

    for i in range(len(dp_lst)) : # dp 리스트의 값을 채워주기 위한 반복문
        for j in range(i) :  # dp 현재 인덱스 바로 전 까지 반복문
            if lst[i] >= lst[j] : # lst의 현재값이 lst의 이전 값보다 큰 경우
                dp_lst[i] = max(dp_lst[i],dp_lst[j]+1) 

    print(f"#{tc} {max(dp_lst)}")

 

1. 1로 채워진 DP 리스트들을 만들어준다.

 

2. 이중 for문을 통해 DP 리스트의 값들을 채워준다.

 

3.  여기에서 j의 범위를 i 이하로 하여, i 이하의 인덱스들을 탐색한다.

 

4. 해당 조건에 맞는 탐색에 성공하면, 현재 dp_lst의 인덱스 값들을 갱신한다. 

 

5. DP 리스트들의 최대값들을 갱신한다.

 

여기에서 주의사항은 DP 리스트에서 최대값을 뽑을때, 맨끝 값이 최대값이 아니라는 것을 기억하자.

(맨끝 값을 최대라 생각하고 문제를 풀어서 에러가 떴다.)

 

 

📌 내가 작성한 코드

T = int(input())
for tc in range(1,T+1) :
    N = int(input())
    lst = list(map(int,input().split()))

    dp_lst = [1] * N  # dp 1차원 행렬 생성
    for i in range(len(dp_lst)) : # dp 리스트의 값을 채워주기 위한 반복문
        mx = 0
        for j in range(i) :  # dp 현재 인덱스 바로 전 까지 반복문
            tmp = 0
            if lst[i] >= lst[j] : # lst의 현재값이 lst의 이전 값보다 큰 경우
                index = j  # index 값 저장
                tmp = dp_lst[index] # 해당 index의 dp_lst 값 출력 
            mx = max(mx,tmp)  # 최대값 갱신 
        dp_lst[i] = mx + 1 

    print(f"#{tc} {max(dp_lst)}")

 

 처음 보여준 파이썬 코드는 다른 사람의 코드를 참고한 것이다. 

내가 작성한 코드도 로직도 같고 문제 pass는 되긴하지만, 불필요한 변수 선언을 많이 한 것 같다. (mx,tmp)

해당 변수 선언 없이고 max값을 갱신 할 수 있으니, 좀 더 효율적인 방법을 찾아보자. 

 

🧐 문제 코멘트

처음에는 완전탐색으로 문제를 풀려했는데, N의 개수가 1000이하라는 것을 보고 얼른 후퇴했다.

그리고  해당 문제를 수기로 풀어보니 DP 방식으로 풀어야겠다는 생각이 들었다.

하지만 DP 문제를 어떻게 코드로 전개할지가 문제였다... 

그래도 하나하나 시도하면, 생각보다 엄청 어렵지만은 않으니 너무 DP를 두려워하지 말자 !

---

📚 문제

주어진 두 수열의 최장 증가 부분 수열(Longest Increasing Subsequence)의 길이를 계산하는 프로그램을 작성하시오.

수열 { A1, A2, ... , AN }의 최장 증가 부분 수열 B는 다음과 같이 정의된다.

{ B1, B2, ... , BK }에서 0≤K≤N, B1 < B2 < ... < BK이고,

AB1 ≤ AB2 ≤ ... ≤ ABK인 최대 K로 구성된 수열이다.

예를 들어, 수열이 { 1, 3, 2, 5, 4, 7 } 이라면, 최장 부분 증가 수열의 길이는 4가 된다.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에는 수열의 길이 N(1≤N≤1,000)이 주어진다. 

둘째 줄에는 수열의 원소 N개가 공백을 사이에 두고 순서대로 주어진다.

각 수열의 원소는 1 이상 231-1 이하의 자연수이다.

[출력]

각 테스트 케이스마다 ‘#T’(T는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 증가 부분 수열의 길이를 출력한다.