[컴퓨터과학의이해🧮] 데이터 추상화 (8장)

교재 : 컴퓨터 과학 총론 (13th Edition)

(배운 내용을 책으로 복습하며 작성한 글입니다.  )

 

1. 기본 데이터 구조

1) 배열

- 배열 (array) : 그 안의 항목이 모두 동일한 타입인 직사각형 모양의 데이터 블록

-집합체 타입(aggregate type) : 타입과 크기가 다를 수 있는 데이터 항목(필드, field) 블록

 

2) 리스트, 스택, 큐

- 리스트 (list) : 기본 데이터 구조로 순차적으로 배열되어 있는 항목들의 집합

• 리스트의 시작은 리스트 헤드(head), 리스트의 다른 쪽 끝은 테일(tail)이라 부른다. 
• 리스트와 그 변형들의 기본 개념은 알고리즘들에서 발견되는 가장 보편적인 데이터 추상화일 것이다. 

- 스택 (stack) : 헤드에서만 항목을 제거하거나 합입할 수 있는 리스트

• 스택의 헤드는 스택의 상단(top)이라 불리고, 스택의 테일은 하단(bottom)이라 부른다.
• 스택에서 항목을 하나 삭제하는 것을 항목을  pop한다고 표현한다. 
• 스택에서 제거되는 항목은 항상 마지막으로 스택에 추가된 항목이다. 
• LIFO(Last-In First-Out) 구조
• 백트래킹 활동의 기초 구조로 사용된다. 

-큐 (queue) 

• 항목에 대한 제거가 헤드에서만 이루어지고, 새로운 항목의 추가는 테일에서만 이루어지는 리스트
• FIFO (First-In First-Out) 구조
• 버퍼의 기초 구조로 종종 사용된다. 

3) 트리

- 트리 (tree) : 계층적 구성을 갖는 항목들의 집합

• 트리상의 각 위치는 노드(node)라 불린다. 
• 최상단의 노드는 루트 노드(root node)라고 불린다.
• 루트의 반대쪽 끝에 있는 노드들은 단말 노드 (terminal node 또는 leaf node)라 불린다. 
• 루트 노드에서 단말 노드에 이르는 최장 경로에 있는 노드의 개수를 트리의 깊이(depth)라 부른다. (==트리 안의 수평계층의 개수)
• 어떤 노드의 바로 아래의 자손을 자식(child)노드라 부른다. 
• 어떤 노드의 바로 위의 조상을 부모(parent) 노드라 부른다. 
• 동일한 부모를 갖는 노드들을 형제(sibling)이라 부른다.
• 각 부모 노드가 둘 이하의 자식을 갖는 트리를 2진트리(binary tree)라 부른다. 
• 트리에서 임의의 노드를 하나 선택하면, 그 노드와 그 아래의 노드들이 트리 구조를 가지는데, 이러한 작은 트리를 서브트리(subtree)라 부른다. 
• 서브트리는 그 부모 노드로부터의 가지(branch)라 불린다. 

 

2. 관련 개념

1) 추상화

- 배열, 리스트, 스택, 큐, 트리 등의 구조들은 사용자가 실제 저장장치의 세부사항들을 신경 쓰지 않고 보다 편리한 형식으로 정보가 저장되어 있는 것처럼 이용할 수 있게 해주는 추상적 도구이다. 

- 사용자는 데이터를 추상적 도구로 이용할 수 있다. 

 

2) 정적 구조와 동적 구조

- 구분 : 구조의 형태나 크기가 시간에 따라 변화하는가?

- 정적 구조의 경우,  구조 상의 다양한 데이터 항목에 접근하는 수단과 지정된 위치의 값을 변경하는 수단을 제공하는 것으로 충분할 수 있다. 

- 동적 구조의 경우, 항목의 추가와 삭제를 처리하는 수단과 데이터 구조의 확장에 따른 필요한 메모리 공간의 확보 수단 등도 갖추어야 한다. 

 

3) 포인터

- 포인터 (pointer) : 인코딩된 주소를 값으로 갖는 메모리 영역

