학은제 수업 1주차로 자료구조의 이해, 자료의 표현에 대해 정리한다.
1. 자료구조
- 자료구조는 계산에 쓰이는 여러 가지 자료들을 조직화, 구조화(organize)한 것이다.
아래의 표는 자료구조를 이해하기 위한 예시를 작성했다.
일상생활에서의 예 | 자료 구조 |
물건을 쌓아두는 것 | 스택 |
음식점 드라이브 스루의 줄 | 큐 |
할 일 리스트 | 리스트 |
영어사전 | 사전, 탐색구조 |
지도 | 그래프 |
조직도 | 트리 |
2. SW코딩
- 대부분의 sw코딩은 자료(data)를 처리하며, 이자료들은 자료구조(data structure)를 사용하여 표현되고 저장됨.
- 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여 최적의 설계를 작성해야 한다.
- 자료구조의 개념과 활용능력에 따라 sw코딩의 효율성이 가늠된다.
SW 코딩의 구조
- sw코딩은 자료구조와 알고리즘으로 이루어져있다.
자료구조 분야 | 설 명 |
이론적인 측면 | 그래프 이론, 집합 이론, 조합적 분석의 이산수학과 확률 이론을 기초로 알고리즘을 분석, 검색, 정렬방법을 선택한다. |
효율적인 측면 | 공간복잡도, 시간복잡도 기초로 효율분석을 하여 최적의 상태를 결정함. |
실제적인 측면 | 자료를 문자열, 리스트, 트리, 그래프, 파일 구조로 표현하고 알고리즘을 구현하고, sw코딩과 파일작성, 메모리 관리, 운영체제 등에 적용함 |
3. 자료구조 자료형태에 따른 분류
자료 형태 | 설 명 |
단순구조 | 자료값을사용하기위한기본형태로 코딩언어에서제공하는정수, 실수, 문자, 문자열등의데이터타입 |
비선형구조 | 계층구조나망구조를갖는트리, 그래프등의자료구조 |
파일구조 | 레코드 집합인 파일에 대한 자료구조로 보조기억장치에 데이터가 실제로 저장되는 형태 순차파일, 색인파일, 직접파일 등이 있다 |
선형구조 | 자료들의관계가1:1 관계인 순차리스트, 연결리스트, 스택, 큐, 데크 등 |
4. 컴퓨터의 자료표현
1. 존 형식
- 10진수를 한 자리를 표현하기 위해서 1바이트(8비트)를 사용하는 형식
영 역 | 설 명 |
존 영역 | 상위 4비트 1111로 표현 |
수치 영역 | 하위 4비트 표현하고자 하는 10진수 한자리값에 대한 2진수 값을 표시 |
- 10 진수의 자릿수만큼 존 형식을 연결하여 사용
- 마지막 자리의 존 영역에 부호를 표시
- 양수(+) : 1100 / 음수(-) : 1101
2. 팩 형식
- 존 영역은 항상 1111로 표시되어 메모리 낭비 제거
- 10진수 한자리를 표현하기 위해서 존 영역 없이 4비트를 사용하는 형식
- 최하위 4비트에 부호를 표시
3. 2진수의 정수 표현
- 일정한 길이의 n비트로 표현, 부호와 절댓 값 형식으로 표현
- 최상위 1비트: 부호 표시
- 양수(+) : 0 음수(-) : 1
- 나머지 n-1 비트: 이진수 표시
4. 1의 보수 형식
- 음수 표현에서 부호 비트를 사용하는 대신 1의 보수를 사용하는 방법
- 1의 보수 형식은 부호를 포함한 7비트 전부 1 인 값에서 절댓 값을 빼서 구한 나머지이다.
위의 경우 1111 1111 - 0001 0101 (- 21 의 절댓값 ) => 1110 1010 이 -21의 1의 보수 이다.
5. 2의 보수 형식
- 음수 표현에서 부호 비트를 사용하는 대신 2의 보수를 사용하는 방법
- 1의 보수에 1을 더한다.
위의 경우 1111 1111 - 0001 0101 (- 21 의 절댓값 ) => 1110 1010 + 1 => 1110 1011 이 -21의 2의 보수 이다.
6. BCD코드
6비트를 사용하여 문자 표현
- 상위 2비트: 존 비트
- 하위 4비트: 2진수 비트
- 존 비트와 2진수 비트를 조합하여 10진수 0~9와 영어의 대/소문자 특수문자를 표현
7. EBCDIC 코드
8비트를 사용하여 문자 표현
- 상위 4비트: 존 비트
- 하위 4비트: 2진수 비트
- 존 비트와 2진수 비트를 조합하여 10진수 0~9와 영어의 대/소문자 특수문자를 표현
8. ASCII 코드
7비트를 사용하여 문자 표현
- 상위 3비트: 존 비트
- 하위 4비트: 2진수 비트
- 존 비트와 2진수 비트를 조합하여 10진수 0~9와 영어대문자/소문자, 특수문자를 표현
9. 유니코드
EBCDIC 코드나 ASCII 코드는 최대8비트로숫자, 몇가지특수문자, 알파벳정의한다.
그렇기 때문에 문자코드표에 정의되어 있지않은 문자는 표현이 불가능하다. 이러한 문제를 해결하기 위해 세계 여러나라의 언어를 통일된 방법으로 표현할 수 있도록 정의한 국제표준코드(ISO/IEC 10646) 가 유니코드이다.
2바이트를 조합하여 하나의 글자를 표현하기 때문에 1바이트 코드로 표현할 수 없었던 다양한 언어를 표현함.