위 링크에서 이진탐색(Binary Search) 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다.
7. 이진탐색(Binary Search)
- 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
- 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
- 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.
- 시간복잡도는 logN이다. 단계마다 탐색 범위를 반으로(÷2) 나누는 것과 동일하므로 위 시간 복잡도를 가지게 된다.
- Python에서는 bisect라는 이진 탐색 라이브러리(모듈)을 지원한다.
기본 코드 예
재귀로 구현한 코드
# 재귀 함수로 구현한 이진 탐색
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
# 원하는 값 찾은 경우 인덱스 반환
if array[mid] == target:
return mid
# 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
elif array[mid] > target:
return binary_search(array, target, start, mid - 1)
# 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
else:
return binary_search(array, target, mid + 1, end)
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))
result = binary_search(array, target, 0, n - 1)
if result is None:
print('원소가 존재 X')
else:
print(result + 1)
반복문으로 구현한 코드
# 반복문으로 구현한 이진 탐색
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
# 원하는 값 찾은 경우 인덱스 반환
if array[mid] == target:
return mid
# 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
elif array[mid] > target:
end = mid - 1
# 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
else:
start = mid + 1
return None
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))
result = binary_search(array, target, 0, n - 1)
if result is None:
print('원소가 존재 X')
else:
print(result + 1)
bisect 사용법
bisect_left(arr, n) : 제일 왼쪽에서 n이 들어갈 수 있는 인덱스 반환
bisect_right(arr, n): 제일 오른쪽에서 n이 들어갈 수 있는 인덱스 반환
from bisect import bisect_left, bisect_right
nums = [0, 1, 2, 2, 2, 5, 5, 5, 5, 5, 5, 6]
print(bisect_left(nums, 2)) => 2출력
print(bisect_right(nums, 2)) => 5출력
문제
(❌ 표시는 혼자 못푼 문제)
2023. 12. 12. 7일차 (1)
❌ 1. 2512번 예산 (실버2) 문제링크
문제 해석
여러 지방의 예산 요청을 심사하여 국가의 예산을 분배할 것이다.
정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.
1. 모든 요청이 배정될 수 있는 경우 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우 특정한 정수 상한액을 계산하여 그 이상인 예산 요청에는 모든 상한액을 배정한다. 상한액 이하의 예산 요청에 대해서는 요청한 금액을 그대로 배정한다.
여러 지방의 예산 요청과 국가 예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.
제한: 1초 128MB
입력
첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.
출력
첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.
참고: https://chanmuzi.tistory.com/237?category=999363
코드
import sys
def _input():
return sys.stdin.readline().strip()
N = int(_input())
arr = list(map(int, _input().split()))
M = int(_input())
result = 0
start, end = 0, max(arr)
while start <= end:
mid = (start + end) // 2
# mid를 상한선으로 했을 때 사용되는 전체 예산
totalCost = 0
for v in arr:
if mid > v:
totalCost += v
else:
totalCost += mid
# 예산을 초과할 경우
if totalCost > M:
end = mid - 1
# 예산 보다 적거나 예산과 동일할 경우
else:
result = mid
start = mid + 1
print(result)
이 문제에서 놓쳤던 것
* min 값이 0 이라는 생각을 하지 못했다. 국가의 예산 요청 중 가장 작은 값이 이분탐색을 시작할 때의 min 이라고 생각했다.
* 국가 계산이 적으면 모든 국가의 예산 요청을 충족할 수 없을 수도 있다는 것을 생각하지 못했다.
* 이분탐색을 위해 sort를 하지 않고 max() 값만 얻어냈어도 됐던 문제였다.
* 그래도 문제 풀이방식은 적절하게 접근했다...
* 1시간 걸려서 못풀어서 풀이를 봤다.
배울 코드
start -1 만으로도 답이 될 수 있다.
마지막까지 결과를 충족한 mid 값을 출력하는 것이다.
import sys
input = sys.stdin.readline
N = int(input())
cities = list(map(int, input().split()))
budgets = int(input()) # 예산
start, end = 0, max(cities) # 시작 점, 끝 점
# 이분 탐색
while start <= end:
mid = (start+end) // 2
total = 0 # 총 지출 양
for i in cities:
if i > mid:
total += mid
else:
total += i
if total <= budgets: # 지출 양이 예산 보다 작으면
start = mid + 1
else: # 지출 양이 예산 보다 크면
end = mid - 1
# 마지막까지 결과를충족한 mid의 -1
print(start-1)
2023. 12. 12. 7일차 (2)
2. 19637번 IF문 좀 대신 써줘 (실버3) 문제링크
문제 해석
게임 개발자인 밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다.
예를 들어, 전투력 10,000 이하의 캐릭터는 WEAK, 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL, 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호를 붙여준다고 하자. 혼자서 게임을 개발하느라 매우 바쁜 밀리를 대신해서, 캐릭터의 전투력에 맞는 칭호를 출력하는 프로그램을 작성하자.
제한: 1초 1024MB
입력
첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 10^5)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 10^5)이 빈칸을 사이에 두고 주어진다.
(1 ≤ N, M ≤ 10^5)
두 번째 줄부터 N개의 줄에 각 칭호의 이름을 나타내는 길이 1 이상, 11 이하의 영어 대문자로만 구성된 문자열과 해당 칭호의 전투력 상한값을 나타내는 109 이하의 음이 아닌 정수가 주어진다. 칭호는 전투력 상한값의 비내림차순으로 주어진다.
N + 2번째 줄부터 M개의 각 줄에는 캐릭터의 전투력을 나타내는 음이 아닌 정수가 주어진다. 해당하는 칭호가 없는 전투력은 입력으로 주어지지 않는다.
출력
M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.
코드 1
출력조건에서 "출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다." 의 의미는 같은 숫자 조건이 나왔을 때 앞에 것 칭호를 사용한다는 의미이다. 그렇기 때문에 총 칭호의 개수는 N이 아니라 중복 조건을 제외한 수라는 것에 유의해야한다.
852ms
import sys
def _input():
return sys.stdin.readline().strip()
N, M = map(int, _input().split())
value = [0]
name = [""]
newN = 0
for _ in range(N):
a, b = _input().split()
if len(value) == 1:
name.append(a)
value.append(int(b))
newN +=1
else:
if value[-1] != int(b):
name.append(a)
value.append(int(b))
newN +=1
N = newN # 중복 조건 제외한 개수로 업데이트
for _ in range(M):
target = int(_input())
start, end = 1, N
while start <= end:
mid = (start + end) // 2
# 원하는 값 찾은 경우 인덱스 반환
if value[mid-1] < target <= value[mid]:
result = mid
break
elif target <= value[mid-1]:
end = mid - 1
elif target > value[mid]:
start = mid + 1
print(name[mid])
코드 2 - bisect 이진탐색 라이브러리 사용해서 풀어보기
272ms
from bisect import bisect_left
import sys
def _input():
return sys.stdin.readline().strip()
name =[]
value =[]
N, M = map(int, _input().split())
for i in range(N):
a, b = _input().split()
if i > 0 and value[-1] == int(b):
continue
name.append(a)
value.append(int(b))
for _ in range(M):
target = int(_input())
result = bisect_left(value, target)
print(name[result])
이 문제의 포인트
* 파이썬으로 이진탐색을 구현할 때 bisect_left, right 라이브러리를 사용하도록 하자. 직접구현하는 것보다 속도도 빠르고 구현도쉽다.
2023. 12. 12. 8일차 (3)
3. 2805번 나무 자르기 (실버2) 문제링크
문제 해석
상근이는 나무 M미터가 필요하다. 한 줄에 연속해있는 나무를 자를 것이다.
상근이는 새로 구입한 목재 절단기로 나무를 구할 것이다.
절단기 동작방식은 다음과 같다.
- 높이H를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다.
- H보다 큰나무는 H위의 부분이 잘린다.
- 이때 H높이로잘라서 잘린 윗부분을 집에 들고간다.
상근이는 필요한 만큼만 집에 가져가려 한다.
적어도 M미터의 나무를 집에 가져가기위해 절단기에 설정할 수 있는 높이의 최댓값을 구하여라.
제한: 1초 256MB
입력
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.
출력
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
코드
4864ms
import sys
def _input():
return sys.stdin.readline().strip()
N, M = map(int, _input().split())
arr = list(map(int, _input().split()))
result = []
start, end = 0, max(arr)
while start <= end:
mid = (start + end) // 2
# mid를 상한선으로 했을 때 사용되는 전체 예산
total = 0
for v in arr:
if mid < v:
total += (v-mid)
# 가져갈 나무 이상의 길이 인경우
if total >= M:
result.append([total, mid])
start = mid + 1
# 가져갈 나무 보다 적을 경우
else:
end = mid - 1
result.sort(key=lambda x: x[0])
print(result[0][1])
배울 코드
나는 만족하는 값을 찾기위해 sort까지 했지만
아래코드를 보면 start -1 만으로도 답이 될 수 있다.
마지막까지 total>=M을 만족했던 mid 값이 start 값일 것이다.
import sys
def _input():
return sys.stdin.readline().strip()
N, M = map(int, _input().split())
arr = list(map(int, _input().split()))
result = []
start, end = 1, 1000000000
while start <= end:
mid = (start + end) // 2
# mid를 상한선으로 했을 때 사용되는 전체 예산
total = 0
for v in arr:
if mid < v:
total += (v-mid)
# 가져갈 나무 이상의 길이 인경우
if total >= M:
start = mid + 1
# 가져갈 나무 보다 적을 경우
else:
end = mid - 1
print(start-1)2023. 12. 12. 9일차 (4)
❌ 4. 6236번 용돈 관리 (실버2) 문제링크
문제 해석
용돈을 효율적으로 활용하기 위해 계획을 짜기로 했다.
앞으로 N일 동안 자신이 사용할 금액을 계산했고
돈을 펑펑쓰지 않기 위해 M번만 통장에서 돈을 빼서 쓰기로 한다.
통장에서 K원을 인출한다. 뺀돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 다시 집어넣고 다시 K를 인출한다.
돈을 아끼기 위해 금액K를 최소화 하기로 하였다.
현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.
제한: 1초 128MB
입력
1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)
2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)
출력
첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.
이해 실패 ㅠ
못풀었다 ㅠㅠ 풀이가 이해가 가질않는다.
의문 - 뺀돈으로 하루를 보낼 수 있으면 그대로 사용하고 모자라면 남은 금액은 통장에 다시 집어넣고 다시 K를 인출한다고 되어있는데. 하루에 K를 두번 인출하는 경우는 없는건가....? 모든 풀이에서는 돈이 부족하면 인출하는 횟수를 한번만 추가한다. 왜그럴까?
코드
#2023. 12. 12. 10일차 (5)
5. 1654번 랜선 자르기 (실버2) 문제링크
문제 해석
박성원은 캠프때 슬 랜선 N개를 만들어야 한다.
오영식은 자체적으로 K개의 랜선을 가지고 있다.
그러나 K개의 랜선은 길이가 제각각이다.
박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다.
ex) 300cm 짜리 랜선에서 140짜리 랜선 2개를 잘라내면 20cm는 버려야 한다.(이미 자른 랜선은 붙일 수 없다.)
기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다.
자를 때는 항상 센티미터 단위로 정수 길이 만큼 자른다고 가정한다.
N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.
이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
제한: 2초 128MB
입력
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.
출력
첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.
직접 푼 코드
K는 1이상이기 때문에 랜선 하나는 나오기 때문에 start 값 은 1
가지고 있는 랜선의 가장 긴 길이 만큼 자를 수도 있기 때문에 end 값은 max(arr)
자르지 않더라도 N 길이보다 작으면 카운트되지 않는 다는것을 생각해야한다.
92ms
import sys
input = sys.stdin.readline
K, N = list(map(int, input().split()))
arr = []
for _ in range(K):
arr.append(int(input()))
start, end = 1, max(arr)
result = []
while start <= end:
mid = (start + end)//2
count = 0
for i in arr:
n = i//mid
count += n
if count < N:
end = mid - 1
else:
result.append(mid)
start = mid + 1
print(max(result))
내가 풀었지만 아직이해못하는 코드
답을 start 변수로 바로 참조하는 코드
풀이들을 보니까 이분탐색은 거의 답을 아래와 같은 방식으로 푼다.
이걸 이해해야 이분탐색을 잘 풀 수 있을 텐데.
이해는 못했지만 이렇게 푸니까 풀리긴한다.
100ms
import sys
input = sys.stdin.readline
K, N = list(map(int, input().split()))
arr = []
for _ in range(K):
arr.append(int(input()))
start, end = 1, max(arr)
while start <= end:
mid = (start + end)//2
count = 0
for i in arr:
n = i//mid
count += n
if count < N:
end = mid - 1
else:
start = mid + 1
print(start - 1) # 조건에 만족하는 mid 최대값이 start -1 에 들어가 있을 것이다.
6. 2343번 기타 레슨 (실버1) 문제링크
7. 2110번 공유기설치 (골드5) 문제링크
8. 2467번 용액 (골드5) 문제링크
9. 16434번 드래곤 앤 던전 (골드4) 문제링크
10. 15732번 도토리 숨기기 (골드2) 문제링크
11. 1300번 K번째 수 (골드2) 문제링크
12. 2632번 피자판매 (골드2) 문제링크
13. 15732번 도토리 숨기기 (골드2) 문제링크
14. 1450번 냅색문제 (골드1) 문제링크
'알고리즘 문제풀이' 카테고리의 다른 글
| 백트래킹 문제 및 풀이 (Python) (0) | 2023.12.04 |
|---|---|
| 문자열 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 구현 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 동적계획법(DP) 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 완전탐색(브루트포스) 문제 및 풀이 (Python) (0) | 2023.12.04 |