반응형
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
- 조인
- 쿼리
- dbeaber
- 백트래킹
- 인덱스
- 결합인덱스란
- 데이터분석
- storage_integration
- 자료구조
- Index
- S3
- 문제풀이
- 백준
- snowflake
- HackerRank
- 알고리즘
- 코딩
- 결합인덱스조건
- DB
- sql
- dfs
- 인덱스튜닝
- 데이터베이스
- AWS
- Oracle
- 오라클
- 개발
- 율코딩
- Join
- MySQL
Archives
- Today
- Total
율코딩
[알고리즘] 백준 2110번 문제 본문
반응형
https://www.acmicpc.net/problem/2110
이문제는 이진탐색을 활용하여 푸는 문제이다.
반복적으로 gap을 설정하여 c개 이상의 공유기를 설치할 수 있는 경우를 찾는다.
먼저,start, end를 설정하여 최소 gap과 최대 gap 을 설정한다.
예제를 활용하여 코드를 구현해 보자.
n,c = 5,3
arr = [1,2,4,8,9]
start = arr[1] - arr[0]
end = arr[-1] - arr[0]
mid = (start + end) // 2
5개의 집이 있고 3개의 공유기가 있고 arr에 집들의 좌표라고 하면
start = 1, end = 8, mid= 4가 된다.
1,2,4,8,9
mid가 4라고 했을 때, 공유기를 설치할 수 있는 좌표가 1, 8 이렇게 2개이다.
그런데 3개의 공유기를 설치해야하므로, gap는 더 작아져야한다.
end = mid-1로 했을 때
mid = 2
1,2,4,8,9
공유기를 3개 설치할 수 있다. 그러면 가장 최대로 큰 거리를 구해야하므로,
gap를 증가시킨다.
mid = 3일때 더이상 gap을 증가시킬 수 없으므로, 최적의 상태가 된다.
이것을 코드로 구현하면 아래처럼 나타낼 수 있다.
n ,c = map(int, input().split(' '))
arr = []
for _ in range(n):
arr.append(int(input()))
arr = sorted(arr)
start = arr[1] - arr[0] #최소 gap
end = arr[-1] - arr[0] #최대 gap
result = 0
while start <= end:
value = arr[0]
mid = (start + end)//2
cnt = 1
for i in range(1,len(arr)):
if arr[i] >= value + mid:
value = arr[i]
cnt += 1
if cnt >= c:
start = mid + 1
result = mid
else: #c개 이상 공유기를 설치할 수 없는 경우
end = mid - 1
print(result)
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[알고리즘] 키로거 5397번 (0) | 2022.08.15 |
---|---|
[알고리즘/백준] N과 M(1) 백트래킹 문제 풀이 (0) | 2022.05.29 |
Comments