[12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색)

2023. 4. 4. 17:07·Coding Test/DP
728x90
 

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

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

www.acmicpc.net

 

LIS

Longest Increasing Subsequence

 

풀이

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

d = [0]

for i in arr:
    if d[-1]<i:
        d.append(i)
    else:
        left = 0
        right = len(d)

        while left<right:
            mid = (right+left)//2
            if d[mid]<i:
                left = mid+1
            else:
                right = mid
        d[right] = i

print(len(d)-1)
import sys
from bisect import bisect_left
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
d = []
for i in arr:
    k = bisect_left(d, i)
    if len(d) == k:
        d+=[i]
    else:
        d[k] = i

print(len(d))

 

 

 

 

728x90
저작자표시 (새창열림)
'Coding Test/DP' 카테고리의 다른 글
  • [14003번] 가장 긴 증가하는 부분 수열5 (LIS, 이분탐색)
  • [18353번] 병사 배치하기(LIS, 이중 for문)
  • [2098번] 외판원 순회(TSP, 비트 마스킹)
  • [11049번] 행렬 곱셈 순서 (행렬 곱 연산 횟수의 최솟값 구하기, DP)
Karla Ko
Karla Ko
𝘾𝙤𝙣𝙩𝙞𝙣𝙪𝙤𝙪𝙨𝙡𝙮 𝙄𝙢𝙥𝙧𝙤𝙫𝙞𝙣𝙜, 𝘾𝙤𝙣𝙨𝙩𝙖𝙣𝙩𝙡𝙮 𝘿𝙚𝙫𝙚𝙡𝙤𝙥𝙞𝙣𝙜 𝙔𝙚𝙨!
    250x250
  • Karla Ko
    karlaLog
    Karla Ko
  • 전체
    오늘
    어제
    • Total (467)
      • Spring (19)
      • JPA (4)
      • Cloud & Architecture (15)
        • Kubernetes (5)
        • Docker (3)
        • MSA (2)
        • GCP (1)
        • AWS (4)
      • Devops (1)
      • Message Queue (4)
        • Kafka (2)
        • RabbitMQ (2)
      • Git (4)
      • DB (4)
      • Java (9)
      • Python (4)
      • CS (11)
        • OS (8)
        • Network (2)
        • Algorithm (1)
      • Coding Test (392)
        • programmers (156)
        • Graph (43)
        • DP (37)
        • Search (31)
        • Tree (13)
        • Data Structure (26)
        • Combination (12)
        • Implement (18)
        • Geedy (23)
        • Sort (7)
        • Math (21)
        • geometry (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    알고리즘
    Algorithm
    힙
    정렬
    조합
    월간코드챌린지
    트리
    재귀
    자료구조
    DP
    이분탐색
    다익스트라
    그리디
    덱
    BFS
    구현
    DFS
    백준
    구간합
    LIS
    플로이드워셜
    프로그래머스
    최단거리
    큐
    그래프
    동적계획법
    스택
    최소신장트리
    최대공약수
    파이썬
  • hELLO· Designed By정상우.v4.10.3
Karla Ko
[12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색)
상단으로

티스토리툴바