알고리즘 검색 데이터 모음 내에서 특정 항목을 찾는 데 사용되는 컴퓨터 과학의 필수 도구입니다. 이러한 알고리즘은 데이터 구조를 효율적으로 탐색하여 원하는 정보를 찾도록 설계되어 다음과 같은 다양한 응용 프로그램의 기본이 됩니다. 데이터베이스, 웹 검색 엔진 , 그리고 더.

검색 알고리즘

e-r 모델 다이어그램

내용의 테이블

• 검색이란 무엇입니까?
• 용어 검색
• DSA 검색의 중요성
• 검색의 응용
• 검색 알고리즘의 기본
• 알고리즘 검색
• 다양한 검색 알고리즘 간의 비교
• 검색 알고리즘의 라이브러리 구현
• 검색에 대한 쉬운 문제
• 검색에 대한 중간 문제
• 검색에 대한 어려운 문제

검색이란 무엇입니까?

검색은 기본 프로세스입니다. 데이터 모음 내에서 특정 요소나 항목 찾기 . 이 데이터 컬렉션은 배열, 목록, 트리 또는 기타 구조화된 표현과 같은 다양한 형태를 취할 수 있습니다. 검색의 주요 목적은 원하는 요소가 데이터 내에 존재하는지 확인하고, 그렇다면 정확한 위치를 식별하거나 검색하는 것입니다. 정보 검색, 데이터 분석, 의사 결정 프로세스 등을 포함한 다양한 계산 작업과 실제 응용 프로그램에서 중요한 역할을 합니다.

용어 검색:

대상 요소:

검색에는 항상 데이터 컬렉션 내에서 찾으려는 특정 대상 요소나 항목이 있습니다. 이 대상은 값, 레코드, 키 또는 기타 관심 있는 데이터 엔터티일 수 있습니다.

검색 공간:

검색 공간은 대상 요소를 찾고 있는 전체 데이터 모음을 나타냅니다. 사용된 데이터 구조에 따라 검색 공간의 크기와 구성이 달라질 수 있습니다.

복잡성:

검색은 사용된 데이터 구조와 알고리즘에 따라 복잡도 수준이 다를 수 있습니다. 복잡성은 종종 시간 및 공간 요구 사항 측면에서 측정됩니다.

결정론적 대 비결정론적:

다음과 같은 일부 검색 알고리즘 이진 검색 , 결정론적입니다. 즉, 명확하고 체계적인 접근 방식을 따릅니다. 선형 검색과 같은 다른 검색은 최악의 경우 전체 검색 공간을 조사해야 할 수 있으므로 비결정적입니다.

100만 중 10은 뭐야?

DSA 검색의 중요성:

• 능률: 효율적인 검색 알고리즘은 프로그램 성능을 향상시킵니다.
• 데이터 검색: 대규모 데이터 세트에서 특정 데이터를 빠르게 찾고 검색합니다.
• 데이터베이스 시스템: 데이터베이스를 빠르게 쿼리할 수 있습니다.
• 문제 해결: 광범위한 문제 해결 작업에 사용됩니다.

검색의 응용:

검색 알고리즘은 다양한 분야에 걸쳐 수많은 응용 프로그램을 가지고 있습니다. 다음은 몇 가지 일반적인 응용 프로그램입니다.

• 정보 검색: Google, Bing, Yahoo와 같은 검색 엔진은 정교한 검색 알고리즘을 사용하여 웹에 있는 방대한 양의 데이터에서 관련 정보를 검색합니다.
• 데이터베이스 시스템: 검색은 사용자 쿼리를 기반으로 특정 데이터 레코드를 검색하여 데이터 검색 효율성을 향상시키는 데이터베이스 시스템의 기본입니다.
• 전자상거래: 검색은 사용자가 선호도, 사양 또는 키워드를 기반으로 제품을 빠르게 찾는 전자상거래 플랫폼에서 매우 중요합니다.
• 네트워킹: 네트워킹에서 검색 알고리즘은 네트워크를 통해 패킷을 효율적으로 라우팅하고, 최적의 경로를 찾고, 네트워크 리소스를 관리하는 데 사용됩니다.
• 인공지능: 검색 알고리즘은 문제 해결, 게임 플레이(예: 체스), 의사 결정 프로세스 등 AI 애플리케이션에서 중요한 역할을 합니다.
• 패턴 인식: 검색 알고리즘은 이미지 인식, 음성 인식, 필기 인식 등의 패턴 일치 작업에 사용됩니다.

