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 | 31 |
Tags
- 이분탐색
- 동적계획법
- 구현
- CS
- 에라토스테네스의 체
- Kotlin
- 시뮬레이션
- 세그먼트 트리
- 투 포인터
- Network
- 문자열
- 위상정렬
- Effective Java
- mst
- 백준
- 알고리즘
- 스택
- 완전탐색
- JUnit 5
- BFS
- 백트래킹
- 플로이드-와샬
- 수학
- 프로그래머스
- 후니의 쉽게 쓴 시스코 네트워킹
- 유니온 파인드
- dfs
- 그리디
- swea
- java
Archives
목록lis (2)
반갑습니다!
[백준] 2631줄 세우기
2631번: 줄세우기 boj.kr 풀이 이 문제는 LIS 알고리즘을 통해 해결할 수 있다. 키 순서가 오름차순으로 정렬된 아이들은 이동시킬 필요가 없다. 나머지 아이들을 최장 증가 수열에 속해있는 아이들 사이에 넣어주면 되기 때문에 LIS 알고리즘을 통해 최장 증가 수열의 길이를 계산한 뒤, 전체 어린이 숫자에서 빼주면 정답이 된다. 아래의 코드는 O(nlogn)의 복잡도를 갖는 LIS 알고리즘을 구현했다. 코드 C++
알고리즘 문제 풀이
2020. 10. 22. 15:28
[백준] 18353 병사 배치하기
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..
알고리즘 문제 풀이
2020. 9. 25. 15:24