728x90
[백준알고리즘] 2352번: 반도체 설계 -Python
https://www.acmicpc.net/problem/2352
언뜻 봐서는 O(N^2)의 방식의 풀이도 통과할 줄 알았는데 시간 초과가 발생했다.
이 문제는 LIS문제이다. 가장 긴 증가하는 부분 수열을 만들어야 한다. 여기서는 직접 부분 수열을 출력하는 것이 아닌 길이만 출력하면 되기 때문에 간단한 lower bound를 이용한 방법을 사용하면 된다.
lower bound를 사용해서 추가할 수 있는 위치에 추가하는 방식은 O(NlogN) 정도의 시간 복잡도를 갖는다.
https://seungkwan.tistory.com/8
마지막 원소보다 삽입하려는 원소의 값이 작다면 삽입될 수 있는 위치에 적절히 교체하게 되면서 LIS를 만드는 것이 아닌 같은 길이의 부분 수열 중 가장 낮은 값을 유지하도록 하는 리스트를 만드는 것이라 보면 된다.. 말로만 보면 이해가 안 되기 때문에 위의 블로그를 참고하면 이해가 쉬울 것이다.
아무튼 lower bound로 삽입할 위치를 이분 탐색으로 찾기 때문에 시간 복잡도를 줄일 수 있게 된다. 이분 탐색을 사용하기 위해서 bisect 모듈의 bisect_left를 사용했다. 그리고 직접 이분 탐색 코드를 짜서도 시도해봤다.
from bisect import bisect_left
n = input()
dest = list(map(int, input().split()))
link = []
for d in dest:
if not link or link[-1] < d:
link.append(d)
else:
link[bisect_left(link, d)] = d
print(len(link))
def bisect_left(arr, val):
s, e = 0, len(arr)-1
while s <= e:
m = (s+e)//2
if arr[m] > val:
e = m-1
else:
s = m+1
return s
n = input()
dest = list(map(int, input().split()))
link = []
for d in dest:
if not link or link[-1] < d:
link.append(d)
else:
link[bisect_left(link, d)] = d
print(len(link))
잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다
728x90
'algorithm > 백준알고리즘' 카테고리의 다른 글
[백준알고리즘] 5557번: 1학년 -Python (0) | 2020.04.21 |
---|---|
[백준알고리즘] 1138번: 한 줄로 서기 -Python (0) | 2020.04.21 |
[백준알고리즘] 1080번: 행렬 -Python (0) | 2020.04.21 |
[백준알고리즘] 2252번: 줄 세우기 -Python (0) | 2020.04.18 |
[백준알고리즘] 1620번: 나는야 포켓몬 마스터 이다솜 -Python (0) | 2020.04.18 |