데이터 구조론 번역 요약

data condensing

데이터 압축

Huffmann coding

허프만 코딩

Often used for the Compression of the Text

텍스트의 압축에 주로 사용한다.

Uses a Binary Tree where each node contains a single character and the node used to identify each character is its path through the tree.

각 노드가 하나의 문자를 포함하는 이진 트리를 사용하고 각 글자를 확인하기 위해 사용되는 노드는 트리를 통한 경로에 사용된다.(?)

More common characters are assigned a shorter code than less common characters.

더 많이 나오는 문자들은 더 적게 나오는 문자보다 더 짧은 코드에 할당된다.

When traversing the tree a "0" indicates a branch to the left and a "1" indicates a branch to the right

트리를 순회할 때 "0"은 왼쪽 줄기를 나타내고 "1"은 오른쪽 줄기를 나타낸다.

Huffmann coding

step 1 : Begin with a forest of a trees. Each tree consists of a single node that contains a character and its frequency of occurence within text to be compressed. The frequency in this case is called the weight of the node.

1단계 : 트리의 바닥부터 시작한다. 각 트리는 한 문자를 포함하는 하나의 노드와 압축될 텍스트(문자열)에서 문자의 발생 빈도수로 구성된다. 이 경우 빈도수는 노드의 웨이트라 불린다.

step 2 : Find the two trees with the smallest weights in their root nodes. Join the two trees as the left and right subtrees of the a new root node with a weight equal to the combined weights of the two subtrees.

2단계 : 루트 노드에서 가장 작은 웨이트를 가진 2개의 트리를 찾는다. 두 개의 서브트리의 웨이트를 합친 것과 같은 웨이트를 가진 새로운 루트 노드와 왼쪽, 오른쪽에 서브트리를 결합한다. 

step 3 : Repeat the second step until there is only one tree remaining.

3단계 : 오직 하나의 트리만 남을때까지 2단계를 반복한다.

Array

배열

An array is a set of pairs, <index, value>, such that each index that is defined has a value associated with it (correspondance, mapping in math).

배열은 수학에서 맵핑, 대응값과 관련된 값으로 정의된 각 인덱스처럼 <인덱스, 값>의 짝의 집합이다. 

An array is a group of related data items that all have the same name and the same data type.

배열은 모두가 같은 이름과 데이터 타입을 가지는 관련된 데이터 아이템의 그룹이다.

Arrays can be of any data type we choose.

배열은 우리가 선택한 어떤 데이터 타입이던 될 수 있다.

Arrays are static in that they remain the same size throughout program execution.

배열은 프로그램을 실행하는 동안 같은 정적인 크기를 가진다.

An array's data items can be stored contiguously in memory.

배열 데이터 아이템은 메모리에 연속적으로 저장될 수 있다.

Each of the data items is known as an element of the array. Each element can be accessed individually.

데이터 아이템의 각각은 배열의 엘레먼트이다. 각 엘레먼트는 각자 접근될 수 있다.

C-implementation of one dimensional Array

1차원 배열의 C구현

Array parameter to a function

함수에서 배열 파라미터

actual parameter : array name, it is a pointer whose value is the address of an array(input = &input[0]).

실제 파라미터 : 배열 이름, 배열(input = &input[0])의 주소인 포인터의 값.

formal parameter : pointer to the array(list)

형식 파라미터 : 배열에 대한 포인터

Structures

구조체

A structure is a collection of data items, where each item is identified by its type and name.

구조체는 각 아이템이 타입과 이름으로 인식되는 데이터 아이템의 집합이다.

Structure assignment

구조체 대입

person1 = person2

ANSI C permits, but most earlier version do not.

ANSI C는 허용하지만 이전 버젼은 안된다.

Unions

공용체

A Union is similar to a structure, but the fields of a union must share their memory space.

공용체는 구조체와 비슷하지만 공용체의 필드는 메모리 공간을 공유해야 한다.

List

리스트

It's common in programs to want to store a collection of items

아이템의 집합을 저장하기 원하는 프로그램에서 보편적으로 사용된다.

An ordered sequence of items.

