탐색 알고리즘
탐색 알고리즘에는 대표적으로 2가지 종류가 있다.
1. 선형탐색 : 데이터를 처음부터 끝까지 순차적으로 탐색하여 원하는 값을 찾는 알고리즘
2. 이중탐색 : 이진 트리 구조에서 데이터를 탐색하는 알고리즘
선형탐색 예제)
function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i; // 찾은 경우 해당 인덱스를 반환
}
}
return -1; // 못 찾은 경우 -1을 반환
}
이중탐색 예제)
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const midValue = arr[mid];
if (midValue === target) {
return mid; // 타겟 값을 찾은 경우 해당 인덱스를 반환
} else if (midValue < target) {
left = mid + 1; // 중간 값보다 큰 경우 오른쪽 부분 탐색
} else {
right = mid - 1; // 중간 값보다 작은 경우 왼쪽 부분 탐색
}
}
return -1; // 타겟 값을 찾지 못한 경우 -1을 반환
}
정렬 알고리즘
정렬 알고리즘은 말그대로 배열을 정렬시키는건데 여러가지 종류가 있지만 쉬우니깐(?) 설명은 패스하고 대표적인 몇개만 예제로 살펴보겠다.
버블 정렬 예제)
function bubbleSort(arr) {
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 두 요소를 교환
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
선택 정렬 예제)
function selectionSort(arr) {
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 최소값을 현재 위치로 이동
if (minIndex !== i) {
let temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
return arr;
}
퀵정렬 예제)
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return left.concat(pivot, right);
}
삽입정렬 예제)
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; i++) {
let key = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return arr;
}
반응형
'코딩테스트' 카테고리의 다른 글
[코테] 그리디 & 분할 정복 & 해시 알고리즘 예제 (0) | 2024.04.21 |
---|---|
[코테] 그래프 알고리즘 & 동적 계획법 예제 (0) | 2024.03.24 |
[코테] 알고리즘의 종류 (0) | 2024.03.22 |
[JavaScript] 프로그래머스 코딩테스트 ChatGPT 로 풀기 - 2 (0) | 2023.02.27 |
[JavaScript] 프로그래머스 코딩테스트 ChatGPT 로 풀기 - 1 (0) | 2023.02.27 |