Javascript/DSA 썸네일형 리스트형 DSA end 알고리즘 스터디가 끝난지 2주가 지났다. 드디어 책에 있는 내용은 모두 정리가 끝났다. 내가 이해 하지 못한건 내것이 아니라고 생각한다. 구글에 검색하면 거의 모든것을 찾을수 있다. 구글에 나오지 않는다면 커뮤니티에 질문을 올린다. 답을 얻을수 있지만 그것을 이해 하지 못하면 내가 누군가에게 그 문제에 대해서 설명할수 없고 그것이 항상 최선인가 라는 질문을 할수가 없다. 이게 최선인가를 스스로에게 질문하는건 매우 중요하다고 생각한다. 현재 우리 나라 같이 기술에 대한 가치가 현저히 낮다면 자존감이라도 있어야 내가 좋아하는 이 일을 계속 이어나갈수 있으니까 개발자로서 자존감을 높이는것 중요하다고 생각한다. 하지만 모든 상황에 대해서 자신이 내린 해답이 무조건적으로 옳다 라는것 그것은 자존감을 새우는것이 아.. 더보기 Search Algorithm About Search Algorithm 정렬 알고리즘에서 정렬은 결국 검색을 하기 위한 것이다 라는 이야기를 했었다. 리스트에서는 순차 검색(sequential search) 와 이진 검색(binary search)으로 데이터를 검색할수 있다. sequential search 순차 검색은 다른말로 선형 검색(linear search) 라고도 한다. 순차 검색은 무작위적인 검색 기법으로 상황에 따라 자료구조의 모든 요소를 검색해야 하는 상황이 발생할 수 있다. function seqSearch(arr, data) { return arr.indexOf(data) === -1? false : arr.indexOf(data); } function dispArr(search) { let nums = new Ar.. 더보기 Set Data Structure About Set 집합이란 고유한 요소의 모임을 집합이라 한다. [1,2,3,3] 3은 고유하지 않기때문에 집합이라 부를수 없다. 집합에는 순서가 없다. [3,1,2,4] 는 집합 이다. ADT Structure method description add(val) 추가 remove(val) 제거 has(val) 존제 여부 체크 clear() 초기화 size() 길이 values() 현재 담겨져 잇는 값 union() 합집합 intersection() 교집합 difference() 차집합 Implementation class Set { constructor() { this.data = []; } add(val) { return this.has(val) ? console.log('val is exist') :.. 더보기 Dynamic Programming & Greedy Algorithms About DP(Dynamic Programming) 우선 뭔가 명칭에서 있어 보인다. 역동적인 프로그래밍 이라니.. 실제로 고안자인 벨만은 있어보여서 dynamic 이란 단어를 선정 했다고 한다. 저서의 서문을 보면 연구소에서 펀딩을 받기에 좋은 단어라 선택했다고 나온다. 저서에는 다음과 같이 DP 를 정의 하고 있다. 어떤 문제를 풀기위해 그 문제를 더 작은 문제의 연장선으로 생각하고 과거에 구한 해를 활용하는 방식의 알고리즘을 총칭한다. DP는 알고리즘 이라기보단 하나의 방법론에 가까운데 Optimal Substructure 라고 불리는 구조에 DP를 활용해야 좋은 효과를 얻을수 있다. 뭔가 구하기위해서 했던 계산을 계속해서 반복하는류에 문제들이 적용 대상이라 할수있는데 피보나치 수열, 배낭문제, .. 더보기 Sorting Data Structure About Sorting 정렬의 목적은 데이터 검색을 위해서 이다. 그렇기 때문에 다음시간에 포스팅할 검색과도 깊은 연관이 있다. 정렬은 매우 중요한 작업이다. 정렬이 되어있지 않은 수백만건의 데이터를 상상해보면 끔찍할것이다. 그래도 어찌됐건 정렬을 해야하는데 순차 검색외엔 다른방법이 없다. 하지만 정렬이 되어있다면 매우 빠른 이진 검색을 사용할수 있다. 컴퓨터가 정렬을 수행하는 여러가지 이유중에 하나가 바로 이진 검색이 가능한 데이터로 가공하기 위한 목적도 있다. 정렬을 하기까지 걸리는 시간은 보통 자료수의 제곱에 비례하여 늘어나기때문에 효과적인 정렬방법을 만드는게 중요하지만 스터디에 목적은 정렬을 알아보기 위함이고 내장되어 있는 정렬을 가져다 쓰는것이 더 빠를것이다. Basical Sorting 기본.. 더보기 Graph Data Structure About Graph 그래프는 Vertex(점:노드) 와 Edge(간선) 로 구성된다. 점과 점사이를 이어주는 역할을 선이 하게 되는데 선에 방향이 없을경우 무향 그래프(Undirected graph) 방향이 있으면 유향 그래프(Directed graph) 라고 부른다. 간선의 경우엔 가중치(Weighted value) 를 가질수 있다. Adjacency List 간선에 가중치는 그래프의 이동경로를 포함하고 있다. 간선을 표현하는데에는 2가지 방식을 사용할수 있는데 인접 행렬과 인접 리스트 방식이 있다. 결론적으로 인접 리스트를 사용하는것이 좋은데 인접 행렬의 문제에 대해서 이야기 해보겠다. 인접 행렬 방식은 Matrix 즉 2차원 배열 형식을 가지고 있다. 그렇기 때문에 특정 노드와 연결된 노드를 찾기.. 더보기 Queue Data Structure About Queue Queue는 Stack 다음으로 가장 기초 적인 자료구조 중에 하나이다. First In First Out: 먼저 들어온 데이터가 먼저 나간다. queue 의 사전적인 의미를 찾아보면 (무엇을 기다리는 사람)줄 , 줄을 서서 기다리다. 로 해석된다. 큐는 주로 프로세스나 네트워크사이에서 자료를 주고 받을때 임시적으로 저장 하는 용도에 많이 사용된다. ADT (Abstract Data Type) methodname contents enqueue(s) 데이터 삽입 dequeue() 데이터를 꺼내고 꺼낸값을 리턴 front() 큐의 가장 앞에 있는 데이터 확인 isEmpty() 큐가 비어 있는지 확인 size() 큐의 크기 implementation //큐 class Queue { con.. 더보기 Stack Data Structure About Stack Stack은 단순하고 빠르며 가장 기초적인 자료 구조 이다. Last in First Out : 마지막에 들어온 데이터가 처음으로 나가게 된다. 검은책부터 -> 빨 -> 녹 -> 검 -> 빨 순으로 책을 가져간다고 연상해볼수 있다. ADT (Abstract Data Type) methodname contents push(el) 스택의 마지막 위치에 데이터 삽입 pop() 스택의 마지막 위치 데이터 꺼냄(삭제) peek() 스택의 마지막 위치에 있는 데이터 확인 clear() 스택 데이터 초기화 length() 스택의 크기 implementation //ES6 class Stack { constructor() { this.storage = []; } push(el) { this.sto.. 더보기 LinkedList Data Structure About LinkedList 자바스크립트에서 리스트는 배열로 구현한다. 다른 언어에서 배열은 길이가 정해져 있어 배열에 저장하는 데이터가 가변적이라면 메모리에 낭비 또는 초과를 일으킨다. 이러한 문제를 개선하기위해 LinkedList 를 사용 할수있다. 기차의 형태를 연상하면 이해하기 쉬우며 추가,삭제가 용이 하지만 특정 요소 접근이나 검색은 비효율적이다. LinkedList 는 Node 라는 객체의 집합인데 각 객체간 연결이 되어 있는 방식이기때문에 요소를 참조할뿐 인덱스를 부여받는것이 아니기 때문이다. let arr = ["hello","world","javascript"]; let head = { element: "head" , next: Node1 } let Node1 = { element: ".. 더보기 Tree Data Structure (Binray Search Tree) About Tree 계층적인 데이터를 저장할때 사용한다. ex)회사 조직도 엣지(Edge)로 연결(Connect)된 노드(Node)의 집합(Group)이다. 노드의 분류 Root : 최상위 노드 Parent : 상위 노드 Child : 자식 노드 left : 자식 노드가 없는 노드 More About Binary Search Tree 자식의 노드수가 두개 이하인 트리를 의미한다. BST 는 작은 값을 왼쪽 노드에 큰값을 오른쪽 노드에 저장한다. 구현방법 루트 노드를 current 노드로 설정한다. 삽입할 노드의 값이 current 노드의 값보다 작으면 current 노드를 왼쪽으로 설정한다. 삽입할 노드의 값이 current 노드의 값보다 크다면 6번 과정을 진행한다. current 노드의 왼쪽값이 nu.. 더보기 이전 1 2 다음
