자료구조

참고 블로그 1
참고 블로그 2
참고 블로그 3
참고 블로그 4

✅ 선형 자료구조 (배열, 리스트, 스택, 큐, 데크)

💡 배열

동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고있는 집합

• 각 원소의 물리적 순서(메모리 주소)가 논리적 순서(인덱스 번호)와 동일
• 정적 자료 구조
• 반복적인 데이터 처리 작업에 적합한 구조
• 조회에 걸리는 시간 복잡도 : O(1)

💡 선형 리스트

일정한 순서에 의해 나열된 자료 구조

1. 연속 리스트

배열과 같이 연속되는 기억장소에 저장되는 자료 구조

• Python의 리스트

2. 연결 리스트

연속적이진 않으나 임의의 기억 공간에 기억시키되, 포인터를 이용해 연결한 자료구조

• 데이터 + 노드(링크를 가짐)
• 논리적 순서와 물리적 순서가 동일하지 않음
• 원소의 삽입 삭제가 빠르나 조회O(n)가 비효율적
  

💡 스택

리스트의 한쪽 끝으로만 자료의 삽입push, 삭제pop 작업이 이루어짐

• LIFO(Last in Firsh Out) : 후입선출. 가장 나중에 들어온 게 가장 먼저 삭제
• 스택의 모든 기억공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 Overflow 발생
• 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 Underflow 발생
• 맨 위 TOP 맨 바닥 BOTTOM

💡 큐

리스트의 한 쪽 에서는 삽입, 다른 한 쪽 에서는 삭제가 이루어지는 자료구조

• FIFO(First in First out) : 선입선출. 가장 먼저 들어온 게 먼저 삭제
• 시작을 표시하는 Front 프런트 포인터와 (제일 먼저 삭제 될 부분)
• 가장 마지막에 삽입된 부분인 Rear 포인터 존재
  

💡 데크

삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료 구조

스택과 큐의 장점을 따서 구성되었다.

✅ 비선형 자료구조 (트리, 그래프)

💡 트리

정점 Node 와 선분 Branch 를 이용해서 사이클를 이루지 않도록 구성한 그래프의 특수 형태

1. 트리의 운행법

1) Preorder 운행 ; 전위 순회

root -> left -> right

위 예제로 전위 순회를 해보자.

2) Inorder 운행 ; 중위 순회

left -> root -> right

위 예제로 중위 순회를 해보자.

3) Postorder 운행 ; 후위 순회

left -> right -> root

위 예제로 후위 순회를 해보자.

2. 트리 관련 개념

* 노드

트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것

이라고 하는데, 그냥 간단하게 트리의 동그라미 하나라고 생각하면 됨!

* Root node ; 뿌리 노드, 근 노드

트리의 맨 위에 있는 노드

* Terminal Node = Leaf Node ; 단말 노드, 잎 노드

자식이 하나도 없는 노드, 즉 디그리가 0

* 부모노드, 자식노드, 형제노드

부모 노드 아래에는 자식 노드들이 있으며,
같은 부모 노드를 가지는 애들이 형제 노드!

* Degree ; 디그리, 차수

각 노드에서 뻗어나온 가지의 수
❗ 트리의 차수 : 전체 트리에서 가장 많은 차수

💡 그래프

• G = (V, E)
• 그래프 D는 정점 V(Vertex)와 간선 E(Edge)의 두 집합으로 이루어져있다!

트리는 사이클이 없는 그래프!