때찌네

047 자료 구조의 분류

• 선형 구조:선형 리스트(배열), 연결 리스트, 스택, 큐, 데크
• 비선형 구조:트리, 그래프

 

048 연결 리스트(Linked List)

 

054 수식의 표기법

• 전위 표기법(Prefix):연산자→Left→Right
• 중위 표기법(Infix):Left→연산자→Right
• 후위 표기법(Postfix):Left→Right→연산자

 

055 정렬(Sort)

특정 키 항목을 기준으로 오름차순(Ascending) 또는 내림차순(Descending)으로 재배열하는 작업

내부 정렬

• 소량의 데이터를 RAM에만 기억시켜서 정렬하는 방식
• 종류:히프 정렬, 삽입 정렬, 셸 정렬, 버블 정렬, 선택 정렬, 퀵 정렬, 2-Way Merge 정렬, 기수 정렬(=Radix Sort)

외부 정렬

• 대량의 데이터를 보조기억장치에 기억시켜서 정렬하는 방식 대부분 병합 정렬(Merge Sort)기법으로 처리.
• 종류:밸런스 병합 정렬, 캐스케이드 병합 정렬, 폴리파즈 병합 정렬, 오실레이팅 병합 정렬

 

056 주요 정렬 알고리즘의 이해

삽입 정렬

초기 상태

8

5

6

2

4

1회전:두 번째 값 5를 첫 번째 값과 비교하여 첫 번째 자리에 삽입

8

5

6

2

4

→

5

8

6

2

4

2회전:세 번째 값 6을 첫 번째, 두 번째 값과 비교하여 8자리 삽입

5

8

6

2

4

→

5

6

8

2

4

3회전:네 번째 값 2를 1,2,3번째 값과 비교하여 사입하고 나머지 뒤로

5

6

8

2

4

→

2

5

6

8

4

4회전: 다섯 번째 값 4를 처음부터 비교 후 5의 자리에 삽입 나머지 뒤로

2

5

6

8

4

→

2

4

5

6

8

버블 정렬

초기 상태

8

5

6

2

4

1회전

5	8	6	2	4	→	5	6	8	2	4
5	6	2	8	4	→	5	6	2	4	8

2회전

5	6	2	4	8	→	5	2	6	4	8
5	2	4	6	8

3회전

2

5

4

6

8

→

2

4

5

6

8

4회전

2

4

5

6

8

선택 정렬

초기 상태

8

5

6

2

4

1회전:첫 번째 칸의 값을 두 번째 값부터 마지막까지 비교 후 치환

5	8	6	2	4	→	5	8	6	2	4
2	8	6	5	4	→	2	8	6	5	4

2회전:두 번째 칸의 값을 세 번째 값부터 마지막까지 비교 후 치환

2	6	8	5	4	→	2	5	8	6	4
2	4	8	6	5

3회전:세 번째 칸의 값을 네 번째 값부터 마지막까지 비교 후 치환

2

4

6

8

5

→

2

4

5

8

6

4회전:네 번째 칸의 값을 다섯 번째 값부터 마지막까지 비교 후 치환

2

4

5

6

8

2-Way 합병 정렬(Merge Sort)

초기 상태:71, 2, 38, 5, 7, 61, 11, 26, 53, 42

 

057 이분 검색(이진 검색, Binary Search)

• 순서화된 파일이어야 검색할 수 있다.
• 두 개의 서브 파일로 분리해 가면서 Key 레코드를 검색한다.
• 찾고자 하는 Key 값을 파일의 중간 레코드 Key값과 비교하면서 검색.
• 중간 레코드 번호(M):F+L/2 (단, F:첫 번째 레코드 번호, L:마지막 레코드 번호)

 

058 해싱(Hashing)

• Hash Table에 기억공간 할당, Hash Function을 이용해서 레코드 키에 대한 Hash Table내의 Home Address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식이다.
• DAM(Direct Access Memory) 파일을 구성할 때 사용, 접근 속도 빠르지만 기억공간이 많이 요구됨.
• 검색 방식 중 속도가 가장 빠름.
• 삽입,삭제의 빈도가 많을 때 유리
• 키-주소 변환 방법이라고도 함.

 

059 색인 순차 파일(Indexed Sequential File)

• 순차 처리와 랜덤 처리가 모드 가능, 키 값 순으로 정렬시켜 기록, 키 항목만을 모은 색인을 구성하여 편성하는 방식
• ISAM(Index Sequential Access Method)라고도 함.
• 색인을 탐색한 후 색인이 가리키는 포인터(주소)를 사용하여 직접 참조 가능
• 자기 디스크에 많이 사용, 자기 테이프에서는 사용 못함

색인 순차 파일의 구성

