배열
- 동일한 데이터 타입의 값들을 연속적으로 저장한 것
큐
- 먼저 들어온 데이터가 가장 먼저 빠져나가는 구조
- 실생활 : 놀이공원 줄서기
- 웹 : 예약 대기번호,
스택
- 가장 마지막에 들어온 데이터가 가장 먼저 빠져나가는 구조(접시 쌓기)
- 실생활 : 설거지 그릇 빼기
- 웹 : 최근 검색기록 삭제
연결리스트
- 동적인 자료 구조라서 원소를 추가/삭제할 수 있고 크기가 계속 변함
- 배열처럼 차례대로 저장하지만 원소들이 메모리상으로 연속적으로 위치하는것은 아님
- 각 원소는 자신과 다음 원소를 가리키는 참조 정보(포인터)가 포함된 노드로 구성
배열과 연결리스트 차이점
- 연결리스트는 포인터가 있어서 원소 추가/삭제 시 다른 원소들을 이동하지 않아도 된다.
- 배열은 특정 원소에 인덱스로 바로 접근할수 있지만
- 연결리스트에서는 원소를 찾을 때까지 처음(head)부터 루프를 반복해야 한다.
이중 연결 리스트
- 연결리스트와 다르게 다음 노드와 이전 노드 2개의 연결 정보를 이중으로 갖고 있다
- 연결정보가 2개를 가지고 있어서 처음에서 끝, 끝에서 처음 양뱡향으로 리스트 순회 가능
객체, 맵, 딕셔너리
- 데이터를 [키, 값]쌍으로 담아두는 자료 구조
더보기
module.exports = function dictionary() {
var items = {};
this.has = function(key){
return key in items;
};
this.set = function(key, value) {
items[key] = value;
};
this.remove = function(key) {
if(this.has(key)){
delete items[key];
return true;
}
return false;
}
this.get = function(key){
return this.has(key) ? items[key] : undefined;
};
this.values = function(){
var values = [];
for(var k in items) { // k변수에 items객체에 들어있는 원소들을 다 넣는다.
if(this.has(k)) {
values.push(items[k]); // values에 items[키]에 해당하는 값을 모두 배열로 변환한다.
}
}
return values;
};
this.getItems = function() {
return items;
}
this.size = function() {
return Object.keys(items).length;
}
this.keys = function() {
return Object.keys(items);
}
}
해시테이블
데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 변경하여 저장한 저장소
더보기
Hash Table
- 해시함수를 통해 key값을 바꾼 결과 : hash
- key에 해당하는 값 : value
- hash와 value를 저장하는 자료구조
장점
다양한 길이를 가지고 있는 키(key)를 고정된 길이를 가지는 해시(hash)로 변경하여
저장소(해시테이블)를 효율적으로 운영할 수 있도록 도와준다.
-
다양한 길이 : [2, ... 33 ... 70 ... 7775] - 데이터는 4개지만, 길이가 7776인 배열
(키(key) 일 경우)
-
고정된 길이 : [7(70), null, 2(2), null, null, 5(7775), 6(33)] - 데이터는 4개지만, 길이가 7인 배열
(해시함수를 통과한 hash일 경우)
단점
공간 효율성이 떨어 질수 있다 <- 데이터가 저장되기 전에 미리 저장공간을 확보해 놓아야 되기때문에
순서가 있는 배열에 어울리지 않는다 <- 순서와 상관없이 key만을 가지고 hash를 찾아 저장하기 때문
정렬
버블 정렬(bubble sort)
- 인접한 2개의 데이터를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환
선택 정렬(selection sort)
- 제자리 정렬
- 해당 순서마다 들어가야하는 원소의 기준이 정해져있고 어떤 원소를 넣을지 선택하는 알고리즘
(첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.)
(두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다.)
삽입 정렬(insertion sort)
- 앞에서부터 순서대로 이미 정렬된 배열 부분과 비교 하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
- 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.
더보기
(설명)
세 번째 자료는 두 번째와 첫 번째 자료,
네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후
자료가 삽입될 위치를 찾는다.
자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
a:17, b:32, c:55, d:1, e:66, f:100
(a)는 통과
(b)를 a와 비교
(c)를 b -> a 순서로 비교
(d)를 c -> b -> a 순서로 비교
(e)를 d -> c -> b -> a 순서로 비교
(f)를 e -> d -> c -> b -> a 순서로 비교
합병 정렬(merge sort)
- 처음에 배열의 총크기/2 하여서 왼쪽에 절반 오른쪽에 절반 나눈다음
- 가장 작은 단위로 배열을 쪼개서 값이 작은 결합함
- 각각 해결한 다음 결합함
계수 정렬(count sort)
- 원소간 비교하지 않고 각 원소가 몇개 등장하는지 갯수를 세서 정렬하는 방법이다.
- 모든 원소는 양의 정수여야 한다.
- 시간복잡도는 퀵정렬, 병합정렬에 비해 일반적으로 빠르다.
재귀
- 자기 자신을 호출하는 함수
- '분할 정복' 방식을 통해 복잡한 문제를 해결
- 기저조건(종료 조건)이 존재한다.
트리
그래프
힙
집합