[프로그래머스] 이진탐색 & 동적계획법

# 2021-03-12 프로그래머스 > 이분탐색 > 입국심사
# 걸리는 시간의 범위를 이진탐색
# 최소범위와 최대 범위를 구한 후 이분 탐색으로 좁히기
def solution(n, times):
    # 최악의 경우, 가장 비효율적인 심사관에게 모든 사람이 심사
    left, right = 1, max(times)*n
    answer = 0
    while left <= right:
        mid = (left + right)//2
        people = 0
        for time in times:
            # 주어진 시간동안 총 몇명의 사람을 심사할 수 있는지
            people += mid // time
            if people >= n:
                break
        
        # 모든 사람을 심사할 수 있는 경우
        # 시간의 범위를 left부터 mid-1까지로 조절
        if people >= n:
            answer = mid
            right = mid - 1
        # 모든 사람을 심사할 수 없는 경우
        # 시간의 범위를 mid+1부터 right까지로 조절
        else :
            left = mid + 1
    return answer

# 2021-03-12 백준 > 이분탐색 & 동적계획법 > 12015 > 가장 긴 증가하는 부분 수열
import sys

x = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
# dp의 값을 1로 초기화
dp = [1 for i in range(x)]

for i in range(x):
    for j in range(i):
        # 현재 위치(i)보다 이전에 있는 원소(j)가 작은지 확인
        if arr[i] > arr[j]:
        	dp[i] = max(dp[i], dp[j]+1)
            
print(max(dp))

# 2021-03-12 백준 > 이분탐색 & 동적계획법 > 12015 > 가장 긴 증가하는 부분 수열
import sys
import bisect

x = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
# dp의 값을 arr[0]로 초기화
dp = [arr[0]]

for i in range(x):
    # 현재 위치(i)가 이전 위치의 원소들보다 크면 dp에 추가
    if arr[i] > dp[-1]:
        dp.append(arr[i])
    else:
        idx = bisect.bisect_left(dp, arr[i])
        dp[idx] = arr[i]

print(len(dp))

bisect.bisect_left(arr, x): arr가 정렬되어있다는 가정하에 x값이 들어갈 위치 반환

이진탐색

References

입국심사 풀이 - 네이버 블로그

가장 긴 증가하는 부분 수열(LIS) 완전 정복 - 백준 파이썬

[백준알고리즘] 12015번: 가장 긴 증가하는 부분 수열 2 -Python