Chapter 4. 데이터 표현과 데이터 구조 e-learning Computers.

Presentation on theme: "Chapter 4. 데이터 표현과 데이터 구조 e-learning Computers."— Presentation transcript:

1 Chapter 4. 데이터 표현과 데이터 구조 e-learning Computers

2 금주에 학습할 내용 4. 데이터표현과 데이터구조 Project 4.1 수치와 문자 데이터 표현
수치데이터와 문자데이터의 표현방법 소리, 그래픽, 동영상의 데이터 표현과 저장 방법 컴퓨터를 이용해서 데이터를 처리하기 위한 데이터구조와 많이 사용하는 알고리즘의 종류

3 01 데이터와 정보란 무엇인가? Project 4.1 수치와 문자 데이터표현 데이터와 정보의 차이점은?
데이터: 단순한 관찰이나 측정을 통해서 수집된 사실이나 값 정보 : 어떤 목적에 필요한 도움을 주는 사실이나 지식 데이터는 입력된 구조화되지 않는 재료를, 정보는 이 재료를 유용한 형태로 변화한 결과 여러가지 데이터의 예로 문자, 소리, 그래픽, 동영상 등으로 이러한 데이터를 멀티미디어 데이터라 한다. 오늘날과 같이 컴퓨터가 널리 이용하게 된 계기도 멀티미디어를 처리할 수 있는 각종 기긱와 소프트웨어의 발달에 기인한다.

4 01 데이터와 정보란 무엇인가? Project 4.1 수치와 문자 데이터표현 정보의 특징은?
정보의 시한성 : 적절한 시기에 유용한 정보를 제공 받아 활용하는 것 정보의 가치성 : 사용자에 따라 가치가 달라지는 변화성을 갖고 있음 정보의 독점성 : 비공개 정보가 공개된 정보 보다 경제성과 경쟁성이 높음 정보의 누적 효과성 : 정보는 누적·가공하므로 정보의 가치성이 높아짐

5 01 데이터와 정보란 무엇인가? Project 4.1 수치와 문자 데이터표현 유용한 정보의 성질은?
관련성 : 현재 상황에 적용 가능하다. 적시성 : 최신의 것이면 필요할 때 사용가능 하다. 정확성 : 입력된 데이터와 출력 내용의 모든 사항이 옳다. 간결성 : 사용가능 한 압축 요약되어 있다. 완전성 : 중요한 것이 모두 내포되어 있다.

6 Project 4.1 수치와 문자 데이터표현 01 데이터와 정보란 무엇인가? 데이터는 어떻게 정보로 변환될까?
컴퓨터 내부의 트랜지스터가 on / off 상태인 2진수 상태만 기억하므로 이들의 조합으로 표현 정보는 어떻게 표현할까? 컴퓨터에서 사용하는 수치, 문자, 특수문자, 소리, 동영상 등의 모든 데이터는 2진수의 조합으로 표현 4비트를 이용해서 정보를 표현하면 16가지(0~15)이다.

7 Project 4.1 수치와 문자 데이터표현 01 데이터와 정보란 무엇인가? 컴퓨터는 어떻게 정보를 표현할까? 비트와 바이트
실제 사용하는 모든 수치, 문자는 8비트로 구성된 코드로 나타냄(표 4.1 참조) 이와 같이, 0 1로 정보를 표현하는 방식을 이진수 시스템이라 함 n비트로는 2n가지 정보를 표현 즉, 4비트는 가지, 8비트는 256가지 비트와 바이트 비트는 정보를 나타내는 최소단위 바이트는 문자를 나타내는 최소단위 문자의 표현 예

8 Project 4.1 수치와 문자 데이터표현 02 수의 구성과 수치 데이터 표현은? 컴퓨터에서 사용하는 진법 2진법
2진법, 8진법, 10진법, 16진법 10진수 324는 100이 3개, 10이 2개, 1이 4개의 합 324 = 3 * * * 1 = 3 * * * 100 각 집법에서 사용하는 기호의 개수를 밑수(base)라함 2진법 0과 1, 2개의 숫자로 모든 수를 나타내는 방법 수 50을 나타내는 6개의 전구로 각 자리마다 2진수 값이 다르다

