BOJ 12015 : 가장 긴 증가하는 부분 수열 2
알고리즘 문제 전체 링크삼성 B형 전체 링크 https://www.acmicpc.net/problem/12015 참고- BOJ 1655 : 가운데를 말해요 with 세그먼트 트리 수열 A의 크기는 1,000,000이고 들어 있는 값은 1부터 1,000,000이므로 세그먼트 트리를 이용해서 문제를 풀 수 있다. 예제의 {10, 20, 10, 30, 20, 50}에서가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)의 길이 4를 찾아보자. 수열에 값이 하나가 추가될 때마다, LIS의 길이를 세그먼트 트리를 이용해서 갱신하면 문제를 풀 수 있다.값 x가 추가되고, 구간 [1, x - 1]의 LIS의 길이가 y라면 구간 [1, x]의 LIS의 길이는 y + 1이 된다..
2024. 12. 20.
