목록LIS (1)

dh_0e

[PS] 전깃줄-2 / C++ (백준 2568번)

전깃줄-2 (백준 2568번) A or B 전봇대 중 하나를 기준으로 선택하여 정렬하고, 나머지 전봇대 배열의 LIS(가장 긴 증가하는 부분 수열)를 구하면 되는 문제. 발상이 생각보다 쉬워서 가장 긴 증가하는 부분 수열 5(백준 14003번)를 풀어봤다면 금방 해결 가능하다. 풀이 과정우선, n이 100,000 이하의 자연수이므로 LIS를 이분 탐색을 사용하여 $O(nlogn)$로 구현하여야 한다.if (vec[vec.size() - 1] vector를 만들어 다음 수가 vector에 들어있는 모든 값보다 크다면 수열의 맨 뒤에 추가해 준다.else{ .. }while(st그렇지 않다면 이분 탐색으로 해당 수보다 작은 수의 바로 다음 순서를 찾는다.vec[en]=d[i].first;다음 순서로 수열에..
Problem Solving/Baekjoon 2026. 1. 15. 11:53
이전 Prev 1 Next 다음