• 데이터 구조에서 포인터는 인코딩된 주소를 값으로 갖는 메모리 영역이다. 
• 포인터는 항상 그 데이터를 가리키고 있다. 
• 프로그래밍 언어들은 프리미티브 데이터 타입으로 포인터를 포함하고 있다. 
• 프로그래머는 컴퓨터 주기억장치에서 관련 항목들은 포인터로 연결하여 정교하게 연결된 데이터 집합을 설계할 수 있다. 

 

3. 데이터 구조의 구현

1) 배열의 저장

- 데이터가 갱신되어도 배열의 크기는 변하지 않는다. (배열을 정적이라 표현함)

- 전체 배열을 위해 필요한 저장 공간의 양을 계산하여 그만큼의 연속된 메모리 셀 블록을 잡아둘 수 있다. 

- 배열의 저장 방식은 배열을 행 단위로 저장하는 행 우선 순위(row major order)와 배열을 열 단위로 저장하는 열 우선 순위(column major order) 가 있다. 

 

2) 집합체의 저장

- 각 필드가 필요로 하는 메모리 셀의 수가 고정되어 있다면, 이 집합체를 연속된 셀들의 블록에 저장할 수 있다. 

- 집합체의 시작 주소, 집합체 안에서 해당 필드의 위치 등을 알면 필드에 대한 참조를 특정 메모리 셀로 변환시킬 수 있다. 

- 집합체를 연속된 메모리 셀 블록에 저장하는 방법 대신 각 필드를 별도의 장소에 저장하고 이들을 포인터로 연결할 수 있다. 

- 포인터를 사용하는 방식은 집합체 필드들의 크기가 동적일 경우 특히 유용하다. 

 

3) 리스트의 저장

- 연속형 리스트 (contiguous list)

• 전체 리스트를 연속된 주소를 갖는 메모리 셀 블록에 저장한다. 
• 전체 리스트가 하나의 큰 메모리 블록에 저장되며, 연속된 항목들은 인접한 메모리 셀에 차례로 저장된다.
• 정적인 리스트를 구현하기 편리하다. 
• 동적인 리스트의 경우에는 불리하다. 

- 연결 리스트 (linked list)

• 리스트상의 개별 항목들을 각기 다른 메모리 영역에 저장한다면, 삽입이나 삭제로 인한 문제가 간단해질 수 있다. 
• 연결 리스트의 시작 위치를 나타내기 위해 첫 번째 항목, 즉, 리스트 헤드의 주소를 저장하는 별도의 포인터(==헤드 포인터 (head pointer))를 사용한다.
• 연결 리스트의 끝을 표시하기 위해 null 포인터를 사용하는데, 리스트에 더이상 항목이 없다는 것을 표시한다. 
• 각 항목에 저장되어 있는 포인터를 따라 null 포인터에 도달할 때까지 항목들을 차례로 방문한다. 

 

4) 스택과 큐의 저장

(1) 스택

- 가장 큰 상태의 스택을 수용하기에 충분한 크기의 메모리 블록을 잡아둔다. 

- 블록의 한쪽 끝은 스택의 하단으로 지정되며, 바로 스택에 push되는 첫 번째 항목을 위한 위치이다. 

- 항목을 push하거나 pop하면, 스택 상단의 위치는 잡아둔 메모리 셀 블록 내에서 앞뒤로 이동한다. 

- 위치를 나타내기 위해 주소가 스택 포인터(stack pointer)라고 불리는 메모리 셀에 저장된다. 

 

(2) 큐

- 최대 크기의 큐를 저장하기에 충분히 큰 연속된 셀들의 블록을 잡는다. 

- 헤드 포인터 (head pointer)는 큐의 헤드를 나타내기 위해 사용한다. 

- 테일 포인터 (tail pointer)는  큐의 테일을 나타내기 위해 사용한다. 

- 큐가 비어있을 경우 헤드 포인터와 테일 포인터는 동일한 위치를 가리킨다. 

 

5) 2진트리의 저장

(1) 연결 구조 사용

- 노드라 불리는 2진트리의 각 항목은 데이터, 노드의 첫 번째 자식에 대한 포인터(왼쪽 자식 포인터 (left child pointer)), 노드의 두 번째 자식에 대한 포인터(오른쪽 자식 포인터 (right child pointer))라는 3개의 요소로 이루어진다. 