9 02 수의 구성과 수치 데이터 표현은? Project 4.1 수치와 문자 데이터표현 8진법 16진법
0부터 7까지 8개의 숫자를 사용하며, 2진수 세자리를 한 묶음으로 표현 16진법 0부터 9까지 10개의 숫자와 A부터 F까지 개의 기호가 사용되며 2진수 4자리를 한 묶음으로 표현 각 진법 간의 관계

10 Project 4.1 수치와 문자 데이터표현 (1) 각 진법간에 수의 변환은 어떻게 할까?
2, 8, 16 진수에서 10진수로의 변환 변환하는 수의 각 자리에 해당하는 가중 값을 곱하여 더하면 된다. [예제1] (1101)2, (736.4)8, (AF)16를 10진수로 변환해 보자.

11 (1) 각 진법간에 수의 변환은 어떻게 할까? Project 4.1 수치와 문자 데이터표현
10진수에서 2, 8, 16 진수로의 변환 변환할 진수의 밑수로 나누어질 때까지 나누어 생긴 나머지를 역순으로 쓰면 된다. [예제2] (20)10, (68)10, (97)10을 2진수, 8진수, 16진수로 변환해 보자.

12 Project 4.1 수치와 문자 데이터표현 (1) 각 진법간에 수의 변환은 어떻게 할까?
10진수에서 2, 8, 16 진수로의 변환 소수점 이하는 변환 진수를 계속 곱하여 곱한 결과의 소수점 윗자리를 위로부터 아래로 읽으면 된다. [예제3] ( )10를 2진수로 변환해보자.

13 (1) 각 진법간에 수의 변환은 어떻게 할까? Project 4.1 수치와 문자 데이터표현 2, 8, 16진수의 상호변환
2진수를 8진수로 변환은 2진수의 소수점을 중심으로 왼쪽과 오른쪽으로 각각 3개씩 묶어서 표현하고 16진수는 4자리씩 묶어서 표현 [예제4] ( )2을 8진수와 16진수로 변환해 보자.

14 (1) 각 진법간에 수의 변환은 어떻게 할까? Project 4.1 수치와 문자 데이터표현 2, 8, 16진수의 상호변환
8진수와 16진수로 표현된 수를 2진수로 변환시 8진수 한자리는 2진수 3자리, 16진수 한자리는 2진수 4자리로 표현함 [예제5] (24.12)8, (3B.7)16을 2진수로 변환해 보자.

15 Project 4.1 수치와 문자 데이터표현 (2) 수치데이터는 어떻게 표현할까? 고정 소수점 데이터형식은 어떻게 표현할까?
정수 표현 : 고정 소수점 데이터형식과 10진 데이터 형식 실수 표현 : 부동 소수점 데이터 형식 고정 소수점 데이터형식은 어떻게 표현할까? 정수는 2byte, 4byte 정수형 첫번째 비트는 부호비트, 나머지 비트는 2진수로 변환되어 표현 부호와 절대치 표현, 1의 보수 표현, 2의 보수표현 중 2의 보수 표현 방법이 가장 많이 사용됨. 고정 소수점 데이터 형식으로 2바이트 정수형은 –32767~32768까지 표현되고, 4바이트 정수형은 –2n-1 < N < -2n-1 –1까지 표현할 수 있으며, 이보다 큰 정수를 표현할 때는 부동 소수점 데이터 형식으로 표현한다.

16 Project 4.1 수치와 문자 데이터표현 (2) 수치데이터는 어떻게 표현할까? 보수(Complement)
R진법의 보수는 R의 보수와 (R-1)의 보수가 있다. 따라서, 10진수의 보수는 10의 보수와 9의 보수가 있다. 예를 들면, 45의 10의 보수는 55이고, 9의 보수는 54이다. 또한, 2진수의 1의 보수는 “0은1, 1은0”으로 하면 되고 2의 보수는 1의 보수에 1을 더하면 된다. [예제 8] 13과 –13을 부호화 절대값 표현, 1의 보수표현, 2의 보수표현으로 나타내 보자.

17 Project 4.1 수치와 문자 데이터표현 (2) 수치데이터는 어떻게 표현할까? 10진 데이터 형식은 어떻게 표현할까?
팩 10진 형식 : 10진수 한자리 수를 4비트로 나타내는 것으로 부호는 맨 오른쪽 4비트로 양수는 1100(C), 음수는 1101(D)로 표현 421의 팩 10진 형식

