[Python] softeer.ai 징검다리2

🎵오늘의 띵곡🎵

 

After LIKE

아티스트

IVE (아이브)

앨범

After LIKE

발매일

2022.08.22

최장 증가 부분 수열(LIS : Longest Increasing Subsequence)

- 동적 계획법

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분 수열을 만듦
만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열

 

첫 번째 방법

시간 복잡도 : O(N^2)

 

원본 배열 A, 새로운 배열 B 선언

int A[8] = {3, 5, 7, 9, 2, 1, 4, 8};

B[i] : A [i]를 마지막 값으로 가지는 가장 긴 증가 부분 수열의 길이

 

i = 0

A[0] = 0 , B[0] = 0

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0

i = 1

A[1] = 3, 3은 A[0] = 0 뒤에 가능 -> B[1] = B[0] + 1 = 1

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1

 

i = 2

A[2] = 5 , A[0] = 0 과 A[1] = 3 다음에 가능 -> B[2] = B[1] + 1 = 2

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1	2

 

i = 3

A[3] = 7 , A[0] = 0 과 A[1] = 3과 A[2] = 5 다음에 가능 -> B[3] = B[2] + 1 = 3

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1	2	3

 

i = 4

A[4] = 9 , A[0] = 0과 A[1] = 3 과 A[2] = 5과 A[3] = 7 다음에 가능 -> B[4] = B[3] + 1 = 4

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1	2	3	4

 

 

i = 5

A[5] = 2 , A[0] = 0 다음에 가능 -> B[5] = B[0] + 1 = 1

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1	2	3	4	1

 

i = 6

A[6] = 1 , A[0] = 0 다음에 가능 -> B[6] = B[0] + 1 = 1

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1	2	3	4	1	1

 

i = 7

A[7] = 4 , A[0] = 0과 A[1] = 3 다음에 가능 -> B[7] = B[1] + 1 = 2

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1	2	3	4	1	1	2

 

i = 8

A[8] = 8 , A[0] = 0과 A[1] = 3과 A[2] = 5과 A[3] = 7 다음에 가능 -> B[8] = B[3] + 1 = 4

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1	2	3	4	1	1	2	4

 

결론 : B의 배열에서 가장 큰 값(B[4] = B[8] = 4)이 수열 A의 LIS의 길이

 

N개의 수들에 대해 자기 자신 전의 모든 수를 훑어봐야 하므로 O(N^2)의 시간복잡도를 가짐

 

 

두 번째 방법

시간 복잡도 : O(NlogN)

 

원본 배열 A, 새로운 배열 B 선언

int A[8] = {3, 5, 7, 9, 2, 1, 4, 8};

B[i] : A [i]를 마지막 값으로 가지는 가장 긴 증가 부분 수열의 길이

✨A[i]보다 작은 A[j]를 가지는 j들 중 가장 큰 B[j]를 찾기✨

✨A[i]보다 작은 A[j]를 가지는 j들 중 가장 큰 B[j]를 찾기✨

 

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0

B[i] = k 인 값들 중 A[i]의 값이 가장 작은 값을 저장

B[i]	0
A[i]	0

 

i = 1

A[1] = 3 , A[1] 앞의 수들 중 가장 긴 증가부분수열 중 마지막 값이 0 이므로 다음에 가능 -> B[1] = 0 + 1 = 1

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1

B[i]	0	1
A[i]	0	3

 

i = 2

A[2] = 5 , 가장 마지막 A[i]의 값이 3이므로 다음에 가능 -> B[2] = B[1] + 1 = 2

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1	2

B[i]	0	1	2
A[i]	0	3	5

 

 

i = 3

A[3] = 7 ,  가장 마지막 값이 5이므로 다음에 가능 -> B[3] = B[2] + 1 = 3

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1	2	3

B[i]	0	1	2	3
A[i]	0	3	5	7

 

i = 4

