코테 스터디 52일차 TIL + 오늘의 학습 키워드 이진함수

- 오늘의 학습 키워드

속도가 클수록 시간이 작게 걸림== 단조성

조건을 만족하는 최소값을 찾는 문제

---

 

 

- 공부한 내용 본인의 언어로 정리하기

function minEatingSpeed(piles, h):
  left=1
  right= max(piles)
  
  while(left< right):
    mid =(left+right)/2
    
    if canFinishIntime(piles, mid, h):
      right= mid
    else:
      left = mid+1
      
  return left
  
  function canFinishIntime(piles, k, h):
    totalHours =0
    
    for each pile in piles:
      totalHours += ceiling(pile/k)
      
    return totalHours <=h

---

function findMin(nums)"
  left=0
  right = nums.length-1
  
  while left<right
     mid(left+right)/2
     
     if nums[mid]>nums[right]:
        left= mid+1
     else:
        right =mid
        
    return nums[left]

- 오늘의 회고
  - 어떤 문제가 있었고, 나는 어떤 시도를 했는지

totalhours를 생각하는거를 어려워함 아래 예시를 이해를 못했음

Explanation: With an eating rate of 2, you can eat the bananas in 6 hours. With an eating rate of 1, you would need 10 hours to eat all the bananas (which exceeds h=9), thus the minimum eating rate is 2.

 

rate 2일때 : 1 /2 => 1시간 (올림으로 처리)

                   4/2 = 2시간

                    3/2 =2시간

                   2/2 =1시간 총 6시간 이렇게 계산됨

 

rate 10일때: 1/1 =1시간

                     4/1 = 4시간

                       3/1 =3시간

                         2/1 = 2시간 총 10시간 걸리니까 최소 먹는 시간은 rate 2가 되는거를 이해해는데 한참 걸렸다.

---

1. O(log n) constraint를 어떻게 풀어야할까?

2. example 1에서 out put이 1,2가 왼쪽으로 다시 회전을 해야 asc 구조로 돌아가는거라서 output이 2가 되야하는거는 아닌지

"Assuming all elements in the rotated sorted array nums are unique, return the minimum element of this array."

 

3. O(n)의 해법?

public int findMin(int[] nums){
   int min =nums[0];
   for(int num:nums){
   min = Math.min(min,num);
	}
  return min
}

- 어떻게 해결했는지

 

 

 

---

문제는 최솟값을 찾는 문제이지 회전을 원상복구하는것이 아니다.

O(log n) 시간복잡도를 위해서 이진 탐색을 사용

중간 요소와 오른쪽 끝 요소를 비교하여 최솟값의 위치를 좁혀나간다.

  - 무엇을 새롭게 알았는지

getMax나 boolean으로 메서드 만들어서 넣는것도 깔끔하게 풀수 있는 방법이었다.

회전된 정렬 배열에서 최솟값은 항상 회전점에 위치한다.

  - 내일 학습할 것은 무엇인지