Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 문자열
- 수학
- 위상정렬
- 플로이드-와샬
- 이분탐색
- 투 포인터
- 백준
- Kotlin
- 시뮬레이션
- 백트래킹
- 후니의 쉽게 쓴 시스코 네트워킹
- 에라토스테네스의 체
- 스택
- BFS
- 동적계획법
- 그리디
- mst
- swea
- CS
- java
- 구현
- 프로그래머스
- JUnit 5
- 완전탐색
- Effective Java
- Network
- 알고리즘
- 유니온 파인드
- dfs
- 세그먼트 트리
Archives
반갑습니다!
[백준] 2631줄 세우기 본문
풀이
이 문제는 LIS 알고리즘을 통해 해결할 수 있다.
키 순서가 오름차순으로 정렬된 아이들은 이동시킬 필요가 없다. 나머지 아이들을 최장 증가 수열에 속해있는 아이들 사이에 넣어주면 되기 때문에 LIS 알고리즘을 통해 최장 증가 수열의 길이를 계산한 뒤, 전체 어린이 숫자에서 빼주면 정답이 된다.
아래의 코드는 O(nlogn)의 복잡도를 갖는 LIS 알고리즘을 구현했다.
코드
C++
'알고리즘 문제 풀이' 카테고리의 다른 글
[백준] 5557 1학년 (0) | 2020.11.01 |
---|---|
[백준] 1644 소수의 연속합 (0) | 2020.10.23 |
[프로그래머스] 최고의 집합 (0) | 2020.10.22 |
[프로그래머스] 섬 연결하기 (0) | 2020.10.21 |
[백준] 1915 가장 큰 정사각형 (0) | 2020.10.20 |