Untitled

Fold the Video

Loading...

27강 이진 탐색 기초 문제 풀이-0
27강 이진 탐색 기초 문제 풀이-1
27강 이진 탐색 기초 문제 풀이-2
27강 이진 탐색 기초 문제 풀이-3
27강 이진 탐색 기초 문제 풀이-4
27강 이진 탐색 기초 문제 풀이-5
27강 이진 탐색 기초 문제 풀이-6

작게 만들면 잘린 떡 길이의 합은

27강 이진 탐색 기초 문제 풀이-8

이진 탐색

있는가를 확인한 뒤에 즉

27강 이진 탐색 기초 문제 풀이-11

탐색 범위를 좁혀서 해결할수 있습니다

27강 이진 탐색 기초 문제 풀이-14
27강 이진 탐색 기초 문제 풀이-15

매 높이마다

최적의 해를 구할수 있습니다

27강 이진 탐색 기초 문제 풀이-18

절단기의 높이는 0부터 10억까지의

그렇기 때문에 우리는 높이를 설정할때 그 높이를 0부터 10억까지의 한 정수로 설정할수 있습니다

27강 이진 탐색 기초 문제 풀이-21

때문에 이처럼 탐색 범위가 클때는 가장 먼저 이진탐색부터 떠올리는 것이 좋습니다

27강 이진 탐색 기초 문제 풀이-23

27강 이진 탐색 기초 문제 풀이-25
27강 이진 탐색 기초 문제 풀이-26
27강 이진 탐색 기초 문제 풀이-27

끝점은 19로 설정 0부터 19까지라고 볼수 있으며

이러한 시작점 부터 끝점까지

27강 이진 탐색 기초 문제 풀이-30

시작점과 끝점을 0 과 19로 설정할수 있으며

27강 이진 탐색 기초 문제 풀이-32

중간점은 자르고자 하는 그높이 자체가 됩니다

27강 이진 탐색 기초 문제 풀이-34

중간점을 9로 설정해서 자르고자 하는

27강 이진 탐색 기초 문제 풀이-36

10 6 1 9 만큼의 떡을 얻을수 있습니다

27강 이진 탐색 기초 문제 풀이-39
27강 이진 탐색 기초 문제 풀이-40
27강 이진 탐색 기초 문제 풀이-41
27강 이진 탐색 기초 문제 풀이-42

따라서 이 시작점을 중간점 오른쪽으로 옮깁니다

그래서 다음 스텝에서는 다음과 같이 시작점이 10이고 끝점은 19

중간점은 14가 되겠습니다 이때도 마찬가지로 이중간점인 14를 높이로 설정해서

떡을 자르게 되면 잘린 떡의 길이가 차례대로 513이기때문에

27강 이진 탐색 기초 문제 풀이-48

손님이 요구하는 떡의 길이인 6보다 더 크기 때문에 이와같이 높이를

14로 설정해서 잘랐을 때에도 조건을 만족하기 때문에

현재의 결과 또한 기록할 수 있도록 합니다

27강 이진 탐색 기초 문제 풀이-52
27강 이진 탐색 기초 문제 풀이-53

15가 되고 끝점이 19가 됩니다 이때 중간점은 17이 되며 이러한 중간점으로

높이를 설정해서 떡을 자르게 되면 우리는 2만큼의 떡만 얻을수 있습니다

따라서 필요한 떡의 크기인 6을 만족하지 못하므로 이떄에 결과는 기록하지 않습니다

27강 이진 탐색 기초 문제 풀이-57
27강 이진 탐색 기초 문제 풀이-58

왼쪽인 16으로 바꿀 필요가 있습니다

27강 이진 탐색 기초 문제 풀이-60

시작점이 15고 끝점이 16이 되어서

27강 이진 탐색 기초 문제 풀이-62

자르기를 수행합니다

27강 이진 탐색 기초 문제 풀이-64

6만큼의 떡을 얻을수 있습니다

27강 이진 탐색 기초 문제 풀이-66

들지 못하게 할때 까지

