[백준] 2352번 반도체 설계
-
알고리즘 : LIS, DP, 이진탐색, lower_bound
-
DP만 이용한 풀이 : O(N^2), pypy3 통과
- 모든 수를 순회
- length_list에 각 인덱스를 마지막으로 하는 촤장 거리 저장
- 매 인덱스마다 length_list 순회
-
DP+이진탐색을 이용한 풀이 : O(NlogN), python3 통과
- LIS 리스트 set
- 모든 수를 순회
- lower_bound를 이용해 LIS에서 현재 수 보다 같거나 큰 위치를 찾음
- 이미 수가 존재하면 갱신
- 아니면 추가
-
소감
- LIS, lower bound, upper bound 추가 공부 필요
코드1
# 동적계획법: O(N^2)
def init():
port_num = int(input(''))
port_list = list(map(int, input('').split(' ')))
return port_num, port_list
port_num, port_list = init()
length_list = [0] * port_num
for i in range(port_num):
length_list[i] = 1
for j in range(i):
if port_list[j] < port_list[i]:
length_list[i] = max(length_list[i], length_list[j]+1)
print(max(length_list))
코드2
# 동적계획법 + 이분탐색: O(NlogN)
def binary_search(start, end, key):
if start > end:
return start
mid = (start+end)//2
if key > num_list[mid]:
return binary_search(mid+1, end, key)
if key <= num_list[mid]:
return binary_search(start, mid-1, key)
def init():
port_num = int(input(''))
port_list = list(map(int, input('').split(' ')))
return port_num, port_list
port_num, port_list = init()
num_list = [port_list[0]]
for i in range(1, port_num):
j = binary_search(0, len(num_list)-1, port_list[i])
if j < len(num_list):
num_list[j] = port_list[i]
else:
num_list.append(port_list[i])
print(len(num_list))
Author And Source
이 문제에 관하여([백준] 2352번 반도체 설계), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-2352번-반도체-설계
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
# 동적계획법: O(N^2)
def init():
port_num = int(input(''))
port_list = list(map(int, input('').split(' ')))
return port_num, port_list
port_num, port_list = init()
length_list = [0] * port_num
for i in range(port_num):
length_list[i] = 1
for j in range(i):
if port_list[j] < port_list[i]:
length_list[i] = max(length_list[i], length_list[j]+1)
print(max(length_list))
# 동적계획법 + 이분탐색: O(NlogN)
def binary_search(start, end, key):
if start > end:
return start
mid = (start+end)//2
if key > num_list[mid]:
return binary_search(mid+1, end, key)
if key <= num_list[mid]:
return binary_search(start, mid-1, key)
def init():
port_num = int(input(''))
port_list = list(map(int, input('').split(' ')))
return port_num, port_list
port_num, port_list = init()
num_list = [port_list[0]]
for i in range(1, port_num):
j = binary_search(0, len(num_list)-1, port_list[i])
if j < len(num_list):
num_list[j] = port_list[i]
else:
num_list.append(port_list[i])
print(len(num_list))
Author And Source
이 문제에 관하여([백준] 2352번 반도체 설계), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-2352번-반도체-설계저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)