문제
느낀점
어떻게 찾지..? 이런 생각에 막막해서 다른 분들의 코드를 참고했다. 일단 이진탐색을 이용하면 "쉽게" 풀린다는 부분만 보고 이진탐색 문제를 방금 풀었는데 적용할 생각이 안나다니..!! 하면서 역시 개념을 아는 건 문제를 봤을 때 직접 적용할 생각이 나기까지 해야 한다는 걸 뼈져리게 느꼈다.. 겨우 이틀을 투자해서 이진탐색을 마스터할 수 있을 거라 생각했던 게 얼마나 웃긴 생각이었는지. 공부는 꾸준히 해야 하는 것이다. 역시나. 너무 조급해하지 말자!! 오늘 안되면 내일 하면 되고, 오늘 이해 안되면 내일 이해하면 된다. 파이팅 나 자신!
cf. 오늘 풀은 이진탐색 문제
https://velog.io/@letsbebrave/백준-1920번-수-찾기
개념
이진탐색
원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘.
중요한 건 검색 대상인 배열이 오름차순이나 내림차순으로 배열되어 있어야만 한다는 것이다.
A.sort() # 검색 대상인 A 를 오름차순 정렬 (필수)
M = int(input())
B = list(map(int,input().split()))
def bin_search(A:Sequence, target:int) -> bool :
left = 0
right = N - 1
while left <= right: # left > right이면 검색범위가 더이상 없음
mid = (left + right) // 2 # 가운데 값은 계속 업데이트를 해줘야 함
if A[mid] == target :
return True
elif A[mid] < target :
left = mid + 1
else :
right = mid - 1
첫 코드 (최대 길이 X)
랜선의 최대 길이를 구해야 했는데, 이 부분을 어떻게 구현할지 잘 모르겠어서 제외하고 짰다. 예시로 주어진 출력은 잘 되길래 제출했는데 역시나 틀렸다.
from typing import Sequence
K, N = map(int,input().split())
n = []
for i in range(K) :
n.append(int(input()))
def sol(n: Sequence) -> int:
left = 1
right = max(n)
while left <= right:
mid = (left + right)//2
count = 0
for i in range(K):
count += n[i] // mid
if count == N : # mid가 최대값인지 모르는상태임
return mid
if count < N : right = mid - 1
if count > N : left = mid + 1
print(sol(n))두번째 코드 (결과가 안 나옴)
answer라는 리스트에 해당값들을 넣어두고 나중에 max를 출력하려고 했는데 어찌된 이유에선지 아무것도 출력되지 않는다. 왜 그런지 아직도 모르겠다.
from typing import Sequence
K, N = map(int,input().split())
n = []
for i in range(K) :
n.append(int(input()))
def sol(n: Sequence) -> int:
left = 1
right = max(n)
answer = []
while left <= right:
mid = (left + right)//2
count = 0
for i in range(K):
count += n[i] // mid
if count == N :
answer.append(mid)
if count < N : right = mid - 1
if count > N : left = mid + 1
return max(answer)
print(sol(n))정답 코드
어떻게 하면 랜선의 최대값을 구할 수 있느냐가 문제였다. 랜선의 갯수가 충족되어도 최댓값을 구할 때까지 계속 이진탐색을 진행해줘야 했다. 중요한 건 left <= right일 때만 이진탐색을 진행하며 count > N일 때만 left = mid+1을 해주는 게 아니라, count == N일 때도 left = mid+1을 해주고 while의 조건문인 left > right이 되면 while문을 더이상 진행하지 않게 하는 것이다. 최댓값을 꼭 max()로 구해야 하는 건아니다. count == mid일 때도 이진탐색을 계속 진행해주고, left <= right 조건일 때에만 반복이 진행되게 하면 자동으로 최댓값을 구할 수 있다.
이렇게 하다가 최댓값을 찾는다.
from typing import Sequence
K, N = map(int,input().split())
n = []
for i in range(K) :
n.append(int(input()))
def sol(n: Sequence) -> int:
left = 1
right = max(n)
answer = []
while left <= right:
mid = (left + right)//2
count = 0
for i in range(K):
count += n[i] // mid
#print("과정중",right, "count값",count,"left값",left,"right",right )
if count < N : right = mid - 1
if count >= N :
left = mid + 1
return mid
print(sol(n))22.04.12에 다시 풀어봄
틀림...ㅜ
오답 코드
import sys
K, N = map(int, sys.stdin.readline().split())
len = [int(sys.stdin.readline()) for i in range(K)]
def bsearch(target):
start = 1
end = max(len)
while start <= end:
mid = (start + end) // 2
num = 0
for i in len:
num += i // mid
if num < target:
end = mid - 1
elif num >= target:
start = mid + 1
return mid
print(bsearch(N))정답 코드
원래 mid를 리턴해주었지만, 그렇게 하면 수렴하다가 num < target으로 조건이 맞지 않는 경우의 mid가 리턴될 수도 있다. 따라서 num >= target인 경우 (즉 조건이 맞는 경우) 최댓값을 리턴 받기 위해 그 때만 answer에 mid 값을 넣어주고 마지막에 answer 변수를 리턴해주는 로직을 세웠다.
저번에 풀었을 때보다 나아진 것은 num == target일 경우에만 리턴해주는 것이 아니라 num > target인 경우에도 조건에 부합한다는 생각을 했다는 것이다.
import sys
K, N = map(int, sys.stdin.readline().split())
len = [int(sys.stdin.readline()) for i in range(K)]
def bsearch(target):
start = 1
end = max(len)
while start <= end:
mid = (start + end) // 2
num = 0
for i in len:
num += i // mid
if num < target:
end = mid - 1 # 수렴하다가 조건에 맞지 않을 때
elif num >= target:
answer = mid # 조건에 맞는 것만 answer에 할당
start = mid + 1
return answer
print(bsearch(N))