Part 1. 데이터 입출력 구현 23.01.19(목)

1. 데이터 입출력 구현 – 논리 데이터 저장소 확인 – 자료 구조

1) 자료 구조(Data Structure)의 개념

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

자료 구조의 현명한 선택을 통해 효율적인 알고리즘을 사용할 수 있게 하여 성능을 향상시킨다.

 

2) 자료 구조의 분류

(1) 선형구조

데이터를 연속적으로 연결한 자료 구조

종류 : 리스트, 스택, 큐, 데크

 

(2) 비선형 구조

데이터를 비연속적으로 연결한 자료 구조

종류 : 트리, 그래프

 

3) 선형 구조

(1) 리스트(List)

1-리스트의 종류

[1] 선형 리스트(Linear List)

배열과 같이 연속되는 기억 장소에 저장되는 리스트

선형 리스트의 대표적인 구조로는 배열(Array) 등이 있음

가장 간편한 자료 구조이며, 접근 구조가 빠름

자료의 삽입, 삭제 시 기존 자료의 이동이 필요

 

[2] 연결 리스트(Linked List)

노드의 포인터 부분으로 서로 연결시킨 리스트

연결하는 방식에 따라 단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중원형 연결 리스트로 구분

노드의 삽입, 삭제가 선형 리스트와 달리 편리

연결을 위한 포인터가 추가되어 저장 공간이 추가로 필요

포인터를 통해 찾는 시간이 추가되어 선형 리스트에 비해 느림

 

* 노드

데이터(Data)

포인터(Pointer)

데이터 저장 부분과 포인터 부분으로 구성된 저장 공간을 뜻한다.

 

* 포인터(Pointer

현 위치에서 다음 위치를 알려주는 요소이다.

 

* 링크와 포인터의 차이점이 뭔가? 연결 리스트의 설명에 의하면 ‘노드 = 데이터 + 포인터’라고 나옴

포인터 = 링크로 보아야 한다.

Java나 파이썬 등에서는 포인터를 사용하지 않고 자동할당 해주기 때문에 정확한 표현은 노드 = 데이터 + 링크

 

 

*  선형 리스트 표현

*  연결 리스트 표현

 

(2) 스택

1-스택(Stack)의 개념

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

 

2-스택 구성도

 

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

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

 

3-스택 연산

[1] PUSH

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

 

[2] POP

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

 

4-스택의 자료 삽입 삭제

연산	코드	설명
삽입	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 감소

 

5-스택 응용 분야

[1] 인터럽트의 처리

현재 진행 중인 명령어 위치를 스택에 PUSH하고, 인터럽트 발생 상황을 처리한 후에 인터럽트 전에 진행 중이던 명령어 위치를 스택에서 POP을 통해 받아옴

 

[2] 함수 호출(재귀 호출 함수) * 함수 호출을 서브 루틴 호출이라고도 부름

함수를 호출 시 현재 진행 중인 명령어 주소를 스택에 저장

 

[3] 후위표현 연산

Postif를 계산할 때 사용

 

[4] 깊이 우선 탐색(DFS; Depth-First Search)

깊이 내려갈 때마다 스택에 값을 PUSH하고, 더 이상 깊이 갈 곳이 없을 경우 스택에서 POP한 노드와 인접한 노드를 찾음

 

(3) 큐

1-큐(Queue) 개념

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

 

2-큐 구성도

 

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

데이터가 꺼내는 쪽에서 가장 가까운 데이터를 Head(Fornt)라고 하고, 데이터를 넣는 쪽에서 가장 가까운 데이터를 Tail(Rear)라고 한다.

 

3-큐 연산

[1] ENQUEUE

데이터를 차례대로 넣는 연산

 

[2] DEQUEUE

처음 저장된 데이터부터 하나씩 꺼내는 연산

 

(4) 데크

1-데크(Deque; Douvle Ended Queue) 개념

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

 

2-데크 구성도

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

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

 

3-데크 연산

[1] PUSH

데이터를 차례대로 데크에 넣는 연산

 

[2] POP

데크에서 Front와 Rear에 있는 데이터를 하나씩 꺼내는 연산

 

4) 비선형 구조

(1) 트리

1-트리(Tree)의 개념

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

그래프의 특수한 형태로 노드(Node)와 선분(Branch)으로 되어 있고, 정점 사이에 사이클(Cycle)이 형성되어 있지 않으며,자료 사이의 관계성이 계층 형식으로 나타나는 비선형 구조이다.

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

트리는 노드(Node)와 노드를 연결하는 링크(Link)로 구성된다.

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

 

2-트리(Tree) 용어

[1] 루트 노드(Root Node)

트리에서 부모가 없는 최상위 노드, 트리의 시작점

