파이썬 알고리즘 073 | 최대 부분 증가수열(LIS : Longest Increasing Subsequence )

73. 최대 부분 증가수열

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰
수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7,
12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길
이가 5인 최대 부분 증가수열을 만들 수 있다.
▣ 입력설명
첫째 줄은 입력되는 데이터의 수 N(2≤N≤1,000, 자연수)를 의미하고,
둘째 줄은 N개의 입력데이터들이 주어진다.
▣ 출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.
▣ 입력예제 1
8
5 3 7 8 6 2 9 4
▣ 출력예제 1
4

<내 풀이>

아직은 내게 너무 낯설다.. 그리고 아이디어도 생각이 나지 않는다

(풀이 듣고 구현해본 코드)

• dfs(x)는 dy(x)를 출력하게 하는 것으로 설정하기 위해
  tmp를 하나 정해서 arr[x-1]>arr[i] 조건 성립하면 tmp에 dy[i+1]에 담겨있는 애들 tmp에 담아서 max(tmp)를 dy(x)로 설정해주는 게 목표였는데
  tmp에 append가 안된다고 한다..

def dfs(x) :
    if x==1:
        return x
    else :
        for i in range(x) :
            if arr[x-1]>arr[i] :
               tmp.append(dfs(i+1)+1)
               print(tmp)
            else : 
            
if __name__=='__main__' :
    n=int(input())
    arr=list(map(int,input().split()))
    dy=[0]*(n+1)
    tmp=[]
    print(dfs(2))

(2) 앞에 설정값을 참고해서 풀이한 것! - 맞았다!

n=int(input())
arr=list(map(int,input().split()))
arr.insert(0,0) #시작값 1번 인덱스부터 하게 하려구
dy=[0]*(n+1)
dy[1]=1 #이건 이렇게 초기화 (직관적으로 알 수 있으니깐)
tmp=[]

for i in range(2,n+1) :
    for j in range(i):
        if arr[i]>arr[j] :
            tmp.append(dy[j]+1)
    if len(tmp)>0:
        dy[i]=max(tmp)
        tmp.clear()
    else : 
        dy[i]=1
print(max(dy))

<풀이>

(1) 우선 입력받은 수는 arr리스트에 넣어주기
(2) dy는 자기가 만들 수 있는 수열의 갯수넣어주는 리스트
자기보다 앞 인덱스에 있는 애들 중에 arr에서 작은 애 있으면 그 애의
dy값에다가 1 더해주면 됨, arr에서 앞에 자기보다 작은 애들 여럿 있으면 그 중에서 최댓값만 골라서 자신의 dy값으로 넣어주면 된다
(3) 그리고 1은 항상 확정이니깐 지정해주기

n=int(input())
arr=list(map(int,input().split()))
arr.insert(0,0) #시작값 1번 인덱스부터 하게 하려구
dy=[0]*(n+1)
dy[1]=1 #이건 이렇게 초기하
res=0
for i in range(2,n+1) :
    max=0
    for j in range(i-1,0,-1):
        if arr[j]<arr[i] and dy[j]>max:
            max=dy[j]
        dy[i]=max+1
        if dy[i]>res:
            res=dy[i]
print(res)

<반성점>

• 무조건 dy[n]을 출력하면 안된다고 한다!
• dy중에서 max인것을 출력해야 하는 것이지
• 굳이 dfs방식 안써도 된다

<배운 점>

• 핵심은 아주 간단한 문제에서 시작해서 확장시켜 나가는 것
• arr=list(map(int,input().split()))
  arr.insert(0,0) #시작값 1번 인덱스부터 하게 하려구
  =>이와 같이 insert(0,0)해줘서 1번 인덱스부터 쉽게 접근가능하게 하면 좋음

<2차 내 풀이>

=> 놓친 부분 존재 :
j할 때 1,i가 아니라 range(i)야

n=int(input())
a=list(map(int,input().split()))
a.insert(0,0)
dy=[0]*(n+1)
dy[1]=1
for i in range(2,n+1) :
    maxi=-1
    for j in range(1,i) :
        print(dy[j])
        if a[j]<a[i] and maxi<dy[j] :
            maxi=dy[j]
    dy[i]=maxi+1

print(max(dy))

=> 최종 수정한 풀이

n=int(input())
a=list(map(int,input().split()))
a.insert(0,0)
dy=[0]*(n+1)
dy[1]=1
for i in range(2,n+1) :
    maxi=-1
    for j in range(i) :
        #print(dy[j])
        if a[j]<a[i] and maxi<dy[j] :
            maxi=dy[j]
    dy[i]=maxi+1
print(max(dy))