[이상선의 10분 강의 자료구조] 1. 자료구조의 개념

자료구조

안녕하세요. 하루 10 분 강의 자료구조 편입니다.
이 강의도 마찬가지로 C언어 강의를 전부 수강한 분께서 들으면 매우 적합한 강의입니다.
C언어 문법을 모르고 공부하는 것은 매우 어려울 것이라 생각하므로
필수로 C언어 기초를 배우고 와서 도전해보시길 바랍니다.

자료구조 역시 짧고 굵게 개념부터 이해하고 가시죠!

자료구조란?

• 자료(data) : 사람이나 컴퓨터가 인식하고 처리하는데 알맞은 형태로 존재하며 평가되지 않은 것
• 자료구조(data structure) : 자료의 처리 및 자료를 기억공간에 저장하는 방법

자료의 단위

① bit(binary digit) - 0또는 1을 의미하는 정보의 최소단위
② byte - 8bit의 한 묶음으로 1문자를 나타냄
③ word - CPU에서 처리되는 명령의 단위 (HalfWord=2byte, FullWord=4byte, DoubleWord=8byte)
④ field - 같은 종류의 data가 기록되는 항목으로 최소한의 문자집합
⑤ record - 관련된 field의 집합으로 자료의 처리 및 기록의 단위
⑥ block - 레코드의 묶음, 물리적 기억장치에 입출력되는 단위
⑦ file - 구조가 같은 레코드의 집합
⑧ database - 관련 file의 통합체

자료구조 선택 시 고려사항

1. 데이터의 양과 접근 빈도
2. 데이터의 성격
3. 사용되는 컴퓨터의 기억장치 용량
4. 접근시간
5. 프로그램 작성의 용이성

자료의 표현

(1) 수치자료의 표현

1. 10진 데이터 표현
   ① zone decimal 형식 = unpacked

• 1바이트에 숫자 1개 저장
• 부호가 양수이면 C 음수이면 D

② packed decimal 형식

• 1바이트에 2개의 숫자 저장

1. 고정 소수점 형식(fixed point format)

• 소수점의 위치가 고정되어 있는 수로 정수를 표현한다
  ① 부호화 절대치 방법(signed magnitude)
• MSB(Most Significant Bit)를 부호 비트로 두어 MSB가 0이면 양수, 1이면 음수를 나타냄
• 음수의 표현이 간단, 하드웨어 비용증가(가산기와 감산기 모두 필요)
• 수의 표현범위 : -(2n-1승-1) ～ (2n-1승-1)

• 보수를 사용하는 이유

• 뺄셈을 수행할 때
  가산기를 사용할 수
  있도록 하기 위해서

