Searching Algorithm

semin·2023년 6월 22일
algorithm
0
post-thumbnail

이진 탐색(Binary Search)

특징정렬 배열에서 사용 가능, 범위를 반으로 나눠서 탐색하는 방식
장점신속함
단점정렬 배열에서 효율적. 삽입, 삭제 등 동적인 작업에는 부적합
안정성안정
체크 요소탐색 대상의 정렬 상태
시간 복잡도O(logN)
function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1; // 탐색 실패
}

// Ex
const arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
const target = 12;
const result = binarySearch(arr, target);
if (result !== -1) {
  console.log("탐색 성공! 인덱스:", result);
} else {
  console.log("탐색 실패!");
}

해시 테이블(Hash Table)

특징해시 함수로 데이터를 해시 테이블에 저장, 상수 시간 내 탐색
장점매우 신속. 데이터 크기에 관계없는 상수 시간 복잡도
단점해시 충돌 위험성. 해시 함수의 성능과 충돌 처리 방법에 따른 성능 영향. 순서 보장 X
안정성안정적이나 순서가 보장되지 않음
체크 요소충돌 처리 가능한 공간, 해시 함수 성능
시간 복잡도평균: O(1), 최악: O(N) - 해시 충돌의 경우
class HashTable {
  constructor(size) {
    this.size = size;
    this.table = new Array(size).fill(null);
  }

  hashFunction(key) {
    return key % this.size;
  }

  insert(key, value) {
    const index = this.hashFunction(key);
    if (this.table[index] === null) {
      this.table[index] = [];
    }
    this.table[index].push({ key, value });
  }

  search(key) {
    const index = this.hashFunction(key);
    if (this.table[index] !== null) {
      for (const item of this.table[index]) {
        if (item.key === key) {
          return item.value;
        }
      }
    }
    return null;
  }
}

// Ex
const hashTable = new HashTable(10);
hashTable.insert(5, "Apple");
hashTable.insert(15, "Banana");
hashTable.insert(25, "Orange");

console.log(hashTable.search(15)); // 출력: Banana
console.log(hashTable.search(10)); // 출력: null (탐색 실패)

선형 탐색(Linear Search)

특징배열의 모든 요소를 순차적으로 탐색
장점간단. 비정렬 배열에 사용 가능
단점최악: O(N) - 선형 증가
안정성안정
체크 요소큰 배열의 경우 성능 저하
시간 복잡도O(N)
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1; // 탐색 실패
}

// Ex
const arr = [3, 1, 5, 2, 4];
const target = 5;
const result = linearSearch(arr, target);
if (result !== -1) {
  console.log("탐색 성공! 인덱스:", result);
} else {
  console.log("탐색 실패!");
}

순차 탐색(Sequential Search)

특징연결 리스트 같은 순차 구조에서 요소를 하나씩 탐색
장점간단, 비정렬 데이터 구조에 사용 가능
단점최악: O(N) - 선형 증가
안정성안정
체크 요소탐색하는 데이터 구조 특성에 따른 성능 변동
시간 복잡도O(N)
function sequentialSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1; // 탐색 실패
}

// Ex
const arr = [3, 1, 5, 2, 4];
const target = 5;
const result = sequentialSearch(arr, target);
if (result !== -1) {
  console.log("탐색 성공! 인덱스:", result);
} else {
  console.log("탐색 실패!");
}

B-트리(B-Tree)

특징해시 함수로 대용량의 데이터를 해시 테이블에 저장, 상수 시간 내에 탐색
장점대용량 데이터에서도 신속
단점해시 충돌 위험성, 해시 함수 성능과 충돌 처리 방법에 따른 성능 변동. 순서 보장 X
안정성안정적이나 순서가 보장되지 않음
체크 요소충돌 처리 가능한 공간, 해시 함수 성능
시간 복잡도평균: O(1), 최악: O(N)
class BTreeNode {
  constructor(order) {
    this.order = order;
    this.keys = [];
    this.children = [];
  }

  isLeaf() {
    return this.children.length === 0;
  }
}

class BTree {
  constructor(order) {
    this.order = order;
    this.root = new BTreeNode(order);
  }

  insert(key) {
    if (this.root.keys.length === 2 * this.order - 1) {
      const newRoot = new BTreeNode(this.order);
      newRoot.children.push(this.root);
      this.splitChild(newRoot, 0, this.root);
      this.root = newRoot;
    }
    this.insertNonFull(this.root, key);
  }

  insertNonFull(node, key) {
    let i = node.keys.length - 1;
    if (node.isLeaf()) {
      while (i >= 0 && key < node.keys[i]) {
        node.keys[i + 1] = node.keys[i];
        i--;
      }
      node.keys[i + 1] = key;
    } else {
      while (i >= 0 && key < node.keys[i]) {
        i--;
      }
      i++;
      if (node.children[i].keys.length === 2 * this.order - 1) {
        this.splitChild(node, i, node.children[i]);
        if (key > node.keys[i]) {
          i++;
        }
      }
      this.insertNonFull(node.children[i], key);
    }
  }

