1.자료구조(Data Structure)

• 문제 해결이 쉽도록, 손쉬운 접근, 변경, 처리가 가능하게, 데이터를 조직화, 저장, 표현하는 방법
  • 구조화된 데이터에 특정한 연산들을 용이하게 할 수 있는 구조
• 알고리즘 적용시, 효과적으로 처리 가능하도록 만들어진 특화된 데이터 체제/형태
  • ex) 배열, 링크드 리스트, 스택, 큐, 트리, 그래프 등
• 자료 및 그 처리를 합계 고려하는 데이터 형식
  • 즉, 자료와 그 작동을 합계 고려하면서
    • 이를 컴퓨터에 효과적으로 표현, 저장, 처리하는 기술
  • 특히, 이 둘을 잘 감싸는(캡슐화) 것을, 추상자료형이라고 한다.

2.자료구조의 목적/이유

• (추상화) 현실 세계에 존재하는 개념, 구조의 표현
  • 약속된 자료구조를 쓰면 좀 더 높은 단계의 프로그래밍이 가능
• (효율성) 효율적으로 데이터를 사용하기 위함
  • 통상, 좋은 자료구조는 연산의 횟수를 작아지게 할 수 있지만,
    • 모든 목적에 적합한 단일한 자료구조는 없으며, 응용에 따라 달라진다.
  • 또한, 사칙연산 이외에도,
    • 읽기, 삽입, 삭제, 비교, 교환, 검색 등의 용이성, 효율성도 고려 필요
• 즉, 문제 마다 적절한 자료구조를 사용함으로써,
  • 사용 편의성, 메모리 효율성, 코드 성능, 버그 감소 등 측면에서 유리하다.

3.자료구조의 종류

• 단순 구조 (통상, 자료구조로써 구분 포함시키지 않음)
  • 문자형, 문자열형, 숫자형, 논리형 등
• 자료 간의 연결 형태/모양에 따른 구분
  • 선형 자료구조 (linear, 전후 1:1 연결 형태)
    • 기본 선형 자료구조 : 리스트, 연결 리스트, 배열, 레코드 등
      • 특히 배열, 리스트 이 둘로부터, 대부분의 다른 자료구조들을 구현 가능
    • 제한 선형 자료구조 : 스택, 큐, 데크(스택과 큐가 혼합된 형태) 등
      • 자료의 입출력이 정해진 위치에서 만 가능
  • 비선형 자료구조(nonlinear, 전후 다대다 연결 형태)
    • 트리, 그래프 등
• 자료 간에 연속, 연결 구조에 따른 구분
  • 배열에 기반한 연속 방식 구조(continuation) : 리스트 등
  • 포인터 기반의 연결 방식 구조(link) : 연결 리스트 등
• 기타 자료구조 구분
  • 입출력 순서를 중심으로 성립되는 자료구조 : 스택, 큐 등
  • 자료들 간에 입출력 순서가 중요하지 않은 자료구조 : 집합, 딕셔너리/사전 등
  • 키 값의 연산에 의해 직접 접근이 가능한 자료구조 : 해시 테이블
  • 파일 구조에 따른 구분 : 순차 파일, 색인 파일, 직접 파일

4.자료구조의 선택 (고려 사항)

• 데이터의 양
• 데이터 사용 횟수 및 방법
• 요구되는 기억장치의 양
• 데이터 수정에 필요한 시간
• 알고리즘 복잡도 등

5.자료구조의 관점 (저장, 처리)

• 데이터의 저장/접근 관점
  • 데이터를 컴퓨터 메모리에 저장/접근할 때,
  • 데이터의 순서 및 위치관계 등이 명확하게 정해져야 올바른 처리 가능 하다.
• 데이터 및 연산을 다루는 관점
  • 자료형(Data Type) : 데이터 중심으로 만 고려
    • 자료(변수)가 갖는 값의 종류를 표현
    • 이때, 연산은 그 자료형에 맞도록, 별도/부가적/부차적으로 수행되는 관점이다.
  • 추상 자료형(Abstract Data Type) : 데이터와 연산을 함께 고려
    • "자료" 및 "연산"을 모두 하나로 묶어 하나의 단위로 표현
    • 자료 저장 및 처리보다는 문제 해결 지향적인 자료형이다.
• 예) 자료구조별 대표적인 연산들
  • 스택 : push(), pop(), createStack() 등
  • 큐 : inqueue(), dequeue(), createQueue() 등

6.자료구조의 표현 (구현)

• 사전 정의형 (프로그래밍 언어에서 기본 내장 제공)
  • C언어 (배열, 구조체 등)
  • 파이썬 (리스트, 튜플, 집합 등)
• 사용자 정의형 (프로그래머가 응요에 따라 직접 구현)
  • 다루는 데이터들에 대해,
    • 단순히 적절한 자료형을 선택하는 것 이상으로,
  • 종합적으로 고려하면서,
    • 어떤 연산들이 필요하고,
    • 데이터를 효율적으로 저장하는 방법은 어떻고,
    • 유효한 연산들은 무엇인지 등
  • 자료구조 및 알고리즘 등을 설계 구현해야 한다.