A[4] = 9 , 가장 마지막 값이 7이므로 다음에 가능 -> B[4] = B[3] + 1 = 4

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1	2	3	4

B[i]	0	1	2	3	4
A[i]	0	3	5	7	9

 

i = 5

A[5] = 2 , 2는 A[i]에서 0과 3 사이의 값이므로 B[5] = 0 + 1 = 1

A[i]은 3보다 더 작은 2로 갱신 -> B[i] = 2인 수열을 찾기 위해서 A[5] = 2 뒤에 붙일 수 있는지만 확인하면 됨

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1	2	3	4	1

B[i]	0	1	2	3	4
A[i]	0	2	5	7	9

 

i = 6

A[6] = 1 , 1은 A[i]에서 0과 2 사이의 값이므로 B[6] = 0 + 1 = 1

A[i]은 2보다 더 작은 1로 갱신

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1	2	3	4	1	1

B[i]	0	1	2	3	4
A[i]	0	1	5	7	9

 

i = 7

A[7] = 4 , 4는 A[i]에서 1과 5 사이의 값이므로 B[7] = 1 + 1 = 2

A[i]은 5보다 더 작은 4로 갱신

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1	2	3	4	1	1	2

B[i]	0	1	2	3	4
A[i]	0	1	4	7	9

 

i = 8

A[8] = 8 , 8은 A[i]에서 7과 9 사이의 값이므로 B[8] = 3 + 1 = 4

A[i]은 9보다 더 작은 8로 갱신

i	0	1	2	3	4	5	6	7	8
A	0	3	5	7	9	2	1	4	8
B	0	1	2	3	4	1	1	2	4

B[i]	0	1	2	3	4
A[i]	0	1	4	7	8

 

결론 : B의 배열에서 가장 큰 값(B[4] = B[8] = 4)이 수열 A의 LIS의 길이

 

N개의 수들에 대해 오름차순 정렬된 밑의 테이블을 비교하므로 이진탐색 사용 -> O(NlogN)의 시간복잡도를 가짐

 

(●'◡'●)정답코드(●'◡'●)

import sys
import bisect

N = int(sys.stdin.readline())
stone = list(map(int, sys.stdin.readline().split()))

# 밟을 수 있는 돌의 높이 DP 배열
B = [stone[0]] # 원본 중 가장 작은 값(앞에서부터)
C = [stone[-1]] # 원본 중 가장 작은 값(뒤에서부터)
B_c = [1] * N # 앞에서부터 밟은 돌의 개수
C_c = [1] * N # 뒤에서부터 밟은 돌의 개수

# 앞에서부터
for i in range(N):
    # 높이가 더 올라갔으면
    if stone[i] > B[-1]:
        B.append(stone[i])
    # 높이가 더 낮아졌으면
    else:
        # 이분탐색으로 현재 높이보다 더 작은, 가장 큰 높이의 index
        # bisect_left(a, x) : 정렬된 a에 x를 삽입할 위치 리턴
        # bisect_left(a, x) : 그 위치의 오른쪽 위치 리턴
        index = bisect.bisect_left(B, stone[i])
        B[index] = stone[i]

    B_c[i] = len(B)

# 뒤쪽부터인데 편하게 reverse
stone.reverse()

for i in range(N):
    # 높이가 더 올라갔으면
    if stone[i] > C[-1]:
        C.append(stone[i])
    # 높이가 더 낮아졌으면
    else:
        # 이분탐색으로 현재 높이보다 더 낮은, 그 중에서 가장 큰 높이의 index
        index = bisect.bisect_left(C, stone[i])
        C[index] = stone[i]
    
    C_c[N - i - 1] = len(C)

sum = 0
for i in range(N):
    # 양 방향에서 돌을 건널 때, 그 합의 최대인 것
    sum = max(sum, B_c[i] + C_c[i])

# 가장 높은 위치의 돌을 밟았을 때 겹치기 때문에 -1
print(sum - 1)