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
- 응용 계층
- 릿코드
- swea
- baekjoon
- STL
- Transport layer
- 부트시퀀스
- 자료구조
- 백준
- BST
- Embedded
- 임베디드
- 프로그래머스
- leetcode
- 전송 계층
- 다익스트라
- BHS
- DB
- Application Layer
- boot sequence
- Djikstra
- ps
- 데이터베이스
- dp
- Network
- Database
- 문제풀이
- C++
- 네트워크
- 관계형 모델
Archives
- Today
- Total
목록2110 (1)
BOBO's Note
[ Baekjoon ] 2110. 공유기 설치
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 풀이 방법 N개의 집 중 C개의 집에 공유기를 설치하는 모든 경우의 수는 이다. 각 경우의 수에 대하여 최소 인접 거리를 구하는 것은 O(C)의 시간이 걸리기 때문에 전체 시간복잡도는 이다. Brute force 방식으로 모든 경우의 수에 대하여 계산하면 시간 초과가 발생한다. 따라서 이진 탐색을 활용해 인접한 공유기 사이의 최소 거리를 찾아..
Algorithm/Problem Solving
2020. 6. 24. 18:21