🗒️ 탐색 (4)

1. 2022.06.29 [Python] 탐색(Search)

   탐색(Search) 탐색의 기본 개념 탐색(Search) : 어떤 집합에서 원하는 것을 찾는 것으로 검색이라고 한다. 탐색의 종류 순차 탐색(Sequential Search) 이진 탐색(Binary Search) 트리 탐색(Tree Search) 검색 결과로 특정 집합의 위치인 인덱스를 알려 준다. 검색에 실패하면(찾는 데이터가 집합에 없다면) -1을 반환하는 것이 일반적이다. 탐색 알고리즘의 종류 탐색은 데이터 상태에 따라 다양한 알고리즘을 사용할 수 있다. 탐색할 집합이 정렬되어 있지 않은 상태라면 순차 탐색을 해야 한다. 순차 탐색(Sequential Search) 순차 탐색은 처음부터 끝까지 차례대로 찾아보는 것으로, 쉽지만 비효율적인 탐색 방법이다. 하지만, 집합의 데이터가 정렬되어 있지 않다면..
2. 2021.05.29 [C++] 선형 탐색(Linear Search), 이진 탐색(Binary Search)

   선형 탐색(Linear Search), 이진 탐색(Binary Search) 선형 탐색(Linear Search) 시퀀스 전체 원소를 방문하면서 해당 원소가 N과 같은지 확인 다음과 같은 코드로 구현할 수 있음. bool linear_search(int N, std::vector& sequence) { for (auto i : sequence) { if (i == N) { return true; // 찾음! } } return false; } 장점 입력 시퀀스의 정렬 여부와 상관없이 항상 잘 동작함. 단점 효율적이지 않음. 주어진 배열이 정렬되어 있다는 점을 전혀 이용하지 못함. 시간 복잡도 : O(N) 이진 탐색(Binary Search) 주어진 시퀀스가 정렬되어 있다는 사실을 이용하여 검색하는 방법 ..
3. 2021.05.22 [C++] 뻐꾸기 해싱(Cuckoo Hashing)

   뻐꾸기 해싱(Cuckoo Hashing) 크기가 같은 2개의 해시 테이블을 사용함. 각각의 해시 테이블은 서로 다른 해시 함수 를 가짐. 모든 원소는 두 해시 테이블 중 하나에 있을 수 있음. 위치는 해당 해시 테이블의 해시 함수 에 의해 결정됨. 뻐꾸기 해싱이 다른 해싱 기법과 다른 점 원소가 두 해시 테이블 중 어디든 저장될 수 있음. 원소가 나중에 다른 위치로 이동할 수 있음. 다른 해싱 방법에서는 재해싱을 수행하지 않는 이상 원소가 최초 삽입된 위치에서 다른 위치로 이동할 수 없음. 그러나, 뻐꾸기 해싱 방법에서는 모든 원소가 2개의 저장 가능한 위치를 가지며, 상황에 따라 이동할 수 있음. 더 나은 성능을 얻고, 재해싱 빈도를 줄이기 위해 저장 가능한 위치 개수를 증가 시킬 수도 있음. 룩업 연..
4. 2017.06.21 [C] 탐색(Search)

   탐색(Search) [탐색이란?] - 탐색(search)은 컴퓨터가 가장 많이 하는 작업 중의 하나임. - 탐색은 컴퓨터 프로그램에서 가장 많이 사용하는 작업임과 동시에 많은 시간이 요구되므로 탐색을 효율적으로 수행하는 것은 매우 중요함. - 탐색은 기본적으로 여러 개의 자료 중에서 원하는 자료를 찾는 작업. - 탐색을 위하여 사용되는 자료 구조는 배열, 연결 리스트, 트리, 그래프 등 매우 다양할 수 있음. - 탐색 중에서 가장 기초적인 방법은 배열을 사용하여 자료를 저장하고 찾는 것. - 그러나 탐색 성능을 향상하고자 한다면 이진 탐색 트리와 같은 더욱 진보된 방법으로 자료를 저장하고 탐색해야 함. - 탐색의 단위는 항목이며, 항목은 간단하게 숫자일 수도 있고, 아니면 구조체가 될 수도 있음. - 항..