18 Project 4.1 수치와 문자 데이터표현 (2) 수치데이터는 어떻게 표현할까? 10진 데이터 형식은 어떻게 표현할까?
언팩 10진형식 : 10진수 한자리를 8비트로 표현하며 존형식 존형식 : 4비트씩 나누어 존 영역은 1111(f)로 디지트는 2진수로 표현, 부호는 팩 형식과 같은 팩은 기억장치 내 연산을 위해서, 존형식은 입출력 표현을 위해 사용됨 -421의 존 형식(언팩형)

19 (2) 수치데이터는 어떻게 표현할까? 부동 소수점 데이터 형식 Project 4.1 수치와 문자 데이터표현
실수나 숫자의 절대값이 매우 크거나 작은 경우에 사용 4바이트, 8바이트 실수형 부동 소수점 데이터 형식 : 부호 양수이면 0, 음수이면 1

20 Project 4.1 수치와 문자 데이터표현 (2) 수치데이터는 어떻게 표현할까? 부동 소수점 데이터 형식
가수부는 소수점이하의 유효숫자를 2진수로 변환하여 표현 [예제 9] 10진수 155를 부동 소수점 데이터 형식으로 나타내보자.

21 Project 4.1 수치와 문자 데이터표현 03 문자 데이터는 어떻게 표현 할까? 비시디(BCD)코드
산술계산에 사용되는 수를 제외한 모든 수치나 문자, 한글 등은 모두 코드(code)로 표현 현재는 아스키코드를 많이 사용하고 있으나, 향후는 16비트인 유니코드가 사용될 전망임. 비시디(BCD)코드 2비트의 존비트(그룹 분류)와 4비트의 디지트로 구성 총 64가지 종류만 표시하기 때문 초창기 컴퓨터에 사용

22 03 문자 데이터는 어떻게 표현 할까? Project 4.1 수치와 문자 데이터표현 입시딕(EBCDIC)코드
IBM에서 개발한 8비트 코드로 256가지 정보 표현 2개의 존과 디지트로 구성

23 Project 4.1 수치와 문자 데이터표현 03 문자 데이터는 어떻게 표현 할까? 아스키(ASCII)코드
데이터 통신에 활용하고자 만든코드 현재 문자 데이터 표현에 가장 많이 사용됨 표준 아스키는 7비트로 128가지 문자 표현 행렬에서 소문자 ‘a’를 아스키코드로 나타내는 방법

24 Project 4.1 수치와 문자 데이터표현 03 문자 데이터는 어떻게 표현 할까? 유니 코드
16비트 코드로 6500가지 이상 서로 다른 글자 표현가능 세계 모든 언어의 문자와 그 밖에 사용하는 모드 기호도 표현 가능 데이터, 프로그램, 시스템의 호환성과 확장성 문제 해결 Unicode 홈페이지

25 01 그래픽과 비디오 데이터는 어떻게 표현할까? Project 4.2 멀티미디어 데이터 표현
애니메이션이나 상품광고, 설계 및 제도 분야에서 이용 그래픽 생성방법 : 이미지와 드로잉 방식 저장 방법 : 비트맵(모노크롬, 그레이스케일, 컬러)과 벡터 그래픽 비트맵(래스터 : raster) 그래픽 픽셀 단위로 저장 파일의 크기는 그래픽 해상도에 비례(화면 확대 시 화질이 떨어짐) 비트맵 저장 방식

26 01 그래픽과 비디오 데이터는 어떻게 표현할까? Project 4.2 멀티미디어 데이터 표현
모노크롬 그래픽은 어떻게 표현할까? 픽셀 단위로 저장(검은색 0, 흰색은 1로 표현) 그림을 나타내기 위한 비트수 = 픽셀수 실체감이 없어 거의 사용되지 않음 모노크롬 그래픽스 : 각 픽셀은 1개의 비트로 표현된다.

