반응형
가장 긴 증가하는 부분 수열 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()n = int(input())수열의 길이 n을 입력받습니다.
a = list(map(int,input().split()))공백으로 구분된 n개의 정수를 입력받아 수열 a에 저장합니다.
d = [0]*n d[i]는 수열 a의 i번째 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 저장하는 배열입니다.
v = [-1]*n v[i]는d[i]를 최대로 하는j의 인덱스를 저장하는 배열입니다. 이를 이용하여 가장 긴 증가하는 부분 수열을 추적합니다.
- 이중
for문을 이용하여 가장 긴 증가하는 부분 수열의 길이를 계산합니다.
ans = max(d)가장 긴 증가하는 부분 수열의 길이를 구합니다.
p = [i for i,x in enumerate(d) if x == ans][0]가장 긴 증가하는 부분 수열이 시작되는 인덱스를 구합니다.enumerate(d):enumerate함수는 d 배열의 인덱스와 값에 대해 반복할 수 있는 객체를 생성합니다. 여기서 i는 인덱스를 나타내고, x는 해당 인덱스의 값입니다.
if x == ans: 조건문을 사용하여 d 배열에서 ans와 같은 값을 갖는 원소를 찾습니다. ans는 가장 긴 증가하는 부분 수열의 길이입니다. 따라서, 이 조건문은 d 배열에서 가장 긴 증가하는 부분 수열의 길이와 일치하는 원소를 찾는 것을 의미합니다.
[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루프를 통해 각 요소와 인덱스에 접근하여 출력합니다.
[0]: 리스트 컴프리헨션으로 생성된 리스트에서 첫 번째 인덱스를 선택합니다. 이 예제에서는 첫 번째로 발견된 가장 긴 증가하는 부분 수열의 시작 인덱스를 사용합니다.
print(ans)가장 긴 증가하는 부분 수열의 길이를 출력합니다.
- 함수
go(p)를 정의합니다. 이 함수는 인덱스p부터 시작하여v배열을 따라가며 가장 긴 증가하는 부분 수열을 출력하는 함수입니다.if p == -1: 종료 조건으로,p가 -1이면 함수를 종료합니다.
go(v[p]):v[p]인덱스를 따라 이전 원소로 이동합니다.
print(a[p],end=' '): 현재 인덱스p에 해당하는 원소를 출력합니다.
go(p)인덱스p부터 시작하여 가장 긴 증가하는 부분 수열을 출력합니다.
print()줄 바꿈을 위해print()를 호출합니다.
- 첫째줄에 6, 둘째줄에 10 20 10 30 20 50을 넣었을 때 코드 계산 과정
n = int(input())에서 n에 6이 저장됩니다.
a = list(map(int,input().split()))에서a에 [10, 20, 10, 30, 20, 50]이 저장됩니다.
d = [0]*n와v = [-1]*n에서d와v리스트가 [0, 0, 0, 0, 0, 0]과 [-1, -1, -1, -1, -1, -1]로 초기화됩니다.
for i in range(n):에서i가0부터5까지 반복됩니다.d[i] = 1에서d[0]부터d[5]까지1로 초기화됩니다.
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로 업데이트합니다.
- i가 1일 때, d와 v의 값은 [1, 2, 0, 0, 0, 0]과 [-1, 0, -1, -1, -1, -1]입니다.
- i가 2일 때, d와 v의 값은 [1, 2, 1, 0, 0, 0]과 [-1, 0, -1, -1, -1, -1]입니다.
- i가 3일 때, d와 v의 값은 [1, 2, 1, 3, 0, 0]과 [-1, 0, -1, 1, -1, -1]입니다.
- i가 4일 때, d와 v의 값은 [1, 2, 1, 3, 2, 0]과 [-1, 0, -1, 1, 2, -1]입니다.
- i가 5일 때, d와 v의 값은 [1, 2, 1, 3, 2, 4]과 [-1, 0, -1, 1, 2, 3]입니다.
ans = max(d)에서d의 최댓값인 4가ans에 저장됩니다.
p = [i for i,x in enumerate(d) if x == ans][0]에서d에서ans와 같은 값을 가지는 원소의 인덱스를 리스트로 저장한p는 [5]가 됩니다.
print(ans)에서 LIS의 길이인 4가 출력됩니다.
go(p)에서p인 5부터 시작하여,v[p]가 -1이 될 때까지go함수를 재귀적으로 호출합니다.p가 5인 경우,go(5)를 호출합니다.
go(5)에서go(v[5])를 호출합니다.v[5]는 3이므로,go(3)을 호출합니다.
go(3)에서go(v[3])을 호출합니다.v[3]은 2이므로,go(2)을 호출합니다.
go(2)에서go(v[2])을 호출합니다.v[2]는 -1이므로, 종료합니다.
- 다시
go(3)으로 돌아와서a[3]인 30을 출력합니다.
- 다시
go(5)으로 돌아와서a[5]인 50을 출력합니다.
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을 넣었을 때 코드 계산 과정
- 코드 실행 전 변수 상태
N = 6 A = [10, 20, 10, 30, 20, 50] dp = [1, 1, 1, 1, 1, 1] answer = [] order = 1
- 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]
- 최장 증가 부분 수열의 길이 출력
print(max(dp)) # 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]
- 최장 증가 부분 수열 출력
answer.reverse() print(*answer) # 10 20 30 50
- 코드 실행 전 변수 상태
Uploaded by N2T
반응형
'Algorithm' 카테고리의 다른 글
| [백준 1699 파이썬/python] 제곱수의 합 (0) | 2023.04.18 |
|---|---|
| [백준 1912 파이썬/python] 연속합 (0) | 2023.04.18 |
| [백준 11053 파이썬/python] 가장 긴 증가하는 부분 수열 (0) | 2023.04.18 |
| [백준 2193 파이썬/python] 이친수 (1) | 2023.04.18 |
| [백준 10844 파이썬/python] 쉬운 계단 수 (0) | 2023.04.18 |