27강 이진 탐색 기초 문제 풀이-68
27강 이진 탐색 기초 문제 풀이-69

최적의 해를 구할 수 있는겁니다

떡의 크기 이상의

정리 : 이와같이 이진 탐색을 수행해서 더이상 탐색 범위를 줄어들지 못하게 할때까지 시작점과 끝점에 위치를 바꾸어 가면서 이높이 값을 매번 바꾸어 보며 현재 높이로 잘랐을때 조건을 만족할 수 있는지를 체크하는 방식으로 문제에서 요구하는 최적의 해를 구할수 있는 것임

실제로 이문제는 현재의 높이에서 잘랐을때 필요한 떡에 크기 이상의 떡을 얻을수 있다면 그때마다 결과를 기록해서 최종적으로 이진 탐색을 더이상 수행 할수 없을때 까지 반복했을때 기록 되어 있는 그결과 값을 출력하도록 만들면 그 결과 값이 최적의 높이 값이라고 할 수 있습니다.

27강 이진 탐색 기초 문제 풀이-77
27강 이진 탐색 기초 문제 풀이-78
27강 이진 탐색 기초 문제 풀이-79
27강 이진 탐색 기초 문제 풀이-80

시간이 지날수록

27강 이진 탐색 기초 문제 풀이-84
27강 이진 탐색 기초 문제 풀이-85
27강 이진 탐색 기초 문제 풀이-86
27강 이진 탐색 기초 문제 풀이-87

떡에 개수 n과 그리고 손님이 요청한 떡에길이 M에 대한 값을 입력받고 각 떡에 개별

높이 정보를 입력 받을수 있도록 합니다

27강 이진 탐색 기초 문제 풀이-90

가장 긴 떡의 길이를 end값으로 설정 할수 있습니다

27강 이진 탐색 기초 문제 풀이-92

스타트부터 엔드까지 범위로 국한 되기 때문에

27강 이진 탐색 기초 문제 풀이-94

이진 탐색

27강 이진 탐색 기초 문제 풀이-96
27강 이진 탐색 기초 문제 풀이-97

있도록 합니다

떡이 길이가 이 높이 보다 더 클때만 실제로 떡을 얻을수 있으므로

27강 이진 탐색 기초 문제 풀이-101

전체의 떡을 잘랐을때 떡의 양 정보가 담길 수 있도록 합니다 그래서 이제

떡의 양이 부족한 경우

27강 이진 탐색 기초 문제 풀이-105

더 많이 잘릴수 있도록 하기 위해서

27강 이진 탐색 기초 문제 풀이-107

하는걸 확인할수 있고요

27강 이진 탐색 기초 문제 풀이-109

떡의 양이 충분한 경우 떡의 양이 m이상인 경우

덜 자를수 있도록 합니다

27강 이진 탐색 기초 문제 풀이-112

높이 값을 키울수 있는건데요

27강 이진 탐색 기초 문제 풀이-114

떡의 양이 충분한 경우 즉 m 이상의 떡을 얻을수 있는 경우에는 리절트 값을

27강 이진 탐색 기초 문제 풀이-116
27강 이진 탐색 기초 문제 풀이-117
27강 이진 탐색 기초 문제 풀이-118
27강 이진 탐색 기초 문제 풀이-119
27강 이진 탐색 기초 문제 풀이-120
27강 이진 탐색 기초 문제 풀이-121
27강 이진 탐색 기초 문제 풀이-122
27강 이진 탐색 기초 문제 풀이-123
27강 이진 탐색 기초 문제 풀이-124

잘라 본 뒤에

27강 이진 탐색 기초 문제 풀이-126

최대 10억까지의 값으로

롱롱 자료형을 이용해서

27강 이진 탐색 기초 문제 풀이-129

마찬가지 로직으로

-1에 위치로

27강 이진 탐색 기초 문제 풀이-132

탐색 하므로써

27강 이진 탐색 기초 문제 풀이-134

리절트에 정답판정을 받을수 있습니다

