개발 관련78 Trie Trie 자료 구조 1. 개요 문자열을 다루는 작업은 정수나 실수 등의 다른 자료형을 다루는 것과는 다르다. 왜냐하면 정수나 실수형 변수는 그 크기가 정해져 있어 비교에 상수 시간이 걸린다고 봐도 되지만, 문자열 변수는 최악의 경우 문자열의 길이에 비례하는 시간이 걸린다. 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조 위와 같은 트리 형태의 구조를 가지며, 공간을 많이 차지하는 대신, 시간 복잡도는 O(M - M은 문자열 길이) 이 되어 엄청 빠르게 검색이 가능하다. 2. 사용되는 곳 일단, 어디에서 사용되는지 알고 배워야 좋지 않을까? 단어 검색 (자동완성으로도 사용이 가능한 것 같다.) 스펠 체크 아이피 라우팅 (아이피를 숫자로 바꿔서 할 줄 알았는데, 문자열 그대로 하나보다..).. 2022. 7. 14. DFS (깊이 우선 탐색) 깊이 우선 탐색 (Depth-First Search) 1. 개요 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 것 중요한 특성은 더 따라갈 간선이 없을 경우 이전으로 돌아간다는 점 그렇기 때문에 재귀호출로 구현하는 경우가 많으며, 어떤 노드를 방문했는지 여부를 검사해야 한다. 1을 방문 -> 2를 방문 -> 3을 방문 -> 4를 방문 더이상 갈 곳이 없으므로 3으로 back, 3에서 2로 back, 2에서 1로 back 1에서 인접한 노드인 5로 방문 -> 6을 방문 ..... 2. 의사 코드(pseudocode) void dfs(Node root) { if(root .. 2022. 7. 14. Brute Force Brute Force (무식하게 풀기) 1. 개요 사람들이 가장 많이 하는 실수는 쉬운 문제를 어렵게 푸는 것 문제를 마주하고 나면 가장 먼저 무식하게 풀 수 있을까 라는 질문을 스스로에게 하자 말 그대로 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법 이런 방법을 흔히 완전 탐색 이라고 부르고, 왜 굳이 언급할까 싶지만, 컴퓨터의 장점은 결국 속도가 빠르다는 것이기에 장점을 잘 활용하는 것이기도 하다. 2. 재귀 호출과 완전 탐색 2-1. 재귀 호출(함수) 재귀 호출(함수) 란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킴 // 1부터 n까지의 합을 구하는 반복문과 재귀함.. 2022. 7. 14. Object.assign 에 대해 자바스크립트 4장에서 객체 복사에 대한 내용을 다루다가 Object.assign() 을 통해 복사가 가능하다는 얘기를 잠깐 했었는데, 자세히 모르니 이번 기회에 짚고 넘어가보자 Object.assign() 우선 MDN 에서 하는 설명을 보면 The Object.assign() method is used to copy the values of all enumerable own properties from one or more source objects to a target object. It will return the target object. 대상 객체로 하나 또는 그 이상의 열거 가능한 프로퍼티를 타겟오브젝트 복사할 때 사용.. 한다고 하는데, 글만 봐서는 잘 모르겠다. 우선 문법을 살펴보면, Obj.. 2022. 7. 13. Apply,Call,Bind 에 대해 apply, call, bind 서버 사이드인 java 의 this 와 javascript 의 this 가 헷갈리는 부분이 많은데, this 와 관련된 내용인 call, apply, bind 에 대한 내용이 5장(참조 타입) 에 나와 이 부분은 따로 정리해보고자 한다. this 우선 this.. java 에서는 자기 자신을 가리키지만, javascript 에서는 다르다. javascript 에서의 this 는 함수가 어떻게 호출되었는지에 따라 다르게 동적으로 매핑? 된다. var foo = function() { console.log(this); } foo(); // this == window var obj = {foo : foo}; obj.foo(); // this == obj var instance .. 2022. 7. 13. 22. 고급테크닉 다루는 내용 고급 함수 쉽게 조작할 수 없는 객체 타이머 조작 커스텀 이벤트 1. 고급 함수 단순한 절차적인 방식, 복잡하고 동적인 방식, 클로저, 함수 포인터 등을 사용하는 다양성 1.1 안전한 타입 탐지 typeof 나 instanceof 처럼 내장된 타입 탐지는 완벽하지 않음 Object 의 toString() 메소드를 이용 Object.prototype.toString.call(value) == "[object Function]" window.JSON && Object.prototype.toString.call(JSON) == "[object JSON]" 1.2 스코프 확인 생성자 (scope-safe constructor) new 연산자 없이 객체를 생성하면 this 가 전역에 묶여버리는 문제가.. 2022. 7. 13. 이전 1 ··· 6 7 8 9 10 11 12 13 다음