9:30
출근했다. 어제 못풀었던, 잠 들기 전까지 날 괴롭힌 공유기 설치 문제를 알아보았다.
3번 (2110) 공유기 설치
https://www.acmicpc.net/problem/2110
n개의 집에 x들의 집합들로 있는데, 그 사이에 C개의 공유기를 설치해야한다. 공유기 간 거리를 최대한 멀리 두어 설치해야한다. 공유기를 설치했는데 대수가 적으면 거리를 줄인다. 대수가 많다면 거리를 늘린다. low는 최소거리, high는 가장 먼 두집의 거리, mid값을 정해서 공유기 설치하고 집 위치는 소트로 재정렬해야한다.
# 입력단
N, C = map(int, input().split())
arr = []
for _ in range(N): # 입력값을 배열에 넣는다.
arr.append(int(input()))
arr.sort()
start = 1 # 공유기 거리 최소
end = arr[-1] - arr[0] # 공유기 거리 최대(마지막 집 - 첫 집)
result = 0
# 재귀로 적절한 두 공유기 사이의 거리를 찾는다
while (start <= end):
mid = (start + end) // 2 # 현재 공유기 거리
current = arr[0] # 배열의 첫번째는 최근값
count = 1 # 공유기값을 처음엔 1로 한다.
# 공유기 설치 몇 대 할 수 있는지 체크
for i in range(1, len(arr)): # 집 갯수만큼 수행
if arr[i] >= current + mid: # 기준보다 집의 위치가 크거나 같으면
count += 1 # 공유기 한대 증가
current = arr[i] # 최근 집을 업데이트
# 공유기 설치 수가 목표 보다 크면 공유기 사이 거리 늘림
if count >= C:
start = mid + 1 # 시작지점을 기준에서 +1하면서 오른쪽 범위로 이동
result = mid
# 공유기 설치 수가 목표 보다 작으면 공유기 사이 거리 줄임
else:
end = mid - 1
print(result)
# 근데 솔직히 70퍼센트는 이해가 되는데, 그 이상 이해가 안된다...
# 해당문제는 다른 문제를 풀어보다가 다시 한번 풀어볼 예정이다.
# 머리가 과열됐는지 생각이 많은지 문제가 잘 풀리지 않는다.근데 솔직히 70퍼센트는 이해가 되는데, 그 이상 이해가 안된다... 해당문제는 다른 문제를 풀어보다가 다시 한번 풀어볼 예정이다. 머리가 과열됐는지 생각이 많은지 문제가 잘 풀리지 않는다.
4번 (2470) 두 용액
https://www.acmicpc.net/problem/2470
값을 비교해서 절대값 쓰워서 제일 작은 값에 해당하는 두 용액을 뽑으면 된다. 하나 값을 잡고 나머지와의 차이를 비교한다. 만약 사이클 한 번 돌리면 전체적인 차를 알 수 있기 때문에 전체적인 차를 알 수 있지 않을까?(절대값은 씌어야한다) 근데, 이렇게하면 시도 횟수가 증가하여 시간 초과가 걸린다. 그러므로 투 포인터 알고리즘을 써야한다. 투포인터는 정해진 합의 조합 수를 찾는 알고리즘이다. 투포인터에 관련되서 https://butter-shower.tistory.com/226 해당 블로그의 글이 제일 정리가 잘되어있는 것 같다. 그림을 보면서 이해하면 편하다.
# n만큼 용액 값 받고 재정렬
n = int(input())
L = list(map(int, input().split())) # 용액들의 리스트
L.sort()
left, right = 0, n-1 # 포인터 초기화
best_sum = float('inf') # 두용액의 최적의 합을 구한다(최솟값을 찾을때 유용하다, 범위는 무한대)
best_pair = (L[left], L[right]) # 최적의 두 값
# 투 포인터를 탐색한다.
while left < right:
current_sum = L[left] + L[right] # 현재 합 비교
# 두 용액의 차이가 더 적으면 갱신
if abs(current_sum) < abs(best_sum): # 두 용액의 차이를 현재와 예전값 비교해서 더 작으면
best_sum = current_sum # 갱신한다
best_pair =(L[left], L[right]) # 최고의 조합 두 값이다.
# 투 포인터를 이동시킨다.(조합 조사를 위해)
# 양쪽에서 시작해서 합이 음수다? 왼쪽 기준 인덱스 0이 1로 이동해서 합을 구하고
# 그 합이랑 전에 있던 합이랑 절댓값으로 비교해서 최적합으로 저장한다.
# 양수일 때도 반대로 생각하면된다.
if current_sum < 0: # 합이 음수일시, 값을 증가시켜야함
left += 1 # 투포인터 이론에 따라 이동
elif current_sum > 0: #합이 양수일시, 값을 감소시켜야함
right -= 1 # 투포인터 이론에 따라 이동
else: # sum == 0이면 정답으로 즉시 종료
break
# 정답 출력
print(best_pair[0], best_pair[1])확실히 이번 문제는 팀원분의 설명을 어제 들어서 이해가 잘되었다. 팀별 발표를 하는 것이 확실히 도움이 되었다. 앞으로도 적극 참여해야겠다. 첨엔 맨위에 말한것처럼 조합 다 보면서 차이 뽑아서 절댓값으로 min으로 차이 적은걸 뽑으면 되는게 아닌가? 했는데 찾아보니 그러면 연산이 복잡도 N^2로 100억이라 한다. 투 포인터를 사용하면 N log N으로 170만 연산만 하면 결과가 나와서 시간초과가 걸리지 않는다. 이렇게 투포인터로 구현하는 방법을 익혔다.
5번을 풀기위해선 DP라는 개념을 아는 것이 좋다. 사실 이진탐색으로 풀어볼 예정이지만 DP도 이번 기회에 알아보는 것도 좋으니 DP에 대해 써보았다.
DP란 무엇인가?
5번 문제는 쉽게 풀려면 다이나믹 프로그래밍(DP)을 사용해서 풀어야한다. 내가 아는 DP는 DisplayPort밖에 모르는데, 좀 생소한 단어이다. 유튜브나 서적을 통해 공부를 한 후 다시 풀어 보겠다.
DP라는 것은 1차적으로 계산한 값을 저장해두고 다음 중복계산시에 불러와서 불필요한 계산을 줄이는 방식입니다. 기억하기 알고리즘이라고도 하며 컴퓨터의 메모리를 효율적으로 사용하여 중복연산을 줄이고 수행속도를 빠르게 하는 방법입니다.
DP를 쓸지 고려하는 경우
- DFS/BFS로 풀수는 있지만 경우의 수가 너무 많은 문제
- 경우의 수들에 중복적인 연산이 많은 경우
DP와 관련된 문제는 30분정도 뒤돌아 가지 않을 방법을 고민하다가, 답이 나오지 않으면 풀이를 보고 본인의 코드를 다시 짜보는 것이 도움이 된다.
