인프런 커뮤니티 질문&답변

박우림님의 프로필 이미지

작성한 질문수

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

44. 마구간 정하기 (이분검색 응용 : 결정 알고리즘)

lt=1로 하는 것 보다는...

작성

·

229

0

안녕하세요 강의 너무나 잘 보고 있습니다.

동영상에서 lt=1; 로 초기화 하셨는데, x[1]의 값이 1이 아닐 수도 있으니까

lt=x[1]; 로 초기변수를 잡아주는 것이 더 낫지 않나 싶습니다. 

답변 2

1

김태원님의 프로필 이미지
김태원
지식공유자

강의 잘 보고 있다니 정말 감사합니다.

lt와 rt는 답이 존재하는 구간의 양 끝값입니다. x[n]이 우리가 구하고자 하는 답범위의 최대값이 확실하지만 

마구간의 최소 좌표값인 x[1]이 우리가 구하고자 하는 답범위의 최소값이라고 확신할 수 없습니다.

즉 마구간 좌표의 최소값보다 답이 더 작을 수 있습니다. 그래서 lt=1로 초기화하는 것입니다.

아래 입력이 lt=x[1]으로 하면 안되는 예입니다.

5 3

5

6

12

8

14

위와 같이 입력이 들어오면 답이 3 이지만 lt=x[1]으로 초기화하면 lt=5로 초기화되어 5~14범위에서만 답을 찾으려고 해 답이 없는 결과가 나옵니다.

시작 범위를 좀더 줄여보겠다면 x[1]의 값이 1이 아닐 수 있으니 rt=x[n]-x[1]; 로 하면 더 좋을 것 같습니다. 우리가 구하고자 하는 답이 가장 가까이 이웃한 두 말의 최대 거리이니까요. 말을 두 마리 배치한다면 답이 x[n]-x[1]이 되겠죠.

0

박우림님의 프로필 이미지
박우림
질문자

답변감사합니다.😃

"구간의 거리"을 나타내는 값의 범위니까 1부터 시작해야하네요. 

제가 잠시 넋이 나갔던 거 같습니다. 😱

친절한 답변 갑사드립니다.