[자료구조] 내용 정리

1) 자료구조란?

• 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업
• 궁극의 효율을 가진 자료구조는 존재하지 않음
• 요구사항에 의존적으로 선택

2) 배열과 리스트

• 배열
  • 동일한 형태의 자료
  • 메모리에 연속으로 정적 할당
  • 단순하지만 처리 효율은 떨어짐
• 연결 리스트
  • 재귀적 자료 구조
  • 메모리에 불연속적으로 동적 할당
  • 복잡하지만 처리 효율 우수
• 배열과 리스트의 차이
  • 배열은 연속된 메모리 공간으로 한번 할당하면 메모리 크기 변경이 용이하지 않다.
  • 리스트는 필요할 때 메모리를 할당하여 데이터를 저장할 수 있어 메모리 관리 차원에서는 배열보다 효율적이다.
  • 리스트에서 메모리 블록은 연속적이라는 보장은 없다.

3) 알고리즘 (Algorithm)

• 컴퓨터로 문제를 풀기 위한 단계적인 절차
• 조건
  • 입력 : 0개 이상의 입력이 존재해야한다.
  • 출력 : 1개 이상의 출력이 존재해야한다.
  • 명백성 : 각 명령어는 모호하지 않고, 명확해야 한다.
  • 유한성 : 한정된 수의 단 후에는 반드시 종료되어야 한다.
  • 유효성 : 각 명령어들은 실행 가능한 연산이어야 한다.

4) 컨테이너

• 대부분의 일반적 추상형 데이터 타입 (ADT : Abstract Data Type)
  • 내용물이 무엇으로 구성되어 있는지 상관하지 않고 컨테이너에 보관한다.
• 객체에 접근하고 저장하는 등의 자료의 구조를 묘사함

컨테이너의 연산

• 컨테이너 생성
• 기존 컨테이너의 복사나 폐기
• 컨테이너 비움
• 컨테이너 내 객체의 개수 반환
• 컨테이너가 수용할 수 있는 최대 객체의 수 반환
• 두 컨테이너에서 합집합, 교집합 계산

컨테이너에 저장된 객체의 연산

• 객체의 삽입
• 객체에 접근 혹은 수정
• 객체의 삭제
• 컨테이너 내에 존재 유무 확인
• 컨테이너 내 객체 모두를 반복 (혹은 한번에 하나씩 한꺼번에 접근)

#include <iostream>
#include <set>

using namespace std;

int main()
{
	// Ignores duplicates: (-3)*(-3) == (3)*(3)
	set<int> ints;
	
	for (int i = -100; i <= 100; i++)
	{
		// insert result : 101 value (0, 1, 4, 9...10000)
		ints.insert(i * i);		
	}

	cout << "Size of 'is' : " << ints.size() << endl;

    
	ints.erase(50); // Does nothing
	ints.erase(9);  // Remove 9
	cout << "Size of 'is' : " << ints.size() << endl;

	return 0;
}

5) 관계와 순서

관계

• 객체 간의 관계
• 관계를 기반으로 추가적 연산 수행
• 탐색
  • 저장 뿐 아니라 객체의 개수에 관계없이 빠르게 처리할 수 있는 자료 구조 필요
  • Hash 함수를 사용한다.
• 종류
  • 선형 순서
  • 단계적 순서
  • 부분 순서 : 전체가 아닌 부분적으로 관계가 형성
  • 동치 관계 : 모양은 다르지만 내부적으로 동일하다.
  • 약한 순서 : 두 객체간의 강하고, 약한 관계
  • 인접 순서 : 인접한 객체와의 관계
• 논리적 연산
  • 같은가? x = y
  • 작은가? x < y
  • 나누어 지는가? x | y

순서 (선형적)

• 관계가 추이적일 때, 다음 세가지 중 하나인 경우로 비대칭 관계
  1. x > y
  2. x < y
  3. x = y
• 선형적 순서 관계
  • 정수 : 1, 2, 3, 4, 5…
  • 실수 : 1.2, 1.2001, 1.24, 1.35…
  • 문자 : a, b, c, d, e, f…
  • 메모리 : 0x0000, 0x0001…
• 사전적 순서 관계
  • 순서화된 영어 단어의 집합 : 순서는 첫글자 비교
• 계층적 순서 관계
  • 파일 시스템에서의 디렉토리 : x가 y를 서브 디렉토리로 가지고 있음

6) 추상 데이터 형 (ADTs : Abstract Data Types)

• 공학적 관점에서 반복되는 어떤 패턴들이 존재
• 우선 패턴을 명명하고 표준 해답 혹은 구현 방법을 정의
• 제한된 처리와 연산의 객체와 연관된 관계가 구현된 컨테이너가 존재
• 이 컨테이너를 모델링 한 것
• 요구사항
  • 어떤 관계가 있는가?
  • 어떤 처리, 연산이 필요한가?
  • 어떤 관계적 처리, 연산이 필요한가?
