페어 프로그래밍

문제풀이

1. 공유기 설치

풀이

전체 코드

N, C = map(int, input().split())
lst = []

for _ in range(N):
    lst.append(int(input()))

lst.sort()

# 2. 이분탐색 대상은 '최대거리'.
# 최솟값은 1, 최댓값은 양 끝값의 차이.
lo = 1
hi = lst[-1] - lst[0]
min_gap = 0

# 3. 최대 거리를 찾을 때까지 이분탐색
while lo <= hi:
    # 중간 거리를 시험해본다.
    mid = (lo + hi) // 2

    # 0번째 요소에 항상 설치하므로 1개를 깔고 간다.
    cnt = 1
    # 0번째 요소부터 시작.
    cur = lst[0]

    # 1번째 ~ 마지막 요소를 연결시켜본다.
    for i in range(1, len(lst)):
        # 연결만 된다면 더 멀리 있는 것도 괜찮다
        # 이해가 안된다면 문제의 예시인
        # [1, 2, 4, 8, 9] 를 최대거리 3으로 연결하는 경우를 찬찬히 생각해보자.
        # (1, 4, 8)에 설치한 경우, 1~4 거리는 3, 4~8 거리는 4다.
        # 가장 인접한 두 점의 최대 거리가 3이므로 4가 괜찮은 것이다.
        if lst[i] >= cur + mid:
            cur = lst[i]
            cnt += 1

    if cnt >= C:
        min_gap = mid
        lo = mid + 1
    else:
        hi = mid - 1

print(min_gap)

2. k번째 수

풀이

전체 코드

import sys

input = sys.stdin.readline


N = int(input())
K = int(input())
	
left = 1           
right = N * N     # 9
	
while left <= right:
	mid = (left + right) // 2 # 5 -> 7 -> 6
		
	count = 0
	for i in range(1, N + 1): # 1~3
		count += min(mid // i, N) # 3+3+2
		
	if count >= K: 
		right = mid - 1 # 5
	else: 
		left = mid + 1 # 6
	
print(left)

3. 가장 긴 증가하는 부분 수열 2

풀이

전체 코드

N = int(input())

A = list(map(int, input().split()))[:N]

B = [0]

for i in A:
    if i > B[-1]:
        B.append(i)
    else:
        start = 0
        end = len(B)
        while start <= end:
            mid = (start + end) // 2
            if B[mid] < i:
                start = mid + 1
            else:
                end = mid - 1
        B[start] = i

print(len(B)-1)

4. 나무 자르기

풀이

전체 코드

def difference(lst, n):
    ret = 0
    for i in range(len(lst)):
        if lst[i] > n:
            ret += lst[i] - n
    return ret

N, M = map(int, input().split())
trees = list(map(int, input().split()))

trees.sort()

start = 0
end = trees[-1]

while start <= end:
    mid = (start + end) // 2

    if difference(trees, mid) >= M:
        start = mid + 1
    elif difference(trees, mid) < M:
        end = mid - 1

print(end)

후기

스스로 푼 문제는 마지막 문제인 나무 자르기 문제 뿐이었다.

이분 탐색 개념 자체는 큰 어려움 없이 이해가 되지만 알고리즘 문제들에 적용하는 게 익숙치가 않아서 많이 어려운 것 같다.

알고리즘 주차는 끝났지만 앞으로 재귀, 이분탐색, 동적 계획법은 하루에 한 문제씩이라도 풀어보는 게 좋을 것 같다.