[개발자매일영어] Binary Search - Cracking Coding Interview
이번에는 Binary Search에 대한 내용 입니다.
코딩 인터뷰 문제도 한문제씩 같이 풀어보도록 하겠습니다. 제일 아래에 기출문제가 있습니다. 같이 풀어봐요!
영어 공부는 왕도는 없습니다. 매일 꾸준히 듣고 말하기 연습 하는 것이 가장 중요합니다.
개발자매일영어는 당분간은 Cracking Coding Interview의 저자로 유명한 Gayle Laakmann McDowell저자의 강좌를 지속적으로 공부해보도록 하겠습니다.
전체 분량은 너무 길어서 주요부분 한 두 군데만 1분 이하로 발췌하여 mp3파일로 만들고 있습니다.
즉 한 주제당 1분 이하 분량의 mp3파일이 한 두개씩 제공되겠습니다. 나머지 부분은 리스닝 연습 하시면 되겠습니다.
이번에는 따라하기 쉽도록 최대한 짧게 잘랐습니다.
공부하는 3단계 방법은 아래와 같습니다.
1분 분량을 번역
전체 듣기 두번
문장 듣고 따라 말하기 두번
한국말로 듣고 영어로 말하기
하루에 한시간 이상 들으면서 말하기 연습하면 좋을 것 같습니다.
연습 mp3 파일 다운로드: https://drive.google.com/open?id=1FCSEt_5l-feV3VbFYZ7FO6sXBUDZKmpn
원본 동영상:
--- mp3 script & 번역 예 ---
So in an integer array that looks like this, you take some element that you're looking for, like 13, and you compare it to the midpoint, and it has to be a sorted array for this to work, it's very important, and you compare it to the midpoint.
13 is less than this midpoint and so 13, if it's in the array at all, it has to be on the left side.
And then you repeat this process on the left side and say let me look at the midpoint of the left side.
Is 13 before and after that, before or after that, and you just repeat that process until you either find 13 or you know that 13 can't be in it.
So how fast is this is algorithm? Well let's imagine we start off with n elements so we have a search space of n elements.
In a single comparison, just one, we've cut our search space down to n over 2. Then with one more comparison we cut it down to n over 4 and then in half again and half and half and half again.
So how many total operations in the very worst case will we have to run until we figure out if it contains an element or not?
Well the total number of operations we'll have to do is determined by how many times can we divide n by 2 until we get down to just one. So this is what log of n expresses. A log base 2 of n expresses.
So if you pause the video you can study that math for a second and see the relationship between those two things. But this means that binary search is a log n problem.
이 같은 정수 배열에서 13같은 찾고있는 어떤 요소를 가지려고 할 때 중간값과 비교하려면 중요한 것은 정렬된 배열을 사용해야한다는 것이고, 그리고 중간값과 비교합니다.
13은 중간값 보다 작고, 우측 배열에 없다면 좌측에 있을 것입니다. 그리고 이 처리 방법을 왼편에 반복합니다. 13이 이전이나 뒤에 있다면 계속해서 13이 없다는 것을 알거나 13을 찾을 때 까지 합니다.
이 알고리즘은 얼마나 빠를까요? N 요소들과 시작했다고 생각해 봅시다. 우리는 n 요소들만큼의 검색 공간을 가지고 있습니다.
한번의 비교에 우리는 검색 공간을 반으로 줄였습니다. 또 한번 더 비교하면 우리는 1/4로 자르고 또 반으로 또 반으로 다시 자를 수 있습니다.
이 요소가 있는지 없는지 찾기위해 최악의 경우에는 얼마나 많이 해야할까요?
우리가 해야하는 총 수행 수는 1개가 될때까지 얼마나 많이 2로 나누는가에 결정 됩니다. 이것이 log n입니다. Log 2에 n입니다.
동영상을 정지하고 잠깐 계산해 보고 두개 간의 관계를 보세요. 이것은 binary search가 log n 문제라는걸 의미합니다.
----- 이주의 Interview Question (같이 풀어 봐요!) -----
Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.
Example :
Input: root = [4,2,6,1,3,null,null]
Output: 1
Explanation:
Note that root is a TreeNode object, not an array.
The given tree [4,2,6,1,3,null,null] is represented by the following diagram:
4
/ \
2 6
/ \
1 3
while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.
Note:
The size of the BST will be between 2 and 100.
The BST is always valid, each node's value is an integer, and each node's value is different.
원 문제 링크: https://leetcode.com/problems/minimum-distance-between-bst-nodes/description/