• 구현
  • Hash Table 자료 구조
  • 순서화된 리스트
  • 배열이나 연결 리스트는 비효율적

7) 메모리 할당의 개념

연속적(Contiguous) 할당 : 배열

• 하나의 배열로서 단일 연속적인 메모리 공간에 n객체가 저장된다.
• 더 많은 메모리가 필요할 때에는 새로 메모리 공간을 할당 받고, 모든 정보를 복사해야 한다.
• 일반적으로 OS에게 추가로 연속된 n객체의 공간을 할당 받을 수 없다.

연결적(Linked) 할당 : 연결 리스트

• 두 데이터를 연결적으로 저장할 수 있도록 할당한다.
• 객체 자기 자신 그리고 자신과 연결되어 있는 다음 아이템에 대한 참조로 구성한다.
• C++ 객체에서의 노드란 다음 노드의 주소를 지칭한다.

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

• 연산방법
  • 새로운 노드의 생성
  • 노드의 값을 읽음
  • 다음 포인터를 가져옴

Node(const Type& = Type(), Node* = nullptr);
Type retrieve() const;
Node *next() const; 

• 필수항목
  • 연결 리스트는 반드시 첫 번째 객체를 가리키는 객체가 필요하다.
  • 실제로 연결 리스트 클래스는 머리(head)와 꼬리(tail), 두 포인터를 반드시 가지고 있어야 한다.
  • 선택적으로 노드의 개수(int count)를 가질 수 있다.
  • Next_node의 마지막 노드는 nullptr로 저장한다.

• 클래스의 구현

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

색인적(Indexed) 할당

• NULL을 포함하여 포인터의 배열이 할당된 메모리 공간을 가리킨다.
• C++ STL(Standard Template Library)에서 사용한다.
• 색인적 할당은 행렬로 표현할 수 있다.

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

8) 다른 할당 형식

트리(Tree)

• 트리는 연결 리스트의 변형으로서 여러 개의 다음 포인트를 가진다.
• 각 노드는 임의의 개수의 다음 노드를 가리킨다.
• 계층적 데이터의 저장에 유용하다.
• 정렬된 데이터의 저장에 유용하다.
• 보통의 경우 다음 노드의 개수를 두 개 이하로 제한한다

그래프(Graph)

• 한 컨테이너에서 두 객체 간의 임의의 관계를 허용한다고 가정하자.
• 대칭성을 허용한다면
  • n개의 객체가 있다면 (n*n - n)개의 가능한 관계가 존재한다.

배열(Array)

• 한 컨테이너에서 두 객체 간의 임의의 관계를 허용한다고 가정하자.
  • 이를 2차 배열을 이용하여 표현할 수 있다.
  • 이 때 이 행렬은 대칭행렬이다.

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

• 한 컨테이너에서 두 객체 간의 임의의 관계를 허용한다고 가정하자.
  • 배열과 연결 리스트의 혼합 형식을 사용할 수 있다.

연결 배열(Linked Array)

• 다른 혼합 형식으로 배열의 연결 리스트가 있다.
• 이는 C++ STL의 Dequeue 컨테이너로 사용된다.

혼합 구조(Hybrid Structure)

• Unix의 Inode는 대용량의 파일 정보를 저장하는데 사용되었다.
• 다음 개체는 다음 1024 블록을 저장할 수 있는 배열을 참조한다.
• 32-bit 컴퓨터에서 최대 4MB 용량의 파일을 저장한다.

9) 알고리즘의 효율성

정렬된 배열의 연산 효율표

비정렬 배열의 연산 효율표

연결리스트의 연산 효율표

이중 연결리스트의 연산 효율표

10) 알고리즘의 분석

• 공간적 효율성과 시간적 효율성
  • 공간적 효율성은 얼마나 많은 메모리 공간을 요하는가를 말한다.
  • 시간적 효율성은 얼마나 많은 시간을 요하는가를 말한다.
  • 효율성을 뒤집어 표현하면 복잡도(Complexity)가 된다. 복잡도가 높을수록 효율성은 저하된다.

빅 오(Big O)

• 효율을 분석하기 위해 사용되는 수학적 도구
• 조건
  • 시간적 복잡도를 데이터 크기 N의 함수로 표시하되 계수를 무시한다.
  • N이 무한대로 갈 때를 기준으로 평가한다.
  • 입력 데이터가 최악일 때 알고리즘이 보이는 효율을 기준으로 한다.
• 임의의 상수 N0와 c가 있어서 N≥N0인 N에 대해서