자료구조

자료구조(Data Structure), 알고리즘(Algorithm)

-> 자료구조(메모리), 알고리즘(속도)

 

어떻게 하면 최저의 비용으로 최고의 성과를 낼지
메모리가 줄면, 속도도 줄어든다. (비용감소)
메모리가 증가하면, 속도도 빨라진다. (비용증가)

 

- 자료구조 : 데이터를 효율적으로 저장, 조직화, 관리하기 위한 방법

1. 배열(Array)
2. 스택(Stack)과 큐(Queue)
3. 연결리스트(Linked List)
4. 트리(Tree)
5. 그래프(Graph)
6. 해시 테이블(Hash Table)

 

배열(Array)

동일한 유형의 요소들의 데이터들이 연속적인 메모리 공간에 저장되는 자료구조
1) 연속적인 메모리 공간 : 배열의 데이터들이 메모리에서 연속적으로 할당되기 때문에, 인덱스를 통해 데이터에 접근할 수 있다.
2) 고정된 크기 : 배열은 생성할 때 크기가 결정되며 일단 생성된 배열의 크기는 변경할 수 없다.
3) 인덱스 기반 접근 : 시작 요소가 0번째로 시작된다. 인덱스 기반 접근이기 때문에 빠른 읽기와 쓰기가 가능하다.
4) 동일한 유형의 데이터 저장

 

장점 : 속도가 빠르다, 연속적인 할당으로 캐시 지역성(Cache Locality) 성능 향상, 간단하고 직관적
단점 : 크기 제약, 삭제와 삽입 불가능, 메모리 낭비

 

스택(Stack)

후입선출(LIFO, Last-in-First-Out)
마지막에 삽입된 요소가 가장 먼저 제거된다.
push : 스택의 맨 위에 요소를 추가한다.
pop : 스택의 맨 위의 요소를 제거하고 반환한다.
peek/top : 스택의 맨 위의 요소를 조회한다.

함수 호출과 복귀 : 함수 호출 시 호출된 함수의 정보(지역변수, 매개변수 등)을 스태겡 저장하고,
    함수가 완료되면 역순으로 복귀한다.
괄호 검사 : 괄호 짝이 맞는지 확인하기 위해 여는 괄호가 나오면 stack에 push 하고 (닫는 괄호가 나올 때까지)
    짝을 이루면 pop을 한다.
뒤집기 : 문자열, 배열 스택에 넣고 순서대로 꺼내면 역순이 된다.

 

큐(Queue)

선입선출(FIFO, First-In-First-Out)
가장 처음 삽입된 요소가 가장 먼저 제거된다.
Enqueue : 큐의 뒤쪽(rear)에 요소를 추가한다.
Dequeue : 큐의 앞쪽(front)이 요소를 제거하고 반환한다.
Front, Peek : 큐이 앞쪽에서 요소를 조회한다.

작업 대기열(Task Queue) : 여러 작업들이 들어올 때 순서대로 처리하기 위해 큐를 사용한다.
너비 우선 탐색(BFS, Breadth-First-Search) : 그래프나 트리 탐색 시 BFS에서 인접한 정점들을 방문 순서대로 처리한다.

 

연결 리스트(Linked List)

노드(node)들이 포인터로 서로 연결되어 있는 자료구조
노드 : 데이터와 다음 노드를 가르키는 포인터(주소)

1. 단일 연결 리스트(Singly Linked List)
각 노드는 데이터 필드와 다음 노드를 가르키는 포인터 필드로 구성된다.
마지막 노드의 포인터 필드 값은 보통 NULL이며, 이는 리스트의 끝을 나타낸다.

장점)
삽입, 삭제가 효율적이고 간단하다. 앞, 뒤 노드만 수정하면 되기 때문에
동적 크기 조정이 가능하다.
단점)
특정 위치에 직접 접근하기 위해서는 처음부터 순차적으로 탐색해야 한다. (탐색시간 증가)

2. 이중 연결 리스트(Doubly Linked List)
각 노드는 데이터 필드와 이전 노드를 가리키는 포인터 필드, 다음 노드를 가리키는 포인터 필드로 구성된다.
첫 번째 요소, 마지막 요소에 대한 접근이 가능하다.

