TIL 3일차

배열(순차 리스트)

연관된 데이터를 연속적인 형태로 구성된 구조를 가지며, 배열에 포함된 원소는 순서대로 번호(index)가 붙는다. index를 활용해서 꺼내 쓰거나 새로운 데이터를 넣을 수 있다.

특징

• 고정된 크기를 가지며 일반적으론 동적으로 크기를 늘릴 수 없다.(C일 경우) 하지만 스크립트언어(javascript, python)는 동적으로 크기가 증감되도록 만들어져 있다.
• 원하는 원소의 index를 알고 있다면 O(1)로 원소를 찾을 수 있다.
• 원소를 삭제하면 해당 index에 빈자리가 생긴다.
• 추가와 삭제 시 중간에 추가하거나, 삭제 후 순서를 맞추려면 O(n)이 소요된다.
• 추가와 삭제가 반복되는 로직이라면 배열 사용을 권장하지 않는다.
• 자바스크립트에서는 배열이 근복적으로 객체이기 때문에 숫자 외에 다른 값을 index에 넣는다면 자동으로 key값으로 문자열로 들어간다. 하지만 객체와 다른점은 length가 내부적으로 관리 되기 때문에 배열이 존재한다.

연결리스트

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

특징

• 배열과 다르게 메모리가 허용하는 한 요소를 제한 없이 추가할 수 있다.
• 배열과 다르게 탐색은 O(n)(선형시간)이 소요된다.
• 요소를 추가하거나 제거할 때는 O(1)이 소요된다. 탐색,추가,제거는 배열과 정반대인 시간을 갖는 특징을 가짐
• 추가와 삭제가 연속적으로 일어나는 로직이라면 연결리스트가 효율적이다.

종류

• 단일 연결 리스트(Singly Linked List): Head에서 Tail까지 단방향으로 이어지고 가장 단순한 형태인 연결리스트다. 포인터 영역이 Null이면 연결리스트의 끝이다.
• 이중 연결 리스트(Doubly Linked List): 양방향으로 이어지는 연결리스트이며 단일연결리스트보다 자료구조의 크기가 크다.
• 환형 연결 리스트(Circular Linked List): Singly 혹은 Doubly Linked List에서 Tail이 Head로 연결되는 연결 리스트이며, 메모리를 아껴쓸 수 있는 장점이 있다. 또한 원형 큐 등을 만들때도 사용된다.

스택

Last In First Out이라는 개념을 가진 선형 자료구조이다. keyword는 push(추가), pop(삭제), top(최상단)이고, 바닥이 막힌 상자를 생각하면 편하다.

큐

First In First Out 이라는 개념을 가진 선형 자료구조이며, Linear Queue와 Circular Queue가 존재한다. 또한

특징

• 맨 앞을 Front라고 하며, 맨뒤를 Rear라고 한다.
• 요소를 제거하는 것을 Dequeue라고 하며 Front가 사라지는 것을 의미한다.
• 요소를 삽입하는 것을 Enqueue라고 하며 Rear에 추가 해준다.

해시 테이블

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

문제점

해시함수의 결과가 동일하여 겹친다면 문제점이 발생함 이를 해시 충돌이라고 한다.

해결법

• 선형 탐사법: 충돌이 발생하면 충돌이 나지 않게 한칸 씩 이동한다.
• 제곱 탐사법: 충돌이 발생한 지점에서 발생한 횟수의 제곱만큼 옆으로 이동한다.
• 이중해싱: 충돌이 발생하면 다른 해시함수를 이용한다.
• 분리 연결법: 버킷의 값을 연결리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다.

그래프

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이며, 정점(Node) 집합과 간선(Edge) 집합으로 표현할 수 있다.

특징

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

그래프 종류

1. 무방향 그래프 간선의 방향이 없다라는 뜻이며 반대로 말하면 양방향으로 이동이 가능하다. 표현하기에 A→B 와 B→A는 같은 간선으로 취급된다.
2. 방향 그래프 간선에 방향이 존재하고 간선 두개 중 하나가 존재하지 않는다면 그것은 이동 할 수없다.
3. 연결 그래프 모든 정점이 서로 이동 가능한 상태인 그래프
4. 비연결 그래프 특정 정점쌍 사이에 간선이 존재하지 않는 그래프
5. 완전 그래프 모든 정점끼리 연결된 상태인 그래프
6. 사이클 그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분

🚑깨달은 점

항상 알고리즘 공부를 하면서 왜 JS는 자료구조 라이브러리가 없는 거야 이러면서 툴툴 거렸던 적이 있었다.😣 하지만 문제를 빨리 풀어야지라는 생각에 쌓여 직접 자료구조를 구현하지 못했었다. 이번 데브코스에 나의 모든 시간을 쏟고 처음부터 꼼꼼히 가자는 생각에 자료구조를 구현하는 경험을 했다.

그중 평소에 알고리즘 문제를 풀면서 가장 궁금했던 부분이 queue였다. 왜냐하면 js는 queue를 활용하려면 배열을 사용하여 푼다. Enqueue 과정은 배열에 push 하기 때문에 시간적으로 문제가 없었지만, Dequeue 는 shift메서드를 사용해야 되는데 shift를 사용하게 되면 시간이 pop하는 시간보다 6배? 정도 많이 걸리는 것으로 알고있었다. 그래서 이번 수업에서 queue를 연결리스트로 구현하면 이 문제가 해결되는 것을 알게 됐다. 그래서 queue를 강의 보면서 직접 구현하면서 나의 지식의 갈증을 채울 수 있었다. 3일차 TIL인데 아주 성공적이었다.😊

🚀Feedback

자료구조 별 시간 복잡도 추가

참고

https://daelumgi.postype.com/post/5270208