본문 바로가기

뇌세포덩어리""/알고리즘

(14)
BM25(Okapi BM25) 바쁘신 분들을 위한 결론 BM25는 단어의 빈도수가 같을 경우 문서의 길이가 길수록 낮은 score를 가진다. 다른 문서에 잘 등장하지 않는 단어 a를 포함한 문서는 a의 빈도수가 높지 않아도 높은 score를 가진다. 같은 단어가 너무 많이 등장하면 낮은 score를 가진다. BM25 : 키워드 기반의 랭킹 알고리즘 BM25(a.k.a Okapi BM25)는 주어진 쿼리에 대해 문서와의 연관성을 평가하는 랭킹 알고리즘으로, TF-IDF 계열의 검색 알고리즘 중 SOTA(State-of-the-art) 엘라스틱서치에서도 ElasticSearch 5.0서부터 기본(default) 유사도 알고리즘으로 BM25 알고리즘을 채택 BM25 살펴보기 BM25는 Bag-of-words 개념을 사용하여 쿼리에 있는 용..
[baekjoon] dijkstra 문제들 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net https://www.acmicpc.net/problem/1835..
[leetcode] dijkstra https://leetcode.com/problems/network-delay-time/description/ Network Delay Time - LeetCode Network Delay Time - You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a leetcode.com https://leetcode.com/problems/path-wi..
[leetcode] dfs / bfs 재밌는 문제들 https://leetcode.com/problems/surrounded-regions/ Surrounded Regions - LeetCode Surrounded Regions - Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. Example 1: [https://assets.leetcode. leetcode.com https://leetcode.com/problems/count-servers-that-com..
[leetcode] dfs/bfs 섬 문제들 https://leetcode.com/problems/number-of-islands/ Number of Islands - LeetCode Number of Islands - Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may ass leetcode.com https://leetcode.com/problems/island-perimeter/ Is..
문자열 검색 알고리즘 ( Brute force search / 라빈 카프 / KMP / Boyer-Moore) 서문 https://leetcode.com/problems/implement-strstr/ 의 문제를 풀면서 의문이 들었다. 해당 문제는 이중 for문을 사용하면 timeout이 발생한다. python로 문제를 푼다면 find 함수를 사용하여 간단히 풀 수 있다. 각 언어별로 find(text, pattern)는 (문자열 text에 특정 문자열 pattern의 위치를 리턴하는 함수)가 있을텐데 pytho은 "어떤 알고리즘을 사용하길래 문자열을 빠르게 찾는걸까?"에서 시작했다. 언어별 결과를 빠르게 알고 싶다면 글의 마지막 번외를 보시면 됩니다. 문자열 검색 알고리즘에 어떤것들이 있는지, 차근차근 공부를 해보는 문서이다. 1. Brute force search 무차별 문자열 검색은 매우 기본적인 하위 문자..
탐색 (선형 / 이진 / 이진트리) def linear_search(list, find_key): for i in range(len(list)): if list[i] == find_key: return i return "not find" def binary_search(list, find_key): mid = len(list)//2 while True: if list[mid] == find_key: return mid elif list[mid] = len(list): mid = len(list)-1 else: mid -= mid/2 if mid/2 == 0: mid = 0 class binary_tree: value = 0 left = None right = None def __i..
정렬 알고리즘 ( 버블 / 선택 / 삽입 / 퀵) 파이썬을 간단하게 짠 정렬들... 원리만 알면 구하기 쉬움. def bubble(list): for i in range(len(list)): for j in range(len(list)): if list[i] list[j]: min_temp = j list[i], list[min_temp] = list[min_temp], list[i] return list def insertion(list): for i ..