[개념] 검색, 탐색 : Algorithm

Ik·2022년 7월 18일
0

Algorithm 

목록 보기
8/18

검색 알고리즘 종류

  • 순차 탐색(Sequential Search)이라고도 부름

  • 배열을 검색하는 방법 가운데 가장 기본적인 알고리즘

  • 무작위로 늘어놓은 데이터 모임에서 검색

  • 정렬되지 않은 리스트에서 데이터를 찾을 때 사용
    • 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

  • 알고리즘은 무조건 종료해야기에
    - 선형 검색의 경우 키 값을 발견하거나, 배열의 끝에 도달했을 경우 종료
    - 키 값에 해당하는 요소 값이 두개 이상인 경우 맨 처음에 위치한 요소 반환

  • 시간 복잡도 : O(N)
    • 판단하는 횟수 평균 N/2회
      - N : 데이터 갯수

  • 보초법 - sentinel method
    • 종료 조건 검사 비용을 줄이기 위해 사용(비용 50% 감소)
      • 키 값을 배열의 마지막 요소로 추가해 배열의 끝을 지나간 경우를 없애 비용 줄임
    • 마지막에 원래 데이터인지 보초인지만 판단






이진(=이분) 검색(binarySearch)

  • 일정한 규칙으로 늘어놓은 데이터 모임에서 빠른 검색
    • 알고리즘을 적용하는 전제 조건은 데이터가 키 값으로 이미 정렬(sort)되어 있다는 것
      - 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘

  • 범위 (시작 요소와 끝 요소, 중앙 요소) 세 가지를 기준으로 중앙 요소와 같아질 때까지 반복해서 갱신하며 키 값을 찾아감
    - 범위가 계속해서 줄어들다 범위가 없기 직전에 선택한 중앙 요소 +-1을 이용해 시작하는 값 or 마지막에 위치한 값 설정해 키 값을 찾음

  • 종료 조건
    - 중앙 요소로 선정된 요소가 키 값과 같은 경우
    - 검색 범위가 더 이상 없는 경우

  • 검색에 필요한 비교 횟수의 평균값은 log2N(검색에 실패할 경우 log2(N+1), 성공할 경우 log2(N-1))

  • 시간 복잡도 : O(log2N)

  • 절반식 줄어든다는 점에서 퀵 정렬과 공통점

  • 구현 방법
    • 재귀 함수
    • 반복문

  • 이진 탐색 트리 관련 : https://velog.io/@sung-ik-je/Tree-%ED%8A%B8%EB%A6%AC

자연 정렬

  • 이진 검색 종류 중에 하나
    • 문자열 정렬과는 다르게 사람이 봤을 때 자연스럽게 정렬이 되어 있는 것
      • 자연 정렬이 되어 있지 않은 경우에는 제네릭 메서드 사용하면 된다

문자열 정렬

  • 동일한 위치에 있는 문자의 대소 비교를 통해 정렬






해시법

  • 추가 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행

체인법 - 같은 해시 값의 데이터를 선형 리스트로 연결

오픈 주소법 - 데이터를 위한 해시 값이 충돌할 때 재해시하는 방법






완전 탐색(Brute Force)

  • 가능한 모든 경우의 수를 다 구해서 값을 찾는 것
    • 컴퓨터의 빠른 성능을 활용
    • 효율성 측면에서는 최악의 방법
  • 가장 확실하지만 그만큼 시간 오래걸림
    • 데이터 큰 경우 계산 오버헤드가 클 수 있음
  • 방법
    • 일반적으로 DFS, BFS 이용해 문제 해결
      - 반복문, 재귀문





DFS

  • Depth First Search, 깊이 우선 탐색
  • 하나의 경우의 수에 대하여 모든 경우의 수를 조사하고 다음 경우의 수를 조사하면서 해를 찾는 과정
    • tree에서 leaf node 도달이 우선, 최대한 멀리 있는 노드 우선 탐색
    • stack 자료구조를 사용하며 노드가 방문되어 있지 않은 경우 한개씩 삽입
  • 소요시간
    • 재귀 > 스택






BFS

  • Breath First Search, 너비 우선 탐색
  • 하나의 경우의 수에 대한 다음 단계의 모든 경우의 수를 조사하면서 해를 찾는 과정
    • tree 구조에서 leaf node가 우선이 아닌 계층이 우선, 가까운 노드 탐색 우선
    • DFS와 달리 QUEUE를 사용하며 방문 안되어 있는 노드들 한 턴에 모두 삽입
  • 일반적인 경우 실제 수행시간 DFS보다 좋은 편





참고

  • 알고리즘 선택에 있어 어떤 목적을 이루기 위해 선택할 수 있는 알고리즘이 여러 가지인 경우에는 용도나 목적, 실행 속도, 자료구조 등을 고려하여 알고리즘을 선택해야 한다
    • ex) 찾는 것과 찾아서 수정하는 것은 목적도 비용도 다르다. 






0개의 댓글