- 노드들을 저장하기 위한 메모리 셀 블록을 찿는 일과 원하는 트리 구조에 따라 노드들을 연결하는 일이 필요하다. 

- 각 포인터는 해당 노드의 왼쪽 자식 또는 오른쪽 자식을 가리키도록 설정되거나 해당 방향의 자식 노드가 없을 경우 null값을 갖도록 설정된다. 

- 루트 노드의 주소를 저장하는 특별한 위치인 루트 포인터(root pointer)를 위한 장소를 잡는다. 

- 트리에 처음 접근하기 위해 사용되는 것이 바로 루트포인터이다. 

 

(2) 전체 트리를 하나의 연속된 메모리 셀 블록을 사용해 저장

- 블록 안에서 트리가 사용하지 않는 위치를 나타내는 셀들은 데이터가 들어 있지 않음을 나타내는 특별한 비트 패턴으로 표시한다.

-기본적으로 트리의 각 계층의 노드들을 위에서부터 한 층씩 차례대로 저장한다. 

- 2진트리가 거의 균형을 갖추고 있고(루트 노드의 서브트리 둘 다 동일한 깊이를 가짐) 거의 가득 차 있을 경우, 저장 공간을 효율적으로 사용한다. 

- 위와 같은 특성을 가지지 못할 경우 상당히 비효율적일 수 있다. 

 

6) 데이터 구조의 조작

- 사용자가 데이터 구조를 추상적 도구로 사용할 수 있도록 하기 위해, 사용자에게서 실제 저장 방식의 복잡성을 가려야 한다. 

- 사용자가 사용하는 (추상적 도구에 대해 표현한) 명령이 실제 저장 방식에 맞는 단계들로 변환되어야 함을 의미한다. 

- 리스트, 스택, 큐, 트리의 경우, 추상적 구조에 대해 표현된 명령들은 대개 사용자들에게서 바탕이 되는 저장 방식의 세부사항을 가리면서 필요한 작업을 수행하는 함수들을 이용해 적절한 동작들로 표현된다. 

 

5. 사례 연구

- 연결을 사용하는 2진트리 구조와 검색, 인쇄, 삽입 등을 위한 함수 등으로 이루어지는 소프트웨어 패키지는 우리의 가상적 응용에서 사용될 수 있는 추상적 도구가 될 수 있다. 

 

5. 맞춤형 데이터 타입

1) 사용자정의 데이터 타입

- 사용자정의 데이터 타입(user-defined data type) : 프로그래머가 프리미트 타입을 기초 요소로 사용하여 추가적인 데이터 타입을 정의할 수 있도록 허용하는 상황에서, 정의되는 데이터 타입 중 가장 기본적인 형태

(기본적으로 여러 개의 프리미티브 타입을 하나의 이름으로 모은 것)

- 사용자정의 데이터 타입의 실제 항목을 그 타입의 인스턴스(instance)라고 부른다. 

- 사용자정의 데이터 타입은 기본적으로 그러한 타입의 인스턴스들을 생성하기 위해 사용하는 틀(templete)에 해당한다. 

- 틀은 그러한 타입의 모든 인스턴스들이 갖는 속성들을 기술하고 있지만, 그러한 타입의 개체를 구성하는 것은 아니다. 

 

2) 추상 데이터 타입

- 추상 데이터 타입(abstract data type) : (표현에 해당하는) 데이터와 (동작에 해당하는) 함수 모두를 포함할 수 있는 사용자 정의 데이터 타입이다. 

- 추상 데이터 타입을 지원하는 프로그래밍 언어는 (1)추상 데이터 타입을 하나의 단위로 정의하기 위한 구문, 그리고 (2)추상 데이터 타입을 사용하는 프로그램상의 다른 부분으로부터 해당 추상 데이터 타입의 내부 구조를 감추기 위한 매커니즘 등 두 가지 기능을 제공한다. 

• (1) : 유지보수와 디버깅을 쉽게 수행할 수 있도록 추상 데이터 타입의 데이터와 함수를 한 곳에 모아주는 중요한 구성 도구
• (2) : 추상 데이터 타입 바깥의 코드에서 추상 데이터 타입 내부 데이터에 대한 접근 목적으로 제공되는 함수들을 사용하지 않고 직접 접근하는 것을 방지해주며, 이를 통해 코드의 신뢰성을 제고한다. 

 

