[자료구조] 1. 자료구조의 개념

1. 자료와 정보 사이의 관계

 I = P (D) 

* I : Information, P : Processing, D : Data

 

* 자료의 정의

 - 현실 세계에서 관찰이나 측정을 통해 수집된 값이나 사실

 - 우리의 생활에서 실제로 만질 수 있거나 볼 수 있거나 하는 것(길이, 무게, 부피 등을 측정할 수 있는 대상)에 대해서 

   물리적인 단위로 표현하여 얻어낼 수 있는 것

 

* 정보의 정의

 - 어떤 상황에 대해서 적절한 의사결정을 할 수 있게 하는 지식.

   자료의 유효한 해설이나 자료 상호간의 관계를 표현. 

 - 어떤 상황에 적절한 결정이나 판단에 사용될 수 있는 형태로 가공되거나 분류되기 위해서 

   '처리과정'을 거쳐서 정리되고 정돈된 '자료'의 2차 결과물. 

 

 

2. 추상화의 개념

* 추상화란? 

 - 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것

 - 추상화를 통해 간결하게 말하는 사람의 의사를 전달할 수 있게 되는 것 

 

* 자료의 추상화

 - 다양한 객체를 컴퓨터에서 표현하고 활용하기 위해 필요한 자료의 구조에 대해서

   공통의 특징만을 뽑아 정의한 것

 - 자료의 추상화에는 컴퓨터 내부의 이진수의 표현 방법, 저장 위치 등은 포함되지 않고

   단순하게 개발자의 머릿속에 그림을 그리는 것처럼 개념화하는 것. 

 

3. 자료구조의 개념

* 자료구조

 - 추상화를 통해 알고리즘에서 사용할 자료의 논리적 관계를 구조화한 것

 - 자료의 추상화와 구조화가 적절히 이루어지지 못하면

   소프트웨어는 비효율적으로 수행되거나 소프트웨어의 확장성에 문제가 생길 수 있음 

 

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

 - 자료구조가 입력 자료에 대한 추상화된 상태라면, 

    알고리즘은 컴퓨터가 수행해야 할 명령의 추상화. 

 

* 자료구조와 알고리즘의 추상화/구체화 

 - 입력값을 머릿속에서 추상화된 형태(자료구조)로 구조화하고, 

   수행되어야 할 명령어를 머릿속에서 추상화된 형태(알고리즘)로 체계화.

* 자료구조의 종류와 관계

 

4. 자료구조와 알고리즘의 관계

* 알고리즘

 - 컴퓨터에게 일을 시키는 명령어의 연속된 덩어리 

 - 컴퓨터에 의해 수행되기 위해 필요한 명령어의 유한 집합이

   사람의 머릿속에 추상화되어 존재하는 것 

 - 사람(개발자)이 컴퓨터에게 일을 시키기 위해서

   사람의 의도와 명령을 전달하기 위한 방법 (언어/글) 

 

* 알고리즘의 조건

 - 출력, 유효성, 입력, 명확성, 유한성 

 

5. 알고리즘 성능의 분석과 측정 

* 실행시간 분석

 - 알고리즘을 실행하는 데 필요한 예측 실행시간을 추정하여 

   알고리즘의 성능을 분석

 - 실행 시간 예측

    ㄴ 알고리즘의 실행 횟수를 O(n) 이라고 표현

    ㄴ 같은 O(n)을 가진다는 것은 실행 시간이 동일한 것이 아니라, 

        실행 시간의 증가 경향이 유사하다는 의미임. 

 

* 실행 메모리 분석

 - 알고리즘을 실행하는 데 필요한 공간(메모리)을 추정하여

   알고리즘의 성능을 분석함 

 - 실행 메모리 예측 

   ㄴ 알고리즘의 공간 복잡도(space complexity)

       : 프로그램을 실행시켜서 완료하는 데 필요한 총 메모리 공간

   ㄴ 고정 공간

       : 프로그램의 크기나 입출력의 횟수에 관계 없이 컴파일 시에 결정되어 

        프로그램의 실행이 끝날 때까지 고정적으로 필요한 메모리 공간 

   ㄴ 가변 공간

       : 프로그램의 실행 과정에서 동적으로 할당되어야 하는 

         자료 구조와 변수들을 위해 필요한 메인 메모리 공간 

   ㄴ Sp = Sc + Se 

       (공간 복잡도 = 고정 공간 + 가변 공간) 

 

* 성능 측정 

 - 컴퓨터가 실제로 프로그램을 실행하는 데 걸리는 시간을 측정하여 

   알고리즘의 성능을 측정

 - 실행 시간의 측정

    ㄴ 실제로 실행 시간을 시계로 잰다는 것

    ㄴ 실제로 실행될 수 있는 프로그램(실행 파일)이 있어야 함 

    ㄴ 시스템 시계를 이용