Lis3 이진탐색LIS ( 최장 증가 부분 수열 ) 알고리즘 파헤치기 # 백준 12015번 from bisect import bisect_left n = int(input()) arr = list(map(int,input().split())) x = [arr[0]] d = [1] * n for i in range(1,n): if x[-1] < arr[i]: x.append(arr[i]) d.append(d[-1]+1) else: idx = bisect_left(x,arr[i]) x[idx] = arr[i] print(max(d)) 위에는 백준 12015번 문제의 답이다. 전형적인 이진탐색LIS 예제이기에 올려본다. 기존에 2중 for문으로 구현한 LIS와는 달리 for문을 한번만 사용하여 계산속도를 올려주는 방식이다. 이진탐색은 for문을 하나로 없에준다. 방식은 dp를 .. 2022. 11. 25. 백준 11053번 - 가장 긴 증가하는 부분 수열 n = int(input()) arr = list(map(int,input().split())) d = [1] * n for i in range(n): for j in range(i): if arr[j] < arr[i]: d[i] = max(d[i],d[j]+1) print(max(d)) 제일 기본적인 Lis의 예제이다. 2중 for문으로 돌아가면서 최적의 수열을 찾아내는 방식이다. 2022. 11. 25. 백준 2491번 - 수열 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int,input().split())) d1,d2 = [1]* n, [1]*n for i in range(1,n): if arr[i] = arr[i-1]: d2[i] = max(d2[i],d2[i-1]+1) print(max(max(d1),max(d2))) # 연속된 상황이 끊기면 다시 1부터 카운트를 시작한다. # d[i]에는 i번째에 도달했을 때 i번째가 수열의 마지막 수인 수열의 집합 중 # 가장 긴 수열의 길이가 저장되어있다. 처음엔 기존의 lis의 2중 for 문 방식으로 작성을 하려 했으나 시간초과가 떴다. 그래서 for문을 하나만 쓰는 이진탐색법으로 구현을 하려다가 닭.. 2022. 11. 25. 이전 1 다음