27 01 그래픽과 비디오 데이터는 어떻게 표현할까? Project 4.2 멀티미디어 데이터 표현
그레이스케일 그래픽은 어떻게 표현할까? 잿빛 음영을 사용하여 영상을 표현하는 방식 256가지색(백색, 흰색, 254개의 잿빛 음영색) 그레이스케일 이미지 256그레이스케일 그래픽에서는 각 필섹은 1바이트로 나타낸다. 서로 다른 바이트들은 잿빛의 서로 다른 음영을 나타낸다.

28 01 그래픽과 비디오 데이터는 어떻게 표현할까? Project 4.2 멀티미디어 데이터 표현 컬러 그래픽은 어떻게 표현 할까?
컴퓨터 그래픽 종류 : 16컬러, 256컬러, 1670컬러 컬러사진 24비트로 1670만 가지의 컬러 표현(트루컬러 그래픽)

29 01 그래픽과 비디오 데이터는 어떻게 표현할까? Project 4.2 멀티미디어 데이터 표현 해상도 (resolution)
단위 길이당 표시할 수 있는 픽셀수 DPI(Dot per Inch)단위로 표현 800 * 600 해상도 = 800픽셀 * 600픽셀 * 8비트(=256가지색) = 480,000 byte

30 01 그래픽과 비디오 데이터는 어떻게 표현할까? Project 4.2 멀티미디어 데이터 표현 벡터 그래픽은 어떻게 표현할까?
그래픽을 명령어 단위로 기억 재생하는 방식 그래픽을 객체 단위로 처리하여 이동, 수정, 확대, 색 변환 등의 용이 = 드로잉 소프트웨어 벡터 그래픽과 비트맵 그래픽의 비교

31 01 그래픽과 비디오 데이터는 어떻게 표현할까? Project 4.2 멀티미디어 데이터 표현 벡터 그래픽은 어떻게 표현할까?
Tip – 그래픽스 파일구조 BMP : 윈도에서 지원하는 그래픽스 형식으로 압축되어 있지 않아 파일크기가 크다. PCX : IBM PC에서 광범위하게 사용하였으나 점차 그 사용이 적어지고 있다. GIF : 웹에서 JPEG형식과 함께 널리 사용되고 있다. TIFF : IBM PC, UNIX, 매킨토시 등에서 모두 사용되고 있는 비트맵의 대표적인 방식이다. JPEG : GIF와 함께 웹에서 가장 널리 이용되고 있다.

32 Project 4.2 멀티미디어 데이터 표현 02 소리 데이터는 어떻게 표현할까? 소리의 기본 요소 소리는 어떻게 저장할까?
주파수 : 신호의 주기가 1초 동안 반복되는 횟수 진폭 : 파형의 기준점에서 최고점까지의 거리 음색 : 음마다 고유한 특징 소리는 어떻게 저장할까? 소리 데이터가 입력되어 출력되는 과정

33 02 소리 데이터는 어떻게 표현할까? Project 4.2 멀티미디어 데이터 표현 디지털 오디오 저장방식
디지털 오디오 : 아날로그 형태의 사운드를 디지털화 시킨 것 디지털 오디오의 처리 순서

34 Project 4.2 멀티미디어 데이터 표현 02 소리 데이터는 어떻게 표현할까? 디지털 오디오 저장방식
표본화 : 아날로그 파형을 디지털 형태로 변환하기 위한 표본을 취하는 것 양자화 : 소리 정보의 양 부호화 : 소리 정보의 디지털화 표본화와 양자화를 거친 디지털 정보를 표현하는 과정 아날로그 파형과 표본화 : 표본화가 되면 디지털화하는 것이다. 1초 동안에 취한 표본 수(디지털화하는 횟수)를 표본화율이라 하며, Hz 단위를 사용

35 02 소리 데이터는 어떻게 표현할까? Project 4.2 멀티미디어 데이터 표현 MIDI 저장 방식 소리별 미디어의 사용 예
전자 악기와 컴퓨터간에 정보를 주고 받기 위해 만든 통신 프로토콜 소리별 미디어의 사용 예 형태 확장자 사용 예 오디오 CD 배경음악 미디 *.mid 웨이브 *.wav 음성,음향효과

