1. 자료 구조의 개념

1. 자료구조의 개념

1. 컴퓨터 시스템
1. 시스템의 정의
1. 컴퓨터
   = Electronic Data Processing System(EDPS)
   = 전기 신호에 의해 자료가 처리되는 시스템
2. 자료의 효율적인 처리 위해 자료형(data type) 개념 사용
3. 문자, 정수, 실수, 복소수, 레코드, 구조체 등
2. 시스템의 구성 요소
1. 입력(input)
1. 처리할 자료
2. 처리 방법
2. 처리(processing) → 자료 가공
3. 출력(output) → 처리 결과 출력
4. 제어(control)
5. 귀환(feed back) → 처리 결과를 다시 입력 자료로 사용
2. 자료와 정보
1. 정의
1. 데이터(D) → 처리기(P) → 정보(I)
   I = P(D)[I(Information), P(Process), D(Data)]
2. 정보가 유용성을 갖기 위해서는 다음 두 가지를 갖춰야 함
1. 정확성
2. 현재성
2. 자료
1. 개념
1. 현실 세계로부터 단순 관찰 또는 측정 통해서 수집된 사실이나 값
2. 인식 및 처리에 알맞는 형태로 존재하며 평가되지 않음
2. 데이터의 성격
1. 데이터의 성격에 따라 다르게 분류하고 관리
1. 이름, 소유자, 날짜, 생성자 → 음악
2. 색깔, 길이, 범주 등 → 상품
3. 자료구조
1. 목적
1. 정렬(배열)
2. 관리
2. 목적 달성 위해 특정 구조체의 형태로 관리 → search, sort 등 가능
3. 데이터를 컴퓨터 메모리 상에 체계적으로 형성하는 방법을 배운다
4. 종류
1. array
2. stack
3. queue
4. list
5. heap
6. tree
7. graph
4. 정보
1. 자료가 프로그램에 의해 처리된 원하는 결과
2. 어떤 상황에 대해
   적절한 의사결정 할 수 있게 하는
   데이터의 유효한 해석 또는 상호관계
3. 발전단계
   Data → Information → Knowledge → Intelligence
4. 알고리즘? 자료를 이용하여 정보를 구하기 위한 논리를 기술한 것
   프로그램? 알고리즘을 프로그래밍 언어를 이용하여 실행논리로 구현한 것
3. 자료의 단위
1. 개요
1. 자료 단위
   bit → byte → word → record → block → file → db → data bank
   bit → byte → field(item) → record → file → db → data bank
2. 용량 단위
   bit → byte → KB → MB → GB → TB
3. 연산속도 단위
   ms → us → ns → ps → fs → as
4. 기본 자료
1. 수치(정수, 실수)
2. 문자
3. 논리
4. 포인터
5. 파일
1. 순차 파일 구조
2. 직접 파일 구조
3. 인덱스된 순차 파일 구조
6. DB
1. 계층 구조
2. 네트워크 구조
3. 관계 구조
4. 객체 지향 구조
2. 비트(binary digit)
1. 자료의 최소단위로 0 또는 1로 표현되는 2진수 한 자리를 기억시킬 수 있는 공간
2. 컴퓨터는 내부적으로 2진수로 데이터 처리
3. 니블
1. 4비트 의미. 10진수 한 자리 표현하는 단위로 사용 가능
4. 바이트
1. 8비트  의미. 1문자 나타냄.
2. 하나의 문자를 나타낼 수 있는 단위로 일반적으로 8개 비트가 연속된 것
   0 = 0000 0000, 17 = 0001 0001, 3 = 0000 0011
5. 워드
1. CPU에서 처리되는 명령의 단위
1. half word = 2바이트
2. full word = 4바이트
3. double word = 8바이트
2. 컴퓨터에서 자료가 연산되는 단위. 컴퓨터가 한꺼번에 처리할 수 있는 자료의 양
3. 컴퓨터의 모든 명령은 기본적으로 워드 단위로 수행.
   → 워드 길이 = CPU 구성하는 레지스터 크기
   ex. 64비트 컴퓨터 = CPU가 한꺼번에 64비트씩 처리할 수 있음 의미
6. 필드 또는 항목
1. 레코드를 구성하는 항목으로 파일을 구성하는 단위 중 최소의 논리적 단위.
2. 같은 종류의 data가 기록되는 항목으로 최소한의 문자집합
7. 레코드
1. 서로 관련된 필드 또는 항목의 집합. 프로그램 상에서 자료의 처리 및 기록의 단위
   → 논리적 단위, 내부에서 처리되는 단위
2. 필드의 집합으로 DB에서 실제로 정보를 처리할 때 기본이 되는 단위
3. 배열 → 데이터 원소의 크기와 데이터 타입이 동일
   레코드 → 데이터 원소의 크기와 데이터 타입이 서로 다름
8. 파일
1. 물리적인 구조가 같은 레코드의 집합
2. 기억매체에 저장되는 단위
9. 데이터베이스
1. 여러 응용분야에서 여러 사람들이 공동으로 사용할 수 있도록  조직 및 관리되고  있는 자료의 모임
4. 데이터 구조
1. 정의
1. 데이터 객체에 적용될 연산의 종류와 기능 결정 → 실제로 어떻게 이뤄지는가 기술 → 데이터 구조가 정의된다
2. 수학적인 모델 또는 논리적 모델을 컴퓨터 내부에 표현
3. 컴퓨터 기억공간에서 자료처리를 위한 데이터 표현법, 자료간의 상호관계를 파악하여 작업을 수행하기 위한 알고리즘을 연구
2. 분류
1. 선형구조
1. 배열
1. 물리적 연속성 있음
2. 검색 연산, 기록밀도, 수정연산 높다
3. 삽입, 삭제 연산 낮다
4. 정적구조
5. 외부단편화 발생
2. 연결
1. 논리적 연속성 있음
2. 검색연산, 기록밀도, 수정연산 낮다
3. 삽입, 삭제 연산 높다
4. 동적구조
5. 외부단편화 미발생
2. 비선형구조
1. 트리
1. 그래프의 특수한 구조.
2. 사이클 허용하지 않음
2. 그래프
1. 사이클 허용
3. 자료구조 선택시 고려사항
1. 데이터 양, 접근빈도, 접근시간
2. 데이터의 성격
1. 잦은 변경?
2. 일정 형태 유지?
3. 사용되는 컴퓨터의 메모리 허용도
4. 프로그램 작성의 용이성
5. 데이터의 사용 빈도 및 저장 방식
4. 데이터 객체
1. 자료형의 실체를 구성하는 원소의 집합 ex. 자연수 N의 데이터 객체 = {1, 2, 3, 4, … } ex. 정수형 D의 데이터 객체 = { … , -3, -2, -1, 0, 1, 2, 3, … }