[algorithm] 탐색 알고리즘

• 탐색의 개념
  
  • 여러 데이터 중에서 원하는 값을 가진 데이터를 찾는 것
  • 데이터 형태 -> 리스트, 트리, 그래프 등
  • 내부탐색 vs 외부탐색
  • 연산 -> 탐색 + 초기화(정렬), 삽입, 삭제 등
  • 순차 탐색
    • 리스트 형태로 주어진 원소들에 대해서 처음부터 하나씩 차례대로 비교하면서 원하는 값을 가진 원소를 찾는 방법
    • 탐색 실패의 경우 -> 항상 n번 비교 O(n)
    • 탐색 성공의 경우 -> 최소 1번 ~ 최대 n번 비교 O(n)
    • 삽입 -> O(1)
    • 삭제 -> O(n)
      • 삭제할 데이터에 대한 탐색이 필요
    • 특징
      • 모든 리스트에 적용 가능
        • 원소가 무순서로 연속해서 저장된 비정렬 데이터 탐색에 적합
      • 데이터가 큰 경우에는 부적합
        • 탐색과 삭제 -> O(n)
  • 이진 탐색
    • 개념과 원리
      • 정렬된 배열 형태로 주어진 원소들을 절반씩 줄여가면서 원하는 값을 가진 원소를 찾는 방법
        • 분할정복 방법
      • 탐색 방법
        • 배열의 가운데 원소 A[mid]와 탐색키 x를 비교
          • 탐색키 = 가운데 원소 -> 탐색 성공(인덱스 mid 반환 후 종료)
          • 탐색키 < 가운데 원소 -> 이진 탐색(원래 크기 1/2인 왼쪽 부분배열) 순환 호출
          • 탐색키 > 가운데 원소 -> 이진 탐색(원래 크기 1/2인 오른쪽 부분배열) 순환 호출
          • 탐색을 반복할 때마다 대상 원소의 개수가 1/2씩 감소
        • T(n) = T(n/2) + O(1) (n>1), T(1) = 1 => T(n) = O(logn)
      • 초기화 알고리즘의 성능: O(nlogn)
      • 삽입 알고리즘
        • 이진탐색 후 자료가 삽입 될 위치를 찾은 후(O(logn)) 해당 위치에 있는 자료부터 뒤에 있는 자료들을 하나씩 뒤로 이동시킨다(O(n))
        • 성능: O(n)
      • 삭제 알고리즘
        
        • 이진탐색 후 자료가 삽입 될 위치를 찾은 후(O(logn)) 해당 위치에 있는 자료부터 뒤에 있는 자료들을 하나씩 앞으로 이동시킨다(O(n))
        • 성능: O(n)
      • 삽입/삭제 연산_ 연결 리스트로 구현한 경우
        • 연결 리스트의 경우 인덱스로 접근할 수 없으므로 이진 탐색 자체가 불가능함
      • 성능 분석
        • 탐색 -> O(logn)
        • 초기화 -> O(nlogn)
        • 삽입, 삭제 -> O(n)
      • 특징
        • 정렬된 리스트에 대해서만 적용 가능
        • 삽입과 삭제가 빈번한 경우에는 부적합
          • 삽입/삭제 후 입력 리스트의 정렬 상태를 유지하기 위해서 O(n)의 자료 이동이 필요
  • 이진 탐색 트리
    • 개념과 원리
      • 이진 트리
      • 각 노드의 왼쪽 서브트리에 있는 모든 키값은 그 노드의 키값보다 작다.
      • 각 노드의 오른쪽 서브트리에 있는 모든 키값은 그 노드의 기값보다 크다.
      • 탐색 알고리즘
        • 루트 노드로부터 시작해서 크기 관계에 따라 트리의 경로를 따라 내려가면서 탐색을 수행
      • 삽입 알고리즘
        • 삽입할 원소를 탐색한 후, 탐색이 실패하면 해당 위치에 자식 노드로 추가
      • 삭제 연산
        • 후속자successor, 계승자 노드
          • 어떤 노드의 바로 다음 키값을 갖는 노드
        • 삭제되는 노드의 자식 노드의 개수에 따라 구분해서 처리
          • 자식 노드가 없는 경우(리프 노드의 경우)
            • 남는 노드의 위치 조절이 불필요
          • 자식 노드가 하나인 경우
            • 자식 노드를 삭제되는 노드의 위치로 올리면서 서브트리 전체도 따라 올린다.
          • 자식 노드가 두개인 경우
            • 삭제되는 노드의 후속자 노드를 삭제되는 노드의 위치로 올리기
            • 후속자 노드를 삭제되는 노드로 취급하여 자식 노드의 개수에 따라 다시 처리
      • 성능 분석
        • 탐색, 삽입, 삭제의 시간 복잡도
          • 키값을 비교하는 횟수에 비례 -> 이진 트리가 높이가 h라면 O(h)
          • 모든 노드의 차수가 2인 경우(리프노드 제외): 모든 노드들이 루트노드에 가장 가깝게 붙음
            • 평균 수행 시간: O(logn)
          • 모든 노드의 차수가 1인 경우(리프노드 제외) = 경사이진트리
            • 최악 수행 시간 O(n)
      • 특징
        • 삽입/삭제 연산 시 기존 노드의 이동이 거의 발생하지 않음
        • 원소의 삽입/삭제에 따라 경사 트리 형태가 될 수 있어 비효율적일 가능성이 있음
          • 최악의 수행 시간 O(n)
            • 경사 트리가 되지 않도록 균형을 유지해서 O(logn)을 보장 -> 균형 탐색 트리(흑적 트리, B-트리)
  • 정리
    • 탐색의 개념
      • 내부탐색, 연산(초기화, 탐색, 삽입, 삭제)
      • 종류: 순차 탐색, 이진 탐색, 이진 탐색 트리, 흑적 트리, B-트리, 해싱
    • 순차 탐색
      • O(n), 모든 리스트에 적용 가능 -> 비정렬 데이터 탐색에 적합
    • 이진 탐색
      • O(logn), 정렬된 배열에 대해서만 적용 가능 -> 삽입/삭제가 빈번한 응용에는 부적합
      • 연결리스트는 이진 탐색 불가능
    • 이진 탐색 트리
      • 개념, 연산 -> 탐색, 삽입, 삭제(자식 노드의 개수에 따라 구분해서 적용)
      • 평균/최선 O(logn), 최악 O(n)