36 Project 4.2 멀티미디어 데이터 표현 03 애니메이션 효과는 어떻게 낼까? 키 프레임과 트위닝 애니메이션
잔상 효과를 이용하여 일련의 정지 그림들을 연속적으로 보여주어 연속된 동작을 만들어내는 효과 키 프레임과 트위닝 애니메이션 키 프레임은 애니메이션에서 사건이 시작되는 중요한 장면을 의미하며, 트위닝을 이러한 키 프레임과 키 프레임 사이를 채우는 것을 의미 트위닝 과정

37 03 애니메이션 효과는 어떻게 낼까? Project 4.2 멀티미디어 데이터 표현 스프라이트 애니메이션이란 벡터 애니메이션이란
배경과 독립적으로 움직이는 개체 벡터 애니메이션이란

38 03 애니메이션 효과는 어떻게 낼까? Project 4.2 멀티미디어 데이터 표현 모핑(morphing)이란 무엇인가?
어떤 사물의 형상을 다른 모습의 형상으로 서서히 변환시키는 방법 모핑기법에 의해 자동차가 호랑이로 변해가는 영상으로 우리나라의 자동차 회사가 TV 광고에서 사용한 적이 있다.

39 03 애니메이션 효과는 어떻게 낼까? Project 4.2 멀티미디어 데이터 표현 모션 캡쳐는 무엇인가?
인간의 움직임을 만들어 내는 가장 자연스러운 방법 3차원 컴퓨터 애니메이션의 생성을 위해 가장 많이 사용되는 기술 모션 캡쳐를 사용한 게임제작 과정

40 Project 4.2 멀티미디어 데이터 표현 04 동영상은 어떻게 만들까? 비디오 스트리밍 코덱
인터넷 웹에서 비디오 및 오디오 파일을 처리할 때 효율을 높이기 위한 비디오 처리기술 코덱 음성이나 영상의 아날로그 신호를 디지털 신호로 변환하는 코더와 디지털 신호를 음성이나 영상으로 변환하는 디코더의 합성어로 변복조기 시스템에 설치된 코덱은 윈도 운영체제인 경우 [제어판]-[사운드 및 멀티미디어]-[하드웨어]탭에 있는 [Audio Codecs/Video Codecs] 항목 각각의 [등록정보]에서 확인할 수 있음 윈도에서 코덱 확인

41 04 동영상은 어떻게 만들까? Project 4.2 멀티미디어 데이터 표현 데이터의 압축이란
그래픽이나 소리 데이터는 많은 기억 공간이 소요될 뿐만 아니라 전송할 때도 많은 시간이 소요되므로, 이를 효과적으로 하기위한 방법이 데이터 압축(Data Compression)임 데이터의 압축과 압축 풀기 과정

42 04 동영상은 어떻게 만들까? Project 4.2 멀티미디어 데이터 표현 문자 파일 압축은 어떻게 하나 적응형 패턴 치환
전체 문자를 읽은 후 2개 이상의 byte로 반복되는 패턴들을 찾은 다음, 그 패텀을 그 파일 안에서 사용하지 않는 1byte 패턴으로 치환하고 색인표를 만드는 방법

43 04 동영상은 어떻게 만들까? Project 4.2 멀티미디어 데이터 표현 문자 파일 압축은 어떻게 하나 포인터를 이용한 압축
파일을 읽어 반복되는 단어를 검색한 후, 그 뒤에 반복되는 단어에 숫자로 치환하는 방법

44 04 동영상은 어떻게 만들까? Project 4.2 멀티미디어 데이터 표현 그림 자료는 어떻게 압축할까?
그림 자료의 양을 줄이는 방법에는 한 픽셀당 표현하는 컬러 수를 줄이는 방법, 그림을 구성하고 있는 픽셀 수를 줄이는 방법, 자료를 압축하는 방법 그림을 압축하여 저장하는 포맷으로는 PCX, JPG, GIF, TIF가 있고 BMP 등은 비압축 방식으로 그림을 저장 무손실 압축 RLE 허프만 방식 산술부호화 유손실 DPCM DM 변환 부호화 FFT DCT 레이트 비트위치 서브샘플링 서브 밴드 벡터 양자화 하이브리드 JPEG MPEG DVI 멀티미디어 시스템의 압축방법

