[알고리즘/자료구조] 자료구조

자료구조

: 여러 데이터의 묶음을 저장하고 사용하는 방법을 정의한 것

: 데이터 (문자,소리,그림,영상 등 실생활을 구성하는 모든 값으로 이를 필요에 따라 데이터의 특성을 파악하여 정리해 저장해 놓는 것이 활용에 유리함)

 

[Stack]

스택(Stack) : 쌓다, 포개지다의 뜻으로 데이터가 쌓이는 순서대로 쌓는 자료구조

구조

: 입력과 출력이 하나의 방향으로 이루어진 제한적 접근

: LIFO(Last In First Out) 구조

특징

: 데이터는 하나씩 넣고 뺄 수 있음

: 하나의 입출력 방향을 가짐

: 먼저 들어간 데이터는 가장 나중에 나오는 후입선출 구조

 

[용어]

스택용 배열 stk

스택 용량 capacity

  ptr : 스택 포인터

  IntStack : 생성자

  push(int x) : 데이터를 푸쉬하는 메서드 (스택이 찼을 경우 에러 발생)

  pop() : 데이터를 제거하고 그 값을 반환하는 메서드 (스택이 비었을 경우 에러 발생)

  peek() : 꼭대기 데이터를 들여다보는 메서드 (스택이 비었을 경우 에러 발생)

  clear() : 스택 내 모든 요소를 삭제하는 메서드

  indexOf(int x) : 같은 값의 데이터가 포함되어 있는지, 포함되어 있다면 어디에 들어있는지를 조사하는 메서드

  getCapacity() : 스택 용량 반환하는 메서드

  size() : 스택 데이터 개수 반환하는 메서드

  isEmpty() : 스택이 비어있는지 검사하는 메서드

  isFull() : 스택이 가득 찼는지 검사하는 메서드

  dump() : 스택 내 모든 데이터를 출력하며 바닥부터 꼭대기 순으로 출력

 

[Queue]

큐(Queue) : 줄을 서서 기다리다, 대기행렬 이라는 뜻으로 데이터가 먼저 들어간 것이 먼저 나가는 자료구조

구조

: 입력과 출력 방향이 고정되어 있어 두 곳으로 접근 가능

: FIFO(First In First Out) 구조

특징

: 데이터는 하나씩 넣고 뺄 수 있음

:두개의 입출력 방향을 가짐

: 먼저 들어간 데이터는 먼저 나오는 선입선출 구조

 

[용어]

  스택용 배열 stk

  스택 용량 capacity

  ptr : 스택 포인터

  IntQueue : 생성자

  enque / add / offer(int x) : 데이터를 푸쉬하는 메서드 (스택이 찼을 경우 에러 발생)

  deque / poll() : 데이터를 제거하고 그 값을 반환하는 메서드 (스택이 비었을 경우 에러 발생)

  peek() : 꼭대기 데이터를 들여다보는 메서드 (스택이 비었을 경우 에러 발생)

  clear() : 스택 내 모든 요소를 삭제하는 메서드

  indexOf(int x) : 같은 값의 데이터가 포함되어 있는지, 포함되어 있다면 어디에 들어있는지를 조사하는 메서드

  getCapacity() : 스택 용량 반환하는 메서드

  size() : 스택 데이터 개수 반환하는 메서드

  isEmpty() : 스택이 비어있는지 검사하는 메서드

  isFull() : 스택이 가득 찼는지 검사하는 메서드

  dump() : 스택 내 모든 데이터를 출력하며 바닥부터 꼭대기 순으로 출력

 

[Graph]

그래프(Graph) : 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조

인접 행렬

: 모든 경우를 저장하기에 메모리 차지를 많이 함

: 두 정점 사이 관계 존재 여부를 판단하기에 용이함. 따라서 가장 빠른 경로를 찾을 경우 사용

: 두 정점을 바로 이어주는 간선이 존재할 경우 각 정점은 인접

인접 리스트

: 각 정점마다 리스트가 존재함