6. 클래스와 객체

- 객체지향 패러다임에서는 작업을 수행하기 위해 서로 상호작용하는 객체라는 단위로 구성되는 시스템이 구축된다. 

- 각 객체는 다른 객체들로부터 수신된 메시지에 반응하는 개체이다. 

- 객체들은 클래스로 알려져 있는 틀에 의해 기술한다. 

- 클래스와 데이터 타입 사이의 차이

• 클래스는 추상 데이터 타입의 확장이다.
• 객체지향 언어에서 클래스는 다른 클래스에서 속성들을 상속받을 수 있으며, 또한 생성되는 개별 객체들을 설정하는 생성자라는 이름의 특별한 메서드를 포함할 수 있다. 
• 클래스는 여러 수준의 캡슐화를 통해 인스턴스의 내부 속성을 잘못 사용하지 않도록 보호하는 기능이 있다.

- 클래스와 객체의 개념은 프로그램에서 데이터 추상화를 표현하기 위한 기법을 진보시켰다. 

 

7. 기계어에서의 포인터

- 스택에서 한 개의 항목을 pop하여 범용 레지스터 중 하나에 저장하기 위한 프로그램을 Vole 기계어로 작성하고 싶은 상황

(스택상단의 항목을 저장한느 메모리 셀의 내용을 레지스터에 넣고자 함)

• 어떤 내용이 들어 있을지 알 수 없으므로 명령 코드 2 사용 불가
• 프로그램이 실행되면서 스택 상단의 주소는 변화하므로 주소가 무엇인지 알 수 없기 때문에 명령 코드 1 사용 불가
• 스택 포인터의 주소는 알고 있다. (== 레지스터에 넣을 데이터의 주소가 들어 있는 곳의 위치를 알고 있다. )
• 피연산자로 레지스터에 넣을 데이터에 대한 포인터의 주소를 갖는 필드를 취하는 제3의 명령 코드가 필요하다. 
• Vole 언얼르 확장하여 명령코드 D를 포함시킨다. 
• 명령코드를 갖는 명령은 DRXY 형식을 가질 수 있으며, 이 명령은 주소 XY에 들어 있는 주소가 가리키는 메모리 셀의 내용을 R번 레지스터에 넣으라는 의미이다. 
• 스택포인터에서 1을 빼서 새로운 상단 위치를 가리키도록 하는 작업이 필요하다. 
• 기계어 프로그램은 새로운 LOAD 명령을 수행한 뒤에, 스택 포인터를 레지스터로 옮긴 다음 1을 빼고 그 결과를 다시 메모리에 저장하게 될 것을 의미한다. 

 

• 메모리 셀 대신 레지스터 중 하나를 스택 포인터로 사용한다면, 스택 포인터의 메모리와 레지스터를 오가며 이동하는 일을 줄일 수 있다. 
• 위의 경우에는 주기억장치 대신 레지스터에 포인터를 예상하도록 새로운 LOAD 명령을 다시 설계해야 한다. 
• 명령코드 D인 명령의 형식이 DR0S가 되도록 정의할 수 있으며, 이 명령은 S번 레지스터가 가리키는 메모리 셀의 내용을 R번 레지스터에 넣으라는 의미이다. 

- push 연산의 구현

• Vole 기계어에 명령코드 E를 추가하여 확장할 수 있으며, ER0S 형식은 명령은 R번 레지스터의 내용을 S번 레지스터가 가리키는 메모리 셀에 저장하라는 의미이다. 
• 위 명령 뒤에 S번 레지스터에 저장된 값에 1을 더하는 명령을 실행함으로써 push 연산을 완성할 수 있다. 

 

- 주소 지정 방식

• 즉석 주소지정 방식 (immediate addressing) : 피연산자 필드가 관련 데이터 자체를 포함함 ex) 명령코드 2
• 직접 주소지정 방식 (direct addressing) : 피연산자 필드는 관련 데이터가 있는 곳의 주소를 포함함 ex) 명령코드 1, 3
• 간접 주소지정 방식 (indirect addressing) : 명령들의 피연산자 필드는 데이터가 있는 곳의 주소가 있는 주소를 포함함. ex) 명령코드 D,E