인프런 커뮤니티 질문&답변
작성한 질문수
안녕하세요. 강사님께서 제공해주신 코드로 다른 문제를 풀려고 합니다.
해결된 질문
작성
·
111
·
수정됨
0
안녕하세요. 강사님께서 제공해주신 이분탐색 1번 2번 코드중 2번 코드로 새로운 문제를 풀려고 합니다.
1번 코드(left와 right 설정)으로는 잘 풀리는데 2번 코드(cur과 step 설정)로는 잘 안풀리네요.
백준 2343번 기타문제를 강사님께서 제공해주신 코드로 풀려고 아래와 같이 코드를 짜보았습니다.
하지만 원하는 결과를 얻지 못했는데요. 어떤 부분이 잘못된건지 알려주실 수 있을까요??
nums, blue_nums = map(int, input().split())
bluelay_length = list(map(int, input().split()))
def check(length):
count = 1
current_length = 0
for i in bluelay_length:
if current_length + i <= length:
current_length += i
else:
current_length = i
count += 1
return count == blue_nums
cur = 0
steps = 10000+1
while steps > 0:
while cur + steps <= 10000+1 and check(cur + steps):
cur += steps
steps //= 2
print(cur)
감사합니다.
답변 2
1
안녕하세요. 승환 김님!
전체적으로 잘 풀어주셨으나 몇 가지 놓치신 부분이 있습니다.
cur의 초기값 세팅
bluelay_length의 최대값보다 작은 값은 유효하지 않은 값을 살펴보는 것이니 cur = max(bluelay_length) - 1로 해야 합니다.
여기서 -1을 해야하는 이유는 현재 탐색하는 구조인 [False, False, False … False, True, True, … True] 구조에서 가장 오른쪽 F를 구해야 하기 때문입니다.
steps의 최대 범위
steps의 최대 범위를 10000으로 잡아주셨는데요.
각 강의의 길이는 최대 10,000이고, 주어지는 강의 갯수는 100,000이므로 답이 될 수 있는 블루레이 크기는 최대 10,000 x 100,000 = 10억까지 봐야합니다.
check 함수의 리턴
check 함수에서 count한 갯수가 문제에서 주어진 blue_nums와 같은 경우 뿐만아니라, 작은 경우도 조건을 만족하기 때문에,
check 함수가 true가 되는 조건은 count == blue_nums가 아니라, count <= blue_nums으로 수정해주셔야 합니다.
또한 만족하지 않는 경우, true가 되는 경우까지 반복하며 이분탐색을 수행하는 것이기 때문에 check가 아닌 not check 조건을 주셔야 합니다.
마지막 출력값 + 1
현재 탐색하는 구조가 [False, False, False … False, True, True, … True] 입니다.
여기서 가장 왼쪽의 True를 찾는 것이기 때문에 not check()로 찾은 가장 오른쪽의 False 인덱스에서 +1을 하여 답을 출력해야 합니다.
따라서 마지막 출력값 cur에서 +1을 하여 cur+1을 출력해주시면 됩니다.
위 내용을 반영하여 수정한 코드입니다.
nums, blue_nums = map(int, input().split())
bluelay_length = list(map(int, input().split()))
def check(length):
count = 1
current_length = 0
for i in bluelay_length:
if current_length + i <= length:
current_length += i
else:
current_length = i
count += 1
return count <= blue_nums
cur = max(bluelay_length) - 1
steps = int(1e9)
while steps > 0:
while cur + steps <= int(1e9) and not check(cur + steps):
cur += steps
steps //= 2
print(cur+1)
또 궁금하신 점 있으시면 언제든 질문 부탁드립니다.
감사합니다. :)
cur은 나올 수 있는 가장 작은 값으로 설정하시면 됩니다.
따라서 보통 0으로 설정하면 됩니다.
하지만 문제에 따라 추가로 고려할 점이 있을 수 있습니다.
이번 문제를 예로 들자면, check()함수의 인자에 max(bluelay_length)보다 작은 값을 넣으면 잘못 작동하게 됩니다.
예를 들어 nums = 5, blue_nums = 5, bluelay_length = [1, 1, 1, 1, 100]인 경우에 check(5)를 하게 되면 True를 반환하게 될 것입니다. 하지만 5에는 100을 담지 못하므로 False를 반환해야 합니다.
위와 같은 문제를 해결하는 방법으로는 두 가지 방법이 있습니다.
cur을 0으로 시작하고, check() 함수에서 유효하지 않은 값(max(bluelay_length)보다 작은 값)이 들어오면 False를 반환하도록 작성
check() 함수는 그대로 하며, cur의 초기값을 애초에 유효한 값으로 설정하기
step같은 경우는 살펴봐야 하는 범위의 최대값으로 설정하시면 됩니다.
이번 문제 같은 경우는 답이 최대 10억까지 나올 수 있으니 10억으로 설정하면 됩니다.
이번 문제는 '파라매트릭 서치 알고리즘 [문제풀이] : BOJ 13397'와 비슷한 구조를 가지는 문제이니, 해당 강의을 듣고 다시 한 번 천천히 이해해보시는 것을 추천드립니다!
0
안녕하세요, 인프런 AI 인턴입니다.
제공해주신 코드를 보면, 이분 탐색을 응용하는 문제 해결 방식에 오류가 있어 보입니다. 백준 2343번 문제는 이분 탐색을 통해 최소한의 블루레이 크기를 찾는 문제입니다. 여러분이 구현하신 코드에서 check 함수는 주어진 길이로 모든 장을 녹화할 수 있는지 없는지를 판단하는 로직으로 적절합니다. 그러나 이분 탐색의 진행 과정에서 탐색 범위를 조정하는 방식에 문제가 있습니다.
오류의 핵심은 탐색 범위 설정과 탐색 조건 로직에 있습니다. cur을 시작점으로 설정하고 steps를 통해 탐색 범위를 줄여가며 최소 길이를 찾으려는 시도는 맞지만, 탐색의 시작 범위와 종료 조건 설정에 오류가 있습니다. 문제의 조건에 맞게 이분 탐색의 시작점은 블루레이의 최대 길이, 즉 bluelay_length 중 가장 큰 값으로 설정해야 하며, 종료점은 모든 길이의 합으로 설정하는 것이 일반적입니다.
또한, 이분 탐색 중 check 함수의 사용 방식에 따라, 탐색 범위를 절반씩 줄여나가며 정답을 찾아가야 합니다. 주어진 코드에서는 cur과 steps를 사용하여 탐색 범위를 변경하려고 하였으나, 이는 문제의 조건에 맞는 이분 탐색을 구현하는 올바른 방법이 아닙니다.
올바른 이분 탐색 알고리즘을 적용하여 문제를 해결하려면, 아래와 같은 접근 방식을 따라야 합니다:
- 이분 탐색을 위한 시작점(
left)을bluelay_length의 최댓값으로, 종료점(right)을 합으로 설정합니다.
- 중간점(
mid)이 조건을 만족하는지check함수를 통해 확인합니다.
- 만족한다면 더 작은 길이로도 만족하는지 확인하기 위해 종료점을 조정(
right = mid - 1)하고, 만족하지 않는다면 시작점을 조정(left = mid + 1)하여 탐색 범위를 줄여 나갑니다.
- 이 과정을 반복하여, 최소한의 블루레이 크기를 찾아냅니다.
주어진 코드를 기반으로, 이분 탐색을 적절히 적용해 다시 문제를 해결해 보시길 권장드립니다.
답변 주셔서 감사드립니다.
추가로 궁금한 사항이 있는데요. 강사님께서 제공해주신 cur과 step을 이용해 코드는 짜는 경우 cur과 step에 따라서 답을 구할 수도 구하지 못할 수도 있는것 같습니다.
cur과 step을 잘 선정할 수 있는 방법이 있을지 궁금합니다.
감사합니다.