🧨 알고리즘 문제풀이에서 이진 탐색을 어떨 때 사용하냐면, 결정 알고리즘이라는 방법론에서 사용한다 !
결정 알고리즘으로 풀 수 있는 문제들은 특징들이 있다.
-
찾고자 하는 답이 특정 범위 안에 있다는 것을 바로 알 수가 있게 나온다.(A~B 사이에 답이 있다는 것을 바로 알 수가 있다.) 거기서 답을 정해놓고 그 범위 내에 있는 어떤 특정 숫자를 정해놓고(답으로써 정해놓음) 이제 이진 탐색을 쓰는 것이다 !
-
그 답이 답으로써 유효한가, 유효하지 않은가를 생각하는 것이다 !! (이걸 확인하는 함수를 만들어서 확인하는 작업을 시행한다.) 답으로써 유효하다면 범위를 좁히는거야.
-
절반은 날리고 그 절반 중에서 이 답보다 더 좋은 답을 찾아서 좁혀 나가는거야
🎈 랜선자르기 문제를 예를 들어서 문제를 확인할 수 있다 !!
🎈 랜선자르기(결정알고리즘)
엘리트 학원은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이
다. 선생님은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을
잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면
20cm 은 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
편의를 위해 랜선을 자를때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의
랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수
길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때
만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
▣ 입력설명
첫째 줄에는 엘리트학원이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이
입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고
항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의
이하의 자연수로 주어진다.
▣ 출력설명
첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.
▣ 입력예제 1
4 11
802
743
457
539
▣ 출력예제 1
200
길이가 같은 N개의 랜선으로 만들고 싶다. K개의 랜선을 잘라서 만들기 !
🎈 이 문제는 한 랜선의 최대 길이 !!!!
결국 문제에서 11개의 주어진 4개의 랜선으로 11개의 랜선을 만들건데, 11개의 랜선의 각각 1개의 랜선의 길이를 최대로 하면 몇인가.를 묻고 있다.
일단 찾고자 하는 1개 랜선 길이는 4개의 랜선 길이 중 최대값보다 작을 것이다. 결국 ! 802보다는 작고 1보다는 크다는 범위가 나온다 (1<x<802)
- 설명을 위해 (1<x<1000)이라고 생각해보자. 이제 중간값 500을 N개의 랜선의 한개의 길이로 했을 때 답이 되는가를 확인해.
🎈 K개의 랜선에 500으로 나눠서 개수를 세보면 돼 그렇게 하면 총 3개밖에 안된다. 이 답은 답으로써 유효하지 않으므로 500보다 큰 쪽의 범위는 버려 ! (길이가 길어지면 당연히 개수가 더 적어질거 아니야)
이제 1~499로 답의 범위를 좁히고 다시 시작.
- 250이 답으로써 유효한가를 다시 확인하는거야 !!
🎈 역시 N개의 개수보다 모자라. 그렇다면 더 줄여야지. 1~249로 답의 범위를 좁혀나가서 다시 중간값으로 답으로써 유효한가를 판단.
- 이렇게 하면 K개의 랜선으로부터 18개. 11개는 당연히 만들 수 있다. 답으로써 유효하다.(남는걸 버리더라도) 그래도 최대 길이를 구하는 것이기에 125보다 큰 값도 검사해보는거야
🎈 125~249까지를 답의 범위로 좁혀서 다시 중간값 187이 답으로써 유효한가 판단.
- 4개의 랜선으로부터 11개를 만든다. 이렇게 되면 187도 답이 될 수 있어!! 근데 한개 랜선의 최대 길이를 구하는 것이기에 187이 더 크니까 이 답이 더 유효!
🎈 이제 다시 188~249를 답의 범위로 좁혀서 중간값을 계산해보자.
정리
결국 ! 이렇게 이진탐색을 계속 해 나가면서 이진탐색이 끝날 때까지 해나가면 가장 좋은 답이 마지막에 나올꺼야! 그걸 답으로 채택화면 돼
- 이 문제의 경우 이진 탐색으로 가질 수 있는 값의 최대를 구하는거잖아.
그래서 값이 적어서 개수가 더 많아지더라도 답의 유효한 범위에 드는거야
import sys
# sys.stdin = open("input.text", "rt")
K, N = map(int, input().split())
data = []
for i in range(K):
data.append(int(input()))
res = -242424242424 #최대값 저장
start = 1
end = max(data) -1
while start <= end:
mid = (start + end) // 2 #한개 랜선의 길이가 mid값이라는거
cnt = 0
for i in range(K):
cnt += data[i] // mid
if cnt >= N: #답의 범위
#답으로써 유효하니 저장한 후에 더 좁혀나가 봐야함.
res = mid
start = mid + 1
else:
end = mid -1
print(res)뮤직비디오(결정알고리즘)
지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다.
DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지
되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번
노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야
한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.
지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는
DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기
로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의 DVD는
모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.
▣ 입력설명
첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다. 다음 줄에는 조영필이 라이브에서
부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다. 부른 곡의 길이는 10,000분을
넘지 않는다고 가정하자.
▣ 출력설명
첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요.
▣ 입력예제 1
9 3
1 2 3 4 5 6 7 8 9
▣ 출력예제 1
17
해당 문제의 경우에는 답의 범위 중 최솟값을 구하는거잖아.
import sys
# sys.stdin = open("input.text", "rt")
N, M = map(int, input().split())
data = list(map(int, input().split()))
start = 1
end = sum(data) #모든 노래가 하나의 DVD에 들어가는게 그 DVD의 최대 길이
def count_max(len): #해당 디비디 길이 들어왔을 때 만들 수 있는 디비디 개수
cnt = 1
sum_data = 0
for i in range(N):
if sum_data + data[i] <= len: #같아도 저장되잖아! 예외...
sum_data += data[i]
else:
cnt += 1
sum_data = data[i]
return cnt
res = 24242424242424
while start <= end:
mid = (start + end) // 2 #최소용량
if count_max(mid) <= M: #M보다 작아도 저장되는건 M으로도 되는거잖아
res = mid #용량의 최소를 찾는 것이기에 더 좋은 답이 없는지 유효성 검사 해야지
end = mid -1
else: #용량이 너무 작아서 M보다 더 필요한거야 답의 범위가 유효하지 않음
start = mid + 1
print(res)그렇기에 해당 코드처럼 최솟값의 값이 커서 만들 수 있는 개수가 M개보다 작더라도 답의 유효한 범위에 들어가는거야. (2개로 만들 수 있다면 3개로도 당연히 만들 수 있잖아)
결국 !! 결정 알고리즘을 통해 문제를 풀 때 이진탐색으로 문제를 풀 때 찾고자 하는 값이 최솟값인지 최댓값인지를 통해 어떤 범위를 설정해야 할 지 고민하면 될 것이다 !! 😁😀
값의 유효한 범위에 들어가는 특수한 경우에 조건 if를 걸자. 그럼 코드를 해석하기 쉬워진다.