검색 알고리즘의 기본:

• 검색 소개 – 데이터 구조 및 알고리즘 튜토리얼
• 데이터 구조에서 검색의 중요성
• 검색 알고리즘의 목적은 무엇입니까?

검색 알고리즘:

• 선형 검색
• 센티넬 선형 검색
• 이진 검색
• 메타 바이너리 검색 | 단방향 이진 검색
• 삼항 검색
• 점프 검색
• 보간 검색
• 지수 검색
• 피보나치 검색
• 유비쿼터스 이진 검색

다양한 검색 알고리즘 간의 비교:

• 선형 검색과 이진 검색
• 보간 검색과 이진 검색
• 삼항 검색보다 이진 검색이 선호되는 이유는 무엇입니까?
• Sentinel 선형 검색이 일반 선형 검색보다 나은가요?

검색 알고리즘의 라이브러리 구현:

• C++ STL의 이진 검색 기능(binary_search, lower_bound 및 upper_bound)
• 예제가 포함된 Java의 Arrays.binarySearch() | 세트 1
• 예제가 포함된 Java의 Arrays.binarySearch() | 세트 2(하위 배열에서 검색)
• 예제가 포함된 Java의 Collections.binarySearch()

검색에 대한 쉬운 문제:

• 배열에서 가장 큰 세 개의 요소 찾기
• 누락된 숫자 찾기
• 정수 배열에서 첫 번째 반복 요소 찾기
• 누락되고 반복되는 숫자 찾기
• 정렬된 배열에서 검색, 삽입 및 삭제
• 정렬된 이진 배열에서 1 개수
• 합이 0에 가장 가까운 두 요소
• 주어진 차이가 있는 쌍 찾기
• k 배열의 가장 큰(또는 가장 작은) 요소
• 행 방향 및 열 방향으로 정렬된 2D 배열에서 K번째로 작은 요소
• 세 개의 정렬된 배열에서 공통 요소 찾기
• 정렬된 배열의 천장
• 정렬된 배열의 바닥
• 배열에서 먼저 증가한 다음 감소하는 최대 요소를 찾습니다.
• 크기가 n이고 숫자가 k인 배열이 주어지면 n/k번 이상 나타나는 모든 요소를 ​​찾습니다.

검색에 대한 중간 문제:

• 제로섬이 있는 모든 삼중항 찾기
• 이전의 모든 요소가 그보다 작고 그 이후의 모든 요소가 더 큰 요소를 찾습니다.
• 정렬되지 않은 배열에서 가장 큰 쌍 합계 찾기
• 정렬되지 않은 배열에서 K번째 최소/최대 요소
• 정렬 및 회전된 배열에서 요소 검색
• 정렬되고 회전된 배열에서 최소 요소 찾기
• 피크 요소 찾기
• 최소 비교 횟수를 사용하는 배열의 최대 및 최소
• 주어진 배열에서 고정점 찾기
• 파일에서 가장 자주 사용되는 k개의 단어 찾기
• 주어진 값에 가장 가까운 k개의 요소 찾기
• 정렬된 배열과 숫자 x가 주어지면 합계가 x에 가장 가까운 배열에서 쌍을 찾습니다.
• 두 개의 정렬된 배열에서 가장 가까운 쌍을 찾습니다.
• 주어진 3개의 정렬된 배열에서 가장 가까운 3개의 요소를 찾습니다.
• 부동 소수점 연산을 사용하지 않고 유리수에 대한 이진 검색

검색의 어려운 문제:

• 두 개의 정렬된 배열의 중앙값
• 서로 다른 크기로 정렬된 두 배열의 중앙값
• 거의 정렬된 배열에서 검색
• 정렬된 무한 숫자 배열에서 요소의 위치 찾기
• 정렬되고 회전된 배열이 주어지면 주어진 합계를 가진 쌍이 있는지 찾습니다.
• 정렬되지 않은 배열에서 K번째 최소/최대 요소 | 최악의 경우 선형 시간
• 스트림에서 K번째로 큰 요소
• 최선의 우선 검색(정보 검색)

빠른 링크:

• 검색에 관한 '연습 문제'
• 검색 시 '퀴즈'

권장사항:

• 데이터 구조와 알고리즘 배우기 | DSA 튜토리얼