<div id="readability-page-1" class="page"><div><blockquote>
해당 내용은 프로그래머스 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 공부하며 정리한 내용입니다.
</blockquote>
<ol>
<li>이진탐색 
1-1 이진탐색 배열</li>
</ol>
정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘 
O(log n)만큼 시간복잡도가 걸린다.
실사용예시
<ul>
<li>업/다운 게임</li>
</ul>
비교 : 선형탐색 
순서대로 하나씩 찾는 탐색 알고리즘 O(n) 시간복잡도가 걸린다.
1-2 이진 탐색 트리
이진 탐색을 위한 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값이 모여있고 오른쪽 서브 트리는 루트보다 큰 값이 모여있다.
이진탐색트리의 문제점
<ul>
<li>최악의 경우 한쪽으로 편향된 트리가 될 수 있음</li>
<li>그런 경우 순차 탐색과 동일한 시간복잡도를 가짐</li>
<li>이를 해결하기 위해 다음과 같은 자료구조를 이용할 수 있음 
- AVL 트리<ul>
<li>레드-블랙 트리</li>
</ul></li>
</ul>
=&gt; 코테에서는 주로 이진 탐색 배열로만으로 푸는 문제가 대부분.
<ol start="2">
<li>특징</li>
</ol>
<ul>
<li>반드시 정렬이 되어있어야 사용할 수 있다.</li>
<li>배열 혹은 이진 트리를 이용하여 구현할 수 있다.</li>
<li>O(log n) 시간복잡도인 만큼 상당히 빠르다.</li>
</ul>
=&gt; 이렇게 빠른 알고리즘은 거의 없다.
<pre><code>function binarySearch(array, findValue) {
 let left = 0;
 let right = array.length - 1;
 let mid = Math.floor((left + right) / 2);
 while (left &lt; right) {
 if (array[mid] === findValue) {
 return mid;
 }

 if (array[mid] &lt; findValue) {
 left = mid + 1;
 } else {
 right = mid - 1;
 }

 mid = Math.floor((left + right) / 2);
 }

 return -1;
}</code></pre>
<ol start="3">
<li>코테 
핵심키워드 : 전체 리스트에서 특정 구간을 찾아야하는 경우, 모든 요소 중 X를 만족하는 가장 큰/작ㅇ느 값을 만족하는 지점, 커트라인 
참고상황 : 제한 조건이 빡세서 O(log(n)) 시간복잡도 적용이 필요시 
대표문제: 입국 심사 문제</li>
</ol>
<img src="https://velog.velcdn.com/images/2taesung/post/a03bb5fb-e586-4c4e-900f-eeda4e6ecd5a/image.png"></div></div>

2taesung.log

Taesung Lee

해당 내용은 프로그래머스 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 공부하며 정리한 내용입니다.
이진탐색
1-1 이진탐색 배열
정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘
O(log n)만큼 시간복잡도가 걸린다.
실사용예시
업/다운 게임
비교 : 선형탐색
순서대로 하나씩 찾는 탐색 알고리즘 O(n) 시간복잡도가 걸린다.
1-2 이진 탐색 트리
이진 탐색을 위한 이진 트리로 왼쪽 서브 트리는 루트보다 작은 값이 모여있고 오른쪽 서브 트리는 루트보다 큰 값이 모여있다.
이진탐색트리의 문제점
최악의 경우 한쪽으로 편향된 트리가 될 수 있음
그런 경우 순차 탐색과 동일한 시간복잡도를 가짐
이를 해결하기 위해 다음과 같은 자료구조를 이용할 수 있음
AVL 트리
레드-블랙 트리
=> 코테에서는 주로 이진 탐색 배열로만으로 푸는 문제가 대부분.
특징
반드시 정렬이 되어있어야 사용할 수 있다.
배열 혹은 이진 트리를 이용하여 구현할 수 있다.
O(log n) 시간복잡도인 만큼 상당히 빠르다.
=> 이렇게 빠른 알고리즘은 거의 없다.
function binarySearch(array, findValue) {
 let left = 0;
 let right = array.length - 1;
 let mid = Math.floor((left + right) / 2);
 while (left < right) {
 if (array[mid] === findValue) {
 return mid;
 }
 if (array[mid] < findValue) {
 left = mid + 1;
 } else {
 right = mid - 1;
 }
 mid = Math.floor((left + right) / 2);
 }
 return -1;
}
코테
핵심키워드 : 전체 리스트에서 특정 구간을 찾아야하는 경우, 모든 요소 중 X를 만족하는 가장 큰/작ㅇ느 값을 만족하는 지점, 커트라인
참고상황 : 제한 조건이 빡세서 O(log(n)) 시간복잡도 적용이 필요시
대표문제: 입국 심사 문제

이진탐색(파라메트릭 서치)

댓글