[백준 14002 파이썬/python] 가장 긴 증가하는 부분 수열 4

문제

입력

출력

예제 입력 1

예제 출력 1

풀이

1)

2)

가장 긴 증가하는 부분 수열 4 스페셜 저지

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	32207	12657	9586	39.229%

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4
10 20 30 50

풀이

1)

n = int(input())
a = list(map(int,input().split()))
d = [0]*n
v = [-1]*n
for i in range(n):
    d[i] = 1
    for j in range(i):
        if a[j] < a[i] and d[j]+1 > d[i]:
            d[i] = d[j]+1
            v[i] = j
ans = max(d)
p = [i for i,x in enumerate(d) if x == ans][0]
print(ans)
def go(p):
    if p == -1:
        return
    go(v[p])
    print(a[p],end=' ')
go(p)
print()

1. n = int(input()) 수열의 길이 n을 입력받습니다.

2. a = list(map(int,input().split())) 공백으로 구분된 n개의 정수를 입력받아 수열 a에 저장합니다.

3. d = [0]*n d[i]는 수열 a의 i번째 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 저장하는 배열입니다.

4. v = [-1]*n v[i]는 d[i]를 최대로 하는 j의 인덱스를 저장하는 배열입니다. 이를 이용하여 가장 긴 증가하는 부분 수열을 추적합니다.

5. 이중 for 문을 이용하여 가장 긴 증가하는 부분 수열의 길이를 계산합니다.

6. ans = max(d) 가장 긴 증가하는 부분 수열의 길이를 구합니다.

7. p = [i for i,x in enumerate(d) if x == ans][0] 가장 긴 증가하는 부분 수열이 시작되는 인덱스를 구합니다.
   1. enumerate(d): enumerate 함수는 d 배열의 인덱스와 값에 대해 반복할 수 있는 객체를 생성합니다. 여기서 i는 인덱스를 나타내고, x는 해당 인덱스의 값입니다.
   2. if x == ans: 조건문을 사용하여 d 배열에서 ans와 같은 값을 갖는 원소를 찾습니다. ans는 가장 긴 증가하는 부분 수열의 길이입니다. 따라서, 이 조건문은 d 배열에서 가장 긴 증가하는 부분 수열의 길이와 일치하는 원소를 찾는 것을 의미합니다.
   3. [i for i, x in enumerate(d) if x == ans]: 리스트 컴프리헨션을 사용하여 조건문이 참인 인덱스 i를 새로운 리스트에 추가합니다. 이 리스트에는 가장 긴 증가하는 부분 수열의 길이와 일치하는 d 배열의 모든 인덱스가 포함됩니다.
      • enumerate()

        enumerate는 파이썬의 내장 함수로, 주로 반복문에서 사용됩니다. 이 함수는 순서가 있는(iterable) 객체(예: 리스트, 문자열, 튜플)를 입력받아, 각 요소와 그 요소의 인덱스를 함께 반환합니다. 이를 통해 반복문에서 요소의 인덱스와 값에 동시에 접근할 수 있습니다.

        enumerate 함수의 기본 사용법은 다음과 같습니다:

        enumerate(iterable, start=0)

        • iterable: 인덱스와 값을 함께 반환할 순서가 있는 객체입니다.

        • start: 인덱스의 시작 값입니다. 기본값은 0입니다. 원하는 경우 다른 시작 값을 설정할 수 있습니다.

        enumerate 함수는 일반적으로 for 루프와 함께 사용되며, 아래와 같이 사용할 수 있습니다:

        fruits = ['apple', 'banana', 'orange']
        
        for index, value in enumerate(fruits):
            print(index, value)

        위 코드의 출력 결과는 다음과 같습니다:

        0 apple
        1 banana
        2 orange

        이 예제에서 enumerate 함수는 fruits 리스트를 입력받아 각 요소와 해당 요소의 인덱스를 반환합니다. for 루프를 통해 각 요소와 인덱스에 접근하여 출력합니다.

   4. [0]: 리스트 컴프리헨션으로 생성된 리스트에서 첫 번째 인덱스를 선택합니다. 이 예제에서는 첫 번째로 발견된 가장 긴 증가하는 부분 수열의 시작 인덱스를 사용합니다.

8. print(ans) 가장 긴 증가하는 부분 수열의 길이를 출력합니다.

9. 함수 go(p)를 정의합니다. 이 함수는 인덱스 p부터 시작하여 v 배열을 따라가며 가장 긴 증가하는 부분 수열을 출력하는 함수입니다.
   • if p == -1: 종료 조건으로, p가 -1이면 함수를 종료합니다.
   • go(v[p]): v[p] 인덱스를 따라 이전 원소로 이동합니다.
   • print(a[p],end=' '): 현재 인덱스 p에 해당하는 원소를 출력합니다.

10. go(p) 인덱스 p부터 시작하여 가장 긴 증가하는 부분 수열을 출력합니다.

11. print() 줄 바꿈을 위해 print()를 호출합니다.

