성능 요약
메모리: 122888 KB, 시간: 212 ms
분류
이분 탐색, 매개 변수 탐색
문제 설명
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
아이디어, 문제풀이
- 거리를 이분탐색하는게 아닌, 공유기의 개수를 이분탐색 해야한다.
TROUBLE SHOOTING
- 일단 이 문제를 풀이할떄, 이 문제를 이분탐색으로 접근해야하는 이유를 찾지 못했다. 나는
-
n개중 c개를 골라 나올수 있는 모든 조합을 가져와서
-
각각 배열 속 모든 차이중 최소값을 구한뒤,
-
그 최소값들중 최대값을 출력한다
와 같은 논리로 접근하는편이 편하다고 생각했고, 실제로 그 코드를 구현해서 제출도 해보았다. 아래는 그 코드다.
import sys from itertools import combinations input = sys.stdin.readline n, c = map(int, input().split()) n_list = [] for i in range(n): a = int(input()) n_list.append(a) n_list.sort() def min_distance(combination): min_dist = float('inf') for i in range(1, len(combination)): distance = combination[i] - combination[i - 1] if distance < min_dist: min_dist = distance return min_dist max_min_distance = 0 for combination in combinations(n_list, c): min_dist = min_distance(combination) if min_dist > max_min_distance: max_min_distance = min_dist print(max_min_distance)실제로 구현은 잘 됐지만, 제출과정 속에서 시간 초과가 나왔다. 뿐만아니라, 하나하나 찾으면서 순차탐색을 통해서도 충분히 구현할수 있다고 생각했지만, 시간복잡도와 관련있는 시간초과가 나오면서 이분탐색을 적용해 풀어야 한다는걸 알게됐다.
-
- 일단 이 문제에서 어려웠던건, 대체 뭘 이분탐색 해야하는걸까? 였다. chat gpt를 통해서 문제는 풀어냈지만, 원리를 떠올리는게 쉽지 않았다. 지금까지 문제를 풀면서 다른 코드들을 참고해본적은 없었는데, 방법을 생각해 내지 못해, 결국 다른 풀이들을 참고 했다. 일단 원리부터 간단 설명 하면, 항상 이분탐색의 핵심 코드는 아래와 같은 for문에서 결정이 된다.
min(n_list) 값이 target이기 때문에, 예제로 치면 맨 앞쪽의 1이 초반 값이 되고, 그다음 뽑아온 n_list 값과의 차이를 mid 와 비교를 해주게 된다. 우선 내가 정한 mid값은 중앙값 이였고, 이를 만족하지 않는다면, 다음 i 로 넘아간다. 만족하게 되면, 공유기 개수인 count를 추가하며 끝값까지 가게되는데, 여기서 최대로 만들수 있는 공유기의 개수가 정해진체로 count 에 담기게 된다. 이 count값에 c와 일치하거나, c와 더 많다는(통나무문제와 비슷한 원리) 이분탐색문을 적용해주게되면, 문제를 만족하는 코드를 작성할수 있게 된다. 이해는 잘 됐지만.. 이게 맞는걸까? 문제를 미리 풀어보거나, 비슷한 문제를 풀어보지 않았다면 아무것도 없는 상태에서 풀어내기 쉽지 않을것 같다. 실제로 1시간반… 정도를 고민했으니, 코딩테스트에서 이 문제를 만나게 된다면 아직은 많이 해맬것 같다. chat gpt를 통해 구현해 내긴 했지만, 다른 문제들만큼 깔끔하게 이해하진 못한체로 구현했어서 아쉬움이 많이 남는다. 유형을 익히는게 중요할것 같다.for i in range(n): if n_list[i] - target >= mid: count = count + 1 target = n_list[i]
- 아래는 문제를 풀이하며, 내가 코드상에서 가진 의문들과, 더 생각해볼만한 것들을 chat gpt 를통해 질문한것들인데, 나중을 위해서… 저장해두고자 한다. 혹시 이글을 보는 다른 분들이 있다면 도움이 되기를!
- 왜 count 공유기 개수를 이분탐색하게 된 거야?
- 이분탐색을 사용하는 이유는 거리 차이를 최대화하는 문제를 빠르게 해결하기 위함입니다. 공유기 개수 자체를 이분탐색하는 것이 아니라, 설치 가능한 거리 차이를 이분탐색합니다. 거리 차이를 이분탐색하면서 가능한 거리를 최대로 하는 경우를 찾는 것입니다.
- count를 1부터 시작해야 하는 이유는 알겠는데, 이건 처음에 어떻게 생각해 내야 하는걸까?
- 문제를 해결할 때, 접근 방식을 고려해야 합니다. 이 문제에서는 거리 차이를 최대로 하는 것이 목표이므로, 가장 왼쪽 집(최소 좌표)에 공유기를 설치하는 것이 자연스럽게 떠오릅니다. 이렇게 생각하면, 첫 번째 공유기를 설치한 상태에서 시작하는 것이 논리적이므로 count를 1부터 시작할 수 있습니다.
- for문과 관련된 수식을 쉽게 생각해 낼 수 있는 방법은 무엇인가요?
- 이 문제의 경우, 거리 차이를 최대로 하는 공유기 설치 위치를 찾아야 합니다. 이를 위해 정렬된 좌표 배열을 순회하면서, 이전에 설치된 공유기와의 거리 차이가 mid보다 크거나 같은 경우에만 공유기를 설치합니다. 이렇게 하면 거리 차이가 가능한 한 크게 유지되면서 공유기를 설치할 수 있습니다.
- 알고리즘 문제를 풀 때, 다양한 문제를 접하고 연습하면 패턴을 파악하는 능력이 향상됩니다. 이를 통해 비슷한 유형의 문제나 수식을 더 쉽게 생각해 낼 수 있게 됩니다. 특히, 이분 탐색과 같은 알고리즘을 익히면 이와 관련된 문제를 해결하는 데 도움이 됩니다.
- 왜 count 공유기 개수를 이분탐색하게 된 거야?
코드
#https://www.acmicpc.net/problem/2110
#공유기 설치
#2110
import sys
input = sys.stdin.readline
n, c = map(int, input().split())
n_list = []
for i in range(n):
a = int(input())
n_list.append(a)
# print(n_list)
n_list.sort()
start = 0
end = max(n_list)- min(n_list)
result = 0
# for i in range(c):
# n중에 c만큼을 정할것임
# 그 c들중의 거리차이중 가장 작은것이 최대가 되게끔 하도록 해야함
# 출력은 그 작은것중 최대인것을 출력할예정
while start <= end:
mid = (start + end) // 2
# count = 0
# target = 0
count = 1
target = min(n_list)
for i in range(n):
if n_list[i] - target >= mid:
count = count + 1
target = n_list[i]
# if count == c:
# result = mid
# if count > c:
# start = mid + 1
if count >= c:
result = mid
start = mid + 1
elif count < c:
end = mid - 1
# if n_list[mid] == target:
# elif n_list[mid] > target:
# start = mid +1
# elif n_list[mid] < target:
# end = mid + 1
print(result)
해보자! 게임 클라 개발자!