코딩 공부 50

**연산자에대한 고찰

**연산자는 거듭제곱을 해주는 연산자이다 2^50을 2**50으로 쓸 수 있다. 나는 2**50은 let result = 1; let base = 2; for (let i = 0; i < 50; i++) { result *= base; } 과 마찬가지로 50번 반복을 할 줄알았는데 for 반복문, **연산자와 내가 쓴 거듭제곱의 시간복잡도를 O(logN)으로 줄이는 알고리즘 거듭제곱 시간복잡도 줄이기 거듭제곱이란 base^exponent의 형태인데 예를들어 2^50이면 2를 50번 곱하는것이며 반복되는 횟수는 50번이다 for문으로 나타낸다면 let result = 1 for(let i = 0 ; i < exponent; i++){ result *= base } consol.. fullfish.tisto..

Hash와 Salt 그리고 Bcrypt

기본 용어 hash : 다양한 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는것 digest : hash에 의해 암호화된 데이터 avalanche(눈사태) 효과 : 작은 변화에도 결과가 완전히 달라짐 rainbow 공격 : 공격자가 rainbow table을 이용해서 원본 데이터 찾는것 rainbow table : 원본 데이터와 매칭되는 digest들을 모아놓은 테이블 salt : digest 생성시 추가하는 임의의 문자열 brute force : 무차별 대입 공격 개념 hash란 일반적으로 자료구조에서 검색을 할때는 선형적으로 검색하므로 시간복잡도가 O(n)이다. 해시를 쓰면 John Smith를 특정 해시함수를 통해 나온 값을 (여기서는 02)인덱스로 사용해서 저장한다 그러므로 시간복잡도가 O(..

socket.io

socket.io를 이용해서 실시간 채팅 구현하기 서버 코드 //index.js var app = require('express')(); var server = require('http').createServer(app); // http server를 socket.io server로 upgrade한다 var io = require('socket.io')(server); // localhost:3000으로 서버에 접속하면 클라이언트로 index.html을 전송한다 app.get('/', function(req, res) { res.sendFile(__dirname + '/index.html'); }); // connection event handler // connection이 수립되면 event hand..

구글 맵 API

https://console.cloud.google.com/google/maps-apis/start?hl=ko Google Cloud Platform 하나의 계정으로 모든 Google 서비스를 Google Cloud Platform을 사용하려면 로그인하세요. accounts.google.com 우선 해당 링크에 들어가서 로그인 및 다음 절차들을 완료해준다 구글 맵 api가 기본적으로는 유료지만 한달 200달러까지는 무료이며 api로 위치만 받아오는 행위는 1회에 0.007달러라서 사실상 공부목적으로 사용한다면 무료나 마찬가지이다 기본적인 코드 위도, 경도에다가 위도, 경도를 입력해준후에 API_KEY에 본인 key값을 입력해주면된다 zoom은 처음 떳을때의 확대정도인데 개인적으로 17정도가 적당해보인다 ..

n-Gram 개선 및 고찰

자음 모음단위로 n-Gram 저번에 구현한 n-gram https://fullfish.tistory.com/109 n-Gram n-Gram이란 문장의 유사도를 비교하는 방법중 하나로 문장을 쪼개서 비교한다 예를 들어 3-gram으로 '과자중에 제일 맛있는건 새우깡' '제일 맛있는 과자는 무엇일까' 이 두문장을 비교한다면 각 문 fullfish.tistory.com 에서는 글자를 음절 단위로 잘라서 썼었다 예를 들어 안녕하세요를 3-Gram으로 한다면 ['안녕하', '녕하세', '하세요']로 나눴는데 활용하기 나름이지만 이번에는 자음 모음단위로 나뉘어 봤다 ['ㅇㅏㄴ', 'ㅏㄴㄴ', 'ㄴㄴㅕ' ...] 해당 방법의 장점은 오타나 어미가 달라도 검색이 될 가능성이 높아지게끔 허들을 낮출 수 있다 우선은 문자..

n-Gram

n-Gram이란 문장의 유사도를 비교하는 방법중 하나로 문장을 쪼개서 비교한다 예를 들어 3-gram으로 '과자중에 제일 맛있는건 새우깡' '제일 맛있는 과자는 무엇일까' 이 두문장을 비교한다면 각 문장을 3글자씩 자른다. "과자중에 제일 맛있는건 새우깡" [ '과자중', '자중에', '중에 ', '에 제', ' 제일', '제일 ', '일 맛', ' 맛있', '맛있는', '있는건', '는건 ', '건 새', ' 새우', '새우깡' ] "제일 맛있는 과자는 무엇일까" [ '제일 ', '일 맛', ' 맛있', '맛있는', '있는 ', '는 과', ' 과자', '과자는', '자는 ', '는 무', ' 무엇', '무엇일', '엇일까' ] 그리고 각 요소를 비교해서 유사도를 측정한다 https://too-marc..

레벤슈타인 거리 시간복잡도와 공간복잡도 개선

이전 게시물 레벤슈타인 거리 (Levenshtein Distance) 레벤슈타인 거리란 문자열의 유사도를 검사하는 기본적인 알고리즘으로 편집 거리라고도 부름 a문자열에서 b문자열로 편집할때 몇번의 조작이 필요한지를 도출해낸다 예를들어 '가나다라'와 ' fullfish.tistory.com 기존 코드 //레벤슈타인 거리 코드 exports.levenshteinDistance = (str, search) => { if (search === undefined) return 0; if (str === search) return 0; let aLen = str.length; let bLen = search.length; if (aLen === 0) return bLen; if (bLen === 0) return ..

레벤슈타인 거리 (Levenshtein Distance)

레벤슈타인 거리란 문자열의 유사도를 검사하는 기본적인 알고리즘으로 편집 거리라고도 부름 a문자열에서 b문자열로 편집할때 몇번의 조작이 필요한지를 도출해낸다 예를들어 '가나다라'와 '가나다마바'의 거리는 2이다 '라' -> '마', '바'추가 코드 exports.levenshteinDistance = (str, search) => { if (search === undefined) return 0; if (str === search) return 0; let aLen = str.length; let bLen = search.length; if (aLen === 0) return bLen; if (bLen === 0) return aLen; //배열 생성 let matrix = new Array(aLen + ..

fuzzy검색의 highlight와 가중치 적용

참고 : https://taegon.kim/archives/9919 [JS] 한글도 지원하는 퍼지 문자열 검색 UI 작업을 하다보면 목록을 검색해야 할 때가 많다. 그런데 사람의 기억이라는 게 정확하지 않아서 혹은 전부 입력하기 귀찮아서 개떡같이 일부만 입력해도 찰떡같이 원하는 결과를 보여주는 UI taegon.kim Highlight 적용 검색을 한 글자를 빨간색으로 반환 가중치 적용 원래 db상 '과일먹자'가 '과자냠냠'보다 id값이 빨라서 상단에 위치했는데 유저가 좀더 찾기를 원했을만한 단어가 위로가게 가중치 적용 빨간색으로 색 바뀌는부분 코드 exports.chageRed = (data, search) => { const regex = createFuzzyMatcher(search); const ..

정규표현식의 capture, group

//예시 문자열 let str = "안녕하세요 안녕 제 전화번호는 010-1234-5678입니다 G gd god good goood!."; capture는 ()로 사용 str.match(/전화번호/) //반환 [ '전화번호', index: 11, input: '안녕하세요 안녕 제 전화번호는 010-1234-5678입니다 good!.', groups: undefined ] str.match(/전화(번호)/) //반환 [ '전화번호', '번호', index: 11, input: '안녕하세요 안녕 제 전화번호는 010-1234-5678입니다 good!.', groups: undefined ] 위 코드에서 처럼 '번호'에 capture을 할 경후 match의 반환값 2번째 인자로 capture안의 문자열이 들어..