자료구조 개념

자료와 정보

(big)data and info 

 

자료 -> 처리 (컴퓨터) -> 정보

P(D) => I

I = P(D)

 

자료의 정의 (중요성)

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

우리의 생활에서 실제로 만질 수 있거나 볼 수 있는 것 (길이, 무게, 부피 등 측정 가능 대상)에 대해 물리적인 단위로 표현하여 얻어낼 수 있는 내용

 

정보의 정의

어떤 상황에 대해서 적절한 의사결정의 할 수 있게 하는 지식 으로서 자료의 유효한 해설이나 자료 강호간의 관계를 표현 하는 내용

어떠한 상항에 적절한 결정이나 판단에 사용될 수 있는 형태로 가공되거나 분류되기 위해 처리과정을 거쳐서 정리되고 정돈된 자료의 2차 처리 결과물

 

추상화의 개념

의사소통을 위한 필요성

자료의 추상화 = 물리적이며 전기적인 동작과는 무관하게 자료를 생각하고 바라보는 사람의 상상 => 정수가 컴퓨터 내부에서 0101의 이진코드로 어떻게 저장 될까 라는 의문 없이 정수 그 자체를 머릿속의 그림처럼 떠올리는 것

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

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

다양한 대상을 컴퓨터에서 저장하고 처리하기 위해 그 대상들의 의미와 구조에 대해서 공통의 특징만을 뽑아 정의 한것 =>컴퓨터 내부의 이진수의 표현 방법, 저장 위치 등은 포함 하지 않고 단순 하게 개발자의 머릿속에 그림을 그리는 것처럼 개념화 하여 개발자들 사이의 의사를 쉽게 전달하기 위해 사용 되는 방법

 

자료구조와 알고리즘

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

자료의 추상화와 구조화가 적절히 이루어지지 못하면 sw는 비효율적으로 수행되거나 sw의 확장성에 문제가 생길수 있음

 

자료구조의 두 가지 측면

개발자 > 추상화 > 자료구조 < 구체롸 < 컴퓨터

 

알고리즘

컴퓨터에게 일을 시키기 위한 추상화된 명령어의 연속된 덩어리

사람이 컴퓨터에게 일을 시키기 위한 사람의 의도와 명령을 전달해 줄 수 있는 방법(언어/글)

컴퓨터에게 시킨 일

컴퓨터가 수행할 명령어의 유한 집합이 사람의 머릿속에서 추상화되어 존재하는것

컴퓨터에게 시킬 일(프로그램)을 머릿속에서 추상화 시켜서 대략적으로 상상해 놓은 것(그림/글)

 

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

자료구조는 입력 자료에 대한 추상화된 상태라면 알고리즘은 컴퓨터가 수행해야 할 명령의 추상화

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

입력값을 머릿속에서 추상화된 형태(자료구조)로 구조화하고 수행되어야 할 명령어를 머릿속에서 추상화된 형태(알고리즘)로 체계화됨

프로그래밍 언어 : 자료구조와 알고리즘을 구체화 하는 방법

 

추상 자료형

자료구조와 알고리즘 중간쯤에 있는 자료의 복잡한 논리적 성격을 정의하는 형식

자료값의 집합과 연산집합에 대한 정의로 구성되며, 자료구조를 표현하는 가장 대표적인 방법

 

추상화와 추상 자료형

추상화 : 그림이나 수식과 같이 의미를 표현하고 전달 하는 방법

추상자료형 : 전산학에서 사용되는 자료구조를 표현하는 방법

 

자료구조

미리 정의된 자료 구조

 - 기본 자료 구조 : 정수, 실수 ,문자

 - 파생된 자료 구조 : 배열, 구조체, 포인터

사용자 정의 자료구조

-  리스트, 트리, 스택, 그래프, 큐

 

알고리즘의 개념과 조건

조건 

출력 : 알고리즘을 수행하고 나면 적어도 한 가지 결과를 생성 해야함

유효성 : 반드시 실행 가능 해야함

입력 : 외부/내부 입력값은 유한해야 하며, 반드시 입력 형태가 정의 되어야 함

명확성 : 각 명령들은 명화하고 애매모호 하지 않아야 함

유한성 : 반드시 종료가 명확하게 정의 되어야 함

 

알고리즘의 성능

알고리즘의 실행시간 분석

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

실행 시간 예측

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

같은 O(n)을 가진다고 해서 같은 실행 시간을 갖는 것이 아니라 실행 시간의 유사한 증가 경향에 대한 표현 방법

 

알고리즘의 실행메모리 분석

 

알고리즘의 성능 측정

컴퓨터가 실제로 프로개름을 실행하는데 걸리는 시간을 측정하여 알고리즘의 성능을 측정

실행 시간의 측정

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

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

시스템 시계를 이용

 

 

1. 자료’는 현실 세계에서 관찰이나 측정을 통해서 수집된 값(value)이나 사실(fact)입니다.
2. ‘정보’는 어떤 상황에 대해서 적절한 의사결정(decision)을 할 수 있게 하는 지식(knowledge)으로서 자료의 유효한 해설(interpretation)이나 자료 상호 간의 관계(relationship)를 표현하는 내용이라고 할 수 있습니다.
3. ‘정보’는 어떠한 상황에 적절한 결정이나 판단에 사용될 수 있는 형태로 가공되거나 분류되기 위해 ‘처리 과정’을 거쳐서 정리되고 정돈된 ‘자료’의 2차 처리 결과물이다. 정보는 자료를 처리(process)해서 얻어진 유용한 결과(result)라고 할 수 있습니다.
4. 자료 사이의 논리적 관계를 컴퓨터나 프로그램에 적용하기 위해서는 자료의 추상화가 필요하며 추상화를 통해 자료의 논리적 관계를 구조화한 것을 자료구조(data structure)라고 합니다.
5. 알고리즘이란 컴퓨터에 의해 수행되기 위해 필요한 명령어들의 유한 집합이 사람의 머릿속에 추상화되어 존재하는 것 입니다.
6. 자료의 추상화와 구조화가 적절히 이루어지지 못하면 소프트웨어는 비효율적으로 수행되거나 소프트웨어의 확장성에 문제가 생길 수 있습니다.
7. 추상화란 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것입니다.
8. 자료구조는 입력값의 추상화된 상태라면, 알고리즘은 컴퓨터가 수행해야할 명령의 추상화입니다.
9. ‘미리 정의된 자료구조’는 프로그래밍 언어를 개발하는 개발자에 의해 정의되고 추상화되었고, 이를 컴퓨터내부에서 프로그래밍 언어의 형태로 구현된 자료구조를 의미합니다.
10. ’미리 정의된 자료구조‘는 프로그래밍 언어 개발자가 프로그램 개발자를 위해 미리 정의하지만, ’사용자 정의 자료구조‘는 프로그램 개발자가 자신의 프로그램 개발 방향에 따라 프로그래밍 언어로 새롭게 정의하여 사용하는 자료구조입니다.
11. 알고리즘이 가지고 있어야 할 조건들 ① 출력, ② 유효성, ③ 입력, ④ 명확성, ⑤ 유한성 등이 있습니다.
12. 알고리즘을 실행하는데 필요한 시간과 공간을 추정하여 알고리즘의 성능을 분석(performance analysis)을 합니다. 그리고 컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간 측정하여 알고리즘의의 성능을 측정(performance measurement)합니다.