배열 ~ 그래프

배열, 순차 리스트 (Array)

특징

• 고정된 크기를 가지며 일반적으론 동적으로 크기를 늘릴 수 없음. JS언어에서 동적으로 크기가 증감되도록 만드는 것임.

• 원소의 index를 알면 O(1)로 원소를 찾을 수 있음.

• 원소를 삭제하면 해당 index에 빈자리가 생김.

• 요소 추가, 삭제는 O(n)이므로 이들이 반복되는 로직이라면 배열 사용 권장x. 탐색에 유리함.

JS 배열의 특이점

• 배열이 동적임.

• index에 숫자가 아닌 문자열, 논리값이 들어갈 수 있음. 이때, 자동으로 문자열로 변환된 값이 key 가 됨. JS 타입이 근본적으로 객체이기 때문.

연결 리스트 (Linked List)

• 각 요소를 포인터로 연결하여 관리하는 선형 자료구조.

• 추가와 삭제에 용이한 리스트임.

특징

• 메모리가 허용하는한 요소를 제한없이 추가할 수 있음.

• 탐색은 O(n)이 소요됨.

• 요소를 추가하거나 제거할 때 O(1)이 소요됨.

Singly Linked List

• head에서 tail까지 단방향으로 이어지는 연결 리스트.

• 가장 단순한 형태인 연결 리스트임.

• 탐색과 추가, 제거가 한 번에 이루어질 경우 O(n)이 소요됨.

Doubly Linked List

• 포인터가 두 개로 이루어져 양방향으로 연결이 가능한 리스트.

• singly Linked List보다 자료구조 크기가 좀 더 큼 (큰 영향은 없음).

Circular Linked List

• Singly 혹은 Doubly Linked List에서 Tail이 Head로 연결되는 연결 리스트.

• 메모리를 아껴쓸 수 있음.

• 원형 큐 등을 만들 때 사용됨.

스택 (Stack)

• Last In First Out. ex)스택 메모리

• 바닥이 막힌 상자.

//Array로 구현 - push, pop으로 표현 가능
const stack = [];

stack.push(1);
stack.push(2);
stack.push(3);
stack.pop();

//Linked List로 구현
스택 강의 3:52 참고

큐 (Queue)

• First In First Out.

• Linear Queue와 Circular Queue가 존재함.

//Array로 구현
class Queue {
    constructor() {
        this.queue = [];
        this.front = 0;
        this.rear = 0;
    }

    enqueue(value) {
        this.queue[this.rear++] = value;
    }

    dequeue() {
        const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front += 1;
        return value;
    }

    peek() {
        return this.queue[this.front];
    }

    size() {
        return this.rear - this.front;
    }
}

//Linked List로 구현
큐 강의 4:24 참고

해시 테이블 (Hash Table)

• 한정된 배열 공간에 key를 index로 변환하여 값을 넣음.

• 해시(hash)란 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑(mapping)한 값.

• 삽입은 O(1)이며 키를 알고 있는 경우 삭제, 탐색도 O(1)로 수행.

• 해시 충돌(해시 함수의 결과가 동일해 겹치는 현상)이 발생하는 문제점이 있음.

해시 충돌 해결 방법

• 선형 탐사법 : 충돌이 발생하면 옆으로 한 칸 이동함. 비어있는 bucket을 찾을 때까지 이동하기 때문에 탐색에 선형 시간이 걸릴 수 있음.

• 제곱 탐사법 : 충돌이 발생한 횟수의 제곱만큼 옆으로 이동. 충돌이 발생할 수록 이동 범위가 커지기 때문에 데이터가 몰리는 것이 덜함.

• 이중 해싱 : 다른 해시 함수를 이용함. 규칙을 다르게 한 해시 함수를 적용하여 같은 bucket으로 값을 저장함.

• 분리 연결법 : bucket의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가함. 다만 하나의 bucket의 값이 무한정 늘어날 수 있다는 단점 존재.

어디에 사용하지?

어떻게 사용하지?

const table = [];
table['key'] = 100;
console.log(table['key']); //100
delete table('key');
console.log(table['key']);//undefined

const table = {};
table['key'] = 100;
console.log(table['key']); //100
delete table('key');
console.log(table['key']);//undefined

• map

const table = new Map();
table.set("key", 100);
table.set("key2", "Hello");
console.log(table["key"]); //undefined
console.log(table.get("key")); //100
console.log(table.keys()); //{"key", "key2"}
console.log(table.values()); //{100, "Hello"}
table.clear();
console.log(table.values()); // {}

• set

const table = new Set();
table.add("key");
console.log(table.has("key")); //true
console.log(table.size); // 1
table.delete("key");
console.log(table.has("key")); //false

그래프

• 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조. ex) 지하철 노선도

• 정점(Node) 집합과 간선(Edge) 집합으로 표현.

특징

• 정점은 여러 개의 간선을 가질 수 있음.

• 크게 방향 그래프와 무방향 그래프로 나뉨.

• 간선은 가중치를 가질 수 있음.

• 사이클이 발생할 수 있음. 탐색 시 무한루프에 빠지지 않도록 주의.

방향, 무방향 그래프

• 무방향 : 간선으로 이어진 정점끼리 양방향으로 이동 가능. (A, B)와 (B,A)는 같은 간선으로 취급.

• 방향 : 간선에 방향성이 존재함. (A, B)와 (B,A)는 다른 간선으로 취급.

그 외

• 연결 그래프 : 모든 정점이 서로 이동 가능한 상태인 그래프.

• 비연결 그래프 : 특정 정점쌍 사이 간선이 존재하지 않는 그래프.

• 완전 그래프 : 모든 정점끼리 연결된 상태인 그래프.

• 사이클 : 그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분.

그래프 구현 방법

//adjacency matrix - true 값은 연결을 의미함.
const graph = Array.from(
    Array(5),
    ()=> Array(5),fill(false)
);

graph[0][1] = true; // 0 -> 1
graph[3][2] = true; // 3 -> 2

//adjacency list
const graph = Array.from(
    Array(5),
    ()=> []
);

graph[0].push(1) = true; // 0 -> 1
graph[3].push(2) = true; // 3 -> 2

Follow Up Tasks