TIL Day-3

자료구조 & 알고리즘

배열

원하는 원소의 index를 알면 O(1) 상수시간(문제를 해결하는데 오직 한 단계만 처리)만에 찾을 수 있다
출석번호를 부르는 것도 비슷한 원리

요소를 삭제하면 당겨지지 않고 빈자리가 생긴다
배열 요소 삭제 후 순서를 맞추려면 최악의 경우 O(N)인 선형시간이 걸린다

배열 요소 추가도 비슷하게 최대 선형시간 만큼 소요
따라서 추가와 삭제가 반복되는 로직이라면 배열 사용은 권장 ❌

배열은 탐색이 더 많은 경우에 유리한 자료구조 ⭕

연결 리스트
각 요소를 포인터로 연결하여 관리하는 선형구조
각 요소는 노드 (데이터 영역 + 포인터 영역)

배열과 상반된 특징
제한없이 요소를 동적으로 계속 추가 가능
요소를 탐색할 때 O(N)선형시간이 소요
요소를 추가하거나 삭제할 때는 O(1)상수시간이 소요

3가지 구현 방식

Singly Linked List
단일 연결 리스트
Head에서 Tail까지 단방향으로 이어짐
가장 단순한 형태
핵심 로직

• 요소 찾기
• 요소 추가
  1. 추가 할 요소의 포인터 영역을 다음 요소의 데이터 영역과 연결
  2. 이전 요소의 포인터가 추가 할 요소의 데이터 영역과 연결
• 요소 삭제 O(1)소요
  1. 삭제 할 요소의 이전 요소의 포인터가 삭제 할 요소의 다음 요소와 연결
  2. 삭제 할 요소를 완전하게 삭제

주의할 점
추가하는 부분만 상수시간이 소요되기 때문에 추가를 위한 탐색(선형시간)을 하지 않도록 코드를 작성

Doubly Linked List
이중 연결 리스트
양방향(포인터2개 다음과 이전 가리킴)
자료구조의 크기가 조금 더 큼
핵심 로직

• 요소 찾기
• 요소 추가 O(1)소요
  1. 추가 할 요소의 다음 노드가 다음 요소와 연결
  2. 추가 할 요소의 이전 노드의 다음 노드가 추가 할 노드와 연결
  3. 다음 요소의 이전 노드가 추가 할 요소와 연결
  4. 추가 할 요소의 이전 노드가 이전 요소와 연결
• 요소 삭제 O(1)소요
  1. 삭제 할 요소 이전 노드가 삭제 할 요소 다음 요소와 연결
  2. 삭제 할 요소 다음 요소의 이전 노드가 삭제 할 요소 이전 요소와 연결
  3. 삭제 할 요소 삭제

Circular Linked List
환형 연결 리스트
리스트의 Tail이 Head로 연결

스택
LIFO 구조

큐
FIFO 구조
Linear(선형) Queue와 Circular(환형) Queue가 있다.

큐의 맨 앞부분은 Front 뒷부분은 Rear이며
큐에 요소를 추가 하는 것은 EnQueue, 삭제하는 것을 DeQueue라고 한다.

큐를 구현할 때 shift함수는 쓰지말 것!
(shift는 선형시간이 걸리기 때문에 큐에서 기대하는 로직이 수행되지 않음)

해시 테이블
키와 값을 받아 해싱하여 나온 index값을 저장하는 선형구조
삽입은 O(1)
키를 알고 있다면 삭제, 탐색도 O(1)로 수행

문제점
해시 함수의 결과가 동일한 경우 해시 충돌(Hash Collision)이 발생

해결 방법

• 선형 탐사법
  충돌이 발생하면 옆으로 한 칸 이동
  최악의 경우 탐색에 탐색에 선형시간이 발생

• 제곱 탐사법
  충돌이 발생한 횟수의 제곱만큼 옆으로 이동

• 이중 해싱
  충돌이 발생하면 다른 해시 함수를 이용

• 분리 연결법
  충돌이 발생 할 경우 버킷 값을 연결 리스트로 사용하여 리스트에 값을 추가
  최악의 경우 하나의 버킷이 무한정 늘어날 수 있음

그래프
정점(Node)과 정점 사이를 연결하는 간선(Edge)으로 이루어진 비선형구조
정점 집합과 간선 집합으로 표현

정점은 여러 개의 간선을 가짐
방향 그래프와 무방향(양방향) 그래프로 분류
간선은 가중치를 가짐
사이클이 발생(무한루프)

그래프의 구현 방법

• 인접 행렬(2차원 배열로 표현)

const graph = Array.from(
	Array(5),
  () => Array(5).fill(false) // 연결이 안된 상태로 초기화
);
// [시작][도착]
graph[0][1] = true; // 0 -> 1
graph[0][3] = true; // 0 -> 3
graph[1][2] = true; // 1 -> 2
graph[2][0] = true; // 2 -> 0
graph[2][4] = true; // 2 -> 4
graph[3][2] = true; // 3 -> 2
graph[4][0] = true; // 4 -> 0

• 인접 리스트(연결 리스트로 표현)

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

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

---

오늘의 마무리

🖤 자바스크립트로 자료구조를 표현하는 것에 부족함을 많이 느꼈다.
🖤 최대한 실습을 많이 해보면서 익숙해질 필요가 있다!!