[Algorithm] 1. Data Structure 복습

자료구조와 알고리즘

- 프로그램이란 데이터를 표현하고 (자료구조) 그렇게 표현된 데이터를 처리하는 것 (알고리즘)

- Input → [Process] → Output

 

자료구조의 분류

- 선형 구조: 1 : n / 비선형 구조: n : m

- 배열, 연결리스트: 물리적으로 어떻게 저장되어 있는지로 구분

- 스택, 큐: 접근 방식에 따라 구분

 

ADT (Abstract Data Type)

- 데이터 타입을 추상적으로 정의한 것

- 데이터나 연산이 무엇(what)인가를 정의함 (Set of operations)

- 데이터나 연산을 어떻게(how) 컴퓨터 상에서 구현할 것인지는 정의하지 않음

- ADT가 설명해야 하는 것:

   - 자료구조를 어떻게 생성하고 제거하는지

   - 어떻게 item을 추가하고 삭제하는지

   - 어떻게 item을 검색/접근하는지

   - (collection이 비어있는지, 꽉 찼는지)

   - (collection의 sub set)

 

Array & Linked List

[ 배열 (Array) ]

- 같은 데이터형을 가진 원소가 순서 있게 구성된 집합

- 각 원소 구분하기 위해 index 사용

- 기억장치 내에서 순차적으로 저장된 리스트

- 하나의 배열은 연속적인 기억장소에 한 개의 블록으로 저장

[ 연결 리스트 (Linked List) ]

- 리스트의 항목들을 node라고 하는 곳에 분산하여 저장

- Node = 데이터 필드 + 링크 필드

   - 데이터 필드: 리스트의 원소, 데이터 값 저장하는 곳

   - 링크 필드: 다른 node의 주소 값을 저장하는 곳 (포인터)

- 종류: 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트

Linked List 종류

- 장점: 삽입/삭제가 용이, 연속된 메모리 공간 필요 없음, 크기 제한 없음

- 단점: 구현 어려움, 오류 발생 확률 높음

Array vs Linked List

 

Stack & Queue

[ 스택 (Stack) ]

- 후입선출 (LIFO: Last In First Out)

- push(): 스택에 데이터 추가 (overflow 발생 가능)

- pop(): 스택에서 데이터 삭제 (underflow 발생 가능)

Stack 구조

[ 큐 (Queue) ]

- 선입선출 (FIFO: First In First Out)

- enqueue(), dequeue()

Queue 구조

- 종류: 선형 큐, 원형 큐, deq

Queue 종류

 

Tree & Graph

[ Tree ]

- 계층적 구조를 나타내는 자료구조 (부모-자식 관계 노드)

- 종류: 이진 트리, 일반 트리

Binary Tree 표현 방법 2가지

- 트리 순회 (traversal): 트리의 모든 노드를 중복 없이 한번씩만 방문해서 순회하는 과정

   - 전위 순회 (Pre-order Traversal): Root > Left > Right

   - 중위 순회 (In-order Traversal): Left > Root > Right

   - 후위 순회 (Post-order Traversal): Left > Right > Root

- Heap:

Max Heap, Min Heap

- 이진 탐색 트리 (Binary Search Tree):

   - 왼쪽 sub tree는 반드시 부모 노드 값보다 작아야 함

   - 오른쪽 sub tree는 반드시 부모 노드 값보다 크거나 같아야 함

Binary Search Tree

BST 삭제

- AVL Tree:

   - Balancing factor가 2 미만

   - 왼쪽이 크면 양수, 오른쪽이 크면 음수

   - 균형을 위한 rotation

AVTL Tree Rotation

- 2-3 Tree:

   - 하나의 node 안에 최대 2개의 요소가 가능하며, 자식 노드는 3개까지 가능

   - Height-balanced (모든 leaves는 같은 level)

2-3 Tree

[ Graph ]

- 연결되어 있는 객체 간 관계가 N:M인 자료구조

- 그래프 G = (V, E)
- 정점(vertices) → V(G): 그래프 G의 정점들의 집합

- 간선(edge) → E(G): 그래프 G의 간선들의 집합

Adjacent Matrix

Adjacency List

 

Hashing

- Key 값 비교를 통해 탐색하고자 하는 항목에 접근

- Key 값에 대한 산술적 연산에 의해 테이블의 주소를 계산하여 항목에 접근

Hash Table

- 충돌:

   - 서로 다른 탐색 key를 갖는 항목들이 같은 해시 주소를 가지는 현상

   - 충돌 발생하면 해시 테이블에 항목 저장 불가능

   - 해결책 1) 선형 조사법: 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장

   - 해결책 2) 체이닝: 각 버켓에 삽입/삭제가 용이한 연결 리스트 할당