[TIL003]

오늘 역대급 난이도였다
이제 3일차인데 ㄷㄷ

1) 연결리스트(Linked List)

각 요소를 포인터로 연결하여 관리하는 선형 자료구조
각 요소는 노드(Node)라고 부르며 데이터 영역과 포인터 영역으로 구성

특징

메모리가 허용하는 한 요소를 무제한 추가 가능
탐색: O(n) 소요
요소 추가/제거: O(1) 소요

종류

• 단일 연결리스트(Singly Linked List)
  Head에서 Tail까지 단방향으로 이어지는 연결 리스트
  가장 단순.

• 이중 연결리스트(Doubly Linked List)
  양방향으로 이어지는 연결리스트
  단일보다 자료구조의 크기가 큼

• 환형 연결리스트(Circular Linked List)
  단일/이중 연결리스트에서 Tail이 Head로 연결되는 연결리스트
  메모리 절약 가능
  원형 큐 등을 만들 때 사용

vs배열

• 메모리
  
• 요소 추가
  
• 요소 삭제
  

스택(Stack) : Last In First Out

큐(Queue) : First In First Out

환형 큐(Circular Queue) :

처음(front)과 끝(rear)이 이어져있는 큐

!주의!
큐, 스택, 연결리스트 뭘 쓰든 간에 class, 함수를 통해 자료구조를 먼저 구축하자
이제 무지성 배열 반복문에서 벗어나도록 하자...

자료구조 구현 시

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class LinkedList {
  constructor() {}

  find(value) {}

  append(newValue) {}

  insert(node, newValue) {}

  remove(value) {}
}

이런식으로 구조를 미리 짜줘야한다

2) 해시 테이블

키와 값을 받아 키를 해싱하여 나온 인덱스에 값을 저장하는 선형 자료구조
삽입: O(1)
삭제/탐색: O(1) < 키를 알고 있을 경우

• 해시함수 : 입력받은 값을 특정 범위 내 숫자로 변경하는 함수
• 해시 테이블의 문제점 : 해시 함수의 결과가 동일한 경우(해시 충돌)
  • 해시 충돌 해결법
    (1) 선형 탐사법 : 충돌이 발생하면 옆으로 한 칸 이동
    (2) 제곱 탐사법 : 충돌이 발생한 횟수의 제곱만큼 옆으로 이동
    (3) 이중 해싱 : 충돌이 발생하면 다른 해시 함수를 이용
    (4) 분리 연결법 : 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가

3) 그래프

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조
정점 집합과 간선 집합으로 표현 가능

• 특징
  정점은 여러 개의 간선을 가질 수 있다
  크게 방향 그래프와 무방향 그래프로 나뉨
  간선은 가중치를 가질 수 있다
  사이클 발생 가능

• 종류

  • 무방향 그래프
    간선으로 이어진 정점끼리는 양방향으로 이동이 가능
    A-B == B-A

  • 방향 그래프
    간선에 방향성이 존재하는 그래프
    A-B != B-A

  • 연결 그래프
    모든 정점이 서로 이동 가능한 그래프

  • 비연결 그래프
    특정 정점 사이에 간선이 존재하지 않는 그래프(고립된 정점이 있는 경우)

  • 완전 그래프
    모든 정점이 서로 연결된 상태

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

이론상으로는 자료구조를 알고는 있었지만, 실제로 코드를 짜는건 처음이었다.
실습문제들을 풀면서 멘붕이 왔다.
주먹구구식으로 공부해왔다는 것을 절감했다.