: 인접 행렬과 비교했을 때 메모리 차지가 덜하기에 메모리를 효율적으로 사용하고자 할 경우 사용

: 각 정점이 어느 정점과 인접한지를 리스트 형태로 표현

 

[기본 용어]

  정점(vertex) : 노드라고도 하며, 데이터가 저장되는 기본 원소

  간선(edge) : 정점간의 관계

  인접 정점(adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점

  가중치 그래프(weight Graph) : 연결의 강도(추가적인 정보)가 얼마나 되는지 적혀있는 그래

  비가중치 그래프(unweight Graph) : 연결의 강도가 적히지 않은 그래프

  무(방)향 그래프(undirected Graph) : 단방향이 아닌 양방향인 그래프

  진입 차수(in-degree) : 한 정점에 들어오는 간선의 수

  진출 차수(out-degree) : 한 정점에서 나가는 간선의 수

  자기 루프(self loop) : 정점에서 진출한 간선이 자신에게 진입하는 경우(다른 정점을 거치지 않고 자신에게 돌아옴)

  사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아오는 경우(다른 정점을 거치고 자신에게 돌아올 수 있음)

 

[Tree]

트리(Tree)

: 데이터 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계증적 자료구조로 사이클이 존재하지 않음

: 그래프의 여러 구조 중 단방향 그래프의 한 구조로 하나의 뿌리로부터 가지가 사방으로 뻗은 형태의 자료구조

깊이(depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현

레벨(level) : 깊이를 가진 노드를 묶어서 표현하며 같은 레벨에 나란이 있는 노드를 형제노드라 함

높이(heigth) : 리프 노드를 기준으로 루트까지의 높이

 

[용어 정리]

노드(Node) : 트리 구조를 이루고 있는 모든 개별 데이터

루트(root) : 트리의 최상위 노드 (=트리 구조의 시작점)

부모 노드(Parent Node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드

자식 노드(Child Node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드

리프 노드(Leaf Node) : 트리 구조의 끝 지점으로 자식 노드가 없는 노드

 

[Binary Search Tree]

- 이진 트리(binary tree)

1) 정 이진 트리(Full Binary Tree) : 각 노드가 0개 또는 2개 자식 노드를 가짐

2) 포화 이진 트리(Complete Binary Tree) : 정 이진 트리이면서 완전 이진 트리로 모든 리프 노드의 레벨이 동일하고, 모 든 레벨이 가득 채워져 있는 트리

3) 완전 이진 트리(Perfect Binary Tree)

: 마지막 레벨을 제외하고 모든 노드가 가득 차있어야 하고, 마지막 노드는 가득 차 있지 않아도 되지만 왼쪽 노드는 채워져 있어야 함

: 자식 노드가 최대 2개인 노드로 구성된 트리로 삽입/삭제 방식에 따라 아래와 같 이 구분함

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

 : 입력 순서에 따라 값이 몰려 탐색 시 시간이 더 걸릴 수 있으며 재구조 과정 알고리즘 추가가 가능함

 : 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가짐

 

[Search Algorithm]

트리 순회 : 특정 목적을 위해 모든 노드를 한 번씩 반복

전위 순회 : 루트에서 시작하여 왼쪽 노드가 존재할 경우 왼쪽 노드를 우선 탐색함

중위 순회 : 맨 아래 왼쪽 노드에서 시작하며 왼쪽 > 부모 > 오른쪽 노드 순으로 탐색 진행

후위 순회 : 맨 아래 왼쪽 노드에서 시작하며 왼쪽 > 오른쪽 > 부모 노드 순으로 탐색 진행

 

BFS(Breathed First Search)

: 가까운 정점부터 탐색을 진행하며, 탐색할 것이 없을 경우 다음 정점으로 이동

: 정점 사이의 최단 경로 탐색에 이용

: 너비 우선 탐색

 

DFS(Depth First Search)

: 하나의 경로를 끝까지 탐색 후, 목적지가 아니라면 다음 경로로 이동

: BFS보다 시간이 오래 걸리나 모든 정점 탐색이 가능

: 깊이 우선 탐색