본문 바로가기

computer/algorithm

BM25 algorithm 2024. 12. 20. 15:46 BM25는 Elasticsearch의 키워드 검색랭킹 알고리즘으로 유명하다. 어떤 의도로 개발된 방법이고 어떻게 계산되는지 간단하게 알아보자.BM25의 수식은 아래와 같다. IDF부분과 TF부분을 곱하여 계산한다.먼저 간단하게 TF, IDF의 개념에 대해 알아보자.TF(Term Frequency)는 문서에서 단어(term)의 빈도를 뜻한다.문서A: "He is a good boy. She is a bad girl. I am a handsome guy."TF("is", Document(A)) = 2/15 TF("He", Document(A)) = 1/15문서A에서 15개의 단어 중 is이라는 단어는 2번 등장하였다. TF를 기준으로 한번씩 등장한 He나 She보다 더 중요하다고 여겨진다. 그러나 관점을 바..
JSON으로 이미지를 전달하려면 어떻게 할 것인가? 2022. 1. 15. 15:00 남세동님의 질문 2번. JSON으로 이미지를 전달하려면 어떻게 할 것인가?와 하위 질문 a, b를 알아보자. JSON형식은 xml에 뒤이어 발표된 표준형식으로 서버-클라이언트가 텍스트로 데이터를 주고받는데 사용한다. 이미지의 바이너리를 문자열로 변환하고 JSON의 형태로 표현하여 전송하면 된다. 파이썬으로 JSON으로 이미지를 전달해보자. 이미지를 바이너리로 읽은 후 base64로 인코딩을 한다. json.dumps()를 실행할때 딕셔너리에 bytes 타입이 있으면 함수는 type error를 반환하기때문에 decode()를 하여 문자열로 변환하였다. 실행 결과는 그림1과 같다. import base64 import json with open("test_image.png", "rb") as image_f..
PNG에서 투명을 표현하는 방법 2022. 1. 15. 14:53 남세동 대표님이 페이스북 면접질문 리스트에 올린 항목의 내용이다. https://t4716.tistory.com/27 남세동 대표의 면접질문 리스트 석사 졸업전 보이저엑스 인턴 면접에 간적이 있다. 40분가량 세분의 면접관과 기술면접을 진행하였고, 컴퓨터공학 기본기가 매우 약한 나는 빠르게 탈락하였다. 컴퓨터 자체에 대한 관심이 많아 t4716.tistory.com PNG (Portable Network Graphics) 무손실 압축 포맷을 지원한다. 32bit True color를 표현한다. 32bit True color는 RGB를 각각 8bit씩 표현하여 24bit를 사용하고 나머지 8bit로 회색의 정도를 표현하여 투명도를 표현한다. 상세질문으로는 a. 하얀색 바탕위에 반투명 빨간색을 올리면 무슨 ..
백준1260 - DFS와 BFS 2021. 11. 28. 13:57 주어진 경로에 대해 dfs, bfs로 순회한 결과를 출력하는 문제이다. 1. dfs, bfs의 개념을 알고 있는가? 2. 그래프를 어떻게 표현할 것인가? 3. 주어진 그래프 순회 법에서 dfs와 bfs를 어떻게 적용할 것인가? 위 세가지를 알아야 문제를 해결할 수 있다. from collections import deque def dfs(graph, begin, visited_list): b = begin - 1 visited_list.append(b) print(begin, end=' ') for i, v in enumerate(graph[b]): if v == 1 and i not in visited_list: visited_list.append(i) dfs(graph, i + 1, visited_l..
P NP 문제 2021. 8. 16. 16:57 P NP 문제에 공부하던 중 가장 이해가 잘 되었던 포스팅을 복기하기위한 글입니다. https://ratsgo.github.io/data%20structure&algorithm/2017/11/30/NP/ P, NP 문제 (1) · ratsgo's blog P/NP 문제에 대해 명철하고 해박하게 서술한 글을 소개해 보겠습니다. 서울대 컴퓨터공학부 이광근 교수님께서 쓰신 컴퓨터 과학이 여는 세계의 일부를 그대로 옮겨 왔습니다. 워낙 좋은 책이라 ratsgo.github.io P 문제 (p class problem) 현실적(쓸만한)비용으로 해결 가능한 문제들 (polynomial complexity) 문제 해결에 필요한 시간(비용)이 다항시간에 속함 알고리즘 실행비용이 입력 n에 대해 상수 제곱 k의 비용을 ..
해시테이블 구현 - 파이썬 2020. 8. 10. 01:19 ※ 이 자료는 공부를 목적으로 출처에 기입한 여러 자료를 단순히 정리한 것입니다. ※ 출처에 기입한 채널의 코드를 복습하기 위해 재구현하였습니다. import collections class hashMap: def __init__(self): self.size = 1000 self.table = collections.defaultdict(ListNode) def put(self, key: int, value: int) -> None: index = key % self.size if self.table[index].value is None: self.table[index] = ListNode(key, value) return p = self.table[index] while p: if p.key == ke..
해시테이블 구현 - 자바 2020. 8. 10. 01:18 ※ 이 자료는 공부를 목적으로 출처에 기입한 여러 자료를 단순히 정리한 것입니다. ※ 출처에 기입한 채널의 코드를 복습하기 위해 재구현하였습니다. import java.util.LinkedList; class hashTable { class Node{ String key; String value; public Node(String key, String value) { this.key = key; this.value = value; } String getValue() { return value; } void setValue(String value) { this.value = value; } } LinkedList[] data; hashTable(int size) { this.data = new Linked..
해시테이블 개념 2020. 8. 7. 00:45 ※이 자료는 공부를 목적으로 출처에 기입한 여러 자료를 단순히 정리한 것입니다. 해시테이블 해시테이블은 키를 값에 매핑할 수 있는 구조인 연관 배열 ADT를 구현하는 자료구조이다. 컴퓨터는 숫자를 해석하는 것으로 컴퓨터에서 숫자는 해석에 따라 숫자, 글자, 픽셀, 명령어 등으로 나뉜다. 해시테이블은 자료구조 컨테이너 중 모든 것은 숫자로 표현한다는 특성을 이용해 효율적인 삽입, 삭제, 탐색이 가능한 자료구조이다. 해시함수(hash function) 해시 함수는 임의 길이의 데이터를 고정된 길이로 매핑하는 함수이다. 해시 함수의 결과 값을 해시 값, 해시 코드, 해시 체크섬, 간단하게 해시라고 한다. 성능이 좋은 해시 함수의 특징은 아래와 같다. 해시 함수 값 충돌의 최소화 쉽고 빠른 연산 해시 테이블 전..

티스토리툴바