concept/data structure
-
time complexity (시간 복잡도)concept/data structure 2020. 5. 16. 00:29
참고 : 코드스테이츠 이머시브 강의 complexity analysis (복잡도분석) : 알고리즘이 그것을 푸는데 있어서 시간과 공간을 얼마나 차지하는지 나타내는 지표 시간과 공간이 무한정으로 있다면? 알파고는 만들기 쉽다. 플레이 가능한 모든 가짓수를 계산하면 됨 그렇지만 시간과 공간이 어마어마하게 필요하겠지? 바둑판은 19x19 = 381가지 플레이 무한정의 경우의 수가 나올 수 있기 때문이다!!! 그렇기 때문에 시간복잡도를 고려해서 메모리를 적게 쓰는 코드를 쓰는 것이 중요하다는 것을 알고 포스팅을 시작해본다. 시간과 배열이 주어졌다. 여기서 두 수의 가장 큰 차이를 구하라. 주어진 배열 : [2, 5, …, 16] 첫번째 방법 모든 숫자를 비교한다. 2, 5, 6, ... 이렇게 계산했을 때 시간..
-
Graph, Tree, BSTconcept/data structure 2020. 5. 10. 21:27
Graph 그래프는 Node (노드)와 Edge (간선)으로 구성되어 있다. 그래프는 엣지가 노드 자기 자신을 가리킬 수도 있고, 한 노드가 다른 노드만 가리키기도 하고, 서로 가리키기도 하고 복잡한 형태를 가졌다. 그래서 그래프는 무방향(undirected - 대칭), 방향성(directed - 비대칭) 그래프로 나뉠수도 있고 그래프의 엣지가 원을 만드는 cyclic, 그리고 그렇지 않은 Acyclic 그래프로 나뉠 수 있고 그래프를 표현하는 방법 -Adjacency Matrix (인접 행렬 방식) : 그래프를 표에 표현하는 방식 노드끼리 연결이 되었다면 1, 그렇지 않다면 0을 표에 적어서 표현하는 방식이다. -Adjacency list (인접 리스트 방식) : 배열 방에 있는 모든 노드를 집어넣고 ..
-
hash table (해시테이블)concept/data structure 2020. 5. 10. 19:24
출처 : 코드스테이츠 본 포스팅은 코드스테이츠의 immersive course 강의를 정리한 내용입니다. hash table (해시테이블) 은 data structure이다. 어떤 data structure이냐면, 두 가지 관계를 연결시켜주는 것. 그럼 예를 들어서 bat을 넣으면 scary가 나오는 해시테이블 구조를 만들고 싶다면? 이렇게 배열에 인덱스에 하나하나 값을 집어넣어주는 방법이 있다. 그런데 이렇게 했을 때, bat을 찾으려면 0부터 하나하나 다 찾아야하기 때문에 O(n)의 시간복잡도가 나오게 된다. 우리가 원하는 것은 O(1)의 시간복잡도이기 때문에 위 구조는 곤란하겠다. 그러면 배열에 어떤 input을 했을 때, 그 index가 새롭게 나오게 되어 배열의 index에 값이 저장되는 구조를..
-
Data structure : 자료구조 (stack, queue)concept/data structure 2020. 5. 2. 18:48
stack Last in First out (후입선출) 구조예시 책상 위에 쌓아둔 책 주방에 쌓아둔 접시 하노이의 탑 활용 예 웹브라우저 방문기록(뒤로가기) 실행취소 자바스크립트에서 지원하는 다양한 stack method들이 있다. pop — Pulls (removes) the element out of the stack. ... push — Pushes (inserts) the element in the stack. ... peek — returns the item on the top of the stack, without removing it. empty — returns true if the stack is empty, false otherwise. swap — the two top most ele..
-
의사코드로 알고리즘 문제를 해결하는 방법concept/data structure 2020. 3. 30. 18:58
예를 들어 텍스트에서 foo라는 단어를 찾아 전부 다른 단어로 바꿔주는 코드를 작성한다고 가정해본다. 다음은 pseudocode의 예제이다. 텍스트를 입력으로 받는다 foo라는 단어를 찾는다 그 단어를 지운다 그 자리에 새로운 단어를 넣는다 바뀐 내용을 리턴한다 아래는 코드로 작성한 예제 이다. function replaceFoo(text) { // foo라는 글자의 index가 -1이 아니면 단어를 찾은 것이다 while( text.indexOf('foo') !== -1 ) { // index를 발견하면 let index = text.indexOf('foo'); // index를 이용해 foo 바로 앞까지의 텍스트를 얻어내고 let beforeText = text.slice(0, index); // f..