[백준]11053 가장 긴 증가하는 부분 수열 14002 가장 긴 증가하는 부분 수열 4 파이썬 얕은 복사 python

문제링크

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/14002

14002번: 가장 긴 증가하는 부분 수열 4

코드

11053

import sys
input = sys.stdin.readline
 
n = int(input())
a =list(map(int,input().split()))
d = [1]*n
 
for i in range(n):
    for j in range(i):
        if a[j]<a[i] and d[i]<d[j]+1:
            d[i] = d[j]+1
print(max(d))

14002

import sys
input = sys.stdin.readline
 
n = int(input())
a = list(map(int, input().split()))
 
d = [1]*n #갯수
id = [ [] for _ in range(n)]
id[0]= [0]
for i in range(1,n):
    for j in range(i):
        if a[i]>a[j] and d[i]<d[j]+1:
            d[i] = d[j]+1
            id[i] = id[j].copy()
    id[i].append(i)
argmax = 0
for k in range(n):
    if d[argmax]<d[k]:
        argmax=k
 
print(d[argmax])
for i in id[argmax]:
    print(a[i],end=' ')
 
 

 

POINT

- DP로 접근

- 11053 풀이 방법:

'd[i] = i번째 수를 포함하여 만들 수 있는 가장 긴 수열의 길이(= i번째 수가 최대값인 가장 긴 수열의 길이)' 라고 정의한다.

 

예를 들어, A = {10, 20, 10, 30, 20, 50}에서

d[3] : 30을 포함하여 만들 수 있는 가장 긴 수열의 길이 이다.

30을 포함시켜 증가하는 수열을 만들기 위해선, 수열 중 30이 가장 큰 숫자가 되어야한다.

따라서, 'd[3] : 30이 최댓값인 가장 긴 수열의 길이'라고 해석할 수 있다. 

d[3] = 3 , {10,20,30} 

 

해당 수를 기존의 배열에 추가하려면 기존 최댓값보다 더 커야하고, (-> a[j]<a[i])

현재 길이(=d[i])보다 하나를 더 추가해서 생성된 수열의 길이(=d[j]+1)가 더 커야 한다. (-> d[i]<d[j]+1)

 

 

- 14002 풀이 방법:

11053과 다른 점은 가장 긴 길이 뿐만 아니라, 직접 수열을 출력해야한다. 따라서 포함시킬 인덱스를 저장해나가는 코드를 추가한다. 배열 id는 지금까지 포함시킨 인덱스를 포함하고 있다.

현재 i번째에서 과거 j번째를 추가할 때, id[i] = id[j].copy()와 같은 코드를 사용하여 j번째가 가지고 있는 인덱스들을 복사한다. * id[i] = id[j]를 하면 얕은 복사가 되어 오류가 난다.

 

파이썬 얕은 복사 vs 깊은 복사 (for mutable객체_list, dictionary,...)

https://blockdmask.tistory.com/576

[python] 파이썬 얕은복사, 깊은복사 (copy, deepcopy, [:], =) 총 정리

1) id[i] = id[j] --> 얕은 복사

1-1) id[i] = id[j].copy() OR  id[i] = id[j][:]  --> 얕은 복사+눈속임으로 깊은 복사 느낌내기

2) id[i] = copy.deepcopy(id[j])     *import copy --> 깊은 복사

 

1) 얕은 복사란, '참조하는 메모리 주소'를 복사한 것이다. 따라서 얕은 복사시에는 같은 곳을 가리키기 때문에 하나의 리스트 값을 변경하면 같은 참조를 가리키고 있는(= 얕은 복사를 한) 다른 리스트의 값에도 동일하게 변경 내용이 적용된다.  

1-2) 얕은 복사 + 눈속임은, 리스트 자체의 참조 메모리 주소는 달라진다. 하지만, 리스트 내 원소들은 모두 동일한 주소를 가리키고 있다. 따라서 .copy 혹은 [:]로 복사시에는 리스트들이 다른 주소를 같게 되서 깊은 복사로 착각할 수 있지만 리스트 내부 원소들은 같은 주소로 묶여있기 때문에 주의해야한다.

2) 깊은 복사란, 아예 모든 객체들이 모두 새롭게 만들어지는 것이다. 아예 독립적인 객체들이 생성된다.