[1028 from 자료구조 by 정광식, 강태원 ] 자료구조_이론

자료와 정보의 관계	자료-> 처리(컴퓨터)-> 정보    I = P(D)
자료	현실 세계에서 관찰이나 측정을 통해서 수집된 값(value)이나 사실(fact) 우리의 생활에서 실제로 만질 수 있거나 볼 수 있거나 하는 것(길이, 무게, 부피 측정가능 대상)에 대해서 물리적인 단위로 표현하여 얻어낼 수 있는 내용
정보	어떤 상황에 대해서 적절한 의사결정(decision)을 할 수 있게 하는 지식(knowledge)이며, 자료의 유효한 해석이나 자료 상호 간의 관계 어떠한 상황에 적절한 결정이나 판단에 사용될 수 있는 형태로 가공되거나 분류되기 위해 '처리과정'을 거쳐서 정리되고 정돈된 '자료'의 2차 처리 결과물
추상화	공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것
자료의 추상화	다양한 객체를 컴퓨터에서 표현하고 활용하기 위해 필요한 자료의 구조에 대해서 공통의 특징만을 뽑아 정의 한 것
자료구조	추상화를 통해 알고리즘에서 사용할 자료의 논리적 관계를 구조화 한 것
자료구조 &알고리즘	자료구조는 입력값에 대한 추상화 알고리즘은 (컴퓨터)수행해야 할 명령의 추상화
자료구조 종류	자료구조 > 미리 정의된 자료구조 = 기본자료구조(정수, 실수, 문자) + 파생된 자료구조(배열, 구조체, 포인터)                +     사용자 정의 자료구조 = 리스트, 트리, 스택, 그래프, 큐
알고리즘	1. 정의 : 컴퓨터가 특정한 일을 수행하는 명령어들의 유한 집합 2. 조건 : 출력, 유효성, 입력, 명확성, 유한성 3. 성능분석(performance analysis) - 실행시간 분석 : O(n) - 실행메모리 분석 : 필요한 공간(메모리)을 추정하여 성능분석 > Sp = Sc + Se   ; 공간복잡도 = 고정공간 + 가변공간 공간복잡도 : 완료하는 데 필요한 총 메모리 공간 고정공간 : 입출력 횟수 관계없이 실행 끝날 때까지 고정적으로 필요한 메모리 공간 가변공간 : 동적으로 할당되어야 하는 자료구조, 변수들을 위해 필요한 메인 메모리 공간 4. 성능 측정(performance measurement) 컴퓨터가 실제로 프로그램을 실행하는 데 걸리는 시간을 측정 하여 알고리즘의 성능을 측정 > 실행시간 시계, 시스템시계
배열	1. 정의 : 인덱스와 원소값의 쌍으로 구성된 집합 (by 사전) 일정한 차례나 간격에 따라 벌여 놓음 2. 특징 배열의 순서는 메모리 공간에 저장되는 "원소값의 물리적 순서" 같은 자료형과 같은 크기의 기억공간을 가짐.  인덱스값을 이용한 직접 접근 가능 3. ADT Array 객체 = <Index, Element> 쌍들의 집합 추상 자료형 : 객체 및 관련된 연산의 정의 자료형 : 메모리 저장 할당을 위한 선언 4. 연산구현 create retrieve store 5. 2차원배열 - 행우선배열 - 열우선배열 6. 희소행렬 0인 원소가 그렇지 않은 원소보다 상대적으로 많을 때, 0아닌 값만 따로 저장  cf) 메모리 주소값 = 실제 메모리 물리적인 위치값 인덱스 값 = 개발자에게 개념적으로 정의
자료형	자료가 기억될 기억 장소의 유형, 즉 정수형, 실수형 등
추상 자료형	자료의 복잡한 논리적 성격을 정의하는 형식으로 자료 값의 집합과 연산 집합에 대한 명세의 집합