  splitChild(parent, index, child) {
    const newChild = new BTreeNode(this.order);
    const middleIndex = Math.floor(this.order / 2) - 1;

    for (let i = middleIndex + 1; i < child.keys.length; i++) {
      newChild.keys.push(child.keys[i]);
    }
    child.keys.length = middleIndex + 1;

    if (!child.isLeaf()) {
      for (let i = middleIndex + 1; i < child.children.length; i++) {
        newChild.children.push(child.children[i]);
      }
      child.children.length = middleIndex + 1;
    }

    parent.keys.splice(index, 0, child.keys.pop());
    parent.children.splice(index + 1, 0, newChild);
  }
}

// Ex
const bTree = new BTree(2);
bTree.insert(4);
bTree.insert(8);
bTree.insert(15);
bTree.insert(7);
bTree.insert(12);
console.log(bTree.root); // BTreeNode 객체 출력

B트리는 강의도 몇 개 보고 chat GPT한테 예시 코드를 물어봐도 정말 모르겠다.
모르는 걸 왜 블로깅하냐?
나중에 내가 이 시점에는 이걸 몰랐다는 것을 알기 위해서...

데일리 코딩 풀이나 하겠습니다

29번~ 회전된 배열에서의 이진 탐색~

rotatedArraySearch

문제

부분적으로 오름차순 정렬*된 정수의 배열(rotated)과 정수(target)를 입력받아
target의 인덱스를 리턴해야 합니다.

부분적으로 정렬된 배열
배열을 왼쪽 혹은 오른쪽으로 0칸 이상 순환 이동할 경우 완전히 정렬되는 배열

예시
[4, 5, 6, 0, 1, 2, 3]은 왼쪽으로 3칸 또는 오른쪽으로 4칸 순환 이동할 경우 완전히 정렬됩니다.

입력

인자 1인자 2
rotatedtarget
number 타입을 요소로 갖는 배열number 타입의 정수
rotated[i]는 정수

출력
number 타입을 리턴해야 합니다.

주의사항
rotated에 중복된 요소는 없습니다.
target이 없는 경우, -1을 리턴해야 합니다.

풀이 & 의사코드

  1. 반복문 내부에서 i++ 탐색, 찾으면 인덱스 i
  2. 못 찾으면 -1
const rotatedArraySearch = function (rotated, target) {
  for (let i = 0; i < rotated.length; i++) {
    if (rotated[i] === target) {
      return i;
    }
  }
  return -1;
};

1.left: 0, right: arr.length - 1

2.left <= right 일 때 반복

3.mid: (left + right) / 2

4-0. rotated[mid] === target ? return mid

4-1. rotated[left] <= rotated[mid] ? 왼쪽 배열 정렬됨
4-1-1. rotated[left] < target < rotated[mid] ? right = mid - 1
4-1-2. else ? left = mid + 1

4-2. rotated[mid] < rotated[right] ? 오른쪽 배열 정렬됨
4-2-1. rotated[mid] < target < rotated[right] ? left = mid + 1
4-2-2. else? right = mid - 1

4-3. 반복 종료
5. target 없으면 ? return -1

const rotatedArraySearch = function (rotated, target) {
  // TODO : 여기에 코드를 작성합니다.
  let left = 0;
  let right = rotated.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (rotated[mid] === target) {
      return mid;
    }

    if (rotated[left] <= rotated[mid]) {
      if (target >= rotated[left] && target < rotated[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (target > rotated[mid] && target <= rotated[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
};

애초에 힌트로 이진 탐색을 줘서 어드밴스드 버전으로 먼저 풀어 봤다.
이진 탐색이랑 비슷하긴 한데 추가 조건문으로 배열이 회전됐다는 걸 고려하면 됐다.
mid vs 타겟 비교, mid의 좌우 배열 중에서 탐색했다.
조건이 생각보다 많아서 좀 당황했다...
그래서 진짜 처음에 작성한 의사 코드는

  1. left, right 선언 (초기화)
  2. loop
    2-0. left && right 업데이트
    2-1. 만약 left와 right가 범위 밖이다? 반복 종료, 리턴 -1
    2-2. mid 계산
    2-3. 만약 mid가 타겟이다? 리턴 mid
    2-4. left / right 업데이트 조건 설정 필요
  3. 반복 종료.
    3-1. else 처리: 리턴 -1

이거였다. 이렇게 적으니까 좀 괜찮긴 했는데...
아니... 기계처럼 생각하기 너무 어렵네?

profile
semin
이전 포스트

UI UX, 왜 같이 부르지?

다음 포스트

balancedBrackets

0개의 댓글

관련 채용 정보