{A}

 

[2] 단말 노드(Leaf Node)

자식이 없는 노드, 트리의 가장 말단에 위치

{F, G, H, E, C}

 

[3] 레벨(Level)

특정 노드를 기준으로 특정 노드까지의 경로 길이

E의 레벨 3

 

[4] 조상 노드(Ancestor Node)

특정 노드에서 루트에 이르는 경로상 모든 노드

D의 조상 노드는 {B, A}

 

[5] 자식 노드(Child Node)

특정 노드에 연결된 다음 레벨의 노드

B의 자식 노드는 {D, E}

 

[6] 부모 노드(Parent Node)

특정 노드에 연결된 이전 레벨의 노드

F의 부모 노드는 {D}

 

[7] 형제 노드(Sibling)

같은 부모를 가진 노드

F의 형제 노드는 {G, H}

 

[8] 깊이(Depth)

루트 노드에서 특정 노드에 도달하기 위한 간선의 수

트리의 깊이는 3

 

[9] 차수(Degree)

특정 노드에 연결된 자식 노드의 수

D의 차수는 3

 

* 트리의 차수를 고르라는 문제인데 특정 노드를 언급하지 않는 문제일 경우는?

특정 레벨을 지칭하지 않는 트리의 차수를 묻는 문제는 ‘전체 트리에서 가장 큰 차수를 가지는 값’을 찾으면 된다.

 

 

(2) 트리 순회방법

 

1-전위 순회(Pre-Order)

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

 

 

 

2-중위 순회(In-Order)

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

 

3-후위 순회(Post-Order)

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

 

 

 

* 수식 Infix -> Prefix, Postfix로 변환하기

대표 예제 : a * ( b + c ) * d

 

1. Infix -> Prefix

1) 계산 순서에 맞게 괄호를 친다.

( ( a * ( b + c ) ) * d )

 

2) Prefix는 기호들을 괄호 안에서 가장 앞쪽을 옮긴다.

( * ( * a ( + b c ) ) d )

 

3) 괄호를 제거한다.

* * a + b c d

 

2. Infix -> Postifx

1) 계산 순서에 맞게 괄호를 친다.

( ( a * ( b + c ) ) * d )

 

2) Post fix는 기호들을 괄호 안에서 가장 뒤쪽으로 옮긴다.

( ( a ( b c + ) * ) d * )

 

3) 괄호를 제거한다.

a b c + * d *

 

3. 수식 Prefix인 (- / * A + B C D E)를 Postfix로 바꾸기

1) 전위식은 Root -> Left -> Right 순인데, Root는 연산자를 나타내므로 연산자, 피연산자, 피연산자 형태를 찾고 묶는다.

- / * A + B C D E

- / * A ( + B C ) D E

- / ( * A ( + B C ) D E

- ( / ( * A ( + B C ) ) D ) E

( - ( / ( * A ( + B C ) ) D ) E )

 

2) Post Fix는 기호들을 괄호 안에서 가장 뒤쪽으로 옮긴다.

( - ( / ( * A ( + B C ) ) D ) E )

( ( ( A ( B C + ) * ) D / ) E - )

 

3) 괄호를 제거한다.

A B C + * D / E -

 

* 전위 순회로 읽는 방식이 Prefix, 중위 순회로 읽는 방식이 Infix, 후위 순회로 읽는 방식이 Postifx

(3) 트리 종류

[1] 이진 탐색 트리(Binary Search Tree)

이진 탐색 트리는 차수가 2 이하인 노드로 구성되어 자식이 둘 이하로 구성된 트리이다.

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

 

[2] AVL 트리(Adelson-Velsky and Landis Tree)

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

 

[3] 2-3 트리(2-3 Tree)

2-3 트리는 차수가 2 {또는 3인 내부 노드를 갖는 탐색 트리이다.

AVL 트리의 단점인 삽입과 삭제 시의 전체 트리를 재구성하는 부분을 줄인 트리이다.

 

[4] 레드-블랙 트리(Red-Black Tree)

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

 

(4) 그래프

1-그래프(Graph)의 개념

그래프는 노드(N; Node)와 노드를 연결하는 간선(E; Edge)을 하나로 모아놓은 자료 구조이다.

트리(Tree)는 사이클이 없는 그래프이다.

 

2-그래프의 유형

 

3-그래프 용어

[1] 경로(Path)

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

 

[2] 경로 길이(Path Length)

경로상 있는 간선의 수

 

[3] 단순 경로(Simple Path)

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

 

[4] 사이클(Cycle)

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

 

4-그래프 탐색 방법

[1] 깊이 우선 탐색(DFS; Depth-First Search)

최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동

 

[2] 너비 우선 탐색(BFS; Breadth-First Search)

최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동