참고 : ktword.co.kr

스택이란?

• 후입선출(LIFO, Last In First Out) 자료구조
• 가장 최근에 삽입된 데이터가 가장 먼저 삭제

1. 스택의 기본 구조

스택의 기본 연산(push, pop, top, isEmpty)을 설명하는 예제

• push : 스택에 요소를 추가, 배열의 끝에 새 요소르 삽입하고, top 인덱스를 증가시킴
• pop : 스택에서 요소를 제거, 배열의 끝에서 요소를 제거하고, top 인덱스를 감소
• peek : 스택의 최상위 요소를 확인, 스택의 top 인덱스에 있는 요소를 반환
• isEmpty : 스택이 비어 있는지 확인, top 인덱스가 -1이면 스택이 비어있는 것

스택 구현

#include <iostream>
#define MAX 1000 // 스택의 최대 크기

using namespace std;

class Stack
{
    int top;
    int capacity;        // 스택의 크기

public:
    int a[MAX];            // 스택 배열

    Stack() 
    {
        top = -1;         // 스택 초기화
        capacity = 0;    // 스택의 크기 초기화
    }

    bool push(int x);
    int pop();
    int peek();
    bool isEmpty();
    int size();            // 스택의 크기를 반환하는 함수
};

// 스택에 요소를 추가하는 함수
bool Stack::push(int x)
{
    if(top >= (MAX - 1))
    {
        cout<< "스택 오버플로우\n";
        return false;
    }
    else
    {
        a[++top] = x;
        capacity++;
        cout<<x<<" 스택에 푸쉬 되었습니다\n";
        return true;
    }
}

// 스택에서 요소를 제거하는 함수
int Stack::pop()
{
    if(top < 0)
    {
        cout<< "스택 언더플로우\n";
        return 0;
    }
    else
    {
        int x = a[top--];
        capacity--;
        return x;
    }
}


// 스택에 최상위 요소를 반환하는 함수
int Stack::peek()
{
    if(top < 0)
    {
        cout<<"스택에 쌓인게 없어요\n";
        return 0;
    }
    else
    {
        int x = a[top];
        return x;
    }
}

// 스택이 비었는지 확인하는 함수
bool Stack::isEmpty()
{
    return (top<0);
}

// 스택의 크기를 반환하는 함수
int Stack::size()
{
    return capacity;
}


int main()
{
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout<<s.pop()<<"\n";
    cout<<s.peek()<<"\n";
    cout<<s.size()<<"\n";
    cout<<s.isEmpty()<<"\n";

    return 0;
}

과제로 하면 좋을 것

1. 스택의 크기 반환 함수를 추가해보자
2. 스택을 동적 배열로 구현해보자
3. 연결 리스트를 이용한 스택을 구현해보자
4. 예외 처리를 추가하여 더 견고한 스택 클래스를 만들어보자

필요에 따라 STL의 std::stack을 사용하는 것도 좋은 방법

스택을 동적 배열로 구현

#include <iostream>
#include <vector>

using namespace std;

class Stack {
private:
    vector<int> a; // 동적 배열을 이용한 스택

public:
    Stack() {}

    bool push(int x);
    int pop();
    int peek();
    bool isEmpty();
    int size(); // 스택의 크기를 반환하는 함수
};

// 스택에 요소를 추가하는 함수
bool Stack::push(int x) {
    a.push_back(x);
    cout << x << " 스택에 푸쉬 되었습니다\n";
    return true;
}

// 스택에서 요소를 제거하는 함수
int Stack::pop() {
    if (a.empty()) {
        cout << "스택 언더플로우\n";
        return 0;
    } else {
        int x = a.back();
        a.pop_back();
        return x;
    }
}

// 스택의 최상위 요소를 반환하는 함수
int Stack::peek() {
    if (a.empty()) {
        cout << "스택에 쌓인게 없어요\n";
        return 0;
    } else {
        return a.back();
    }
}

// 스택이 비었는지 확인하는 함수
bool Stack::isEmpty() {
    return a.empty();
}

// 스택의 크기를 반환하는 함수
int Stack::size() {
    return a.size();
}

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << s.pop() << " 스택에서 팝 되었습니다\n";
    cout << "최상위 요소는 " << s.peek() << " 입니다\n";
    cout << "스택의 크기는 " << s.size() << " 입니다\n";
    cout << "스택이 비었나요? " << (s.isEmpty() ? "네" : "아니요") << endl;

    return 0;
}

1.1 자료구조와 알고리즘

자료구조란?

자료구조(data structure)

자료들을 정리하여 보관하는 여러 가지 구조

알고리즘(algorithm)

주어진 문제를 처리하는 절차

또는

문제를 풀기 위한 단계적인 절차

특정한 일을 수행하는 명령어의 집합

프로그램 = 자료구조 + 알고리즘

정의 1.1 알고리즘