아이템이 순서화된 것.

insert and/or delete an item anywhere

아이템을 어디에서든 추가하거나 삭제할 수 있다.

more general than Stack and Queue

스택과 큐보다 일반적이다.

Stack and Queue are special cases of list.

스택과 큐는 리스트의 특별한 경우이다.

Basic Operations

기본 연산

Insert() : Insert an item x at position in List

Insert() : 리스트에서 x 위치의 아이템을 추가한다.

Delete() : Delete an item at position in List

Delete() : 리스트에서 x 위치의 아이템을 제거한다.

Size() : Number of item in List

Size() : 리스트의 아이템 수

Retrieve() : Search for a particular item in the List

Retrieve() : 리스트에서 특별한 아이템을 찾는다.

Other useful operations

다른 유용한 연산

Traverse all items in List

리스트의 모든 아이템 순회

Update an item value in List

리스트의 아이템 값 갱신

Implementation of List

리스트의 구현

Static Implementation of List - Array_based

리스트의 정적 구현 - 배열 기반

Dynamic Implementation of List - Linked List

리스트의 동적 구현 - 링크드 리스트

Static Implementation of List

insert(pos, item)

move items from pos to count-1 one position up

아이템들을 pos부터 count-1까지 한 위치 올린다.

Put new item in pos

pos에 새로운 아이템을 놓는다.

Increment count by one

count를 1증가 시킨다.

delete(pos);

Shift items from pos+1 to count-1 down by one

pos+1부터 count-1까지 아이템들을 1 아래로 shift이동시킨다.

Decrement count by one

count를 1감소 시킨다.

Limitation of Array Implementation

배열 구현의 한계

Need to move items

아이템을 이동해야 한다.

Need to know the max size of list

리스트의 최대 크기를 알아야 한다.

Too large : waste of memory

너무 크면 메모리 낭비

Too small : can't expand dynamically

너무 작으면 동적으로 확장할 수 없다.

Summary of Array

배열 요약

Collection of items of the same type

같은 타임의 아이템의 집합

Easy to access elements of the array

배열의 요소를 접근하기 쉽다.

Difficult to make the array larger

배열을 더 크게 만들기 어렵다.

Making the array smaller wastes space

배열을 더 작게 만드는 것은 공간 낭비다.

Ideal Implementation of List

리스트의 이상적인 구현

Take as much memory as needed.

필요한 만큼 메모리를 얻는다.

- no more and no less 적절하게

-allocate the memory dynamically if needed

필요시 동적으로 메모리를 할당한다.

No need to move items around

아이템을 이동할 필요가 없다.

Linked Lists

linked representation of ordered lists.

순서화된 리스트의 연결된 표현

noncontiguous 비연속적인

must scan for element 요소를 반드시 검사해야 한다.

insertion/deletion easy 삽입/삭제가 쉽다

associated with each list element is a node which contains both a data component and a pointer, called link, to the next item in the list.

각 리스트 요소와 연관된 값은 리스트에서 다음 아이템으로 가는 link라 불리는 포인터와 데이터를 포함하는 노드이다.

A linked list is a dynamic data structure

링크드 리스트는 동적 데이터 구조이다.

Advantage of Linked List

링크드 리스트 장점

Nodes can be located anywhere in the memory

노드들은 메모리의 어디든 위치할 수 있다.

Getting from one node to another by storing the reference of the next node.

다음 노드의 참조를 보관함으로서 하나의 노드에서 다른 노드를 얻는다.

Insertion/removal does not require moving other items

삽입/삭제할 때 다른 아이템을 이동할 필요가 없다.

Singly linked lists.

단일 링크드 리스트

object has reference to next one in list

오브젝트는 리스트에서 다음 참조를 하나만 가진다.

Doubly linked list : object has reference to previous and next one in list

이중 링크드 리스트 : 오브젝트는 리스트에서 이전 및 다음 참조를 가진다.

Node

A basic element in Linked List

링크드 리스트에서 기본 요소

Node contains items or values, references to next node

노드는 아이템 또는 값이나 다음 노드에 대한 참조를 포함한다.

Head/Tail

