반갑습니다!

2631번: 줄세우기 boj.kr 풀이 이 문제는 LIS 알고리즘을 통해 해결할 수 있다. 키 순서가 오름차순으로 정렬된 아이들은 이동시킬 필요가 없다. 나머지 아이들을 최장 증가 수열에 속해있는 아이들 사이에 넣어주면 되기 때문에 LIS 알고리즘을 통해 최장 증가 수열의 길이를 계산한 뒤, 전체 어린이 숫자에서 빼주면 정답이 된다. 아래의 코드는 O(nlogn)의 복잡도를 갖는 LIS 알고리즘을 구현했다. 코드 C++

18353번: 병사 배치하기 boj.kr 풀이 병사 리스트를 뒤집으면 결국 LIS(Longest Increasing Subsequence) 문제가 된다는 것을 알 수 있다. LIS 알고리즘은 크게 2가지 방법이 알려져있다. 하나는 동적 계획법을 사용해 O(n^2) 시간에 해결하는 방법, 또다른 하나는 이분 탐색(lower_bound)를 사용해 O(nlogn) 시간에 해결하는 방법이다. 아래의 코드에서는 이분 탐색을 활용해 O(nlogn)의 복잡도로 해결했다. 코드 C++ #include #include #include using namespace std; int n; vector soldiers; int get_lis() { if (n == 1) return 0; vector lis; lis.push_b..