[탐색 알고리즘]
<STUDY>
선형 탐색 (Linear Searching)
특정 값이 배열 안에 포함되어 있는지 순서대로 살펴보는 방법
- Big O : O(n)
- indexOf Includes find findIndex 메소드
💡 배열 안의 target 위치를 반환하는 함수 (값이 없는 경우 -1 반환)
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (target === arr[i]) return i;
}
return -1;
}
Big O
- Best : O(1)
- Average : O(n)
- Worst : O(n)
이진 탐색 (Binary Search)
범위를 정해서 그 안에서만 탐색하는 방법
- 데이터가 정렬되어 있어야 함
- 분할 정복 (dividing and conquering)
💡 분류된 배열을 인자로 받아 target의 위치를 반환하는 이진 탐색 함수 (값이 없는 경우 -1 반환)
function binarySearch(arr, target){
let left = 0;
let right = arr.length - 1;
while(right >= left) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] > target) right = mid - 1;
if (arr[mid] < target) left = mid + 1;
}
return -1;
}
Big O
- Best : O(1)
- Average : O(log n)
- Worst : O(log n)
알고리즘 공부가 필요하다고 생각해서 기초부터 다시 시작하고 있는데
구현하는 것에만 초점을 맞춰서 문제를 풀고 있었던 것 같다.
어떤 알고리즘을 선택하는 것이 효율적인지 생각해야 하는데 결과 자체에만 신경을 쓰고 있었기 때문에
그동안 실력이 늘지 않았던 것이 아닐까 하는 생각이 들었다.
앞으로는 어떤 알고리즘을 사용해야 더 효율적으로 구현할 수 있을지에 대해서 더 많이 생각하고 풀어야겠다.
결과보다 과정을 중요시할 수 있도록 열심히 해야징!
'STUDY > Algorithm' 카테고리의 다른 글
연결 리스트 (Linked List) / 단일 연결 리스트, 이중 연결 리스트 (0) | 2023.04.10 |
---|---|
정렬 알고리즘 (Sorting Algorithm) / 버블 정렬, 선택 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 기수 정렬 (2) | 2023.04.07 |
재귀함수 (Recursion Function) / JS (2) | 2023.04.01 |
[프로그래머스_자바스크립트] Lv.2 당구 연습 / math, 좌표 이동, 대칭 (2) | 2023.03.21 |
[프로그래머스_자바스크립트] Lv.1 포켓몬 / 해시 (Hash) (0) | 2023.01.26 |