goal
- Linked List
- Hash Table
<< How to study >>
- 개념의 이해 뿐만 아니라 직접 자료구조를 구현해야 한다면 어떻게 코드를 작성해야 할지 생각하기
- 자료 구조의 모양 추상적으로 그림 그리기
- 해당 자료구조가 가지고 있는 property 와 method 찾아보기
- 각 method는 어떻게 동작되는 것인지 알아보고 수도 코드 직접 작성해보기
알고리즘이란? 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 일컬으며, 알고리즘은 제각기 다른 모양과 형태를 지니고 있기 때문에, 시간복잡도는 알고리즘에서 흔하게 활용, 설명된다.
시간복잡도를 분석하는 것은? input n 에 대하여 알고리즘이 문제를 해결하는 데에 얼마나 오랜 시간이 걸리는 지를 분석하는 것(= 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계)과 같다. Big-O 표기를 이용하여 정의한다.
| 표기 | 시간 | 설명 |
|---|---|---|
| O(1) | 상수 시간 | 입력값 n 이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한단계만 거침 |
| O(n) | 직선적 시간 | 문제를 해결하기위한 단계의 수와 입력값 n이 1:1 관계를 가짐 |
| O(log n) | 로그 시간 | 입력값 n이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦 |
| O(n^2) | 2차 시간 | 문제를 해결하기위한 단계의 수는 입력값 n의 제곱 |
| O(C^n) | 지수 시간 | 문제를 해결하기위한 단계의 수는 주어진 상수값 C의 n제곱 |
Linked List
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조 /
데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음 or 이전의 노드와의 연결을 담당 /
- Linked List란?
: 그 크기가 동적인 자료구조로, 자료구조를 구성하는 요소( = 노드(node) )로 이루어진 자료구조 / 각각의 노드는 데이터와 다음 노드가 무엇인지 알려주는 주소(=자신과 연결된 다음 요소에 대한 참조(주소)값)를 가지고 있음 / linked list는 새로운 데이터를 추가, 검색, 삭제하는 기능이 있어야 함 / 어떠한 임의의 지점에 데이터의 추가, 삭제를 할 경우, O(1) (상수 시간)의 시간 복잡도를 갖음 (배열의 경우, O(n) ) / 각 노드는 인덱스를 갖지 않음 / 따라서, 어떤 특정 데이터를 linked list에서 검색(retrieve)하고자 할 때, 처음부터 ~ 전체 linked list를 훑어야 하며, 이는 O(n) 의 시간 복잡도를 필요로 함 / ex. music playlist
자료구조 가져오기 추가하기 삭제하기 Linked List O(n) O(1) O(1)
Array vs Linked list
- 배열의 장점 : 데이터를 읽어오는데 걸리는 시간이 매!우! 빠름 / 자료구조가 매우 간단 /
- 배열의 단점 : 데이터의 크기를 변경할 수 없음 / 비순차적인 데이터 추가, 삭제할 때 시간이 매우 오래걸림
- 연결리스트의 장점
1) 비순차적이고 불연속적으로 존재하는 데이터를 서로 연결
2) 삭제와 추가가 매우 간단하며 빠름 / 삭제하고자 하는 요소의 이전 요소가 삭제하고자 하는 요소의 다음 요소를 참조하도록 변경 / 새로운 요소를 생성한 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경한 후, 새로운 요소가 다음 요소를 참조하도록 변경
Doubly Linked Lists
: 각 노드가 목록의 다음 노드에 대한 참조와 목록의 이전 노드에 대한 참조를 유지하는 연결 목록 / 목록에서 앞뒤로 이동할 수 있다는 장점 / 목록의 마지막 노드를 제거하는 것은 단일 연결 목록 에서처럼 선형 시간 작업이 아니라 일정한 시간 작업 /
- Linked list의 이동방향은 위의 사진처럼 한방향이기 때문에,
Hash Table
A hash table is a "data structure" that maintains associations between "two data values". Tha data values being associated are commonly referred to as the "key and value". A single instance of hash table may store many associations.
해시 테이블은 "두 데이터 값"간의 연결을 유지하는 "데이터 구조" /
연관되는 데이터 값을 일반적으로 "키 및 값"이라고 하며, /
해시 테이블의 단일 인스턴스는 많은 연결을 저장할 수 있음 /
- 해시 테이블이란?
: (=해시 맵) 키&값 쌍을 저장하고 있는 자료구조 / 해시 테이블은 키를 저장할 때, 메모리 공간을 "덜" 사용할 수 있도록하기 위해 키를 "해시 함수(Hash Function)"라는 함수를 통해 특정 숫자값의 인덱스로 변환함 / 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지
자료구조 가져오기 추가하기 삭제하기 Hash Table O(1) O(1) O(1)
** 아래의 사진을 참고하여 위의 사진을 풀어보자!
tuple : 해쉬 테이블에서 key & value의 쌍
storage : tuple들이 모여 데이터를 저장하고 있는 배열 형태의 테이블
bucket : tuple이 저장되어있는 장소
Objects vs Hash Tables
| JavaScript Object | Hash Table | |
|---|---|---|
| Insert(삽입) | obj["key"] = "value" | ht.insert("key", "value") |
| Retrieve(검색) | obj["key"] | ht.retrieve("key") |
| Remove(제거) | delete obj["key"] | ht.delete("key") |
Hash function
- Only return numbers that are within the array bounds (0 to length -1)
=> 오직 배열 내의 인덱스 안에서만 이루어져야! (0 ~ array.length-1) - Always output the same index value for a given input string and length
=> 주어진 문자열,길이에 대해서 항상 동일한 인덱스 값을 출력해야! - Maintain no memory of previously used array locations or input strings.
=> (이전에 사용되었던) 어떠한 저장도 할 수 없으며, 사용할 때 값을 넣어주면 출력할 수 있어야!
simple hash function 구현
let hashFunction = function (str, max) {
let hash = 0;
for (let i = 0; i < str.length; i++) {
hash = (hash << 5) + hash + str.charCodeAt(i);
hash = hash & hash; // convert to 32bit integer
hash = Math.abs(hash);
}
return hash % max;
}Hash table Resizing
- 해시 테이블은 25%~75%가 채워져 있을 때, 가장 효과적으로 작용
- 75%가 초과한다면, 사이즈를 2배로
- 25% 미만이라면, 사이즈를 반으로
민철님 scrative
- 자료구조 : 어떤 문제를 해결하려고 하는지부터 시작
- real life ex을 찾아봐야!
- visualization of data sctucture -> 사이트 이용
1)
변수는 사물함
let arr = [];
let num = 1;
let name = "delilah"
메모리는 유한 / 따라서 자바스크립트 엔진은 차례대로 붙임 /
let arr2 = []
arr2.push(2)..라고하면 데이터 관리가 점점 복잡해짐 /
배열은 항상 연속적으로 할당
linked list의 경우에는,
node라는 변수를 만들어서 보통 사용하는데
node {
data:1
next : nextNode
}
2)
배열을 쓰는 이유? random access = 어디에 접근하든 속도를 똑같이 접근할 수 있음(array[indexNum])을 통해서 접근하는 시간
배열은 모든 언어 built in
linked list : 강강수월래 손잡기
1. linked 는 항상 처음부터 // 따라서 빠르지 않음
2.
3. 반드시 그런건 아님
4. 중간에 사람이 들어오는 게 부담되지 않음
4. 효율성이 항상 속도는 아님 / 크기를 미리 정해놓고 쓰는 언어에서는, 연결리스트가 배열보다 메모리를 좀더 효율적으로 사용할 수 있다고 할 수 있다 / 가정, 데이터를 얼마나 쓸지 예측이 어려운 경우, 부족 또는 낭비할 수 있음 / 따라서 이러한 가정에서는 연결리스트가 더 효율적 / 그러나, js 배열은, 딱 필요한 만큼만 받음 / 링드리스트는 next라는 포인터도 사용해야하고,. 등등
5. 정의 / 하나의 데이터는 하나의 노드만필요
3) 노드가 5개인 링드리스트를 삭제할 때, 몇번의 연산? 1
1. 메모리에 데이터가 저장되냐 안되냐는,
어떤 데이터는 기억되고 있으면 살아남음 / 듣보는 사라진다
예를들어, 두번째노드가 없어졌을때, 예를 기억하는 애는 원래 3번노드였는데, 사라지는 순간 , 아무도 기억못함.. 사라짐
다른 변수를 선언해서, 노드를 따로 저장하지 않으면,.. 적장의 목을 베면, 쫄병들은다사라진다 / 무궁화꽃이 피었습니다. 예
헤드에 있는 노드만 베면 됨
헤드를 삭제하는 것은 다음 노드에 접근할 수 있는 방법을 없애버린 것!
4)
5가들어가고 10 15 20 //
0을 지우면 -> 10 15 20 (10이 head)
10이 새로운 0 //
10 15 20
0 1 2
1번 인덱스를 찾아라 15
5)
"최대"가 포인트
2번에서도 되는데 ~ 10번까지도 가 최대
6) 재귀가 익숙하지 않은가보다...
컴파일링 : 100100101 컴퓨터가 이해해주는 언어로 변역해주는 것
1번설명.
function alternate (node) {
if (node == null) {
return; // which one?
}
console.log(node.data) //
if (node.next) {
alternate(node.next.next)
}
console.log(node.data) //
}
ap(head)
재귀를 해결하는 법 /
console.log(head.data) //
alternate(head.next.next)
console.log(head.data) //
1 - ap(head.next.next) - 1
여기에서 다시 또 재귀
1 - ap(head.n.n.n.data) - 1 (첫번째 이프문이 무시당하면서 다시 아래 if문으로)
1 - ap(head.n.n.n.n.data) - 1
head.n.n.data = 3
1-3-ap(head.n.n.n.n.data) - 3 -1
ap(5) = 5
1-3-5-ap(null)-5-3-1
ap(null)에서는 종료
7) 해시함수
데이터 스트럭쳐를 직접 구현하는 일은 거의 없을거다 /
매우 옛날.. 데이터크기할당이 매..우 귀할 때
자료구조 & 알고리즘 @@ 그래프 / 바이너리서치트리? / 트리 / 해시테이블 / -> 을 사용해서 쓰는 문제를 만날 수 있음
c. 1:1로 맵핑이 불가능하다 / 문자처럼저장하고싶닥!할때 이를 숫자로 저장해주는 것이 해시테이블 / 문자열은 무한함 .. 출력값 은 유한함.. 그래서 일대일매핑이안됨 또한 같은값으로 매핑되어 충돌되는 결과를 불로올 수 있다 /
ex. 입력ㅎ값은 모든 정수 이를 홀짝수로 정리할거야 / "해시함수는 입력값과 출력값간의 매핑이다" / 문자열이라는 것을 집어넣어서, 같은 방에 매핑될 수도 있다라는 것이야 /
d. sha-256 : 시큐얼해시알고리즘 / 암호학적인 함수라고한다 / 해시함수 종류가 매우 많음 /
e. 해시함수는 암호화된 비밀번호 이런곳에 쓰임 /
8) 함수이기때문에, 같은 값을 넣으면 결과가 항상 같아야 / 덮여쓰여짐
9) 4 3 1 1 1 차가왔어 한번왔어 또왔어
데이터 스트럭쳐 & nqueens... 학습가능한 수준의 것...
속도의 차이는 있다