장점)
양방향으로 탐색이 가능하여 특정 위치에서의 삽입과 삭제가 단일 연결리스트보다 효율적이다.
역방향 탐색 및 반대방향에서의 삽입/삭제가 가능하다.

단점)
이전(prev) 포인터를 유지해야하므로 추가 메모리 공간을 사용한다.

트리(Tree)

비선형 계층구조를 표현하는 자료구조다.
트리는 노드들의 집합으로, 하나의 루트 노드와 0개 이상(없을 수도 있음)의 부분 트리(subtree)로 구성되어 있다
각 부분 트리는 또한 0개 이상의 부분 트리로 구성되어 있다.

+ 이진 트리(Binary Tree) : 이진 트리는 최대 2개의 자식을 가질 수 있는 특별한 트리다.
각각의 노드는 최대 2개의 자식 노드를 가지며, 왼쪽 자식과 오른쪽 자식으로 부른다.

1) 정 이진 트리(Full Binary Tree) : 모든 레벨(깊이)에서 노드가 꽉 찬 이진 트리다.
모든 부분 트리들이 2개의 자식 노드를 가지고 있으며 같은 깊이에 존재한다.
2^n - 1 개가 같은 깊이에 존재해야 한다.

2) 완전 이진 트리(Complete Binary Tree) : 마지막 레벨을 제외하면 모든 노드가 완전히 채워져 있으며,
마지막 단계에서도 왼쪽부터 순서대로 채워져 있는 이진 트리다.

3) 편향 이진 트리(Skewed Binary Tree) : 각각의 내부 노드들이 하나만 있는 경우다.
왼쪽으로 치우치면 Left Skewed, 오른쪽으로 치우치면 Right Skewed라고 부른다.

4) 이진 탐색 트리(Binary Search Tree) : 각 노드의 왼쪽 서브트리에 있는 모든 노드의 값이 해당 노드의 값보다
작고, 오른쪽 서브트리에 있는 모든 노드의 값이 해당 노드의 값보다 큰 구조로 설계된 이진 트리다.
이러한 속성때문에 BST 검색, 삽입, 삭제 등 연산을 평균적으로 O(log n) 시간 복잡도에서 처리할 수 있다.

-  검색(Search) : 루트에서 시작해서 찾으려는 갑싱 현재 노드와 같으면 해당 노드값을 반환한다.
    찾으려는 값이 현재 노드값보다 작으면 왼쪽으로 크면 오른쪽으로 이동한다.

- 삽입(Insertion) : 루트에서 시작해서 삽입하려는 값이 현재 값보다 작으면 왼쪽, 크면 오른쪽으로 이동한다.

- 삭제(Deletion)
삭제할 노드가 리프노드(최하위 노드)인 경우 단순 노드 삭제.
삭제할 노드가 자식 노드를 하나 가지고 있을 경우 그 위치에 자식 노드를 올린다.
삭제할 노드가 자식 노드를 두개 가지고 있을 경우 보통은 오른쪽 중 최소값을 찾아서 그 위치로 올린다.

 

그래프(Graph)

노드(node)와 노드 사이에 연결된 간선(edge)의 정보를 가지고 있는 자료구조다.

그래프는 방향이 있을 수도(directed) 없을 수도(undirected) 있다.

다양한 구조로 설계된다. 구조에 따라 시간 복잡도가 달라지고 다양하게 응용이 가능하다.

새로운 요소들의 추가/삭제가 용이하고 효율적이다.

시간 복잡도/공간 복잡도를 이야기할 때, 노드와 엣지의 수를 사용하여 표현한다.

 

해시 테이블(Hash Table)

해시 테이블은 키(Key)와 값(value)으로 데이터를 저장하는 자료구조로 빠른 검색이 필요할 때 용이하다.

해시 테이블을 구현하기 위해서는 연결 리스트와 해시 함수가 필요하다. 해싱은 해시 함수를 통해서 임의의 값을 고정된 크기의 값으로 변환하는 작업을 말하는데, 키 값을 받아서 해시 함수를 통해 얻은 해시(hash)를 배열의 인덱스로 환산하여 값에 접근하는 것을 의미한다.