27강 이진 탐색 기초 문제 풀이-136
27강 이진 탐색 기초 문제 풀이-137
27강 이진 탐색 기초 문제 풀이-138
27강 이진 탐색 기초 문제 풀이-139

거의 유사한걸

27강 이진 탐색 기초 문제 풀이-141
27강 이진 탐색 기초 문제 풀이-142
27강 이진 탐색 기초 문제 풀이-143

예를들어 수열 1 1 2 2 2 2 3이 있을때 만약에

27강 이진 탐색 기초 문제 풀이-145

x가 2라면 현재 수열에서 값이 2인 원소가 4개이므로 이렇게 4개가 존재하고 있기 때문에 4를 출력하면 됩니다

27강 이진 탐색 기초 문제 풀이-147
27강 이진 탐색 기초 문제 풀이-148
27강 이진 탐색 기초 문제 풀이-149

하네요

27강 이진 탐색 기초 문제 풀이-151
27강 이진 탐색 기초 문제 풀이-152

x인 원소가 하나도 없다면 -1을 출력할수 있도록 합니다

27강 이진 탐색 기초 문제 풀이-154
27강 이진 탐색 기초 문제 풀이-155

수열은 기본적으로 정렬이 수행된 상태로

27강 이진 탐색 기초 문제 풀이-157

이제 이문제를 각자 풀어보고 이어서 해설강의를 들어주세요

27강 이진 탐색 기초 문제 풀이-159

이문제는 기본적으로 O(log N)으로 동작하는 알고리즘을 요구하고 있습니다

따라서 일반적인 선형탐색으로 x라는 값을 가지는 원소의 개수를 세서 문제를 풀고자 한다면 시간 초과 판정을 받을수 있습니다

다만 데이터가 정렬 되어 있기 때문에 우리는 이진탐색을 수행해서 이문제를 해결할수 있습니다

27강 이진 탐색 기초 문제 풀이-164

해결할 수 있습니다

다시말해 이문제는 처음 전체 탐색 범위에 대해서 이진 탐색을 2번 수행하여

하나의 이진탐색은 처음 위치를 찾도록 만들고

27강 이진 탐색 기초 문제 풀이-169
27강 이진 탐색 기초 문제 풀이-170
27강 이진 탐색 기초 문제 풀이-171
27강 이진 탐색 기초 문제 풀이-172

바이섹 레프트, 라이트 을 이용한 이진탐색

https://folivora.tistory.com/83 설명 잘함

27강 이진 탐색 기초 문제 풀이-175

이 문제를 해결할수 있음

27강 이진 탐색 기초 문제 풀이-177
27강 이진 탐색 기초 문제 풀이-179

바이섹 레프트, 라이트 을 이용해서 값이 레프트 벨류이상 롸이트 벨류 이하인 데이터의 개수를 모두 찾을수 있다고 했는데요

27강 이진 탐색 기초 문제 풀이-181
27강 이진 탐색 기초 문제 풀이-182

x인 데이터의

이와같이 레프트 벨류와 라이트 벨류의 값으로 둘다 x를 넣어줍니다

27강 이진 탐색 기초 문제 풀이-185
27강 이진 탐색 기초 문제 풀이-186

값이 x인 원소가 존재하지 않는다면 이처럼 -1을 출력하고

값이 x인 원소가 존재한다면 이와같이 그개수를 그대로

27강 이진 탐색 기초 문제 풀이-189
27강 이진 탐색 기초 문제 풀이-190

말씀 드렸듯이 파이썬의 바이셋 롸잇은 c++의 upper_bound 와 사실상 동일하며 이어서

파이썬의 바이셋 레프트는 c++의 lower_bound와 사실상 같다고 말씀드렸습니다

27강 이진 탐색 기초 문제 풀이-193

log N의 시간 복잡도로 빠르게 구할수 있습니다

27강 이진 탐색 기초 문제 풀이-195
27강 이진 탐색 기초 문제 풀이-196

팀노트에 기록을 해놓으셨다가

27강 이진 탐색 기초 문제 풀이-198

Last Updated:

Summarize & share videos seamlessly

Loading...