자료구조와 알고리즘

* 자료구조와 알고리즘의 관계는 의존적

 

메모리 할당

1. 메모리 할당의 개념

 - 기본적 예제

• 연속적(Contiguous) : 배열
• 연결적(Linked) : 연결 리스트

2. 연속적 할당

 - 하나의 배열로서 단일 연속적인 메모리 공간에 n객체가 저장됨

 - 더 많은 메모리가 필요할 때에는 새로 메모리 공간을 요구하고 할당 받고, 이전 메모리의 모든 정보를 새 메모리에 복사해야 함.

 - 일반적으로 OS에게 추가로 연속된 n객체의 공간할당을 받을 수 없음

ex) ABCD

 

3. 연결적 할당

 - 두 데이터를 연결적으로 저장할 수 있도록 할당

 - 객체 자기 자신 그리고 자신과 연결되어 있는 다음 아이템에 대한 참조로 구성

 - C++ 객체에서의 노드란 다음 노드의 주소(Pointer)를 지칭함

ex) A→B→C→D

 

 - 구현(Sescribing)

template <typename Type>
class Node
{
    private:
        Type element;
        Node *next_node;
    public:
    // ...
};

 - 필수적 연산 방법

  [새로운 노드의 생성]

  [노드의 값을 읽음]

  [다음 포인터를 가져옴]

 - 필수 항목

 1) 연결 리스트는 반드시 첫 번째 객체를 가리키는 객체가 필요함

 2) 실제로 연결 리스트 클래스는 머리(head)와 꼬리(tail), 두 포인터를 반드시 가지고 있어야 함

 3) 선택적으로 노드의 개수(int count)를 가질 수 있다.

 4) Next_node의 마지막 노드는 nullptr(널 포인트)로 저장

 - 클래스의 구현

template <typename Type>
class List
{
	private:
        Node<Type> *head;
        Node<Type> *tail;
        int count;
    public:
    	// constructor(s)...
        // accessor(s)...
        // mutator(s)...
};

 

4. 색인적 할당

 - NULL을 포함하여 포인터의 배열이 할당된 메모리 공간을 가리킴

 - C++ STL에서 사용

 - 행렬로 표현할 수 있음

 - 특징: 대부분 행렬은 단일로 연속된 메모리 공간을 가리키는 색인을 사용하여 구현할 수있음

 

다른 할당 형식

1. 다른 할당 형식의 예

 - 그 외 다른 할당 형식 혹은 혼합된 형식

2. 트리(Tree)

 - 연결 리스트는 선형적으로 정렬된 데이터에 이용할 수 있음

 - 트리의 뿌리는 연결 리스트와 유사하지만 여러 개의 다음 포인트를 가짐

 - 특징

  1) 각 노드는 임의의 개수의 다음 노드를 가리킨다.

  2) 계층적 데이터의 저장에 유용하다.

  3) 정렬된 데이터의 저장에 유용하다.

  4) 보통의 경우 다음 노드의 개수를 두 개 이하로 제한한다.

 

3. 그래프(Graph)

 - 노드와 엣지로 구성이 된다.

 

4. 배열(Array)

 - 한 컨테이너에서 두 객체 간의 임의의 관계를 허용한다고 가정했을 때,
   - 이를 2차 배열을 이용하여 표현할 수 있다.

   - 이 때 이 행렬은 대칭행렬이다.

5. 연결 리스트의 배열(Array of Linked Lists)

 - 한 컨테이너에서 두 객체 간의 임의의 관계를 허용한다고 가정했을 때,

   - 다른 방법으로 배열과 연결 리스트의 혼합 형식을 사용할 수 있다.

6. 연결 배열(Linked Array)

 - 다른 혼합 형식의 배열의 연결 리스트가 있음

 - 이는 C++ STL의 Dequeue 컨테이너로 사용됨

 - 연결 배열의 예

  * 영문자를 다음 중 하나로 저장

   1) 26개 문자의 배열 혹은

   2) 8개 문자의 배열의 연결 리스트

7 혼합 구조(Hybrid Structure)

 - Unix의 Inode는 대용량의 파일 정보를 저장하는데 사용되었다.

 - 다음 개체는 다음 1024 블록을 저장할 수 있는 배열을 참조한다.

 - 32-bit 컴퓨터에서 최대 4MB 용량의 파일을 저장한다.

  - 마지막 개체는 3단계의 최대 4TB 용량의 파일을 위한 간접참조로 쓰인다.

알고리즘의 효율성

1. 개요

 - 실행 시간 효율

 * 객체와 객체를 저장할 수 있는 자료구조가 정해지면 알고리즘으로서 다음과 같은 연산들이 필요함

   [클래스로서의 추상 데이터 형]

   [자료구조는 멤버 변수들로 정의]

   [멤버 함수로 알고리즘을 구현]

 

Q) 알고리즘의 효율성을 어떻게 정의하는가?

- 연산 효율표

 * 다음과 같은 행렬로 구조 내 공간의 연산을 묘사

 * 정렬된 배열에 대한 효율표

# 탐색은 괜찮지만 삽입과 삭제는 비효율적

 

 * 정렬이 되지 않은 배열에 대한 효율표

# 탐색이 비효율적으로 변함

 

 * K번째 객체에 포인터를 갖고 있다면 임의의 위치에서 삽입과 삭제는 매우 효율적

 * 이중 연결 리스트에서는 한 연산만이 보다 효율적

# 탐색의 이중적 방향

# 따라서 값이 비싸진다.