알고리즘 종류: 다이나믹 프로그래밍
혼자서 풀었는가?: O
11053번은 가장 긴 증가하는 부분수열(LIS)의 길이를 다이나믹 프로그래밍으로 풀고, 14002는 길이 뿐만 아니라 그 수열도 구하는 문제이다
수열 A = {10, 20, 10, 30, 20, 50} 에서 가장 긴 증가하는 부분수열은 10, 20, 30, 50이고 길이는 4이다
D(i) = ai를 끝으로 하는 가장 긴 증가하는 부분수열의 길이
로 놓고 다이나믹 프로그래밍 방식으로 풀 수 있다.
문제 이해
예를 들어, a0 = 10, a1 = 20, a2 = 10, a3 = 30 인 수열 A가 있다
A= {10, 20, 10, 30}
여기서 D(1)란, a1를 끝으로 하는 가장 긴 증가하는 부분수열의 길이, 즉 20을 끝으로 하는 가장 긴 증가하는 부분수열의 길이를 말한다.
알고리즘적으로 말고 인간으로서(?) 직관적으로 생각해보면 바로 2라는 걸 알 수 있다. 하지만 컴퓨터는 인간이 아니기 때문에... 컴퓨터가 해결할 수 있는 방식으로 코드를 짜줘야 한다 ~~귀찮은녀석.. ~~
문제 풀이
D(i)의 점화식부터 세워야 한다. D(i)의 점화식은 다음과 같다
D(i) = max{ D(j) | j <i and aj a< ai } + 1
- 그리고 정말 당연한게 D(0) = 1이다 a0이 뭐가 오든지 간에 a0으로 끝나는 수열은 { a0 } 하나밖에 없다. a0 = 1000000 이여도 a0으로 끝나는 가장 긴 부분수열의 길이는 1읻
20을 끝으로 하는 가장 긴 증가하는 부분수열의 길이, 즉 D(2)를 구해야 한다고 하자. 이 수열에서 20보다 앞에 오는 애들은 전부 20보다 작아야 한다(당연함. LIS 정의상 증가하는 부분수열임) 이 바로 전 문장을 변수 j와 i로 표현하면
j < i이고 ai < aj
여야 하는 것이다.
또한 그런 D(i) 중에서도 최대값, Max인 이유는 다음과 같다. D(3)의 경우, 그 앞의 D(j)인 D(1)과 D(2)는 다음과 같다
D(0) = 1 (a0인 10을 끝으로 하는 가장 긴 수열. 여기서 수열은 { 10 } 이다)
D(1) = 2 (a1인 20을 끝으로 하는 가장 긴 수열. 여기서 수열은 { 10, 20 } 이다)
D(3)인 경우는 두 가지가 있다.
1) D(0)일 때 수열 뒤에 a3인 30이 붙는 경우. 이 때 수열은 {10, 30} 이 되며 D(3) = 2가 된다
2) D(1)일 때 수열 뒤에 a3인 30이 붙는 경우. 이 때 수열은 {10, 20, 30} 이 되며 D(3) = 3이 된다
a3인 30이 10 뒤에 붙는 것보다 10, 20 뒤에 붙는 게 더 길다. 따라서 D(j) 중 최대 D(j)에 1을 더해서 본인 D(i)를 갱신시켜 주는 것이다. 본인의 길이가 1이기 때문에 +1이 붙는 거임.
11053
길이만 구하는 11053번은 다음과 같이 구할 수 있다.
n = int(input())
a = input().split(' ')
a = [int(i) for i in a]
d = [0 for i in range(n)]
d[0] = 1
for i in range(1, n):
temp = d[0]
for j in range(0, i):
if (a[j] < a[i]):
if (temp <= d[j]):
d[i] = d[j]
temp = d[j]
d[i] = d[i] + 1
print(max(d))
두번째 for문 안쪽의 두번째 if문이 최댓값을 구하는 건데, 그냥 파이썬 내장함수 max를 쓰는 사람들이 더 많았다 그리고 그게 더 좋아보임....ㅎ
14002
14002번은 LIS 내용까지 출력해야 되는 경우이다. 이건 일고 전공 수업 때 배웠던 trace back 기법으로 푸셈!
trace_back 배열은 전부 -1로 초기화해주었다. 즉, 어디서부터 온 애들이 아니라면 -1값이다.
뒤에서부터 D(5)는 D(3)에서 왔기 때문에 trace_back[5] = 3이다. , D(3)은 D(1)에서 왔기 때문에 trace_back[3] = 1이다. D(1)은 D(0)에서부터 와서 어쩌구... 그림 뭔지 이해 안가면... 전공수업 알고 피피티 복습하자
코드는 다음과 같다
n = int(input())
a = input().split(' ')
a = [int(i) for i in a]
d = [0 for i in range(n)]
d[0] = 1
trace_index = [-1 for i in range(n)]
def printD(index, rst):
if (index == -1):
for i in sorted(rst):
print(i, end=' ')
return
rst.append(a[index])
printD(trace_index[index], rst)
for i in range(1, n):
temp = d[0]
for j in range(0, i):
if (a[j] < a[i]):
if (temp <= d[j]):
d[i] = d[j]
temp = d[j]
trace_index[i] = j
d[i] = d[i] + 1
max = d[0]
max_index = 0;
for i, v in enumerate(d):
if (v > max):
max = v
max_index = i
print(max)
rst = []
printD(max_index, rst)
여전히 내장함수 max 쓸 생각을 못해서 쓸데없이 for문을 날린 코드이다ㅋㅋ..
