이분탐색을 제대로 공부하지 않았던 걸까, 최근 프로그래머스 문제를 풀며 이분탐색을 떠올리지도 이분탐색으로 풀 수 있는 풀이법 조차 생각나지 않았다. 그래서 다시 이분탐색을 정리해보고자 한다. 필자가 부딪혔던 문제는 프로그래머스 level3 - 징검다리 건너기 이다
징검다리 건너기❗️
문제는 굉장히 귀엽다.. 그렇지만 난이도는..필자에겐 어려웠다. 이런 문제를 잘 풀어내는 다른 분들이 참 부럽다. 이 문제는 정확성 테스트와 효율성 테스트가 별개로 있는 문제이다.
각 stone의 내구도?는 200,000,000이다.
그리고 건너야하는 친구들은 무려 무제한 ..
무제한이다. 내가 처음 생각한 로직은 위 입력값을 보고 다시 생각해보아야했다.
일단 내구도가 200,000,000 이니까 건널 수 있는 친구들은 최대 2억명이다.
그런데 배열의 크기는 200,000 이니까 다음과 같이 생각했다.
slice를 이용해서 k만큼 자른 뒤 그 배열에서 최댓값을 뽑자
그럼 그 최댓값은 ? k 길이의 징검다리가 끊어지는 최대인원이된다.
[1,2,3,3,4,4,5,6] 의 징검다리가 있고 k가 4라고 했을 때, k 길이만큼 끊어지려면 몇명이 지나가야할까? 그 배열의 최대값이 될 것이다.
즉, [1,2,3,3]의 길이의 징검다리는 3명이 지나가면 모두 부숴지게 된다. 4명부터는 갈 수 없는 것이다.
그럼 이러한 방식으로 계속 나아가면 [2,3,3,4]는 4명 [3,3,4,4]는 4명
각 구간별로 봤을 때 3명이 지나가면 결국엔 4번째는 첫 번째 k구간에서 건널 수 없게 된다. 이를 생각하고 코드를 다음과 같이 짰다.
첫 번째 시도 ❗️( 효율성 검사 x, 정확도 검사 o)
function solution(stones, k) {
let answer = 20000000;
for (let i = 0; i <= stones.length - k; i++) {
const arr = stones.slice(i, i + k);
const min = Math.min(...arr);
if (answer > min) {
answer = min;
}
}
return answer;
}결과는 ..! 효율성검사는 모두 틀렸고, 정확도 검사만 통과할 수 있었다.
그렇다면 위 로직은 효율성이 좋지 않다는 것이다. 최근에 배운 투포인터를 사용해보려고 했다.
두 번째 시도: 투 포인터 ❗️(효율성 검사 x, 정확도 검사 o)
다음과 같이 생각했다. k구간의 합이 가장 작을 때 그 구간의 가장 최대값이 최대로 건널 수 있는 인원이 아닐까?
근데 이 로직은 너무 억측이었다. 논리가 부족했던 거 같다.
k구간이 만약 [2,2,2][1,2,3] 이면 위 합은 같지만 두 배열의 최대 허용 인원은 2,3 으로 다르다. 첫 번째 배열은 2명이 건너면 부숴지지만 두 번째 배열은 3명이 건너야 부숴진다.
function solution(stones, k) {
let left = 0;
let sum = 0;
let min = 200000000;
let answer;
for (let i = 0; i <= stones.length; i++) {
if (i >= k) {
sum = sum - stones[left];
left++;
}
sum = sum + stones[i];
}
}right는 i가되고 left는 다음과 같이 변수로 재할당받으며 업데이트가 된다.
그럼 sum이 최대가 될때의 left, right를 answer에 저장하여 for문 탈출 후 slice 메서드를 활용해서 그 구간의 최대값을 구해주면 된다.
그렇지만 로직에 문제가있었고 효율성테스트도 절반밖에 통과하지 못했다.
마지막 시도: 이분탐색 ❗️ (효율성 검사 o, 정확도 검사 o)
이분탐색 알고리즘으로 해결해야겠다는 생각은 필자의 머리에서 나온게 아니다.. 질문하기 페이지에 들어갔고 거기서 먼저 문제를 해결하신 분들의 댓글을 봤다.
이미 한 4시간은 고민했던터라..그냥 봐버렸다..😢
꿀팁이 있었다. "Input이 억 단위면 이분탐색을 따져봐라" 웅장하다.
이분탐색 알고리즘에 대해 제대로 이해를 못한 거 같아서 먼저 이분탐색 알고리즘을 학습하였다..! 지금 블로그를 정리하며 그 개념을 다시 한번 포스팅 해보겠다!
이분탐색 알고리즘 ❓
아주 좋은 동영장 자료가 있어서 가져왔다.
gif자료 출처
이분 탐색은 찾는 범위나 값의 대상을 절반씩 줄여가면서 input을 혁신적으로 감소시키는 알고리즘 기법이다.
핵심은 input을 절반씩 줄여나간다는 점 .
여기서 Input은 절반이 아니라 더 줄여질 수 있다. 특정조건에 따라 그 절반의 값을 모두 확인하지 않아도 된다.
위 문제가 그 점을 이용할 수 있었다.
다음과 같이 재귀함수로 이분탐색을 실행할 수 있다.
function solution(){
const arr =[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
let target = 13
let answer;
const binarySearch=(left,right)=>{
const mid = Math.floor((left+right)/2)
if(target===arr[mid]){
answer=mid
return;
}
if(target>arr[mid]){
//target이 더 오른쪽에 있는상황이면?
binarySearch(mid+1,right)
}
else if(target<arr[mid]){
binarySearch(left,mid-1)
}
}
binarySearch(0,14)
return answer
}
solution()위 결과는 12로 원하는 index를 추출 할 수있다.
반복문으로도 그 결과값을 return할 수 있다.
function solution(){
const arr =[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
let left=0
let right = arr.length-1
let target =13
while(left<=right){
const mid = Math.floor((left+right)/2)
if(arr[mid]===target){
return mid;
}
if(arr[mid]<target){
left=mid+1
}
else if(arr[mid]>target){
right= mid-1
}
}
return "none"
}
solution()위와 같이 구현해도 동일한 갑인 12를 return 받을 수 있다.
이분탐색의 핵심은 Input을 아주 확! 줄여준다는 점 이다.
그럼 아까 그 말이 맞다 . Input이 말도안되게 크다면 이분탐색을 의심해보자
시간복잡도는 O(logn)이다. 정확히는 log 2에 n이다.
다시 문제로 돌아가보자!
다시 문제로 ❗️
자, 징검다리는 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 이다.
k= 3 이 말은?? 3만큼의 다리가 끊어지는 최초의 순간이 답이라는 거
사실 말이 너무 어렵다 그냥 다리를 몇명 건널수 있는지를 물어봤다. 그리고 건너야 하는 니니즈는 무한대이고 하나의 다리가 견딜수 있는 최대의 내구도는 2억이다. 즉, 2억의 다리가 3개있고 k가 3이라면 2억명 모두가 건널 수 있는 레전드 다리인거다..
그럼 이렇게 생각하자. 다리를 몇명건널수있는지를 이분법으로 생각해보자.
level3나 level2의 어려운문제를 맞딱들이면 먼저 문제를 나눠서 생각해야하는 거 같다. 먼저 다리를 몇명 건널 수 있는지를 생각하고 이분법을 사용한다는 생각으로 코드를 구성해보자.
function solution(stones,k){
const canTheyCross=(mid)=>{
//mid를 기준으로 이 숫자를 견딜 수 있는 다리를 찾아보자
let brokenStone=0
for(let i = 0 ; i <stones.length; i++){
if(stones[i]-mid<=0){
brokenStone=brokenStone+1
}
else{
brokenStone=0
//연속성제거
}
if(brokenStone>=k){
return false
// k의 길이와 같거나 크면 이제 건널 수 없는 것!
}
}
return true
// brokenStone이 k보다 작다면? 건널 수 있는거 !
}
let left= 0
let right = 200000000
while(left<=right){
const mid = Math.floor((left+right)/2)
if(canTheyCross(mid)){
left=mid+1
}
else if(!canTheyCross(mid)){
right = mid-1
}
}
return left
이를 떠올리는게 참..쉽지않다. 사실 힌트를 보고 이분탐색으로 풀기 시작한거지 혼자서 이런 생각을 떠올리는게 어렵다. 가끔 이런 벽에 부딪히면 생각이 많아진다. 생각을 줄이고 그냥 코드를 쳐야지
다시 정신 차리고 정리를 해보겠다.
이렇게 생각해야한다!
문제에서 뭘 원하는가? => 몇명 건널 수 있는지!
그럼 몇명을 가정하는 것이다.
예를들어
[2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 의 돌다리에서
5명이 건넌다면 ? 2, 4 통과 5 리셋 3,2,1에서 돌다리는 끊어질 것이다.
그럼 3명이 건넌다면 ? 2 통과 4 리셋 3,2,1 까진 건널 수 있다.
즉, 각 몇명이 건너는지를 가정하면서 나아가는 것이다.
사실 2억이라고 안해도 괜찮다. 내 생각엔 배열에서 최대값을 구한 뒤 그 숫자부터 이분탐색을 해 나가면 되지 않을까?
이분탐색해서 mid가 5까지왔다면?? 5일경우에 연속으로 부숴진 돌다리가 k개 이상임으로 right가 한번 더 mid -1 이 되고 다시 2분으로 나눠진다
그럼 0+4 /2 =2
그 다음 2명이 건넌다하면 ? 건너기가 가능하다.
[0,2,3,1,0,x,2,0,3,x]
그럼 mid가 가능하니 left는 mid+1이 된다. 그 다음 다시 검사
1+4/2 => 3 그럼 3일경우?? 가능하다 [x,1,2,0,x,x,1,x,2,x]
3이 가능하니 left는 mid+1이되고 (4 +4)/2 =>4
4명은 불가능하다. [x,0,1,x,x,x,0,x,1,x]
부숴진게 3칸이 되어버려 점프할 수 없다. 4번째에 뛰는 사람이 갈수없다.
그렇기 때문에 right = mid-1 그때 left>rigth가 되니까 while문은 탈출하게 된다..!
let left= 0
let right = Math.max(...stones)
다음과 같이 right의 범위를 Math.max로 한정한다음 이분법을 실행하면 어떨까?
결과는
Spread Operator ❓
평소 코딩테스트를 풀 때 많이 사용하던 Spread Operator의 시간 복잡도는 n^2이다.. 그렇기 때문에 런타임 오류가 발생하는 거 같다. 그냥 주어진 Input의 범위를 기준으로 이분탐색을 바로 실시하는 것이 더 낫다.
어차피 k만큼만 가다가 return 될 것이기 때문이다.
이분탐색에 대해서는 조금 더 이해할 수 있게 되었다.
핵심은 탐색해야할 Input을 그냥 절반씩으로 숙숙 줄여주는 좋은 알고리즘이라는 거.
알고리즘을 공부하면서 알고리즘을 너무 미워하지말자! 나를 이롭게해주는 알고리즘들이다. 더 친근하게 지내보자 즘리고알
