본문 바로가기
[Datastructure] Time Complxity with Data Structure 2020. 2. 11. 14:38 1. Array Access : O(1) (바로 접근 가능) Search : O(n) (search은 모든 원소를 순회해야 하므로) Insertion : O(n) (넣을 index를만들고 이후에 있는 요소들을 한칸씩 뒤로 민다.(n)) Deletion : O(n) (요소 삭제후 이후에 있는 요소들을 앞으로 당긴다.(n)) 2. Linked List Access : O(n) (해당 노드에 접근하기 위해서는 처음부터 순회를 해야하므로) Search : O(n) (해당 노드를 탐색하기 위해서는 처음부터 순회를 해야하므로) Insertion : O(1) (삽입이라는 operation만 보면 연산은 상수번(2번) 일어난다.) Deletion : O(1) (삭제라는 operation만 보면 연산은 상수번(2번) 일..
[Datastructrue] Time Complexity 2020. 2. 11. 14:31 시간 복잡도는 알고리즘을 실행하는 데 걸리는 시간을 설명하는 계산 복잡도입니다. 시간복잡도는 일반적으로 알고리즘에 의해 수행되는 기본 연산의 수를 계산하여 추정되며, 각 기본 연산은 고정 시간이 걸린다고 가정합니다. - wikipedia - 어떤 문제에 대한 알고리즘이 다 같을수는 없을것이다. 시간복잡도는 그러한 알고리즘을 컴퓨터가 실행했을때 얼마만큼의 시간에 대한 퍼포먼스를 보여주는지 측정해주는 지표같은것이다. 예를 들면, 어떤 한 숫자가 요소인 배열이 있고 그 배열에서 두 숫자의 차의 최대값을 구하는 문제를 풀어본다면, 많은 알고리즘들이 나올수 있다. let arr = [3,6,5,7,9]; 1. 각각의 원소마다 비교를 하면서 차의 최대값을 구한다. ==> 일일이 원소를 체크하면서 모든 원소에 대한 ..
[Datastructure] Tree / Binary Tree 2020. 2. 10. 14:59 Tree tree는 계층적인 트리 구조로, root value와 subtree(부모 노드와 자식을 가지는)를 가진다. Binary Tree A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child. 부모 노드가 자식노드 2개를 가진 자료구조를 Binary Tree(이진트리) 라고 한다. 엘리먼트들은 자식노드를 2개만 가져야 하며 보통 letf child와 right child로 불린다. Main applications of trees incl..
[Datastructure] Graph 2020. 2. 10. 13:55 A Graph consists of a finite set of vertices(or nodes) and set of Edges which connect a pair of nodes. 그래프는 유한한 노드들과 노드들의 연결로 구성되어 있는 자료구조이다. 위 그래프에서는 node(= vertices)들은 0,1,2,3,4 이고 Edges는 01, 12, 23, 34, 04, 14, 13 이다.
[Datastructure]Hash Table 2020. 2. 7. 15:11 Hash Table Hash Table은 key 를 이용하여 value를 저장하고 가져올때 빠르게 가져올수 있는 자료구조이다. 해시함수에 key값을 input으로 주면 해시함수에서 어떤 특정한 값을주게 된다. 그 값을 array의 index로 사용하여 값을 저장하게 된다. 이렇게 되면 같은 값으로 data를 찾을때 시간복잡도가 상수시간을 따르기때문에 매우 빠르게 검색이 가능하게 된다. 해시충돌 Separate chaining 방식 해시테이블은 다른 key값을 넣어도 같은 해시값을 가지고 동일한 array의 index으로 값을 넣어버릴수가 있다. 이렇게되면 이전값은 새로 온 값에 아마 지워질것이다. 이런 문제를 해결하기 위해 해시태이블에 array의index값에 새로운 노드를 만들어 linked list ..
[Datastructure]Linked List 2020. 2. 7. 14:25 링크드 리스트는 자료를 표현함에 있어서 노드와 노드사이의 연결을 이용하여 표현한다. 노드는 실제 표현할 data와 다음 노드를 가리킬 변수로 구성되어 있다. next라는 변수로 다음 노드를 가리키면 된다. head 변수는 리스트의 시작점을 가리키는 변수이고 리스트의 끝 부분(tail)을 표현하는것은 해당 노드의 next변수에 null을 할당하면 된다. Linked list의 property와 method는 property : head, tail, current method : insert, delete 등이 있다. insert 새로운 노드와 그 노드를 삽입할 인덱스를 정한다. data를 넣어준다. head부터 순회하면서 삽입합 인덱스를 찾는다. 삽입할 인덱스가 가리키는 노드의 참조값을 변수로 가지고 있는..
[Datastructure] Queue, Stack 2020. 2. 6. 15:31 Datastructure 는 data를 표현하는 방법에 대한 이야기이다. 어떤식으로 data를 표현해야 효율적으로 문제를 해결할수 있을지에 대한 것에서 나왔다고 볼 수 있겠다. 비단 프로그래밍뿐만 아니라 일상생활에서도 적용되는 것들도 있다.(다만 그것이 이런 것이다 라고 표현하지 않을 것일 뿐이다.) 1.Queue (큐) Queue라고 하는 이 자료구조는 first in first out 으로 처음 들어간 data가 처음으로 나오는 구조를 갖는다. 대표적은 queue는 줄서기이다. 그냥 차례차례 그 순서대로 진행되면 전부 다 Queue라고 보면된다. Queue가 가지고 있는 property 는 element의 갯수, 방향(순서,index) 정도가 있고, method는 맨 앞에서 element를 꺼내는 p..
[programming paradigm] Object Oriented Programming 2020. 2. 6. 14:41 OOP 의 기본 컨셉은 프로그램 내에서 표현하고자 하는 실 세계(real world)의 일들을 객체를 사용해서 모델링하고, 객체를 사용하지 않으면 불가능 혹은 무지 어려웠을 일들을 쉽게 처리하는 방법을 제공한다. - mdn 객체의 모델링을 만들고 그것을 활용한다. 이것이 oop의 기초인것 같다. oop가 나온이유는 아마 이전에 절차적으로 작성한 코드들의 문제점, 혹은 불편한 점때문에 나온것이라고 생각된다. 객체의모델링, encapsulation 객체의 모델링은 객체 내에 필요로하는 데이터와 행동들을 표현하는것으로 한다. class라는 모델을 표현하자면 대략 이런식으로 할수 있을것이다. 여기서는 data는 name,age,gender,interests. 행동은 bio, greeting정도로 볼수 있겠다. ..

티스토리툴바