가장 긴 증가하는 부분 수열 파이썬

링크

일단 제목만 봤을때는 무슨 문제인지 전혀 감이 오지 않았다 

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.라는 말이있다

 

부분수열에대한 개념이 없어서 한번 찾아봐야 겠다는 생각이 들었다

내 생각에는 가장 작은수는 맨왼쪽에 가장 큰수는 맨 오른쪽에 있을때 가장 긴 수열의 길이는 구하는것같다

 

뭔가 문제가 간단하게 보이는데 흠..

가장 작은 값을 찾아서 거기서 부분 수열을 구하면 되는 그럲게까지 간단한 문제는 아닌것같다

예를들어 2,3,4,5,6,7,1이 주어졌을때 가장 작은수는 1이지만 1부터 시작하는 수열은 길이가 1 밖에 되지않는것을 확인 하였다

 

구현 아이디어1

다이나믹 프로그래밍을 적용하여해당요소부터 증가 부분수열을 만들었을때의 길이를 각각 리스트의 요소로 삼는다그것들중 큰값을 출력한다

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

코드 구현

N=int(input())
d=[]
a=list(map(int,input().split()))
for i in range(len(a)):
    b=a[i:]
    # ans=b[0]
    ans=1
    for j in range(1,len(b)):
        if b[j] > b[j-1]:
            ans+=1
    d.append(ans)
# print(d)
print(max(d))

시작하자마자 틀렸습니다가 떳다 저 등호가 문제일까 같은것도 증가수열에 포함될수있는건가?

문제 설명이 빈약한게 좀 아쉽다

 

부분열에대해 검색 출처 위키

부분열(部分列)은 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열이다.

역시나 순서대로 접근하는게 맞았다

 

위의 코드가 틀린이유는 너무 단순하게 접근했기때문이다

위코드로 입력이 100 2 3 4 5 6 7 8 이 주어진다면 실제답은 7이지만 출력은 1이된다 어떻게 접근해야할까

 

지금까지는 앞에서부터 새는 방법을 생각했었는데 뒤에서 세보는것은 어떤가?

시간초과에 도움이 될지도 하지만 지금은 일단 틀렸습니다가 나왔으니 나중에 생각해 봐야겠다

 

N=int(input())
d=[]
a=list(map(int,input().split()))
for i in range(len(a)):
    b=a[i:]
    # ans=b[0]
    ans=1
    max_num=b[0]
    for j in range(1,len(b)):
        if b[j] > max_num:
            ans+=1
            max_num=b[j]
    d.append(ans)
# print(d)
print(max(d))

전 제출에서 오류를 발견했다 바로 아래 숫자보다 크기만하면 추가된다고?

반례가 많다 입력으로 100 1 2 가 들어올경우 100과 2가 증가수열로 판단하기때문이다

 

따라서 최대값을 갱신시켜야 추가하는 방향으로 접근하였다 하지만 이것도 오류가 있는것을 발견하였다

 

0  1000 1001 1 2 3 4 가 입력으로 주어졌을때 답은 5 다 하지만 출력으로는 4가 출력된다

 

최대길이의 증가수열을 구하는방식이 최대값을 갱신시키는 간단한방법으로는 타파가 안되는것같다

좋은 방법 없을까

 

몇시간동안 애썻는데 정말 도저히 모르겠다 

문제 설명에는 LIS(Longest Increasing Subsequence)라고 써져있다

그게 뭐냐고!!!

 

푸신분 풀이를 찾아보았다

동적계획법 말고도 이진분류? 그걸로도 풀수있다고 한다

이진분류에 신경쓰기엔 지금 너무 학업스트레스가 심해서 동적계획법 풀이만 보고 넘어가도록 한다

링크

내 첫번째 풀이와 접근법이같다

이 부분배열은 결국 어디서부턴가 시작해서 어딘가에서 끝난다

다만 틀린점은 나는 거기서부터 시작했을때 최대값을 보여주려고 했고 

이분은 거기서 끝났을때의 길이 최대값을 구했다

 

이게 차이점인것같다

 

동적계획법은 간단한 문제부터 시작해서 크게 만들어가는게 핵심인데

배열의 가장 첫번째부터 시작해서 그 수부터 시작하는 부분수열의 최대길이를 구하는것은 사실 가장 어려운문제부터 푸는것이다 

 

아까 내가 위에서 말했던 그렇다면 거기서부터 시작하는 수를 구하되

방향을 거꾸로하면 어떨까

되는것같다

 

배열의 가장 마지막부터 시작해서 처음으로 가며 최대값을 출력함

선택된 원소는 배열상에서 자기보다 앞에 있는수들중 자기보다 큰수들의 max값에 +1을 함

그리고 모든 원소들의 최대값이 구해졌으면 거기서 max값출력

 

이제 구현해보자

제출

N=int(input())
d=[1 for i in range(N)]
a=list(map(int,input().split()))
for i in range(N):
    z=[0]
    for j in range(i):
        if a[N-i-1] < a[N-i-1+j+1]:
            z.append(d[N-i-1+j+1])
    d[N-i-1]=max(z)+1
# print(d)
print(max(d))

정답

굳이 끝점 기준이 아니고 귀찮게 시작점기준으로 한이유는 

뭔가 시작점으로 풀수있다는걸 증명하고 싶었던것같다 

좀 지친다 하하하