📌 데이터 입, 출력 구현 - 자료 구조

 

 

목차

 

 

💡 주요 키워드 ? 배열, 스택, 그래프, 트리, 정렬, 데이터베이스, DBMS, 스키마, SQL, 트랜잭션

 

 

자료 구조의 정의

📌 효율적인 프로그램을 작성할 때 가장 우선적 고려사항은 저장 공간의 효율성과 실행시간의 신속성이다.

📌 자료구조는 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹내에 존재하는 자료 간의 관계, 처리 방법 등을 분석하는 것을 말한다.

 

• 자료 구조는 자료의 표현과 그것과 관련된 연산이다.
• 자료 구조는 일련의 자료들을 조직하고 구조화하는 것이다.
• 어떠한 자료 구조에서도 필요한 모든 연산들을 처리할 수 있다.
• 자료 구조에 따라 프로그램 실행시간이 달라진다.

 

 

자료 구조의 분류

 

 

 

배열 (Array)

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

 

• 배열은 정적인 자료 구조로 기억장소의 추가가 어렵고, 데이터 삭제 시 데이터가 저장되어 있던 기억장소는 빈 공간으로 남아있어 메모리의 낭비가 발생한다.
• 배열은 첨자(인덱스)를 이용하여 데이터에 접근한다.
• 배열은 반복적인 데이터 처리 작업에 적합한 구조이다.
• 배열은 데이터마다 동일한 이름의 변수를 사용하여 처리가 간편하다.
• 배열은 사용한 첨자(인덱스)의 개수에 따라 n차원 배열이라고 부른다.

 

🔔 예) 

arr[0], arrp[1], arr[2] ... arr[n-1]

 

💡 arr은 변수의 이름이고 [숫자]는 첨자에 해당한다. 하나의 사각형은 하나의 기억장소를 가리키며, arr[0] 부터 a[n-1]까지 총 n개의 기억장소가 존재한다. 아울러 배열의 인덱스는 항상 0으로 부터 시작 한다.

 

🔔 예) 크이가 n * n인 2차원 배열 arr

arr[0][0], arr[0][1], arr[0][2] ... arr[0][n-1]

arr[1][0], arr[1][1], arr[1][2] ... arr[1][n-1]

arr[2][0], arr[2][1], arr[2][2] ... arr[2][n-1]

...,               ...,              ...,             ... arr[0][n-1]

arr[n-1][0], arr[n-1][1], arr[n-1][2] ... arr[n-1][n-1]

 

💡 2개의 첨자가 존재하는 2차원 배열로 arr[0][0] 부터 arr[n-1][n-1]까지 총 n x n 개의 기억장소가 존재한다.

 

 

선형 리스트 (Linear List)

📌 선형 리스트는 일정한 순서에 의해 나열된 자료 구조이다.

 

• 선형 리스트는 배열을 이용하는 연속 리스트(Contiguous List)와 포인터를 이용하는 연결 리스트(Linked List)로 구분된다.
• 연속 리스트(Contiguous List)
  • 연속 리스트는 배열과 같이 연속되는 기억장소에 저장되는 자료 구조이다.
  • 연속 리스트는 기억장소를 여속적으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋다.
  • 연속 리스트는 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 하며, 삽입, 삭제 시 자료의 이동이 필요하다.

 

 

💡 포인터는 현재의 위치에서 다음 노드의 위치를 알려주는 요소이다.
- 프런트 포인터(F. Front Pointer) : 리스트를 구성하는 최초의 노드 위치를 가리키는 요소
- 널 포인터(Null Pointer, Nil Pointer) : 다음 노드가 없음을 나타내는 포인터로 일반적으로 마지막 노드의 링크 부분에 0, \0 등의 기호를 입력 하여 표시

💡 밀도란 ? 일정한 면적에 무엇이 빽빽하게 들어 있는 정도를 말하는 것이다. 연속 리스트의 기억장소 이용 효율을 '밀도가 1'이라고 표현한 것은 연속 리스트는 기억장소를 연속적으로 배정받아 데이터를 기억하므로 배정된 기억장소를 빈 공간 없이 꽉차게 사용한다는 의미이다.

 

 

 

선형 리스트 (Linear List)