• 기본 구역(Prime Area):실제 레코드들을 기록하는 부분, 키 값 순으로 저장
• 색인 구역(Index Area):위치를 찾아가는 색인이 기록되는 부분, 트랙 색인 구역, 실린더 색인 구역, 마스터 색인 구역으로 구분
• 오버플로우 구역(Overflow Area):빈 공간이 없어서 저장이 불가능 할 때를 대비해서 예비로 확보해둔 부분
  • 실린더 오버플로우 구역:실린더마다 만들어지는 구역, 해당 실린더의 기본 구역에서 오버플로우 된 데이터를 기록
  • 독립 오버플로우 구역:실린더 오버플로우에서 더 이상 기록할 수 없을 때 대비한 예비 공간, 실린더 오버플로우 구역과는 별도로 만들어짐

장점

• 순차/랜덤 처리 가능하므로 목적에 따라 융통성 있게 처리 가능
• 효율적인 검색 가능, 삽입, 삭제 갱신이 용이

단점

• 색인 구역과 오버플로우 구역을 구성하기 위한 추가 기억 공간이 필요.
• 정렬되어 있어야 하므로 추가, 삭제가 많으면 효율이 떨어진다.
• 색인을 이용하기 때문에 엑세스 시간이 랜덤 편성 파일보다 느리다.

 

060 불대수의 기본 공식

• 멱등법칙:A+A=A, AㆍA=A
• 보수법칙:A+A`=1, AㆍA`=0
• 드모르강:A`+B`=(AㆍB)`, A`ㆍB`=(A+B)`
• 복원법칙:A``=A

 

061 논리 게이트

• XOR=A`B + B`A
• XNOR=AB+A`B`

 

061 반가산기(HA; half Adder)

 

062 전가산기(FA; Full Adder)

• 2개의 반가산기와 1개의 OR Gate로 구성

 

063 디코더(Decoder)

• n Bit의 Code화된 정보를 그 Code의 각 Bit 조합에 따라 2^n개의 출력으로 변역하는 회로
• 명령어의 명령부나 번지를 해독할 때 사용.

 

065 플립플롭

• 현재의 상태를 그대로 유지하는 논리회로
• RS
• JK
• D
• T
• 마스터-슬레이브(M/S)

 

066 자료 구성의 단위

 

067 보수

덧셈 회로를 이용하여 뺄셈을 수행하기 위해 사용된다.

 

068 자료 표현 코드

BCD 코드	ㆍ대표적인 가중치 코드 ㆍ10진수 입ㆍ출력이 간편
Excess-3초과 코드	ㆍ대표적인 자보수 코드 ㆍ비가중치 코드
Gray 코드	X-OR연산 ㆍ입ㆍ출력장치, A/D변환기, 주변장치 등에서 숫자를 표현할 때 사용 ㆍ하드웨어적인 요류가 적음
패리티 검사 코드	ㆍ오류 검사위해 1Bit의 패리티 체크 비트추가 ㆍ1Bit의 오류만 검출 ㆍOdd Parity:1인 Bit의 수가 홀수 ㆍEven Parity:1인 Bit의 수가 짝수
해밍 코드	ㆍ스스로 검출 및 교정 가능 ㆍ1Bit의 오류만 교정 ㆍ검출 및 교정위한 잉여 비트가 많이 필요 ㆍ2^n번째 비트는 오류 검출을 위한 패리티 Bit

 

069 그레이 코드 변환

 

070 CPU의 구성 요소

제어장치

• 모든 장치들의 동작을 지시하고 제어
• RAM에서 명령어를 해독하여 해당 장치에 제어 신호 보내서 정확하게 수행토록 지시
• PC, IR, 부호기, 명령어 해독기, 번지 해독기 등으로 구성

연산장치

• 연산을 수행하는 장치
• 산술, 논리, 관계, 이동(Shift) 등의 연산 수행
• 가산기, 누산기, 보수기, 데이터 레지스터, 오버플로우 검출기, Shift Register 등으로 구성

레지스터

• CPU 내부에서 처리할 명령어나 연산의 중간 결과값 등을 일시적으로 기억하는 임시 저장소
• 플립플롭이나 래치(Latch)들을 병렬로 연결하여 구성
• 메모리 중에서 가장 속도가 빠름

 

071 주요 레지스터

 

072 버스

 

073 명령어의 구성

Operation Code(연산자부) + Operand(자료부)

연산자부(Operation Code부)

• 수해해야 할 동작에 맞는 연산자를 표시함, 흔히 OP-Code부라고 한다.
• n Bit면 최대 2^n개의 명령어를 사용할 수 있다

자료부(Operand부)

• 실제 데이터에 대한 정보를 표시
• 기억장소의 주소, 레지스터 번호, 사용할 데이터 등을 표시
• 크기는 메모리의 용량과 관계
• 길이가 n Bit라면 최대 2^n개의 기억장소를 주소로 지정할 수 있다.

 

074 연산자(Operation Code)의 기능

함수연산기능

• 산술연산:ADD, SUB, MUL, DIV, 산술 SHIFT 등
• 논리연산:NOT, AND, OR, XOR, 논리적 SHIFT, ROTATE, COMPLEMENT, CLEAR 등

자료전달기능

