이분탐색의 로직상 가능한 한 최소의 차이로 줄이려고 하기 때문에 배열에 존재하는 값의 차이가 정답이 될 수밖에 없지 않나요?
1981번 - 배열에서 이동
이분탐색의 로직상 가능한 한 최소의 차이로 줄이려고 하기 때문에 배열에 존재하는 값의 차이가 정답이 될 수밖에 없지 않나요?
다음과 같은 결정 문제를 생각해봅시다.
"값 k가 주어졌을 때, 최댓값과 최솟값의 차이가 k 이하가 되도록 하여 배열의 (1, 1)에서 (n, n)으로 이동할 수 있는가?"
k가 -1이면 발을 내딛을 곳조차 없으니 반드시 불가능할 것이며 k가 200이면 아무데로나 이동할 수 있으니 반드시 가능할 것임을 쉽게 알 수 있습니다.
또한 k가 커질 수록 더 '쉬운' 문제가 된다는 것을 알 수 있습니다. 표현이 조금 애매한데, 정확히 서술하자면, k = x일 때 이동이 가능했다면 k > x일 때에도 반드시 이동이 가능합니다. k = x일 때 사용했던 그 경로를 그대로 사용하면 되니깐요.
k = -1부터 k = 200까지 이 결정 문제의 진위 여부를 T와 F로 쭉 이어서 써보면 아래와 같은 구조일 겁니다.
FFFFFF....FFFTTT...TTTTTT
이 F와 T의 배열의 구조에서 F -> T의 전환이 일어나는 곳은 정확히 한 군데일 수밖에 없습니다. 그 전환이 일어난 직후의 k가 이 결정 문제를 참으로 만드는 가장 작은 k이며 이 위치를 이분 탐색으로 찾을 수 있습니다. 매개 변수 탐색의 기본적인 아이디어 입니다.
자, 그러면 이제 결정 문제를 참으로 만드는 가장 작은 k는 어떻게든 찾아진다는 점을 알았으니 이 k값에 대해 경로가 어떻게 구해질지 생각해봅시다.
이 값보다 차이가 작아지는 경우 이동이 불가능했으며 정확히 이 값이 되었을 때에 이동이 가능했다는 의미는 다시 말해 최댓값과 최솟값의 차이가 k-1 이하인 경로는 존재하지 않지만 최댓값과 최솟값의 차이가 k 이하인 경로는 존재한다는 뜻입니다. 그렇다면 이 경로의 최댓값과 최솟값의 차이는 정확히 k일 수밖에 없습니다. 더 작다면 앞에 모순이고 더 크다면 뒤에 모순이죠.
3분 모두 관심 가져주시고 답변 주셔서 감사합니다.
특히
@lcr7324 님의 설명을 들으니 이해가 정말 쏙 되네요.
다른 분들 코드를 읽으면서도 매개 변수 탐색 풀이라고 스스로 인지를 못한 거 같습니다. 부족한 점 더 공부해보겠습니다. 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
wjsaos2081 11달 전
문제 지문에서 "이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우" 를 구하라고 하였습니다.
그런데 이분탐색을 쓰면 배열에는 존재하지 않는 가상의 최대 최소값이 구하고, 그들 간의 차이가 나올 수도 있지 않나요?
다른 분들이 올리신 '이분탐색' + 'BFS' 풀이를 보면,
1. 배열에서 나올 수 있는 최소값과 최대값을 구해서 start, end의 초기값으로 설정
2. 그 둘 사이에서 mid 값 구함 = (최대 - 최소 차이를 나타냄)
3. mid 값을 만들 수 있는 최대 최소 쌍 (start, start+mid) 를 bfs에 넣어서 그 사이 안에 배열 끝까지 도달 할 수 있는지 체크
순으로 이루어져 있습니다.
여기서 실제 배열안에 해당 최소값(start), 최대값(start+mid) 값이 있는지 확인을 하지 않고 답을 출력하는데, 맞는 경우가 많아서 한 번 여쭤봅니다.
제가 놓치고 있는 부분이 있을까요?
제가 위에 글로 쓴 코드 참조 드립니다. 감사합니다.