입 력 : 0개 이상의 입력이 존재하여야 한다.

출 력 : 1개 이상의 출력이 존재하여야 한다.

명백성 : 각 명령어의 의미는 모호하지 않고 명확해야 한다.

유한성 : 한정된 수의 단계 후에는 반드시 종료되어야 한다.

유효성 : 각 명령어들은 종이와 연필 , 또는 컴퓨터로 실행 가능한 연산이어야 한다.

// 프로그램 1.1 cal_scores.c

#defube MAX_ELEMENTS 100
int scores[MAX_ELEMENTS]; // 자료구조

int get_max_score(int n) // 학생의 숫자는 n
{
	int i, largest;
    largest = scores[0]	// 알고리즘
    for(i = 1; i < n ; i++)
    {
    	if(scores[i] > scores[i];
        {
        	largest = scores[i];
        }
    }
    return largest;
}

알고리즘을 기술하는 4가지 방법

1. 한글이나 영어 같은 자연어

2. 흐름도(flowchart)

3. 의사 코드(pseudo-code)

4. 프로그래밍 언어

가장 많이 쓰이는 방법은 

3. 의사코드

4. 프로그래밍 언어

1.2 추상자료형

자료형(data type)

데이터의 종류

(정수, 실수, 문자열 등 기초적인 자료형의 예)

(스택, 큐, 리스트, 트리 등 새로운 자료형)

- 배열

동일한 자료형아 여러 개 모인 것

- 구조체

다른 자료형이 여러 개 모인 것

연산(operation)

정수 간의 덧셈, 뺄샘, 곱셈, 나눗셈, 나머지 연산 ,==,> , <

추상 자료형(ADT : abstract data type)

추상적, 수학적으로 자료형을 정의

실제적인 구현으로부터 분리되어 정의된 자료형

ADT 안에는 객체(objects) 와 함수(functions) 들이 정의

추상화

어떤 시스템의 간략화된 기술

또는

명세로서 시스템의 정말 핵심적인 구조나 동작에만 집중하는 것

객체지향언어에는 "클래스"개념을 사용하여 ADT가 구현

private나 protected 키워드를 이용하여 내부 자료의 접근을 제한

클래스는 계층구조(상속 개념 사용)로 구성 될수 있음

1.3 알고리즘의 성능 분석

수행시간 측정방법

// 방법 #1
#include <time.h>

start = clock();

...

stop = clock();
double duration = (double)(stop - start) / CLOCKS_PER_SEC;

// 방법 #2
#include <time.h>

start = time(NULL);

...

stop = time(NULL);
double duration = (double) difftime(stop,start);

clock() 함수

호출 프로세스에 의하여 사용된 CPU 시간을 계산

time() 함수

초 단위로 측정된 시간을 반환

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void)
{
	clock_t start, stop;
    double duration;
    start = clock();	// 측정 시작
    
    for(int i = 0; i < 1000000; i++)	// 의미 없는 반복 루프
    ;
    stop = clock();	// 측정 종료
    duration = (double)(stop - start) / CLOCKS_PER_SEC;
    printf("수행시간은 %f초입니다.\n",duration);
    return 0;
 }
 
 // 실행 결과
 // 수행 시간은 0.002000초 입니다.

알고리즘의 복잡도 분석방법

알고리즘 복잡도 분석(complexity)

구현하지 않고도 모든 입력을 고려하는 방법

실행 하드웨어나 소프트웨어 환경과는 관계없이 알고리즘의 효율성을 평가할 수 있다.

시간 복잡도 함수

시간 복잡도(time complexity)
알고리즘의 수행시간 분석

공간 복잡도(space complexity)

알고리즘이 사용하는 기억공간 분석

알고리즘의 비교

빅오 표기법

빅오 표기법을 사용하면 시간 복잡도 함수의 증가에 별로 기여하지 못하는 항을 생략함으로써 시간복잡도를 간단하게 표시할 수 있다.

알고리즘이 지수형이나 팩토리얼형의 시간복잡도를 가지면 사실상 사용할 수 없다.

입력의 개수가 30을 넘으면 현재의 가장 강력한 수퍼 컴퓨터를 동작시켜도 우주가 탄생되어 지금까지 흘러온 시간보다 더 많은 수행 시간을 요구할 수도 있다.

빅오표기법 이외의 표기법

빅오메가(big omega) Ω

어떤 함수의 하한을 표시하는 방법

빅세타(big theta) Θ

3개의 표기법 중에서 가장 정밀한 것은 

빅세타

통상적으로 빅오 표기법을 많이 사용

최선, 평균, 최악의 경우

최악의 경우(worst case)

자료집합 중에서 알고리즘의 수행시간이 가장 오래 걸리는 경우

최선의 경우(best case)

수행시간이 가장 적은 경우

평균적인 경우(average case)

알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려하여 평균적인 수행시간을 의미

참고문헌 : 천인국 · 공용해 · 하상호. C언어로 쉽게 풀어쓴 자료구조. 생능출판사, 2005