45 Project 4.3 데이터구조와 알고리즘 01 포인터 주소 연산자와 포인터 연산자
포인터 : 데이터가 저장되어 있는 기억장소의 번지를 나타내는 주소 값 주소 연산자와 포인터 연산자 변수 : 숫자, 문자 등의 일반 데이터를 대상 포인터 변수 : 주기억 장치의 주소를 대상 주소 연산자와 포인터 연산자의 예 일반 변수와 포인터 변수에 데이터를 기억시킨 예로 일반변수는 데이터의 값을 기억하고있지만 포인터 변수는 데이터 값이 기억된 주소인 번지를 지칭한다.

46 01 포인터 Project 4.3 데이터구조와 알고리즘 포인터 변수 사용 포인터는 주소 값을 갖고 있는 변수
문자열, 배열, 구조체, 함수 등을 가리키는 포인터 변수로 각각의 시작주소를 지칭한다.

47 01 포인터 Project 4.3 데이터구조와 알고리즘 포인터 변수 사용 일반 변수와 포인터 변수의 차이점
일반 변수를 이용함 함수 호출은 처리결과 만을 돌려준다. 포인터 변수를 이용한 함수 호출은 직접 처리를 한다.

48 02 배열 Project 4.3 데이터구조와 알고리즘 여러 개의 기억장소들을 하나의 묶음으로 집단화시킨 자료구조
배열은 행렬처리나 계산, 통계처리에 많이 활용되는 선형구조 (a) 1차원 배열 a(6) (c) 3차원 배열 c(2,2,3) (b) 2차원 배열 b(3,4)

49 03 연결리스트(Linked List) Project 4.3 데이터구조와 알고리즘
노드와 링크로 구성, 노드는 실제 정보를 링크는 인접노드의 위치를 지칭 연결 리스트의 물리적 구조는 기억장치에 기억된 내용으로 프로그램 작성자의 위치는 모르고 있어도 된다. 단지 논리적인 순서만 알고 프로그래밍을 하면 된다.

50 03 연결리스트(Linked List) Project 4.3 데이터구조와 알고리즘 단순 연결 리스트
정보를 저장하는 노드와 바로 다음 노드를 지칭하는 한 개의 링크로 구성 전형적인 단순 연결 리스트로 알파벳 순으로 정렬되어 있다. 시작은 head이고 리스트의 끝은 tail이다.

