sw사관학교 정글 2기/02 이분탐색, 분할정복, 스택, 큐, 우선순위 큐

[이분탐색] 백준 11053번 가장 긴 증가하는 부분 수열 with Python3 ★

금의야행 2021. 8. 16. 13:15

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

 

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

문제

 

내 풀이

import bisect
# 입력
n = int(input())  # 순열의 길이
numlist = list(map(int, input().split()))  # 첫 순열


answer = []


for i in range(len(numlist)):  # 주어진 순열을 처음부터 끝까지 탐색해가며
    print(f'여기{answer}')
    if i == 0:  # 0일 때 값은 바로 answer에 넣어준다.
        answer.append(numlist[0])

# LIS 기법 구현.
    else:
        if numlist[i] > numlist[i-1]:  # 지금 원소가 이전 원소보다 클때, 증가하는 수열이 성립.
            # 해당 원소를 answer에 넣기전 적절한 index를 이분탐색으로 알려줌.
            a = bisect.bisect_left(answer, numlist[i])

            if a > len(answer)-1:  # answer안에 있는 element들보다 값이 클 경우
                answer.append(numlist[i])  # 맨뒤에 붙혀준다.

            else:  # 그이외의 경우 적절한 위치의 element의 값을 바꿔준다.
                answer[a] = numlist[i]

        elif numlist[i] <= numlist[i-1]:  # 위와 동일함.
            a = bisect.bisect_left(answer, numlist[i])
            answer[a] = numlist[i]

print(len(answer))

해설

LIS 기법을 사용하면 된다 해서 구현을 해보았다.

 

정답 풀이

a,b = input().split() a = int(a) b = int(b) print(a+b) print(a-b) print(a*b) print(int(a/b)) #print(a//b) print(a%b) #print("%d\n%d\n%d\n%d\n%d"%(a+b, a-b, a*b, a/b, a%b))

출처:

해석