데이터 입출력 구현

(1) 자료구조

1. 자료구조 개념

- 자료구조는 컴퓨터 자료를 효율적으로 저장하기 위해 만들어진 논리적인 구조

- 효율적인 알고리즘을 사용할 수 있게 하기 위하여 성능을 향상시키는 목적

 

 

2. 자료구조의 분류

구조	설명	종류
선형 구조	데이터를 연속적으로 연결한 자료 구조	리스트, 스택, 큐, 데크
비선형 구조	데이터를 비연속적으로 연결한 자료구조	트리, 그래프

 

 

3. 선형 구조

[1] 리스트

리스트의 종류

 

선형 리스트 : 배열과 같이 연속되는 기억 장소에 저장되는 리스트, 대표적으로 배열이 있음, 가장 간편한 자료 구조, 자료의 삽입, 삭제 시 기존 자료의 이동 필요

연결 리스트 : 노드의 포인터 부분으로 서로 연결시킨 리스트, 노드의 삽입, 삭제가 선형 리스트와 달리 편리함, 포인터가 추가되어 저장 공간이 추가로 필요, 포인터를 통해 찾는 시간이 추가되어 선형 리스트에 비해 느림

 

!!여기서 잠깐!!

포인터란?

- 포인터는 메모리 공간 주소를 가리키는 변수. 그래서 노드 = 데이터 + 링크

 

[2] 스택

- 스택은 한 방향으로만 자료를 넣고 꺼낼 수 있는 LIFO 형식의 자료 구조이다. 

- 한 방향으로만 PUSH와 POP을 이용하여 자료를 넣고 꺼낸다. 

- TOP은 스택에서 가장 위에 있는 데이터로, 스택 포인터라고도 불린다.

 

 

!!여기서 잠깐!!

PUSH와 POP은 무엇일까?

PUSH - 데이터를 차례대로 스택에 넣는 연산

POP - 스택에서 가장 위에 있는 데이터를 하나씩 꺼내는 연산

 

<스택의 자료 삽입 코드>

If Top = n Then
   Overflow
Else {
 Top = Top + 1
 insert S(Top)
}
//스택에 데이터가 n개이면 삽입할 공간이 없으므로 오버플로우
// 스택에 데이터가 n개가 아니면 스택 포인터 Top 값을 1 증가
//스택 포인터 Top이 가리키는 곳에 데이터 삽입

 

<스택의 자료 삭제 코드>

If Top = 0 Then
	Underflow
Else {
   remove S(Top)
   Top = Top - 1
}
//스택에 데이터가 0개면 삭제할 데이터가 없으므로 언더플로우
//스택에 데이터가 0개가 아니면 스택 포인터 Top이 가리키는 곳에 데이터 삭제
//스택 포인터 Top 값을 1 감소

 

스택 응용 분야

• 인터럽트의 처리 : 현재 진행 중인 명령어 위치를 스택에 PUSH하고, 인터럽트 발생 상황을 처리한 후에 인터럽트 전에 진행 중이던 명령어 위치를 스택에서 POP을 통해 받아옴
• 함수 호출 : 함수 호출 시 현재 진행 중인 명령어 주소를 스택에 저장
• 후위표현 연산 : Postfix를 계산할 때 사용
• 깊이 우선 탐색 : 깊이 내려갈 때마다 스택에 값을 PUSH하고, 더 이상 깊이 갈 곳이 없을 경우 스택에서 POP한 노드와 인접한 노드를 찾음 

 

[4]  큐

- 큐(Queue)는 한쪽 끝에서 삽입 작업이 이뤄지고, 반대쪽 끝에서는 삭제 작업이 이루어지는 FIFO(FIirst-In First-Out)형식의 자료 구조이다. 

- 한쪽에서는 ENQUEUE 연산을 이용하여 데이터를 넣고, 한쪽에서는 DEQUEUE 연산을 이용하여 데이터를 꺼낸다. 

- 데이터가 꺼내는 쪽에서 가장 가까운 데이터를 Front라고 하고, 데이터를 넣는 쪽에서 가장 가까운 데이터를 Rear라고 한다. 

 

[5] 데크