② 1의 보수 방법(one's complement)

• 음수 표현 시 0은 1로 1은 0으로 바꾼다
• 덧셈할 때 윤환올림수(End around carry)가 발생할 수 있다.
• 수의 표현범위 : -(2n-1-1) ～ (2n-1-1)
  ③ 2의 보수 방법(two's complement)
• 1의 보수 +1로 음수를 표현
• 위의 두 방식에서 +0과 -0이 표현되는 것을 해결
• 수의 표현범위 : -(2n-1) ～ (2n-1-1)
• 장점 : 0이 하나, 1의 보수 방법보다 하나의 수를 더 표현가능, 윤환올림수 연산과정이 없다.

1. 부동 소수점 형식(floating point format)

• 매우 큰 수나 매우 작은 수를 표현할 때 유리
• 지수+가수의 형태로 지수부(exponent)는 7bit로 표현되며
  소수점은 7bit와 8bit 사이에 있는 것으로 가정한다
• 가수는 정규화 과정을 거쳐 저장
  ① 정규화(normalize)
• 소수점을 이동하여 소수 첫째 자리에 유효수가 오도록 하여 지수부+가수부(소수부)의 형태로
  만드는 것

• 64bias 사용 이유

• 양수만으로 모든 지수를
  표현하기 위해
• 지수부의 계산
  : 지수부는 27=128개의 기수를 표현 가능
  : 64를 0으로 하여 64미만을 음수 64이상을 양의 지수로 한다
  : 지수부는 ‘64+지수’의 결과를 16진수로 변환하여 저장
  ② 정규화 순서 : 10진수를 16진수로 변환 → 소수점을 이동하여 정규화 → 지수+64의 값을 16진수로
  변환하여 지수부에 저장 → 소수점이하인 가수부는 그대로 저장
  ③ 정규화의 이점
• 수의 크기를 간단히 비교 가능
• 표현된 수의 정밀도를 높일 수 있다
• 유효숫자의 범위를 높일 수 있다

(2) 문자 자료의 표현

1. BCD코드(Binary Coded Decimal code)
   ① 6bit로 구성된 2진화 10진 코드
   ② 2bit의 zone bit와 4bit의 digit bit로 구성
   ③ 영문 대문자와 소문자의 구별이 안된다
   ④ zone bit : 00-숫자, 01-문자A～I, 10-문자J～R, 11-문자S～Z

2. EBCDIC코드(Extended Binary Coded Decimal Interchange code)
   ① 8bit로 구성된 확장 2진화 10진 코드
   ② 4bit의 zone bit와 4bit의 digit bit로 구성
   ③ zone bit - 앞 두 bit : 00-여분, 01-특수문자, 11-알파벳대문자, 숫자, 10-소문자
   다음 두 bit : 00-문자A～I, 01-문자J～R, 10-문자S～Z, 11-숫자

3. ASCII코드(American Standard Code for Information Interchange code)
   ① 7bit로 구성되어 데이터 전송용으로 많이 사용
   ② 3bit의 zone bit와 4bit의 digit bit로 구성

1. 기타 코드
   ① 그레이 코드(gray code)

• 아날로그/디지탈 변환기나 입출력 코드로 사용
• 2진수 1010을 gray코드로 변환 1 → 0 → 1 → 0
  ↓ + ↓ + ↓ + ↓
  1 1 1 1
• gray코드 1111을 2진수로 변환 1 1 1 1
  ↓↗+↓↗+↓↗+↓
  1 0 1 0
  ② 패리티 체크(parity check)
• 짝수 패리티 체크 : 1의 개수가 짝수가 되게
• 홀수 패리티 체크 : 1의 개수가 홀수가 되게
  ③ 해밍코드(hamming code)
• 에러의 발견 및 교정이 가능
  ④ 자기보수 코드 - 2-4-2-1코드, 51111코드, 3초과코드(Excess-3 code), 84-2-1코드

• 가중치 코드

• BCD 코드, 8-4-2-1 코드, 2-4-2-1 코드, 이중 5(biquinary) 코드, 5421코드

• 비 가중치 코드

• 3초과 코드, 2 out of 5 코드, 그레이 코드

• 에러 검출 코드

• parity 코드, 2 out of 5 코드, 이중 5 코드, 해밍코드

자료 추상(data abstraction)

(1) 개요 - 추상이란 어떤 물체나 현상을 중요한 특징만을 추출하여 표현하는 것
(2) 자료의 추상 - 문자열, 숫자, 이진트리 등과 같이 연산의 대상이 되는 자료를 추상화

1. 기본적 추상 - 컴퓨터 안에 저장된 자료 값을 추상화
   예) 자료 값이 저장된 메모리에는 이름을 부여하여 추상화시키며 이를 변수라 한다
2. 구조적 추상 - 연관된 자료 값의 집합을 추상화
3. 단위 추상 - 단위 프로그램 전체에 대한 추상

ADT의 개념

(1) 추상 자료형(ADT : Abstract Data Type)

• 객체의 명세와 그 연산의 명세가 객체의 표현과 연산의 규칙으로부터 분리된 데이터 타입
• 프로그램의 제어보다 자료에 관심을 두고 자료구조 및 그와 관련된 연산들로 구성된 모듈을 작성하여
  정수나 실수형과 같은 하나의 자료형으로 취급할 수 있는 것

1. 조건 - 자료형과 연산에 대한 정의가 한 곳에서 가능

• 자료형과 연산이 하나로 묶인 자료형에 대한 프로그램의 접근을 제한할 수 있어야 한다
  (캡슐화와 정보은폐 가능)

1. 추상적 자료형으로 작성된 모듈은 일반 자료형과 똑같은 방법으로 사용
2. 구현 방법
   ① 자료와 그에 관련된 연산들의 기본적인 특성을 기술
   ② 이미 존재하는 자료형을 이용하여 기술된 내용을 구현
   ③ 기술 내용과 구현 결과가 일치함을 보여줘야 한다

매개변수 전달 방법

(1) Call by Value

• 메인 프로그램에서 서브 프로그램을 호출하여 실행할 때 변수의 값을 넘겨주는 방법
• 서브 프로그램에서는 별도의 기억장소를 확보해야 한다
• 형식 매개 변수의 값을 조작해도 메인 프로그램의 값을 변경시킬 수 없다
  (2) Call by Reference (Address, Location)
• 실 매개변수의 주소를 서브 프로그램에 전달하는 방법
• 형식 매개변수를 위한 기억장소가 별도로 확보되지 않으며 실 매개변수의 기억장소를 공유
• 형식 매개변수의 값을 조작할 경우 실 매개 변수의 값이 변경된다
  (3) Call by Name
• 메인 프로그램에서 서브 프로그램으로 변수 자체가 전달되는 방법
• 서브 프로그램에서 변수조작은 메인 프로그램에서 해당변수를 조작하는 것과 같다

오늘은 너무 이론적인 부분이 많았습니다.

하지만 자료구조는 매우 중요한 개념이라 반드시 짚고 넘어가야 될 것에 대하여 적어보았습니다.

다음 시간에는 자료구조의 종류에 대해서 그리고 그 다음시간부터는 같이 소스를 분석하고

열공하는 시간을 가져보도록 하겠습니다.

코드는 무조건 적고 이해하고 또 적는 것입니다.
공부하는 여러분 파이팅입니다.