Today I Learn/알고리즘 (4) 썸네일형 리스트형 [HackerRank] Sherlock and Anagrams (Javascript) 2020. 4. 11. 01:26 요즘 머리 환기 겸 간간히 코딩 테스트를 연습하고 있는데 문자열 관련한 문제를 풀던 중 중요한 사실을 하나 알았다. 우선 문제는 다음과 같다. 문제 설명. 주어진 문자열의 부분 문자열 중 Anagram의 개수를 찾는 것. ※ Anagram: 문자열의 길이와 포함된 문자의 개수가 같은 두 문자열의 집합 예를 들어 'abba'이면, [a, a], [b, b], [ab, ba], [abb, bba]가 Anagram이므로 4를 리턴해야 한다. 출처. https://www.hackerrank.com/challenges/sherlock-and-anagrams/problem 아무리 머리를 싸매도 O(n^4)밖에 생각이 안나서 Brute Force로 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 .. 해쉬 테이블 2020. 3. 29. 23:00 해쉬테이블은 자바스크립트의 객체, 브라우저 기본객체인 로컬스토리지 등에 사용된 자료구조라 잘 알아야 한다. 해쉬테이블은 key를 해싱(hashing)하여 해쉬 코드로 변환 후 해당 코드의 위치에 값을 저장하는 테이블로, key를 알면 해싱함수를 통해 삽입, 삭제, 검색을 바로 수행할 수 있어 O(1)의 시간복잡도를 가진다. 해쉬테이블에서 중요한 건 해싱 함수인데 해싱 함수는 다음 세가지 성질을 지녀야 한다. 1. 같은 입력값에 대해 항상 같은 출력값을 계산 2. 시간 복잡도는 O(1)이어야 함 3. 배열 내 인덱스를 고르게 분포할 수 있게끔 계산 다른 key라도 해싱함수에 따라 같은 해쉬 코드로 변환될 수 있는데 이를 충돌이라고 한다. 충돌을 해결하는 방법으로는 크게 개방 주소법(Open Addressi.. [그래프탐색] DFS/BFS 2020. 3. 28. 14:11 DFS와 BFS를 구현하기 전, Stack과 Queue를 구현할 수 있어야 한다. 1. Stack 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 function Stack () { this.array = []; } Stack.prototype.push = function (e) { return this.array.push(e) } Stack.prototype.pop = function () { return this.array.pop(); } Stack.prototype.peek = function () { return this.array[this.array.length-1]; } Stack.prototype.is.. [정렬] Javascript로 정렬 알고리즘 공부하기 2020. 3. 16. 23:29 가장 기본적인 정렬 알고리즘부터 복기 중! 안보고 칠 수 있을 정도로 해둬야 까먹지 않는 거 같다. 지금까지, C++, Python으로는 많이 했었는데 이제 자바스크립트로도 알고리즘 문제를 어느정도 풀고 싶어졌다. 1. 선택 정렬(Selection sort) 요약: 최소값을 뽑아서 첫번째 인덱스부터 swap 시간복잡도: O(n^2) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 function selectionSort (arr) { var len=arr.length for (var i=0;i 이전 1 다음
요즘 개발