- 데크는 큐의 양쪽 끝에서 삽입과 삭제를 할 수 있는 자료 구조이다. 

- 두 개의 포인터를 사용하여, 양쪽의 삭제/삽입이 가능하다.

- 데크를 이용한 스택과 큐의 구현이 가능하다. 

- 데크 연산에는 PUSH(데이터를 차례대로 넣는 연산), POP(데크에서 Front와 Rear에 있는 데이터를 하나씩 꺼내는 연산)이 있다.

 

4. 비선형 구조

[1] 트리

- 트리는 데이터들을 계층화시킨 자료 구조이다. 

- 노드와 선분으로 되어있고, 정점 사이에 사이클이 형성되어 있지 않으며, 자료 사이의 관계성이 계층 형식으로 나타나는 비선형 구조이다. 

- 인덱스를 조작하는 방법으로 가장 많이 사용하는 구조다.

- 트리는 노드와 노드를 연결하는 링크로 구성된다.

- 배열과 달리 노드들이 포인터로 연결되어 노드의 상한선이 없다. 

 

▼ 트리 용어

• 루트 노드 : 트리에서 부모가 없는 최상위 노드, 트리의 시작점
• 단말 노드 : 자식이 없는 노드, 트리의 가장 말단에 위치
• 레벨 : 루트 노드를 기준으로 특정 노드까지의 경로 길이
• 조상 노드 : 특정 노드에서 루트에 이르는 경로산 모든 노드
• 부모 노드 : 특정 노드에 연결된 이전 레벨의 노드
• 형제 노드 : 같은 부모를 가진 노드
• 깊이 : 루트 노드에서 특정 노드에 도달하기 위한 간선의 수
• 차수 : 특정 노드에 연결된 자식 노드의 수

▼ 트리 순회방법

- 전위 순회 : 먼저 노드를 방문하고, 왼쪽 서브 트리를 방문한 후, 오른쪽 서브트리를 방문하는 순으로 순회

- 중위 순회 : 왼쪽 서브 트리를 중위 순회하고, 노드를 방문한 후, 다시 오른쪽 서브 트리를 중위 순회하는 방식

- 후위 순회 : 왼쪽 서브 트리를 후위 순회하고, 다시 오른쪽 서브 트리를 후위 순회한 뒤에 노드를 방문하는 방식

 

▼ 트리 종류

[1] : 이진 탐색 트리 

- 차수가 2 이하인 노드로 구성되어 자식이 둘 이하로 구성된 트리

- 이진 탐색 트리는 부모 노드보다 작은 값은 왼쪽으로 부모 노드보다 큰 값은 오른쪽 노드에 생성

 

[2] : AVL 트리

- 두 자식 서브 트리의 높이는 항상 최대 1만큼만 차이가 나도록 스스로 균형을 잡는 이진 탐색 트리

 

[3] : 레드-블랙 트리

 - 각 노드는 빨강 또는 검정의 색상을 가지고 있으며, 색깔에 따른 규칙을 통해 스스로 균형을 잡는 이진 탐색 트리

 

▼ 그래프

그래프의 개념

- 그래프는 노드와 노드를 연결하는 간선을 하나로 모아놓은 자료 구조

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

 

* 그래프의 유형

방향 그래프 : 정점을 연결하는 선에 방향이 있는 그래프

우방향 그래프 : 정점을 연결하는 선에 방향이 없는 그래프

 

* 그래프 용어

경로 : 임의 정점에서 다른 정점으로 이르는 길

경로 길이 : 경로상 있는 간선의 수

단순 경로 : 한 경로의 모든 간선이 다를 때의 경로

사이클 : 동일 정점에서 시작과 끝이 이어지는 경로

 

(2) 논리 데이터 저장소

1. 논리 데이터 저장소 개념

- 업무를 모델링 표기법으로 형상화한 데이터의 저장소

- 물리 데이터 저장소와는 별개로 사용자 혹은 개발자가 이해하기 쉬운 논리적인 구조로 추상화하여 제공

 

▼ 논리 데이터 저장소 구조

• 개체 : 관리할 대상이 되는 실체
• 속성 : 관리할 정보의 구체적 항목
• 관계 : 개체 간의 대응 관계