TIL

• 자료구조
  배열 스택 큐 해시 테이블 그래프 연결리스트

리스트를 제외한 나머지는 개념만 짚고 넘어가겠습니다.

배열

연관된 데이터를 연속적인 형태로 가지고 있음

배열의 특징

• 고정된 크기를 가지며 일반적으론 동적으로 크기를 늘릴 수 없다.
• 자바스크립트처럼 대부분의 스크립트 언어는 동적으로 크기가 증감디도록 만들어져 있다
• 원하는 원소의 index를 알고있다면 O(1)로 원소를 찾을 수 있다.
• 원소를 삭제하면 해당 INDEX에 빈자리가 생긴다.

배열의 요소를 삭제하면 단순히 공백으로 두는 경우가 많지만,
앞당기거나 뒤로 당긴다
삭제 후 순서를 맞추려면 O(N)이 걸린다.(선형)
!추가하는것도 O(N)이 소요된다

따라서 추가와 삭제가 반복되는 로직이라면 배열 사용을 권장하지 않는다.!!

JS에서의 배열은 동적으로 작동
배열의 크기가 필요에 따라 줄기도 늘기도한다
인덱스가 숫자가아닌 문자열이나 논리값이 들어간다
그러나 인덱스와 무관한 값을 인덱스에 사용한경우 길이에 영향을 미치지 않는다.

스택

LAST IN FIRST OUT
선형 자료구조
EX)프링글스

스택 활용?
스택 메모리
함수호출 생성되는 지역변수, 매개변수가 저장되는 지역메모리

js에서는?

stack 은 배열로 표현가능
배열을 사용하며, push 왜 pop을 사용하면 된다.

큐

first in first out이라는 개념을 가진 선형 구조이다
현실에 비유하자면 대기줄!

선형큐

배열로 표현

연결리스트로 구현 가능
헤드는 프론트 tail은 rear
인덱스 고민끝!

js에선?
!shift()는 쓰지마세요!!
와요?
js에서 선형시간이 걸리기때문이에오

해시 테이블

키와 값을 받아 키를 해싱하여 나온 index에 값을 저장하는 선형구조
사물함처럼 헤시테이블도 키를 인덱스에 넣어둔다.

만약 해시 함수의 결과가 동일하여 겹친다면?
->이를 해시 충돌이라 부른다

해시충돌을 해결하려면?

• 선형 탐사법

  충돌이 발생하면 옆으로 한 칸 이동한다.

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

충돌이 발생할수록 데이터가 몰리는것이 선형보다 덜하다

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

• 분리 연결법
  버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다.

js에선 해시테이블을 어떻게 사용할까?
객체를 이용해서 사용한다

map,set,reduce를 사용할 수 도 있다.

그래프의 특징

• 비선형이므로 앞뒤로 여러개의 구조를 가질 수 있다.
• 정점은 여러개의 간선을 가질 수 있다
• 크게 방향 그래프와 무방향 그래프로 나눌 수 있다
• 간선은 가중치를 가질 수 있다
• 사이클이 발생할 수 있다. 무한루프가 발생하지 않는게 중요!

그래프의 종류

• 무방향 그래프
  간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다.
  표현하기에 (a,b)와 (b,a)는 같은 간선으로 취급

• 방향 그래프
  간선에 방향성이 존재하는 그래프
  양방향으로 갈 수 있더라도 <A,B> <B,A>는 다른 간선으로 취급된다
  EX)일방 통행

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

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

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

• 그래프의 JS로 사용법
  인접행렬

인접리스트로 나타 낼 수 있음

리스트

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

연결리스트의 특징

메모리가 허용하는한 요소를 제한없이 추가할 수 있다
탐색은 O(N)이소요
요소를 추가, 제거할때는 O(1)이 소요된다

배열과 차이점

메모리 차이
배열은 순차적으로 데이터가 들어가서 데이턱가 연속적으로 들어감
배열 요소 삭제는 O(N)이 걸린다.
왜냐하면 빈요소를 앞으로 당기기위해
추가도 맟찬가지
추가하기우해 뒷요소를 뒤로 당겨야한다

연결리스트는 퍼져있기 때문에 포인터를 사용하여 각 영역을 참조

연결리스트의 요소삭제

삭제요소 선택->삭제할 요소의 이전 요소가 가르키는 포인터를 삭제할 요소의 다음요소에 연결한다
O(1)이 걸린다

연결리스트의 요소추가

추가할 요소의 포인터를 끼어넣을부분을 가르키게 만든다.
이전의 요소의 포인터늘 추가할 요소에 가르킨다

단일연결리스트(singly linked list)

head에서 tail까지 단방향으로 이어지는 연결리스트이다
가장 단순한 형태인 연결 리스트다.

핵심 로직

추가

헤드로 추가

중간에 추가

코드

 insert(node, newvalue){
    const newNode = new Node(newvalue);
    newNode.next=node.next;
    node.next = newNode;
 }

찾기

코드

 find(value){
    let currNode = this.head;
    while (currNode.value!==value){
        currNode=currNode.next;
    }
    return currNode;
 }

삭제

코드

remove(value){
    let preNode=this.head;
    while (preNode.next.value!==value){
        preNode=preNode.next;
    }
    if (preNode.next !==null) {
        preNode.next =preNode.next.next;
    }

double 연결리스트

양방향으로 이어지는 연결 리스트
singly linked list 보다 자료구조의 크기가 조금 더 크다

요소추가

1. 추가할 요소의 다음노드를 다음 요소에가르키게 만들고
2. 추가할 자리의 이전요소의 다음노드를 추가할 요소를 가리키게 만듭니다
3.다음요소의 이전 노드를 추가할요소를 가르키도록 수정합니다
4. 추가할요소의 이전노드를 이전요소를 가르키게 만듭니다

상수시간만이 소요 됩니다

요소 삭제

1.삭제할요소의 이전요소의 다음노드를 삭제할요소의 다음요소를 가르키도록 한다.

2.삭제할요소의 다음요소의 이전노드를 삭제할 요소의 이전 요소를 가르키게 한다

환영 연결리스트

한가지를 제외하면 된다.
tail이 head로 연결되는 연결리스트 메모리를 아껴쓸 수 있다. 원형 큐 등을 만들때도 사용

느낀점

오늘 하루 정말 정신이 없었다. 자료구조 과목의 절반 수준을 하루에 이해하고, 적용하여 문제를 풀려니까 힘들었지만, 한번 배운 내용이기에 다시한번 상기하고, 모르는 점을 짚고 넘어가기 좋았다. 내일부터는 자료구조의 나머지를 배우고,과제가 있다는데...? 스터디 cs 발표준비를 해야 하는데, 시간 관리를 조금 더 잘해서 코스내 과정을 소화해야겠다. 오늘은 배운것이 많아 다시한번 정리해야지. 내일의 나를 위하여~ -끝