CPU와 기억장치 사이에서 정보를 교환하는 기능

• Load:기억장치에 기억되어 있는 정보를 CPU로 꺼내오는 명령
• Store:CPU에 있는 정보를 기억장치에 기억
• Move:레지스터 간에 자료를 전달
• Push:자료를 스택에 저장
• Pop:스택에서 자료를 꺼냄

제어기능

명령어의 실행 순서를 변경시킬 때 사용

• 무조건 분기 명령:GOTO, Jump(JMP)
• 조건 분기 명령:IF 조건, SPA, SNA, SZA
• Call:부프로그램 호출
• Return:부프로그램에서 메인 프로그램으로 복귀

입/출력기능

CPU와 I/O장치, 또는 메모리와 I/O 장치 사이에서 자료를 전달

• INPUT:입/출력장치의 자료를 주기억장치로 입력
• OUTPUT:주기억장치의 자료를 입/출력장치로 출력

 

075 피연산자의 수에 따른 연산자의 분류

단한 연산자

이항 연산자

 

076 연산

AND(Masking Operation)

• 특정 문자나 Bit를 삭제(Clear)시키는 명령, Masking 명령이라고도 함
• 삭제할 부분의 Bit를 0과 AND시켜서 삭제, 대응시키는 0인 Bit를 Mask Bit라함

OR(Selective Set)

• 특정 문자나 삽입 또는 Bit에 1을 세트시키는 명령, Selective Set연산이라고도함
• 삽입하거나 세트시킬 Bit에 삽입할 문자 또는 1을 OR 연산시킴

XOR(Compare)

• 2개의 데이터를 비교하거나 특정 Bit를 반전시킬 때 사용
• 2개의 데이터를 XOR 연산하여 결과에 1Bit라도 1이 있으면 다른 데이터임
• 반전시킬 때는 반전시킬 Bit와 1을 XOR 시킴

NOT(Complement,보수)

• 각 Bit의 값을 반전시키는 연산, 보수 구할 때 사용

논리 Shift

• 왼쪽 또는 오른쪽으로 1Bit씩 자리를 이동시키는 연산으로 데이터의 직렬 전송(Serial Transfer)에 사용
• 삽입되는 자리는 무조건 0임

Rotate

• Shift에서 밀려 나가는 Bit의 값을 반대편 값으로 입력하는 연산
• 문자 위치를 변환할 때 이용

산술 Shift

• 부호(Sign)를 고려하여 자리를 이동시키는 연산, 2^n으로 곱하거나 나눌 때 사용함
• 왼쪽으로 n Bit Shift하면 원래 자료에 2^n을 곱한 값과 같음
• 오른쪽으로 n Bit Shift하면 원래 자료를 2^n으로 나눈 값과 같음
• 홀수를 오른쪽으로 한 번 Shift하면 0.5의 오차가 발생함

 

077 명령어 형식

3번지 명령어

• Operand부가 3개로 구성되는 명령어 형식, 여러 개의 범용 레지스터를 가진 컴퓨터에서 사용
• 연산의 결과는 Operand 3에 기록
• 연산 시 원시 자료를 파괴하지 않음
• 다른 형식보다 프로그램 전체의 길이를 짧게 할 수 있음
• 전체 P/G 실행 시 명령 인출을 위하여 RAM에 접근횟수가 줄어들어 실행속도를 단축시킴

2번지 명령어

• Operand부가 2개로 구성되는 명령어 형식, 가장 일반적으로 사용
• 여러 개의 범용 레지스터를 가진 컴퓨터에서 사용
• 3주소 명령에 비해 명령어의 길이가 짧음
• 연산의 결과는 주로 Operand 1에 저장되므로 Operand 1에 있던 원시자료가 파괴됨
• 전체 P/G의 길이가 깅러짐

1번지 명령어

• Operand부가 1개로 구성
• AC(Accumulator)를 이용하여 명령어를 처리

0번지 명령어

• Operand부 없이 OP-Code부만으로 구성
• 모든 연산은 Stack 메모리의 Stack Pointer가 가리키는 Operand를 이용하여 수행
• 수식을 계산하기 위해서는 우선, 수식을 Postfix형태로 변경해야 함
• 모든 연산은 스택에 있는 자료를 이용하여 수행하기 때문에 Stack Machine이라고도 함
• 원래의 자료가 남지 않음

 

078 주소 설계 시 고려 사항

 

079 주소지정방식(Addressing Mode)의 종류

암시적 주소지정방식(Implied Mode)

• 주소를 지정하는 필드가 없는 0번지 명령어에서 Stack의 SP가 가리키는 Operand를 암시하여 이용함

즉치(즉시)적 주소지정방식(Immediate Mode)

직접 주소지정방식(Direct Mode)

간접 주소지정방식(Indirect Mode)

계산에 의한 주소지정방

 

------------------------------------------------------------------

참고자료

마이크로 명령 형식

• 수평 마이크로 명령

• 수직 마이크로 명령

• 나노 명령

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.