Meaningful for singly linked list

단일 링크드 리스트에서 의미가 있다.

Head indicates the beginning of the List

Head는 리스트의 시작을 나타낸다.

Tail indicates the end of the list

Tail은 리스트의 끝을 나타낸다.

Header nodes

헤더 노드

Header nodes allow us to avoid special cases [in the code] such as insertion of the first element and removal of the last element

헤더 노드는 마지막 엘레먼트의 삭제와 첫번째 엘레먼트의 삽입 같은 특별한 경우를 피할 수 있게 한다.

The header node holds no data but serves to satisfy the requirement that every node have a previous node.

헤더 노드는 데이터를 가지지 않지만 각 노드가 이전 노드를 가지도록 하는 요구사항을 만족시키기 위해 제공된다.

Not necessarily a standard implementation.

표준 구현이 필요하지 않는다.

Doubly-linked list

이중 링크드 리스트

Doubly-linked list : object has reference to previous and next one in list

이중 링크드 리스트 : 오브젝트는 리스트에서 이전 다음 것에 대한 레퍼런스를 가진다.

Stack

스택

All access is restricted to the most recently inserted elements.

모든 접근은 최근 추가된 요소로 제한된다.

Basic operations are push, pop, top.

기본 연산은 푸시, 팝, 톱이다.

알고리즘 : 주어진 문제를 해결하기 위한 유한한 명령문의 집합. 입력 0이상, 출력 1이상. 종결을 해야 한다.

Balanced symbol

Stack can be used to check a program for balanced symbols (such as {}, (), [])

스택은 괄호류가 잘 열리고 닫혔는지 프로그램을 확인하는 데 사용될 수 있다.

When a closing symbol is seen, it matches the most recently seen unclosed opening symbol.

Therefore, a stack will be appropriate.

닫힌 심볼이 나왔을 경우, 이는 가장 최근에 닫히지 않은 열린 심볼과 매칭된다. 그러므로, 스택이 적절할 것이다.

Make an empty stack.

빈 스택을 만든다.

Repeatedly read tokens; if the token is an opening symbol, push it onto the stack.

토큰을 반복해서 읽는다. 만약 토큰이 열린 심볼이라면 스택에 넣는다.

a closing symbol and the stack is empty, then report an error.

닫힌 심볼이고 스택이 비었다면 오류를 보고한다.

otherwise pop the stack and verify that the popped symbol is a match (if not report an error)

그렇지 않으면 스택에서 pop하고 (오류가 없으면) 빼낸 심볼이 맞는지 검증한다.

At the end of the file, if the stack is not empty, report an error.

파일의 끝이고 스택이 비어있지 않다면 오류를 보고한다.

Performance

Running time is O(N), where N is amount of data(that is, number of tokens)

실행시간은 O(N)이며 N은 데이터의 양이다. (즉, 토큰의 수)

Algorithm is online:it processes the input sequentially, never needing to backtrack.

알고리즘은 온라인이다. 입력을 순서대로 처리하며 백트랙이 필요없다.

Procedure Stack

프로시저 스택

Matching symbols is similar to procedure call and procedure return, because when a procedure returns, it returns to the most recently active procedure. Procedure stack can be used to keep track of this.

심볼을 매칭하는 것은 프로시저 콜과 리턴과 비슷한데, 그 이유는 프로시저가 리턴할 때 가장 최근에 활성화된 프로시저로 돌아가기 때문이다. 프로시저 스택은 이를 기록하는 데 사용될 수 있다.

Activation Records

The top of stack can store the current procedure environment.

스택의 톱은 현재 프로시저 환경을 저장할 수 있다.

When procedure is called, the new environment is pushed onto stack.

프로시저가 호출될 때, 새로운 환경이 스택에 푸시된다.

On return, old environment is restored by pop.

리턴시, 이전 환경이 팝에 의해 복구된다.

Other Applications

Recursion removal can be done with stacks.

재귀 제거는 스택으로 실행될 수 있다.

Operator precedence parsing

연산 우선순위 파싱

Reversing things is easily done with stacks.

뭔가를 뒤집는 것은 스택으로 쉽게 수행된다.

