지난 두 편에서 검색의 두 갈래를 따로 살펴봤는데요. BM25 키워드 검색은 단어가 정확히 일치할 때 강하고, 의미 검색은 표현이 달라도 뜻으로 문서를 찾아줍니다. 그리고 두 글 모두 마지막에 "둘을 합치면 어떨까?"라는 떡밥을 남겨뒀죠. 키워드 검색의 정확함과 의미 검색의 유연함을 동시에 누리자는 게 하이브리드 검색(hybrid search)의 아이디어입니다. 말은 간단한데, 막상 합치려고 하면 곧바로 벽에 부딪힙니다. 두 검색기가 내놓는 점수가 완전히 다른 단위거든요. BM25는 0에서 수십까지 제한 없이 커지는 점수를 주고,
검색창에 단어를 넣으면 결과가 주르륵 나오는데요. 그런데 이 결과들의 "순서"는 누가 정하는 걸까요? 단순히 단어가 들어간 문서를 다 모아서 보여주기만 한다면, 정작 내가 찾던 문서는 47번째쯤에 묻혀 있을 수도 있어요. 검색이 쓸모 있으려면 가장 관련 있는 문서가 맨 위로 올라와야 합니다. 이 "관련도 순 정렬"을 책임지는 게 바로 랭킹 함수입니다. 그리고 지난 20여 년간 텍스트 검색의 사실상 표준으로 자리 잡은 랭킹 함수가 바로 BM25예요. Elasticsearch, OpenSearch, Apache Lucene, SQLit
빠른 선택 알고리즘은 여러 값이 주어졌을 때 k 번째로 작은 값이나 큰 값을 찾을 매우 유용한 검색 알고리즘인데요. 보통 이럴 때 정렬을 생각하지만 빠른 선택 알고리즘을 이용하면 배열을 정렬하지 않고도 빠르게 해당 원소를 찾을 수 있습니다. 알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝 아이디어 일반적으로 빠른 선택 알고리즘을 설명할 때 빠른 정렬 (Quick Sort) 알고리즘이 빠지지 않는데요. 이 두 알고리즘은 공통적으로 피봇(pivot)이라고 하는 임의의 값을 기준으로 배열을 분할하는 로직을
정렬된 데이터를 검색할 때 가장 널리 사용되는 이분 탐색(binary search)에 대해서 알아보겠습니다. 알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝 기본 개념 책으로된 영어 사전(요즘은 거의 안 쓰죠? 😓)에서 단어를 찾거나 지역 업소록에서 상호명을 어떻게 찾으시나요? 수백, 수천 페이지가 되는 이러한 책을 맨 첫 페이지부터 한 장씩 넘기면서 찾으시는 분들은 아마 없으실 것입니다. 보통은 대강 중간 쯤 어딘가를 어림잡아서 페이지를 펼쳐본 후에 찾으려는 단어나 업소명과 비교하면서 검색 범위를
가장 널리 알려진 알고리즘 중의 하나인 피보나치(Fibonacci) 알고리즘에 대해서 알아보겠습니다. 알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝 피보나치 수열 피보나치 수열에서는 첫 번째 항은 0, 두 번째 항은 1, 그 다음부터는 바로 전 두 항의 숫자의 합이 현재 항의 값이 됩니다. 따라서 피보나치나 수열은 다음과 같은 모습을 가지게 됩니다. 재귀 알고리즘 피보나치 수열을 구현하는 가장 흔한 알고리즘은 재귀(recursion)를 사용하는 것입니다. 이 재귀 알고리즘의 시간과 공간 복잡도는 모
이번 포스팅에서는 가장 유명한 정렬 알고리즘 중 하나인 퀵 정렬(Quick Sort)에 대해서 알아보겠습니다. 알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝 기본 컨셉 병합 정렬과 마찬가지로 퀵 정렬도 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘입니다. 쉬운 이해를 위해서 다음과 같이 1부터 7까지 총 7개의 숫자가 들어있는 배열을 기준으로 설명하겠습니다. 항상 정 가운데를 기준으로 분할을 하는 병합 정렬과 달리, 퀵 정렬은 흔히 피봇(pivot)이라
![[알고리즘] 병합 정렬 - Merge Sort (Python, Java)](https://i.stack.imgur.com/YlHqG.gif)
대표적인 O(logN) 알고리즘인 병합 정렬(Merge Sort)에 대해서 알아보겠습니다. 알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝 기본 컨셉 병합 정렬은 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용해서 정렬 알고리즘입니다. 즉, 주어진 배열을 원소가 하나 밖에 남지 않을 때까지 계속 둘로 쪼갠 후에 다시 크기 순으로 재배열 하면서 원래 크기의 배열로 합칩니다. 예를 들어, 다음과 같이 1부터 8까지 총 8개의 숫자가 들어있는 배열에 있다고 가정해보겠습니다. 먼
선택 정렬, 거품 정렬과 더불어 대표적인 O(N^2) 정렬 알고리즘인 삽입 정렬(Insertion Sort)에 대해서 알아보겠습니다. 알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝 기본 컨셉 삽입 정렬은 한마디로 표현하면 정렬 범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘입니다. 예를 들어, 다음과 같이 1부터 5까지 총 5개의 숫자가 들어있는 배열에 있다고 가정해보겠습니다. 맨 처음에는 첫번째 2개의 값만 정렬 범위에 포함시키고
선택 정렬(Slection Sort)과 더불어 대표적인 O(N^2) 정렬 알고리즘인 거품 정렬(Bubble Sort)에 대해서 알아보겠습니다. 알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝 기본 컨셉 거품 정렬은 큰 그림에서 보았을 때 뒤에서 부터 앞으로 정렬을 해나가는 구조를 가지고 있습니다. 즉, 맨 뒷자리에 제일 큰 값을 제일 뒤로 보내고, 제일 큰 값 바로 앞에 두번째로 큰 값을 보냅니다. 이를 위해 배열 내의 값들을 앞뒤로 서로 비교해서 자리를 바꾸는 작업을 지속적으로 수행해야 합니다. 이
정렬 알고리즘 중에서 가장 직관적이고 쉽게 구현이 가능한 선택 정렬(Selection Sort)에 대해서 알아보겠습니다. 알고달레에서 코딩 테스트/인터뷰 준비에 좀 더 특화된 컨텐츠를 만나보세요! 📝 기본 아이디어 선택 정렬은 알고리즘에 대해 배워본 적이 없는 사람도 쉽게 생각해낼 수 있는 정렬 알고리즘입니다. 왜냐하면 우리가 일상에서 무언가를 크기 순으로 나열할 때 흔히 사용되는 사고 방식이기 때문입니다. 예를 들어, 위와 같이 키를 알고 있는 네 친구들을 키 순으로 세우려면, 우선 4명의 키를 모두 비교하여 키가 제일 작은 1