51 03 연결리스트(Linked List) Project 4.3 데이터구조와 알고리즘 단순 연결 리스트
노드의 삽입과 삭제 작업이 링크 포인터만 조작함 노드의 삭제 모습(D의 링크 값을 C의 링크에 저장하면 된다. 노드의 삽입 모습(E의 링크 값을 H에 넣고, E의 링크는 H를 지칭하면 된다.

52 03 연결리스트(Linked List) Project 4.3 데이터구조와 알고리즘
환형 연결(Circular Linked)리스트 선형리스트의 마지막 노드가 처음 노드를 지칭하는 연결리스트 구조 이중환형 연결리스트 이중 연결 리스트는 노드를 삽입하거나 삭제할 때 4개의 링크 필드 값을 조작하기 때문에 다소 복잡한 점이 있으나 링크 값이 변경 되도 복구할 수 있는 장점이 있다.

53 04 스택(Stack) Project 4.3 데이터구조와 알고리즘 스택의 구조와 원리 데이터 삽입과 삭제
한쪽 끝에서만 삽입과 삭제가 일어나는 선형구조 후입선출 선형 리스트(LIFO; Last in First out) 데이터 삽입과 삭제 삽입 : Top 포인트, 증가시킴, 데이터 항목 삽입 삭제 : 스택 포인터의 위치에 있는 데이터 항목 삭제 후 스택 포인터 감소 TOP 포인터는 데이터 항목의 위치를 나타낸다.

54 05 큐(Queue) Project 4.3 데이터구조와 알고리즘 큐의 원리와 구조 스택과 큐의 성질
서로 다른 방향에서 삽입과 삭제가 일어나는 선형구조 선입선출(FIFO; First in First out)방법 스택과 큐의 성질 스택과 큐는 대표적인 선형구조(Linear data structure)로 입출력이 한 방향에서 이루어지는 스택, 서로 다른 방향에서 이루어지는 큐, 양방향에서 이루어지는 데크(Deque)가 있으며 이들을 제한된 선형구조라고도 부른다.

55 05 큐(Queue) Project 4.3 데이터구조와 알고리즘 선형 큐
삽입은 리어(rear)에서, 삭제는 프런트(front)에서 일어남 삽입 시 : 큐의 리어포인터, 증가시킨 후 데이터 항목저장 삭제 시 : 큐의 프런트 포인터 증가 후, 그 위치 데이터 항목 삭제 선형 큐의 구조

56 05 큐(Queue) Project 4.3 데이터구조와 알고리즘 환형 큐 선형 큐의 overflow를 해결하는 한가지 방법
자료삽입 시 끝점에 채워진 경우 시작점으로 옮겨져 채우는 것이 선형큐와 다름 삽입 시 : 큐의 리어포인터 증가, 그 자리에 데이터항목저장, 만약 리어 포인터가 끝점이면 리셋시켜 시작점으로 옮김 삭제 시 : 프런트 포인터, 증가, 그 위치에 있는 데이터 항목 제거, 만약 프런트 포인터가 끝점을 지칭하면 리셋시켜 시작점으로 한다. 저장 공간이 8개인 환형 큐의 구조

57 Project 4.3 데이터구조와 알고리즘 06 트리 대상 정보를 계층적으로 구조화한 비선형 자료구조 우리집의 혈통도

58 Project 4.3 데이터구조와 알고리즘 06 트리 표 4-6 트리의 용어 설명

59 Project 4.3 데이터구조와 알고리즘 06 트리 이진 트리 차수가 그 이하인 트리 이진 트리의 종류

60 06 트리 Project 4.3 데이터구조와 알고리즘 이진 트리의 표현방법
배열을 이용한 이진트리 표현 : Top-down, left to right순으로 나열하는 방법 배열을 이용한 이진 트리의 표현

61 06 트리 Project 4.3 데이터구조와 알고리즘 연결리스트를 이용한 이진 트리의 표현
배열을 이용하는 경우보다 기억장소의 낭비가 적음 연결 리스트 표현을 위한 노드의 구조 이진트리의 연결 리스트 표현한 것으로 여기서 null이라함은 지칭하는 값이 없음(자노드가 없음)을 뜻한다.

62 06 트리 Project 4.3 데이터구조와 알고리즘 이진 트리의 순회(Traversal)
트리의 모든 노드들을 오직 한번씩 방문하는 것 중위순회, 전위순회, 후위순회가 있음

63 07 검색 알고리즘은? Project 4.3 데이터구조와 알고리즘 순치검색(Sequential Search)
컴퓨터의 기억공간에 표현하거나 보관된 레코드나 자료 값 중에서 어떤 조건을 만족시키는 것을 찾아내는 방법 순치검색(Sequential Search) 모든 자료들을 처음부터 차례대로 하나씩 비교 하면서 마지막까지 찾아가는 방법 이분 검색(Binary Search) 정렬된 자료를 두개부문으로 나누고 찾고자 하는 값이 속하는 부분만 검색하는 방법

64 07 검색 알고리즘은? Project 4.3 데이터구조와 알고리즘 블록 검색(Block Search)
레코드들을 일정한 수의 블록 단위로 나누어서 저장하고, 그 들중 주어진 키를 갖는 레코드를 순차검색에 의해 찾는 방식 블록 검색으로 39를 검색하는 과정(먼저 32보다 크고, 56보다 작으므로 블록 2를 선택하고, 블록 2에서는 처음부터 순차 검색으로 찾아 2번째 39를 찾는다.

65 07 검색 알고리즘은? Project 4.3 데이터구조와 알고리즘 이진 트리 검색 이진 검색 트리를 이용하여 검색하는 방법
이진 검색 트리의 특징 1, 모든 노드의 자료값은 유일한 값을 갖는다. 좌측 서브 트리의 노드들의 자료값은 T의 근 노드의 자료값보다 모두 작다. 우측 서브 트리의 노드들의 자료값은 T의 근 노드의 자료값보다 모드 크다. 균형 탬색 트리는 루트 노드를 기준으로 죄측 노드들은 작고, 우측 노드들은 모두 키 값이 크다.

66 07 검색 알고리즘은? Project 4.3 데이터구조와 알고리즘 해싱(Hashing)
해싱에 의한 레코드의 주소 지정 방식은 자료 값을 해싱 함수로 인하여 계산되면 해당 레코드의 저장 주소를 지정하는 직접 주소 지정방식이다.

67 08 정렬(Sorting) 알고리즘 Project 4.3 데이터구조와 알고리즘 선택(Selection) 정렬
자료들을 특정 항목의 값에 따라 오름차순이나 내림차순으로 재배열 하는 것 선택(Selection) 정렬 한 회전 마다 최소값(최대값)을 한 개씩 찾는 방식 선택 정렬의 진행 과정은 1단계는 최소값 2를 , 2단계는 그 다음 작은 3을, 그 다음 단계는 4를, 4단계는 그 다음 작은 5를 선택하여 정렬을 완성한다.

68 08 정렬(Sorting) 알고리즘 Project 4.3 데이터구조와 알고리즘 삽입(Insertion) 정렬
정렬되어 있는 서브 파일에 새로운 자료를 하나씩 삽입하는 방식 삽입 정렬(오름차순)의 진행 과정은 1단계는 4에 3을 삽입하여 (3, 4), 2단계는 (3, 4)에 7을 삽입하여(3, 4, 7), 3단계는 (3, 4, 7)에서 2를 삽입하여 (2, 3, 4, 7)이고, 마지막으로 5를 삽입하여 정렬을 완성한다.

69 08 정렬(Sorting) 알고리즘 Project 4.3 데이터구조와 알고리즘 버블(bubble) 정렬
두개의 인접한 레코드의 키를 비교하여 키 값에 따라 자료위치를 서로 교환하는 방식 버블 정렬(오름차순)의 진행 과정

70 08 정렬(Sorting) 알고리즘 Project 4.3 데이터구조와 알고리즘 퀵(Quick) 정렬
특정자료의 키 값을 중심으로 그 값보다 큰 것들을 오른쪽, 작은 것을 왼쪽에 오도록 교환하여 정렬하는 방식 퀵 정렬의 1단계의 상세 과정으로 제어기는 5이므로 5를 기준으로 작은 것은 왼쪽, 큰 것은 오른쪽에 놓는다.

71 09 파일 처리란? Project 4.3 데이터구조와 알고리즘 파일처리 데이터 파일의 종류 파일 내용 확인에 의한 분류
파일은 레코드로 구성되고, 레코드는 항목으로 구성 데이터 파일의 종류 데이터의 기록형식에 따라 순차파일과 랜덤파일로 구분 파일 내용 확인에 의한 분류 텍스트(Text) 파일과 이진(Binary)파일 데이터 파일 구성의 예로 파일은 레코드로 구성되고, 레코드는 필드로 구성된다.

72 10 파일 처리시스템과 데이터 베이스 Project 4.3 데이터구조와 알고리즘 파일 처리 시스템
파일 처리 시스템은 각각의 파일을 처리하기 위해서 별도의 응용프로그램을 갖고 있어야 한다. 따라서 성적파일, 학급파일, 등록금 파일 등에서 학생의 이름과 학번이 모두 포함되어 있어 필드의 중복성이 크고 관리가 어려운 점이 있다.

73 10 파일 처리시스템과 데이터 베이스 Project 4.3 데이터구조와 알고리즘 데이터 베이스의 구성요소
DB는 한 조직체의 여러 응용시스템들이 공동으로 사용하기 위해 통합, 저장된 운영데이터의 집합 데이터베이스의 장점 : 데이터의 공유기능, 데이터 중복성 감소, 데이터 불일치의 최소화, 데이터 무결성, 데이터 보안성, 데이터 표준화 데이터베이스의 관계

74 10 파일 처리시스템과 데이터 베이스 Project 4.3 데이터구조와 알고리즘 데이터 베이스 관리 시스템
데이터베이스 관리 시스템

75 4주차의 과제 웹상에서 유용한 정보를 제공하는 정부기관을 알아보고, 즐겨찾기에 등록해 놓자
인기가 높은 Plug-in 응용소프트웨어의 종류와 내용을 알아보자 평가해보기에서 객관식, 진위형, 완성형 문제 풀어보기 주관식 3번과 4번 문제를 해결한 후 레포트를 작성하여 제출하기