Undo operation in many editor tools

많은 편집 툴에서 Undo 연산

Queue

All access is restricted to the least recently inserted elements.

모든 접근은 가장 오래전에 추가된 요소로 제한된다.

Basic operations are enqueue, dequeue, getFront,

기본 연산은 enqueue, dequeue, getFront다.

Queue is a British word for line.

큐는 선이라는 뜻의 영국 단어이다.

Expect O(1) time per queue operation because it tis similar to stack.

큐 연산 당 O(1)이며 스택과 비슷하기 때문이다.

The word "queueing" and its derivatives are the only English words with five consecutive vowels.

단어 큐잉은 5개의 모음이 연속적으로 오는 영어 단어이다.

Applications

Queue are useful for storing pending work.

큐는 대기하고 있는 일을 보관하는데 유용하다.

We will see several examples later in the course

우리는 다음 몇 가지 예시를 볼 것이다.

Shortest paths problem (minimize the number of connecting flights between two arbitrary airports)

최단거리 문제(두 개 공항 사이에 연결 편의 수를 최소화한다.)

Topological ordering :given a sequence of events, and pairs(a,b) indicating that event a MUST occur prior to b, provide a schedule.

토폴로지 순서 : 이벤트의 순서가 주어지며, 이벤트를 나타내는 (a,b)쌍은 b 이전에 발생해야 하며 스케쥴을 제공한다.

Array Implementations

배열 구현

Stack can be implemented with an array and an integer top that stores the array index of the top of the stack.

스택은 스택의 톱의 배열 인덱스를 보관하는 정수 통과 배열로 구현된다.

Empty stack has top equal to -1

빈 스택은 -1과 같은 톱을 가진다.

To push, increment the top counter, and write the array position.

푸시할때, 톱 카운터를 증가시키고 그 배열 위치에 쓴다.

To pop, decrement the top counter.

팝할 때 톱 카운터를 감소시킨다.

Array doubling

If stack is full (because array size has been reached), we can extend the array, using array doubling.

스택이 꽉 찼을 때(배열 크기에 도달했기 때문), 우리는 배열을 array doubling을 사용하여 확장할 수 있다.

We allocate a new, double-sized array and copy contents over.

우리는 새로운 2배 크기의 배열을 할당하고 그 내용을 복사한다.

Running Time

실행시간

Without array doubling, all operations are constant time, and do not depend on number of items in the stack.

array doubling이 없으면 모든 연산은 상수이고 스택에서 아이템의 수에 의존하지 않는다.

With array, doubling, a push could occasionally be O(N). However, it is essentially O(1) because each array doubling that costs N assignments is preceded by N/2 non-doubling pushes.

array를 doubling 할 때 push는 우연히 O(N)이 될 수 있다. 하지만, 본질적으로는 N개의 할당된 값의 비용을른 각 배열 doubling은 N/2의  non-doubling push에 의해 선행되었기 때문에 본질적으로는 O(1)이다.(?)

Queues : Simple idea

Store items in an array with front item at index zero and back item at index back.

인덱스 0에 front 아이템을 두고 제일 뒤 index에 back 아이템을 둔다.

Enqueue is easy : increment Back.

Enqueue는 쉽다 : back을 증가시킨다.

Dequeue is inefficient : all elements have to be shifted.

Dequeue는 비효율적이다. : 모든 요소가 이동되어야 한다.

Result : Dequeue will be O(N).

결과 : Dequeue는 O(N)이 될 것이다.

Better Idea

Keep a Front index.

Front 인덱스를 보관한다.

To Dequeue, increment Front

Dequeue시 Front를 증가시킨다.

Palindrome Evaluation Using a Stack and Queue

A Palindrome is a word that reads identical forwards and backwords.

Palindrome은 앞으로나 뒤로 똑같이 읽히는 단어이다.

Example(예시) : Radar, Sees, Bib

Whatever we read in and out of our stack and queue should output identical result from both the stack and queue.

우리가 스택과 큐에서 무엇을 읽던 스택과 큐 모두에서 같은 결과가 나와야 한다.