• 연결 리스트(Linked List)
  • 연결 리스트는 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.
  • 연결 리스트는 노드의 삽입, 삭제 작업이 용이하다.
  • 기억 공간이 연속적으로 놓여 있지 않아도 저장할 수 있다.
  • 연결 리스트는 연결을 위한 링크(포인터) 부분이 필요하기 때문에 순차 리스트에 비해 기억 공간의 이용 효율이 좋지 않다.
  • 연결 리스트는 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다.
  • 연결 리스트는 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.

 

연결 리스트의 종류

 

💡 노드는 자료를 저장하는 데이터 부분과 다음 노드를 가리키는 포인터인 링크 부분으로 구성된 기억 공간이다.

 

 

스텍 (Stack)

📌 스택은 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조이다.

 

• 스택은 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO: Last In First Out) 방식으로 자료를 처리한다.
• 스택의 응용 분야 : 함수 호출의 순서 제어, 인터럽트의 처리, 수식 계산 및 수식 표 기법, 컴파일러를 이용한 언어 번역, 부 프로그램 호출 시 복귀주소 저장, 서브루틴 호출 및 복귀 주소 저장
• 스택의 모든 기억 공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 오버플로(Overflow)가 발생 하며, 더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로(Underflow)가 발생한다.

 

 

• TOP : 스택으로 할당된 기억 공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소이다.
• Bottom : 스택의 가장 밑바닥이다.
• 자료의 삽입(Push)
  • M : 스텍의 크기
  • Top : 스택 포인터
  • X : 스택의 이름
  • Overflow : 스택으로 할당 받은 메모리 부분의 마지막 주소가 M번지라고 할 때, Top Pointer의 값이 M보다 커지면 스택의 모든 기억장소가 꽉 채워져 있는 상태이므로 더 이상 자료를 삽입할 수 없어 Overflow를 발생시킨다.
  •  

Top = Top + 1		// 스택 포인터(Top)를 1증가시킨다.
If Top > M Then	// 스택 포인터가 스택의 크기보다 크면, 더이상 자료를 삽입할 수 없다.
	Overflow		// Overflow를 처리한다.
Else				// 그렇지 않으면 ..
	X(top) <- Item	// Item이 가지고 있는 값을 스택의 Top 위치에 삽입한다.

 

• 자료의 삭제(Pop)
  • Stack에 기억되어 있는 자료를 삭제시킬 때는 제일 먼저 삭제할 자료가 있는지 없는지부터 확인해야 한다.
  • Underflow : Top Pointer가 주소 0을 가지고 있다면 스택에는 삭제할 자료가 없으므로 Underflow를 발생시킨다.

 

If Top = 0 Then	// 스택 포인터가 0이면 스택의 바닥이므로 더이상 삭제할 자료가 없다.
	Underflow		// Underflow를 처리한다.
Else				// 그렇지 않으면 ...
	Item <- X(Top)	// Top위치에 있는 값을 Item으로 옮긴다.
   Top = Top -1	// 스택 포인터를 1감소시킨다.

 

 

큐 (Queue)

📌 큐는 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조이다.

 

• 큐는 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO : First In First Out) 방식으로 처리한다.
• 큐는 시작과 끝을 표시하는 두 개의 포인터가 있다.
• 프런트(F, Front) 포인터 : 가장 먼저 삽입된 자료의 기억 공간을 가리키는 포인터로, 삭제 작업을 할 때 사용한다.
• 리어(R, Rear) 포인터 : 가장 마지막에 삽입된 자료가 위치한 기억 공간을 가리키는 포인터로 삽입 작업을 할 때 사용한다.
• 큐는 운영체제의 작업 스케줄링에 사용한다.

 

 

 

그래프 (Graph)

📌 그래프 G는 정점 V(Vertex)와 간선 E(Edge)의 두 집합으로 이루어진다.

 

• 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분된다.
• 통신망(Network), 교통망, 이항관계, 연립 방정식, 유기화학 구조식, 무향선분 해법 등에 응용된다.
• 트리(Tree)는 사이클이 없는 그래프(Graph)이다.

 

• 방향/무방향 그래프의 최대 간선 수
  • n개의 정점으로 구성된 무방향 그래프에서 최대 간선 수는 n(n-1)/2이고, 방향 그래프에서 최대 간선 수는 n(n-1)이다.

 

🔔 예) 정점이 4개인 경우 무방향 그래프와 방향 그래프의 최대 간선 수는 다음과 같다.

 

💡 무방향 그래프의 최대 간선 수 : 4(4-1)/2 = 6
💡 방향 그래프의 최대 간선 수 : 4(4-1) = 12