[TIL] 99클럽 코테 스터디 23일차 TIL + 오늘의 학습 키워드

 

* 오늘의 학습 키워드 : 이분탐색(Binary Search)

 - 정렬된 배열이나 리스트에서 특정 값을 찾을 때 사용하는 알고리즘, 반으로 나누는 전략을 사용하여 검색 범위를 좁혀나간다.

• 핵심 개념
  
  • 시작 인덱스와 끝 인덱스를 설정하고 중간 인덱스를 계산합니다. 중간 인덱스의 값과 결과값을 비교합니다.
    • 일치 : 인덱스를 반환
    • 작다 : 중간 인덱스 값이 결과값보다 작으면, 오른쪽 절반에 있으므로 low = mid + 1로 설정
    • 크다 : 중간 인덱스 값이 결과값보다 크면, 왼쪽 절반에 있으므로 high = mid - 1로 설정
  • Lower Bound 접근법 : 특정 값 이상이 처음 나타나는 위치를 찾는 이분 탐색
  • Upper Bound 접근법 : 특정 값보다 큰 값이 나타나는 위치를 찾는 이분 탐색

---

* leetcode 1011. Capacity To Ship Packages Within D Days : https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/description/

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int right = 0; //모든 수의 합
        for(int weight : weights) right += weight;
        int left = 1;
        right += 1;

        while(left < right) {
            int mid = left + (right - left)/2;
            if(canShip(weights, days, mid)){
                right = mid;
            } else {
                left = mid+1;
            }
        }
        return left;
    }

    private boolean canShip(int[] weights, int days, int weightMax) {
        int current = 0;
        int currentDays = 1;
        for(int weight : weights) {
            if(weight > weightMax) return false;
            if(current + weight > weightMax) {
                currentDays++; // 다음날 적재
                current = weight;
            } else {
                current += weight; //계속 적재
        	}
        }
        return currentDays <= days;
    }
}