TIL - 2024.05.14 화요일

· 성취/개선/학습한 내용 🏆

  오늘은 이진 탐색 알고리즘과 Heap 자료구조에 대해 학습을 하였다. 이진 탐색 같은 경우엔 배열의 중간에 있는 임의 값을 기준으로 타깃 값과 비교해서 중간에 있는 임의 값이 타깃 값보다 작으면 우측의 데이터 값들을 대상으로 탐색을 하고, 타깃 값보다 크다면 좌측을 대상으로 탐색하는 탐색 알고리즘이다. 단순히 배열의 index를 0번부터 탐색을 시작하는 것보다 훨씬 시간을 절약할 수 있다. 다만 중요한 점은 데이터가 '정렬'되어 있어야 한다는 조건이 붙는다. 이 조건만 충족한다면 내가 원하는 값을 빠르게 찾을 수 있으며, 구현코드도 간단하다.

func binarySearch<T: Comparable>(_ arr: [T], _ target: T) -> Int? {
  var left = 0
  var right = arr.count - 1
  var mid: Int

  while left <= right {
    mid = (left + right) / 2

    if arr[mid] == target { return mid }
    else if arr[mid] > target { right = mid }
    else { left = mid  }
  }
  return nil
}

 

 Heap 자료구조는 최댓값 or 최솟값 검색을 위한 자료구조이다. 완전 이진 트리라는 자료구조의 특징을 사용하기 때문에 인덱스로 바로 접근이 가능하다!! 따라서 최소힙 혹은 최대힙에 따라 기준을 정하고 힙 성질에 만족할 수 있게 위치를 바꿔줘야 한다.

 

 

• 이진 탐색 알고리즘
• Heap 자료구조

· 어려웠던 내용 😵😵‍💫

• Heap에 대한 원리는 이해를 했다. 하지만 구현 방법에 대해서는 더 고민해봐야 할 것 같다.