2021 하계 모각코 2주차 목표와 회고

11 Jul 2021

Reading time ~2 minutes

2주차 (07월 11일)

목표

알고리즘 < 이진탐색 > 문제풀기 (백준 10816번, 백준 1654번, 백준 2110번, 백준 1300번)

회고

알고리즘 < 이진탐색 > 문제 : 백준 10816번(“숫자카드2”) -> 난이도 : 실버4

해결 방법 : bisect_left와 bisect_right의 차이를 이용해서 정렬된 리스트에 해당하는 숫자가 몇개인지 찾을 수 있다.

코드일부

result = []
N = int(input())

card = list(map(int, sys.stdin.readline().rstrip().split()))
card.sort()

M = int(input())

number = list(map(int, sys.stdin.readline().rstrip().split()))

for i in range(M):
    count = bisect_right(card, number[i]) - bisect_left(card, number[i])
    result.append(count)

for i in result:
    print(i, end=' ')

알고리즘 < 이진탐색 > 문제 : 백준 1654번(“랜선 자르기”) -> 난이도 : 실버3

해결 방법 : 이진탐색을 사용해서 1과 이미 갖고있는 랜선의 최대길이 중 필요한 랜선의 개수보다 같거나 더 많이 만들 수 있는 길이를 찾는다.

코드일부

lan.sort()

left = 1
right = max(lan)
result = 0

while left <= right:
    mid = (left + right) // 2
    count = 0

    for i in range(K):
        count += (lan[i] // mid)

    if count < N:
        right = mid - 1
    else:
        result = mid
        left = mid + 1

알고리즘 < 이진탐색 > 문제 : 백준 2110번(“공유기 설치”) -> 난이도 : 실버1

해결 방법 : 이진탐색을 할 때 공유기 사이의 거리를 사용해서 탐색한다. 처음에 left는 1로 right는 집 사이의 최대거리로 초기화 한다. 그런 후에 집 사이의 거리가 mid 값 보다 크다면 공유기를 설치한다. 공유기를 모두 설치 한 후에 원래 설치하려던 C보다 적게 설치했다면 right를 mid - 1로 범위를 바꿔주고, C보다 같거나 많이 설치 했다면 left를 mid + 1로 범위를 바꿔준다.

코드일부

home.sort()

left = 1
right = max(home) - min(home)
result = []

while left <= right:
    mid = (left + right) // 2

    check = min(home)
    count = 1

    for i in range(1, len(home)):
        if home[i] >= check + mid:
            count += 1
            check = home[i]

    if count < C:
        right = mid - 1
    else:
        result = mid
        left = mid + 1

print(result)

2021 하계 모각코