빅오 표기법
빅오표기법의 수학적 정의는 다음과 같다.
f(n)의 알고리즘 시간 효율성이 있고 n0보다 충분히 큰 값 n을 넣을떄, f(n)의 런타임 시간이 최악의 경우에도 점근선인 k*g(n)을 넘을 수 없다. 이때 빅오 표기법을 사용해 O(g(n))이라고 나타낸다.
빅오 표기법은 크게 2가지 특성이 있다.
1. 상수항 무시
빅오 표기법에서 데이터 입력값은 충분히 크다고 가정하고, 알고리즘의 효율성도 데이터의 크기에 따라 영향을 받기 때문에 상수항 같은 사소한 부분은 무시한다.
예를들어 O(2N) -> O(N)과 같이 상수항은 무시하고 표기한다.
2. 영향력 없는 항 무시
가장 영향력이 큰 항 외에 영향력 없는 항들은 무시된다.
예를 들어O(n^2 + 2n + 1) -> O(n^2)과 같이 영향력이 지배적인 n^2이외에 영향력이 없는 항들은 무시한다.
배열
배열을 이용해 연관된 데이터를 모아서 처리할 수 있다. 연관된 데이터를 연속적인 형태로 구성된 구조를 갖는다. 배
배열에 포함된 원소는 순서대로 번호(index)가 붙는다.
배열의 특징으로 고정된 크기를 가지며 일반적으로 동적으로 크기를 늘릴 수 없다.
- 자바스크립트와 같은 스크립트 언어는 동적으로 크기가 증감되도록 만들어져 있다.
원하는 원소의 index를 알고 있다면 O(1)로 원소를 찾을 수 있다.
배열에 요소를 삽입하거나 삭제하는 경우, 배열 요소를 연속적으로 유지하기 위해 요소의 이동이 일어나야 하는 단점도 있다.
자바스크립트에서의 배열
일반적인 밀집배열과는 다르게 배열의 요소를 위한 메모리 공간이 동일한 크기를 갖지 않아도 되고 연속적으로 이어져 있지 않을 수 있다. 이러한 배열을 희소배열이라고 한다.
자바스크립트에서 배열은 객체인데, 일반적인 배열을 흉내한 특수한 객체이다.
console.log(Object.getOwnPropertyNames([1, 2, 3]));
//[ '0', '1', '2', 'length' ]
자바스크립트에서는 length프로퍼티와 인덱스를 프로퍼티로 갖는 특수한 객체이다. 따라서 일반적인 배열과 장단점을 비교해보면 다음과 같다.
- 일반적인 배열은 인덱스로 배열 요소에 빠르게 접근할 수 있다. 하지만 특정 요소를 탐색하거나 요소를 삽입 또는 삭제하는 경우에는 효율적이지 않다.
- 자바스크립트 배열은 해시 테이블로 구현된 객체이므로 인덱스로 배열 요소에 접근하는 경우, 일반적인 배열보다 성능적인 면에서 느릴 수 밖에 없는 구조적인 단점을 갖는다. 하지만 특정 요소를 탐색하거나 요소를 삽입 또는 삭제하는 경우에는 일반적인 배열보다 빠른 성능을 기대할 수 있다.
연결리스트
데이터 요소의 선형 집함이며, 논리적 저장 순서가 메모리의 물리적 저장 순서와 일치하지 않는다.
각각의 원소들은 자기 자신 다음의 원소를 가리키는 구조로 이루어져 있고
링크드 리스트는 순서를 표현하는 노드들의 집합으로 이루어져 있다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SingleLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
isNodeisNull(node) {
if (node === null) {
return true;
}
return false;
}
find(value) {
let curNode = this.head;
//마지막 노드에 도달할때까지 반복
while (curNode !== null && curNode.value !== value) {
curNode = curNode.next;
}
return curNode;
}
append(newValue) {
const newNode = new Node(newValue);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
}
insert(node, newValue) {
const newNode = new Node(newValue);
newNode.next = node.next;
node.next = newNode;
}
remove(value) {
//제거 불가능한 경우
if (this.head === null) {
return;
}
//가장 처음의 노드를 삭제하려는 경우 헤드를 옮겨줌
if (this.head.value === value) {
this.head = this.head.next;
return;
}
//그 외의 경우
let prevNode = this.head;
while (prevNode.next.value !== value && prevNode.next !== null) {
//삭제할 노드가 리스트의 마지막인 경우
prevNode = prevNode.next;
}
if (prevNode.next !== null) {
prevNode.next = prevNode.next.next;
//삭제할 노드가 마지막 노드인 경우
if (prevNode.next === null) {
//tail을 null이 아니게 새로 갱신함
this.tail = prevNode;
}
}
}
display() {
let curNode = this.head;
let list = [];
while (!this.isNodeisNull(curNode)) {
list.push(curNode.value);
curNode = curNode.next;
}
console.log(list);
}
}
const linkedList = new SingleLinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(5);
linkedList.display();
//[ 1, 2, 3, 5 ]
linkedList.remove(3);
linkedList.display();
//[ 1, 2, 5 ]
linkedList.insert(linkedList.find(2), 10);
linkedList.display();
//[ 1, 2, 10, 5 ]스택
스택은 말 그대로 "쌓아놓은 더미"를 의미한다. 식당에 쌓여있는 접시 더미, 책상에 쌓인 책 등이 있을 수 있다.
LIFO : Last In First Out
스택의 가장 큰 특징은 후입선출이다. 가장 최근에 들어온 데이터가 가장 먼저 나가는 것을 의미한다.
자바스크립트에는 스택이라는 구조가 따로 정의되어 있지 않지만, 간단히 구현할 수 있다.
class Stack {
constructor() {
this.stack = [];
}
// 스택에 요소를 추가합니다.
push(element) {
this.stack.push(element);
}
// 스택에서 가장 위에 있는 요소를 제거하고 반환합니다.
pop() {
if (this.isEmpty()) {
return null; // 스택이 비어있을 경우 null 반환
}
return this.stack.pop();
}
// 스택의 가장 위에 있는 요소를 반환합니다.
peek() {
if (this.isEmpty()) {
return null; // 스택이 비어있을 경우 null 반환
}
return this.stack[this.stack.length - 1];
}
// 스택이 비어있는지 여부를 확인합니다.
isEmpty() {
return this.stack.length === 0;
}
// 스택의 크기를 반환합니다.
size() {
return this.stack.length;
}
// 스택의 모든 요소를 문자열로 반환합니다.
toString() {
return this.stack.toString();
}
// 스택을 초기화합니다.
clear() {
this.stack = [];
}
}
// 스택 사용 예시
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.toString()); // 출력: "1,2,3"
console.log(stack.peek()); // 출력: 3
stack.pop();
console.log(stack.toString()); // 출력: "1,2"
console.log(stack.isEmpty()); // 출력: false
stack.clear();
console.log(stack.toString()); // 출력: ""
console.log(stack.isEmpty()); // 출력: true
'TIL' 카테고리의 다른 글
| 23/06/05 TIL (0) | 2023.06.05 |
|---|