• 첫째줄에 6, 둘째줄에 10 20 10 30 20 50을 넣었을 때 코드 계산 과정
  1. n = int(input())에서 n에 6이 저장됩니다.
  2. a = list(map(int,input().split()))에서 a에 [10, 20, 10, 30, 20, 50]이 저장됩니다.
  3. d = [0]*n와 v = [-1]*n에서 d와 v 리스트가 [0, 0, 0, 0, 0, 0]과 [-1, -1, -1, -1, -1, -1]로 초기화됩니다.
  4. for i in range(n):에서 i가 0부터 5까지 반복됩니다.
     1. d[i] = 1에서 d[0]부터 d[5]까지 1로 초기화됩니다.
     2. for j in range(i):에서 j가 0부터 i-1까지 반복됩니다.
        • 0 <= j < i이기 때문에, i번째 원소 이전의 원소들을 순차적으로 탐색합니다.
        • if a[j] < a[i] and d[j]+1 > d[i]:에서 a[j] < a[i]와 d[j]+1 > d[i]가 모두 참이어야 if문 안의 코드가 실행됩니다.
        • 현재 j번째 원소가 i번째 원소보다 작은 경우, j번째 원소에서 시작하는 LIS의 길이에 1을 더한 값이 i번째 원소에서 시작하는 LIS의 길이보다 큰 경우, d[i]와 v[i]를 각각 d[j]+1과 j로 업데이트합니다.
     3. i가 1일 때, d와 v의 값은 [1, 2, 0, 0, 0, 0]과 [-1, 0, -1, -1, -1, -1]입니다.
     4. i가 2일 때, d와 v의 값은 [1, 2, 1, 0, 0, 0]과 [-1, 0, -1, -1, -1, -1]입니다.
     5. i가 3일 때, d와 v의 값은 [1, 2, 1, 3, 0, 0]과 [-1, 0, -1, 1, -1, -1]입니다.
     6. i가 4일 때, d와 v의 값은 [1, 2, 1, 3, 2, 0]과 [-1, 0, -1, 1, 2, -1]입니다.
     7. i가 5일 때, d와 v의 값은 [1, 2, 1, 3, 2, 4]과 [-1, 0, -1, 1, 2, 3]입니다.
  5. ans = max(d)에서 d의 최댓값인 4가 ans에 저장됩니다.
  6. p = [i for i,x in enumerate(d) if x == ans][0]에서 d에서 ans와 같은 값을 가지는 원소의 인덱스를 리스트로 저장한 p는 [5]가 됩니다.
  7. print(ans)에서 LIS의 길이인 4가 출력됩니다.
  8. go(p)에서 p인 5부터 시작하여, v[p]가 -1이 될 때까지 go 함수를 재귀적으로 호출합니다.
     1. p가 5인 경우, go(5)를 호출합니다.
     2. go(5)에서 go(v[5])를 호출합니다. v[5]는 3이므로, go(3)을 호출합니다.
     3. go(3)에서 go(v[3])을 호출합니다. v[3]은 2이므로, go(2)을 호출합니다.
     4. go(2)에서 go(v[2])을 호출합니다. v[2]는 -1이므로, 종료합니다.
     5. 다시 go(3)으로 돌아와서 a[3]인 30을 출력합니다.
     6. 다시 go(5)으로 돌아와서 a[5]인 50을 출력합니다.
  9. print()에서 줄바꿈을 출력합니다.

  따라서, 입력값으로 6 10 20 10 30 20 50을 받으면, 다음과 같은 결과가 출력됩니다.

  LIS의 길이는 4입니다. 10 20 30 50

2)

N = int(input())  # 수열의 길이를 입력받음
A = list(map(int, input().split()))  # 수열을 입력받음
dp = [1] * N  # 각 원소를 끝으로 하는 최장 증가 부분 수열의 길이를 저장하는 리스트를 초기화

# 각 원소에 대하여
for i in range(N):
    # 그 이전의 원소들을 순회하며
    for j in range(i):
        # 현재 원소보다 작은 이전 원소 중
        if A[i] > A[j]:
            # 현재 원소를 끝으로 하는 최장 증가 부분 수열의 길이를 갱신
            dp[i] = max(dp[i], dp[j] + 1)

# 최장 증가 부분 수열의 길이를 출력
print(max(dp))

answer = []  # 최장 증가 부분 수열을 저장할 리스트
order = max(dp)  # 최장 증가 부분 수열의 길이를 저장

# 역순으로 순회하며
for i in range(N - 1, -1, -1):
    # 현재 원소가 최장 증가 부분 수열에 포함되는 경우
    if dp[i] == order:
        # 해당 원소를 정답 리스트에 추가
        answer.append(A[i])
        # 최장 증가 부분 수열의 길이를 1 감소
        order -= 1

# 역순으로 저장한 원소를 다시 뒤집어서 정답 리스트를 만듦
answer.reverse()
# 정답 리스트를 출력
print(*answer)

• 첫째줄에 6, 둘째줄에 10 20 10 30 20 50을 넣었을 때 코드 계산 과정
  1. 코드 실행 전 변수 상태

     N = 6
     A = [10, 20, 10, 30, 20, 50]
     dp = [1, 1, 1, 1, 1, 1]
     answer = []
     order = 1

  2. dp 리스트 값 갱신 과정

     i = 0, dp = [1, 1, 1, 1, 1, 1]
     i = 1, dp = [1, 2, 1, 1, 1, 1]
     i = 2, dp = [1, 2, 1, 1, 1, 1]
     i = 3, dp = [1, 2, 1, 3, 1, 1]
     i = 4, dp = [1, 2, 1, 3, 2, 1]
     i = 5, dp = [1, 2, 1, 3, 2, 4]

  3. 최장 증가 부분 수열의 길이 출력

     print(max(dp))  # 4

  4. 최장 증가 부분 수열 출력을 위한 과정

     i = 5, dp[5] == order -> order = 3, answer = [50]
     i = 3, dp[3] == order -> order = 2, answer = [50, 30]
     i = 1, dp[1] == order -> order = 1, answer = [50, 30, 20]
     i = 0, dp[0] == order -> order = 1, answer = [50, 30, 20, 10]

  5. 최장 증가 부분 수열 출력

     answer.reverse()
     print(*answer)  # 10 20 30 50

Uploaded by N2T