[항해99 취업 리부트 코스 학습일지] 3기 15일차 TIL(부제: 이분탐색! 조금은 친해졌을지도..)

안녕하세요. delay100입니다.

오늘도 열심히 Stream을 쓰려고 노력했고.. 5-12번을 풀려고 노력했습니다..! 실제로도 다 풀었구요!!

이분탐색에 마냥 어렵다라고만 생각했는데 오늘 이분탐색에 대한 장벽을 좀 허물게 되었습니다!ㅎㅎㅎ

이분탐색이 생소해서,, 오늘도 다른 지식을 학습하진 못했고 코테만 했습니다..ㅠㅠ 쉽지 않네요..

 

그리고 팀원분이 굉장히굉장히 도움을 많이 주시고 꿀팁도 많이 주셔서!!!! 끙끙대던 12번 마지막 문제도 잘 넘겼습니다! 최고.. 7조 너무 좋구요.. 너무 많이 배웁니다..ㅠ

오늘도 12번까지..!!!

---

 

3주차 TIL 질문 키워드

 

Q1. 오늘 진행된 강의에서 학습한 내용은 무엇인가요?

 

A.

이분탐색(BinarySearch)

 

Q2. 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?

 

A1. 이분탐색 키워드

제한된 공간에서 최대한
범위가 이상한경우(시간 이상한경우)
(구현->완탐->백트래킹->dp->이분탐색)
정렬해서 주는 경우

 

A2. Stream 좋은 글 추천 *꼭 읽기

https://sigridjin.medium.com/java-stream-api%EB%8A%94-%EC%99%9C-for-loop%EB%B3%B4%EB%8B%A4-%EB%8A%90%EB%A6%B4%EA%B9%8C-50dec4b9974b

Java Stream API는 왜 for-loop보다 느릴까?

 

A3. upper_bound, lower_bound 구현된 자바 코드 얻기

자바는 이분탐색에서 자주쓰이는 upper_bound, lower_bound를 직접 구현해야함

내가 이해하기 쉬운 upper_bound와 lower_bound코드를 찾아서 정리해두는 것이 코테볼때 좋다

parametric search << 코테에서 이분탐색 문제 나오는 유형!

 

A4. 프로그래머스 디버깅 

1. 그냥 try catch(IOException)한다음에 System.out.println() 값을 확인하는게 좋음

2. 재귀 터지면 대충 depth-4까지해서 그냥 return해서 코드 확인

 

A5. 이분탐색 프레임

// 백준 3079번

long start = 0L;
long end = Long.MAX_VALUE;
long answer = Long.MAX_VALUE;
while(start<=end){
    long mid = start + (end - start)/2;
    long possible = 0;
    for(long time : list){
        possible += mid / time;
        if (possible < 0) {
            possible = Long.MAX_VALUE;
            break;
        }
    }
    if(M <= possible){
        answer = Math.min(answer, mid);
        end = mid - 1;
    }else{
        start = mid + 1;
    }
}

// 백준 2110번

int start = 0;
int end = Integer.MAX_VALUE;
int answer = 0;
while(start<=end){
    int mid = start + (end - start)/2;
    if(isPossible(mid)){
        start = mid + 1;
        answer = Math.max(answer, mid);
    }else{
        end = mid - 1;
    }
}

팀원분께서 열심히 설명해주셨던 코드입니다..!

핵심은

1. end를 Long과 Long.MAX_VALUE로 설정해서 문제 범위 신경쓰지 않고도 이분탐색 쓸 수 있음!

2. mid를 구할때 start + (end - start)/2를 이용. (start+end)/2를 할 때 overflow가 발생할 수 있는데 이를 방지함!

3. if possible < 0은 possible에서 합 연산도중 범위를 넘어가는 overflow 발생 시 음수가 되는데, 이를 다시 MAX_VALUE로 바꾸고 값을 순회하면 됨 

이게 왜 되냐면 MAX_VALUE가 넘어가는 숫자라는 거는 엄청 큰 범위를 뜻하기 때문에,

값을 찾기 위해서는 어차피 다시 더 범위를 줄여서 실행해야 함 !

---

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

[할인]란에 “추천왕 3기 백지연” 입력 시 10만원 할인
(*얼리버드, 타 혜택 중복 적용 가능)

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지