백준 알고리즘에서 제공되는 문제들 중 단계별로 문제 풀기 - 이분 탐색 1번~7번을 파이썬으로 풀어보았다. 이분 탐색
7문제 모두 깃허브에 올려놓았다.
이분 탐색 단계
흔히 parametric search라고도 부르는, 이분 탐색을 응용하여 최솟값이나 최댓값을 찾는 테크닉을 배우는 문제
www.acmicpc.net
tomy9729/Algorithm
🐗 내가 직접 작성한 내 코드 🐗. Contribute to tomy9729/Algorithm development by creating an account on GitHub.
github.com
0. 이분 탐색
이분 탐색이란 검색 알고리즘으로 탐색 범위를 절반으로 줄여가면 목표를 탐색하는 알고리즘이다. 범위를 절반으로 계속 나눠가면 탐색하기 때문에 시간 복잡도가 O(log n)으로 일반적으로 모든 범위를 하나씩 탐색하는 알고리즘보다 빠르다. 단, 이분 탐색을 배열이 오름차순 또는 내림차순으로 정렬되어있어야만 사용이 가능하다.
탐색 과정은 다음과 같다.
- left, right 또는 start, end로 배열의 처음과 끝을 설정하고 두 수의 중간값인 mid와 목표 값을 비교한다.
- 만약 목표 값이 mid보다 크다면 mid보다 큰 수들에 대해서 다시 탐색하기 위해 left를 mid+1로 바꾼다.
- 만약 목표 값이 mid보다 작다면 mid보다 작은 수들에 대해서 다시 탐색하기 위해 right를 mid-1로 바꾼다.
- 위 과정을 start가 end보다 같거나 클 때까지 반복한다.
이때 left와 right를 옮기는 작업은 문제에 따라 특정 조건이 추가된다. 탐색 과정의 조건을 정확히 정의하는 게 이분 탐색의 핵심이다.
1. 1920번 수 찾기
문제
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
배열에서 어떤 수가 존재하는 지를 확인하는 문제이다. 모든 배열을 돌아가면 확인할 수도 있겠지만 시간이 너무 오래 걸리니 이분 탐색을 통해 확인해본다.
bin_search는 이분 탐색을 하는 함수이며 N개의 정수 nums와 찾고자 하는 값 num을 인자로 갖는다. 이분 탐색을 위해 nums는 오름차순으로 정렬된 배열이어야 하며 bin_search함수에 넘겨주기 전에 정렬을 수행한다. left와 right를 배열의 양 끝 값으로 저장하고 그 중간값이 mid를 선언한다. mid와 num을 비교하며, num이 더 크다면 left에 mid+1을 저장하고, mid가 더 크다면 right에 mid-1을 저장하며 이 과정을 반복하여 이분 탐색을 진행한다. 만약 두 조건을 다 만족하지 않는다면 num을 찾았거나, num이 존재하지 않는다는 뜻이므로 반복문을 종료한다.
최종적으로 도착한 mid값을 확인하여 num과 비교한다. num이라면 1을 반환하고 num이 아니라면 num이 존재하지 않는다는 의미이므로 0을 반환한다.
#1920번 수 찾기
def bin_search(nums, num) : #이분탐색 리스트 nums, 찾고자 하는 값 num
left = 0 # 가장 왼쪽
right = len(nums)-1 # 가장 오른쪽
mid = (left + right)//2 # 왼쪽과 오른쪽의 중앙
while left <= right : # left > right인 동안 반복
if nums[mid] < num : # mid값이 num보다 작으면
left = mid+1 #left를 miod+1로
mid = (left + right)//2
elif nums[mid] > num : # mid값이 num보다 크면
right = mid-1 #right를 mid-1로
mid = (left + right)//2
else : # 위 두조건을 다 만족하지 못하면 반복문 종료
break
if nums[mid] == num :
return 1
else :
return 0
if __name__ == "__main__":
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
m = int(input())
b = list(map(int,input().split()))
for i in range(m) :
print(bin_search(a,b[i]))
2. 10816번 숫자 카드 2
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.
이 문제를 풀기 위해서 lower_bound와 upper_bound에 대해서 먼저 알아야 한다. 숫자 num이 존재할 때 lower_bound란 가장 먼저 나오는 num 이상인 수이며, upper_bound는 가장 먼저 나오는 num을 초과하는 수이다. 즉 정렬된 배열에 대해서 upper_bound에서 lower_bound를 빼면 num의 개수를 구할 수 있다. 그리고 lower_bound와 upper_bound는 이분 탐색을 통해 구할 수 있다.
앞서 이분 탐색을 구현할 때 특정 조건을 언급했다. lower_bound에서 특정 조건은 "num 이상"이다. 만약 mid 값이 num 이상이라면 mid는 lower_bound가 될 수 있는 후보기 때문에 end를 mid로 바꿔서 다시 탐색한다. upper_bound에서 특정 조건은 "num 초과"이다. 만약 mid가 num을 초과한다면 mid는 upper_bound가 될 수 있는 후보기 때문에 end를 mid로 바꿔서 다시 탐색한다. 이를 통해 각 함수를 아래 코드와 같이 구현할 수 있다.
추가로 배열에서 가장 큰 숫자에 대해서는 해당 숫자를 초과하는 숫자가 없기 때문에 upper_bound를 사용해도 해당 숫자의 마지막 index가 반환된다. 문제에서는 정확한 개수를 물어보기 때문에 1만큼 더해준다.
#10816번 숫자 카드2
#import sys
#input = sys.stdin.readline
def lower_bound(nums, num) : # 가장 먼저 나오는 num 이상인 수
start = 0
end = len(nums)-1
while end > start : # end가 start와 같거나 작으면 종료
mid = (start+end)//2
if nums[mid] >= num : # 중앙값이 num보다 같거나 크면
end = mid # end를 mid로
else : # 중앙값이 num보다 작으면
start = mid + 1 #start를 mid+1로
return end
def upped_bound(nums, num) : # 가장 먼저 나오는 num 초과인 수
start = 0
end = len(nums)-1
while end > start :
mid = (start+end)//2
if nums[mid] > num :
end = mid
else :
start = mid + 1
return end
if __name__ == "__main__":
n = int(input())
card = list(map(int, input().split()))
card = sorted(card)
m = int(input())
check_card = list(map(int, input().split()))
for i in range(m) :
count = upped_bound(card,check_card[i])-lower_bound(card,check_card[i])
if check_card[i] == card[n-1] : # 가장 큰 값이 배열 끝에 있는 경우 upperbound는 실제값보다 1작게 나온다. 배열의 크기보다 커질수 없기 때문
count += 1
print(count,end=' ')
3. 1654번 랜선 자르기
문제
집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.
이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
이분 탐색의 핵심은 특정 조건을 정의하는 것이다. 구해야 하는 것은 N개를 만들 수 있는 랜선의 최대 길이이며 만들어지는 랜선의 개수는 N보다 같거나 커야한다. N이 커질수록 랜선의 개수는 작아질 것이며, N이 작을수록 랜선의 개수는 많아질 것이다.
랜선의 최소 길이는 1이며 최대 길이는 K개의 랜선 중 가장 큰 랜선의 길이다. 그러므로 start는 1, end는 K개의 랜선 중 가장 큰 랜선의 길이로 설정한다. mid를 K개의 랜선에 대해서 나눈 몫의 합을 구해서, 자르는 랜선의 길이가 mid일 때 생기는 랜선의 개수 len_count를 구할 수 있다. 만약 len_count이 n보다 같거나 크다면, mid보다 더 큰 값이 최대 랜선의 길이가 될 수 있으므로 확인해봐야한다. start를 mid+1로 바꿔서 다시 탐색한다. 만약 len_count이 n보다 작다면 랜선의 개수를 늘리기 위해 mid의 크기를 줄여야 한다. mid를 줄이기 위해 end를 mid-1로 바꾼다.
#1654번 랜선 자르기
def find_cm(nums, n) : # 정수 찾기
start = 1
end = max(nums)
mid = (start + end)//2
while start <= end :
len_count = sum([nums[i]//mid for i in range(len(nums))])
if len_count >= n : # 찾고자 하는 값의 조건 : n보다 같거나 커야한다. 랜선의 길이가 최대가 되야하므로 mid 값을 올린다.
start = mid + 1
else : # len_count < n 이라면 n보다 크게 만들기 위해 mid 값을 내린다.
end = mid - 1
mid = (start + end)//2 # 위 조건에 맞춰 mid 재설정
return mid
if __name__ == "__main__":
k, n = map(int,input().split())
lan = []
for i in range(k) :
lan.append(int(input()))
print(find_cm(lan,n))
4. 2805번 나무 자르기
문제
상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재 절단기를 이용해서 나무를 구할 것이다.
목재 절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.
상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.
마찬가지로 특정 조건을 먼저 정의한다. 구하고자 하는 나무의 높이는 반드시 M미터를 넘어야 하며, 절단기에 설정할 수 있는 높이의 최댓값을 구해야 한다. 절단기에 설정하는 높이를 크게 할수록 가져갈 수 있는 나무는 줄어들며, 작게 할수록 가져갈 수 있는 나무는 길어진다. 나무는 필요한 만큼만 가져가기 위해 추가적으로 잘리는 나무는 최소화해야 한다.
start는 나무의 최소 길이인 1, end는 나무의 최대 길이인 나무 중에서 가장 큰 나무의 길이로 설정한다. mid는 절단기에 설정하는 높이이다. mid에 대해서 가져갈 수 있는 나무의 길이 log_len을 구한다. 만약 log_len이 m보다 같거나 크다면 절단기에 설정하는 높이를 더 키우기 위해 start를 mid+1로 바꾼다. 만약 log_len이 m보다 작다면 절단기에 설정하는 높이를 줄이기 위해 end를 mid-1로 바꾼다.
#2805번 나무 자르기
def H(tree, m) : # H의 최댓값 구하기
start = 1 #최소 높이
end = max(tree) #최대 높이
mid = (start + end)//2
while start <= end :
log_len = 0 # 현재 잘라서 얻을 수 있는 나무의 길이 합
for i in tree :
if i > mid :
log_len += i-mid
if log_len >= m : # 길이 합이 m보다 같거나 크면
start = mid + 1 # start를 높여서 H의 길이가 더 높도록 한다.
else :
end = mid - 1
mid = (start+end)//2
return mid
if __name__ == "__main__":
n, m = map(int,input().split())
tree = list(map(int,input().split()))
print(H(tree,m))
5. 2110번 공유기 설치
문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러 개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
구하고자 하는 것은 가장 인접한 두 공유기 사이의 거리의 최댓값이다. C개의 공유기를 전부 설치해야 하며 공유기끼리 가능한 멀리 설치해야 한다.
start는 공유기가 설치될 수 있는 가장 인접한 거리 1로 설정했으며 end는 가장 먼 두 집의 거리로 설정했다. 배열 internet은 공유기가 설치되는 집의 위치를 저장하며 크기는 공유기의 개수와 같다. 첫 집에는 항상 공유기를 설치한다. 현재 두 공유기 사이의 거리인 mid에 대해, 이 전에 공유기를 설치한 집과 현재 집까지의 거리가 mid보다 크다면 공유기를 설치하고 그렇지 않다면 다음 집으로 넘어간다. 만약 모든 공유기가 설치가 가능하면 mid보다 더 큰 "가장 인접한 공유기의 거리"가 존재할 수 있으므로 start를 mid+1로 바꿔 다시 탐색한다. 만약 모든 공유기가 설치가 되지 않았다면 mid를 줄여서 모든 공유기가 설치 가능하도록 해야 하므로 end를 mid-1로 바꾼다.
#2110번 공유기 설치
def internet_distance(x, c) :
start = 1 #최소 거리
end = x[-1]-x[0] #최대 거리
mid = (start + end)//2
while start <= end :
internet = [-1]*c # 설치할 공유기의 위치를 저장
internet[0] = x[0] # 첫 공유기는 항상 첫번째 집에 설치
x_index = 1
for i in range(c)[1:] :
while True :
if x_index >= len(x) :
break
if x[x_index] - internet[i-1] >= mid : # 다음으로 설치할 집의 위치부터 그 전집까지의 위치가 mid보다 크면
internet[i] = x[x_index] # 공유기 설치
break
else :
x_index += 1
if -1 not in internet : # 공유기를 모두 설치 했다면
start = mid + 1 # 더큰 "가장 인접한 공유기의 거리"가 있을 수 있으므로 mid를 크게 한다.
else :
end = mid - 1
mid = (start+end)//2
return mid
if __name__ == "__main__":
n, c = map(int, input().split())
x = []
for i in range(n):
x.append(int(input()))
x.sort()
if c == 2 :
print(x[-1]-x[0])
else :
print(internet_distance(x,c))
6. 1300번 K번째 수
문제
세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자.
배열 A와 B의 인덱스는 1부터 시작한다.
start는 행렬의 최솟값 1, end는 행렬의 최댓값 n*n으로 설정한다. 행렬에서 mid보다 같거나 작은 값의 수 count를 구해서 만약 count가 k보다 작으면 B[k]에 도달하기 위해 count의 크기를 키워줘야 하므로 start를 mid+1로 바꾼다. 만약 count가 k보다 크다면 count의 크기를 줄여줘 하므로 end를 mid-1로 바꾼다.
여기서 count를 구하는 다양한 방법이 있는데 가장 쉬운 방법은 모든 행렬을 돌아가며 세는 것이다. 단 이 방법으로는 시간 복잡도가 O(N^2)가 걸리기 때문에 시간 제약에 걸린다. 다음 방법을 통해 시간 복잡도를 줄일 수 있다.
- 각 행의 마지막 열과 mid를 비교한다.
- mid가 더 크다면 count에 열의 크기만큼 추가한다.
- mid가 더 작다면 count에 "mid에 행을 나눈 몫"을 추가한다.
#1300번 K번째 수
def num_k(n, k) :
start = 1
end = n*n
mid = (start + end)//2
while start <= end :
count = 0
for i in range(1,n+1) :
if i*n <= mid :
count += n
else :
count += mid//i
if count < k :
start = mid + 1
else :
end = mid - 1
mid = (start+end)//2
return start
if __name__ == "__main__":
n = int(input())
k = int(input())
b = [0]
print(num_k(n,k))
7. 12015번 가장 긴 증가하는 부분 수열 2
문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
문제에서 요구하는 답은 LIS의 길이일 뿐 LIS 자체가 아니다. 그러므로 이분 탐색을 통해 LIS의 길이를 구할 수 있다. 정답 배열 result와 수열 A에 대해서 A를 돌며 result의 마지막 값보다 큰 수가 나오면 result에 추가하고, 작은 값이 나오면 result에서 lower_bound를 찾아 대체하여 LIS의 길이를 구할 수 있다. 단 정확한 LIS를 구하기 위해서는 다른 방법이 필요하다.
#12015번 가장 긴 증가하는 부분 수열 2
def lower_bound(nums, num) : # 가장 먼저 나오는 num 이상인 수
start = 0
end = len(nums)-1
while end > start :
mid = (start+end)//2
if nums[mid] >= num :
end = mid
else :
start = mid + 1
return end
if __name__ == "__main__":
n = int(input())
a = list(map(int,input().split()))
result = []
result.append(a[0])
for i in range(1,n) :
if result[-1] < a[i] :
result.append(a[i]) # result의 최댓값보다 크면 추가
else : # 같거나 작으면
result[lower_bound(result,a[i])] = a[i] # result의 해당 값을 a[i]로 대체
print(len(result))'Problem Solving > 백준BOJ' 카테고리의 다른 글
| [백준BOJ] 1259번 팰린드롬수.py (0) | 2021.04.26 |
|---|---|
| [백준BOJ] 단계별로 문제풀기 - 우선 순위 큐 정답 및 후기(파이썬, python) (0) | 2021.04.26 |
| [백준BOJ] 단계별로 문제풀기 - 분할 정복 정답 및 후기(파이썬, python) (0) | 2021.04.09 |
| [백준BOJ] 단계별로 문제풀기 - 큐, 덱 정답 및 후기(파이썬, python) (0) | 2021.03.17 |
| [백준BOJ] 단계별로 문제풀기 - 스택 정답 및 후기(파이썬, python) (2) | 2021.03.08 |
