his130   1년 전

기본적인 이분탐색 공부중인데요...

69%까지 가서 틀렸다고 나오네요...


아무리 봐도 long long 도 하고 다 그럤는데...

도와주세요ㅠㅠ


ehddml3   1년 전

high=v.back()+1

v.back()값이 답으로 출력되어야할때는 lo가 hi에 막혀서 더 못 올라갑니다

his130   1년 전

너무 감사합니다.

그렇다면 다른 문제를 풀 때도 lo 값도 0이 아닌 더 낮은 값으로 수정해야 겠군요?

ehddml3   1년 전

위 코드에서 lo를 정답으로 하려고 하기 때문에 lo는 지금처럼만 하셔도 될 것 같습니다.

범위가 a이상 b이하이면 초기 lo=a, hi=b+1이면 될 거에요

his130   1년 전

계속 질문해서 죄송한데...

결국 답은 lo , mid, high 가 거의 근사하게 되는건가요? 이분법이라는게?

그러면 만약 답을 high 로 하면 

범위가 a이상 b이하일때 초기 lo=a-1, hi =b  이렇게 해도 된다는 말씀인가요??

그렇다면 답을 mid 로 한다면

lo=a hi=b 이렇게 해도 답이 된다는 말이신지..?


제가 너무 많이 물어봐서 죄송합니다. 그리고 감사합니다.

his130   1년 전

위의 질문에 추가로..

문제마다 다른것인지.. 제가 이분탐색을 처음 공부하다 보니 헷갈리네요..ㅠㅠ

ehddml3   1년 전

음.. 일단 이런 방식을 사용할 때는 변수가 증가할때 나오는 값이 계속해서 증가하거나 감소하는 조건에서 질문을 하신다고 보면 됩니다.

이 문제에서는 x의 길이로 잘랐을 때, n개를 만들 수 있니?? 를 가정하고 풀면 그런 방식이 됩니다. 뭐 여기서는 n개 이상을 만들 수 있으면 n개를 만들 수 있다고 생각하면 되겠죠?

예를 들면, 3cm로 자르니까 100개가 나온다면, 6cm로 자르면 100개보다는 적게 나오겠죠? 한 50개라고 생각해볼까요

저는 가장 길게 만들면서 70개를 만들고 싶어요. 그럼 3~6cm사이의 어떤 값 중에 하나일 겁니다. 그렇게되면 그 중간즈음에 해당하는 어떤 값으로 테스트 해본다면 위에서 했던 추적(?)과정을 또 할 수 있을거라 기대할 수 있습니다.

그래서 위에서 말씀하신 lo,hi,mid는 탐색을 많이 거칠수록 70에 더 가까워지게 됩니다. lo가 69.999999... , hi가 70.000000000000000....1 뭐 이런식으로..? 실수형에서는 그렇습니다.

KakaoTalk_20171125_015618903.jpg

예를 들면, 초기 lo=0. hi=1이었다면 mid가 0.5 0.75.... 이런식으로 끝 없이 내려가기 때문이에요. 한 100번 정도 돌린다고 치면 같다고 생각될정도로 차이가 줄어들게 될거에요. 그래서 a이상 b이하의 범위라면 lo=a, hi=b라고 넣어도 괜찮습니다.(실수형에서 그렇습니다. 그리고 이럴 경우에 보통 답과 1e-9 이하인 차이를 가지면 정답으로 인정한다 비스무리한 문구가 달리기 때문에 매우 작은 차이는 괜찮다고 봐도 됩니다.)

하지만 이 문제에서는 정수형 답안을 요구하고 있죠? 랜선 두개가 2cm이고 2개를 구하고싶다 라고 치면 초기 값이 lo=1, hi=2이라고 했을 때, mid는 계속 1이 되겠죠?(정수형이니까) 1cm로는 4개를 만들 수 있으니 lo=mid가 계속 실행됩니다. 그래서 lo = mid = 1이 계속 반복됩니다. 첫 답변에 lo가 hi에 막혀서 못 올라간다고 한 말이 이것입니다.  이걸 방지하려고 hi를 하나 더 높게 잡아주는 것입니다. 답을 lo에 저장하도록 했는데 ( if (decision(v,mid,N)) lo = mid; 이부분에서 ) lo가 갈 수 있는 범위(답이 될 수 있는 범위)는 정수형 제한때문에 lo ~ hi-1이 되어버리기 때문입니다.

lo에 답을 넣느냐 hi에 답을 넣느냐는 decision(mid)의 결과로 나온 것이 해당 질문을 만족할 때 건드리는 변수가 출력해야할 답이겠죠? 위 코드에서는 decision이 true를 리턴했을 때(문제 조건을 만족할 때) lo에 넣었으니까 lo는 답이 될 수 있는 변수겠지요.

his130   1년 전

아.. 친절한 설명 너무나 감사합니다 

너무 큰 도움이 됐어요!

한가지 질문을 더 드리자면

hi에 막혀서 답이 될 수 없다 이 부분은

위의 예제 처럼 hi의 초기값이 답일 때만 말씀하시는게 맞죠?


즉, 제 코드에서 보자면 반복문의 i값이 0일때..

제가 이해한 대로라면 그때의 예외만을 판단하기 위해 그런게 맞나요?

여러번 돌면 어차피 hi = mid값으로 

계속 변하게 되니까요?

말이 두서가 없네요..제가

his130   1년 전

i값이 0일때라기 보다는

hi = vector() 가 정답이 되는경우만 말씀하시는거죠...?

his130   1년 전

hi. =vector.back() 을 잘못썼습니다..

ehddml3   1년 전

네 그렇게 생각하시면 될 것 같아요

음.. 그러니까 hi가 답이라면 lo가 계속 갱신되었을때, hi에 가까워져야하는데 lo가 hi-1까지 왔을 때는(이 때 lo가 10이라고하면) 10.5 10.75 ..... 처럼 11에 점점 더 가까워질 수 있어야하는데 정수형이라 10 10 10 10 10 .... 이 반복된다는 말이에요

his130   1년 전

너무 감사합니다 ㅠㅠ 복받으세요!!!

댓글을 작성하려면 로그인해야 합니다.