- 집적 회로

- 종류 별 전달지연 시간이 짧은 순서

- ECL < TTL < CMOS < MOS

- 논리 회로

- 반가산기 : 1비트 두개를 더했을 때, 합과 자리올림 수를 구하는 회로

- 전가산기 : 자리 올림수를 포함해서 1비트 두개를 더했을 때, 합과 자리올림 수를 구하는 회로

- 2개의 반가산기와 OR게이트로 만들 수 있다.

- 디코더 : n 자리수의 code화된 정보를 각 bit 조합에 따른 2^n개의 출력으로 출력해주는 회로

- 플립 플롭 : 1비트의 정보를 보관하고 유지할 수 있는 논리 회로, 레지스터에 쓰인다.

- latch : 1비트의 정보를 데이터가 바뀌기 전까지 계속 유지하는 회로.

- gated latch : 입력의 반영시기를 조절할 목적으로 별도의 제어 입력(E/ EN)을 받는 latch

- SR latch = set-reset latch : SR NOR latch / SR NAND latch

- RS 플립플롭 : S=R=1 일때는 출력값이 에러로 나와버리는 단점

- D 플립플롭 : d는 데이터 혹은 딜레이로 알려져 있대.. 클록의 엣지에서 D값을 캡쳐하여 Q에 반영함. 엣지가 발생하지 않으면 Q는 유지된다.

- JK 플립플롭 : K=J=1 일때는 토글의 기능. RS를 보완

- T 플립플롭 : JK 플립플롭의 J와 K를 묶어 T로 만들었다. T가 0이면 현상유지, 1이면 보수로 바뀐다. 토클을 의미.

- M/S 플립플롭 = master and slave : 출력신호가 입력측에 피드백되어 오동작하는 레이스 현상을 방지하는 플립플롭. 입출력이 완전 분리

- 순차 회로 / 조합 회로

1. 순차 회로는 플립플롭과 게이트들로 이루어진 회로다. 즉 이전상태에 대한 정보를 순차적으로 사용한다. 즉 시간에 따라 변화한다.

2. 조합 회로는 조합에 따라 결과가 정해지는 회로다. 시간이 흘러도 변하지 않는다.

- 레지스터

- CPU 내부에서 처리할 명령어나, 연산의 중간 결과등을 임시적으로 기억하는 저장장치

- 플립플롭 / 래치들을 병렬로 연결하여 구성한다.

- 레지스터간에 자료 전송하는 방법

1. 직렬 전송 : A에서 B로 하나씩 옮긴다.

2. 병렬 전송 : A에서 B로 동시에 옮긴다. 즉 워드가 한번에 전송된다. 직렬보다 빠르다.

3. 버스 전송 : 모든 레지스터들이 공통으로 사용하는 통로를 만든다. 

- 종류

1. 범용 레지스터 : AX, EBX, ECX, EDX (32비트) : 계산용

2. 세그먼트 레지스터 : 메모리 영역에 대한 주소지정용, CS, DS, SS, ES, FS, GS, 응용프로그램이 접근할 수 없다.

3. MAR = 메모리 주소 레지스터 : 기억장치를 출입하는 데이터의 주소를 기억

4. MBR = 메모리 버퍼 레지스터 : 기억장치를 출입하는 데이터를 기억

- cpu가 데이터를 처리할 때 반드시 거치는 레지스터

5. PC = program counter : CPU 내의 레지스터로 다음에 수행될 명령어의 주소를 갖고 있다.

6. 누산기 = accumulator = ALU : CPU의 산술 연산 중간 결과가 저장되는 레지스터. 연산기능을 담당하는걸로 착각하기 쉽다.

7. SR, PSWR : 시스템 순간 내부 상태를 기록하는 레지스터. psw = program status word

- 마이크로 명령어 : 마이크로 오퍼레이션의 집합

- 오퍼레이션 : cpu에 특정 연산을 명령하는 이진코드 

- 제어 장치

- 제어 장치 구성 방식

1. 하드 와이어드 방식 = hard wired : 논리 회로로 구현해서 빠르지만, 새로운 버전으로 유지보수가 어렵다. = 하드웨어

2. 마이크로 프로그래밍 : 느리지만, 회로가 간단하고 경제적이며, 융통성있다. = 소프트웨어, 주로 ROM에 저장된다.

- 일련의 제어워드 ( = 마이크로 명령어 = micro instruction = 여러 개의 micro operation )의 모임

- 한 마이크로 오퍼레이션은 한 cpu cycle에 수행된다. = micro cycle time

- micro cycle time을 부여하는 방식

1. 동기 고정식

- 모든 micro operation의 수행 시간이 같다고 가정해서, cpu clock을 가장 느린 micro cycle time과 같게 정의함

- 구현이 간단하지만, 당연히 cpu 시간을 낭비하게 된다.

2. 동기 가변식

- 수행 시간이 비슷한 micro operation끼리 묶어서 micro cycle time을 다르게 정의한다.

- 서로 다른 그룹들 간에 동기를 맞추기 위해 정수배가 되게 정의한다.

- 구현이 까다롭지만, cpu 시간 낭비를 줄일 수 있다.

3. 비동기식

- 모두 다르게 micro cycle time을 정의

- 구현이 헬이지만, 시간 낭비가 하나도 없다. 즉 이상적이기만 한 방식

- 마이크로 명령어 형식

- 수평적 : 연산 필드의 각 비트가 제어신호와 일대일로 대응시킴. 필요한 비트수가 길어지므로 제어 기억장치의 필요용량이 커진다.

- 수직적 : 연산 필드에 인코드된 비트만 올리기 때문에 필요한 비트수가 줄어들었지만, 추가적인 해독기가 필요해짐

- 나노 명령

- 연산 필드가 두 개면, 두 연산을 동시에 수행할 수 있다.

- 조건 필드는 분기 필드에 사용될 조건 플래그를 나타낸다.

- 분기필드는 분기의 종류와, 다음에 실행할 마이크로 명령어의 주소를 결정하는 방법을 알려준다.

- 주소 필드엔 분기하는 경우의 목적지 마이크로 명령어의 주소가 담긴다.

- 제어장치로 입력되는 항목 : 클록, 명령어 레지스터, 플래그 -> 제어신호 출력

- 캐시 : cpu의 계산을 돕기 위해 임시적으로 데이터가 거쳐가는 겁나 빠른 기억장치

- 캐시의 기록정책

1. write through : 캐시에 쓸 때는 주메모리에도 쓴다.

2. write back : 캐시에 다 쓰고 나서 제거할 때만 주메모리에 쓴다.

- 캐시의 라인교체 정책

- FIFO / LIFO : Belady's anomaly

- LRU = least recently used : 사용된지 가장 오래된 라인부터 교체, 지역성을 고려해 최근 참조된 라인은 다시 참조될 가능성이 높다는 관점

- 페이지 참조시마다 시간을 기록해야 하는 오버헤드가 존재.

- LFU = least frequently used : 가장 사용횟수가 낮은 라인부터 교체

- 연관 메모리 = 연관 기억장치 = CAM

- 가상메모리 기법, 캐시 메모리에서 사용하는 매핑 테이블에 적합한 메모리

- 주소로 접근하는 것이 아니라, 주소에 담긴 내용으로 접근할 수 있는 기억장치.

- 주소로 접근하는 메모리보다 빠르지만, 매개변수와 내용을 비교하는 병렬 판독 논리 회로가 들어가기 때문에 하드웨어 비용을 늘어난대.

- RAM = random access memory

- 자유롭게 읽고 쓸 수 있는 기억장치 <-> ROM, 읽기만 가능

- 휘발성 메모리

- 종류

1. 동적램 DRAM

- 구성소자가 콘덴서, 전력 소모가 적은대신 느리다. 그래서 싸다. 일반적인 주기억장치로 사용. 주기적인 전원 재충전이 필요

2. 정적램 SRAM

- 구성소자가 플립플롭, 전원공급동안에는 내용을 기억한다. 그래서 전력 소모가 큰 대신 빠르다. 그래서 비싸다. 캐시메모리로 사용.

- 자기 코어 기억 장치 : 0 또는 1의 값을 갖는 코어 플레인들로 구성. 코어 중심의 전선에 흐르는 방향에 따라 1/0의 값이 정해진다.

- IO 방식

- CPU 제어 = PIO

- DMA = directed memory accecss : 주변장치들이 메모리에 직접 접근하게 DMA 제어기에 cpu버스를 할당해준다. 이후 cpu는 유휴.

- 사이클 스틸링 방식 : 한 개의 데이터 워드를 전송하고 버스를 다시 cpu에게 돌려줌.

1) DMA 제어기 초기화 

2) IO 장치가 DMA 요청

3) DMA 제어기가 CPU에 버스요청 4) 버스 승낙 5) DMA 승낙

6) 전송과정

7) DMA 제어기가 CPU에 완료를 인터럽트로 알림

- 입출력 채널 : 시스템의 프로세서와는 독립적으로 입출력만을 수행하는 프로세스들로 구성. CPU와는 독립적이다.

- 셀럭터 채널 = selector channel : 한 개의 보조 채널로 한 순간엔 한 개의 주변기기만 서비스할 수 있다. 블록 단위 전송, 고속장치(디스크)

- 멀티플렉서 채널 = multiplexer channel

- 여러 개의 보조 채널로 한 순간에 여러개의 주변기기를 서비스. 바이트 단위 전송. 저속장치(키보드)

- 여러 입력 신호 중에 하나를 선택하여 하나의 출력선에 전달

- 디멀티플렉서 채널

-  하나의 입력선으로 입력 신호를 받아 여러 출력선 중에 하나를 선택해 전달

- 메모리 인터리빙

- 여러개의 독립된 모듈로 이루어진 메모리와 CPU간에 주소 버스가 한 개라면 같은 시간에 여러 모듈로 주소를 전달할 수 없다.

- 따라서 각 모듈로 전달할 주소를 교대로 분산배치하고, 차례대로 전송하여 여러 모듈을 병행 접근할 수 있다.

- 즉 이 메모리을 구성하는 모듈 수 만큼의 word에 동시에 접근할 수 있다.

- cpu의 쉬는 시간을 줄일 수 있고, 단위시간당 수행하는 명령어의 수를 증가시킬 수 있다.

- cpu와 메모리 사이의 대역폭을 높일 수 있다.

- 캐시 메모리, DMA 전송 등에서 많이 사용된다.

- 자료 표현 코드

- 아스키 코드 : 7비트(존 비트(3) + 디지트 비트(4)) + 1비트(패리티)

- BCD 코드 : 10진수의 각 자리에 4비트씩 할당하여 표면하는 방법

- excess-3 코드

- bcd 코드의 일종으로, bcd에 3을 더해 표현한다. 이를 통해 0의 보수는(1의 보수화) 9가 되는 이점이 있다. = 자기 보수 코드

- 또한 모든 비트가 0인 경우가 없으므로, 오류 검출에 활용할 수 있다.

- gray 코드

- bcd 코드의 인접하는 비트들을 XOR하여 만든 코드

- 2진법 to gray 코드

- 1001의 첫 번째 비트를 그대로 내려다 쓴다.

- 나머지는 인접한 비트들을 XOR -> 1101

- gray 코드 to 2진법

- 1001의 첫번째비트를 그대로 내려다 쓴다.

- 나머지는 인접한 비트들을 XOR -> 1110

- 해밍코드

- bcd 코드에 대한 오류 검출기능이 있지만, 한 비트의 오류만 교정할 수 있다. 1, 2, 4, 8, ... 비트는 패리티 비트임.

- n번째의 패리티 비트는 n번째 비트부터 n개씩 포함한 비트들을 대상으로 결정된다.

- 1011(bcd)를 해밍코드로 바꿔보자.

- x x 1 x 0 1 1

- 1번째 패리티 비트는 1 / 3 / 5 / 7의 비트 on의 숫자가 짝수여야 한다. -> 2개 -> 0

- 2번째 패리티 비트는 2,3 / 6,7 의 비트 on의 숫자가 짝수여야 한다. -> 3개 -> 1

- 4번째 패리티 비트는 4,5,6,7 의 비트 on의 숫자가 짝수여야 한다. -> 2개 -> 0

- 최종적으로 0 1 1 0 0 1 1

- 팩/언팩 10진법

1. 언팩 10진법

- bcd에 부호질하기, 1바이트를 반띵해서 zone/digit으로 나누고, zone에는 부호를, digit에는 bcd를 표기

- +375는 F(1111) + 3(0011) / F(1111) + 7(0111) / C(1100) + 5(0101)

- -375는 F(1111) + 3(0011) / F(1111) + 7(0111) / D(1101) + 5(0101)

2. 팩 10진법

- zone은 맨 오른쪽 하위 4비트에만 표기

- +375는 3(0011) / 7(0111) / 5(0101) / C(1100)

- 병렬 컴퓨팅 : 컴퓨터들을 병렬적으로 묶음 = 슈퍼 컴퓨터 // 성능 척도 MIPS = million instructions per second

- 병렬 처리 기법

1. 파이프 라인 : 한 프로세스를 서로 다른 기능을 하는 서브 프로세스들로 나눠, 동시에 서로 다른 데이터들을 건드리게 하는 기법이다.

- 공장 조립 라인을 생각해보면 된다. 첫 제품은 라인을 모두 거쳐 완성될 동안 다음 제품들도 라인을 거치고 있다.

ex) 세그먼트의 부연산 속도가 20이고 4세그먼트의 파이프라인으로 100개의 태스크를 수행한다면, 비파이프라인시스템보다 얼마나 빠를까?

- 첫 태스크 4 * 20 + 나머지 99개 태스크 * 20 = 100개 태스크 * 20 * x배 빠르다.

2. 벡터 프로세서

 - 벡터라 선형적으로 처리될 줄 알았는데 아닌가봄

3. 배열 프로세서

- 배열이라 선형적으로 처리될 줄 알았는데 아닌가봄.

- PE = processing element 라는 다수의 연산기가 병렬로 처리하는 동기적 병렬 처리기래.

4. 데이터 흐름 컴퓨터

- instruction을 수행하는데 필요한 피연산자가 전부 준비되면 수행하고, 결과를 필요로 하는 instruction에 보내준대.

- 따라서 pc가 필요없대.

- 인터럽트

- 인터럽트에 해당하는 서비스 루틴을 수행할 때, IF(인터럽트 플래그)를 0으로 설정하면 추가 인터럽트 발생을 막을 수 있다.

- 종류

1. 외부 : 정전, cpu내부 오류, 입출력 인터럽트

2. 내부 = trap : 0으로 나누기, overflow, 잘못된 주소 참조

3. 소프트웨어 = SVC = supervisor call

- 입출력 장치들의 인터럽트 우선순위

1. 소프트웨어적으로 결정 = 폴링 = polling : 프로그램상에서 결정되므로 변경 가능하다.

- 차례대로 인터럽트 했는지 물어보는 방식

2. 하드웨어적으로 결정 = vectored interrupt : 어쨌든 장치와 cpu가 연결되어 있고 인터럽트 발생시 정보(인터럽트 벡터)를 제공한다.

2-1) 데이지 체인 = Daisy Chain : 모든 인터럽트을 만들 수 있는 장치들이 직렬로 cpu에 연결되어 있다.

2-2) 패러럴 = parallel : 각 장치들이 병렬로 연결되어 있다.

- 명령어 형식에 따른 분류

1. 0번지 명령어 : opcode로만 구성됨.

- 스택으로 모조리 연산 -> 후위연산식으로 되어 있어야 한다.

- stack machine

2. 1번지 명령어 : operand 한개 추가

- 누산기로 연산

ex) ADD B

3. 2번지 명령어 : operand 가 두 개.

- 가장 일반적이다. 연산결과가 주로 첫 operand에 저장되느라 첫번째 자료가 파괴되느라 프로그램 길이가 길어지는 단점.

4. 3번지 명령어 : operand 가 세 개.

- 원시 자료가 파괴되지 않아 프로그램 길이가 짧아지고, 주기억장치에 접근하는 횟수가 줄어드니까 속도도 빠르다.

- 산술 shift에 따른 결과

1. 왼쪽 shift로 인해 잃어버리는 비트가 1이라면 = overflow = 범람

2. 왼쪽 shift로 인해 잃어버리는 비트가 1이라면 = truncation = 절단

- 스키마 : 데이터의 구조, 표현 방법, 데이터들 간의 관계를 형식 언어로 정리한 구조

- cardinality : 수학에선 집합의 원소 수를 뜻함. db에선 릴레이션(테이블)의 tuple(row, record, 행)의 수.

- 트리의 degree(차수) : max(각 노드들에 연결된 간선의 수)

- 개체 무결성 : relation엔 기본 키가 존재해야 하고, 기본 키를 구성하는 attribute는 고유해야 하며, null 일 수 없다.

- key : relation에서 튜플들을 찾거나 정렬할 때 기준이 되는 attribute 들의 집합

- super key : 키를 통해 tuple들을 고유하게 구분할 수 있다(유일성)

- candidate key : super key 중에 더 이상 보유 원소들을 줄일 수 없음(= irreducible = 최소성)

- primary key : (= 기본 키), 후보 키들 가운데 설계자가 설정한 tuple 식별자.

- 대체 키 : surrogate key, alternate key, 기본 키가 되지 못한 후보 키들.

- foreign key : (= 외래 키), 다른 릴레이션을 참조하기 위해 설정된 키

- 참조 무결성 : 참조 관계에 있는 릴레이션들의 데이터가 일관되게 유지되어야 한다.

- 뷰 : DB 사용자는 실제 데이터로 부터 내가 원하는 것만 골라서 보게 가상의 논리적 구조를 만들 수 있다. 

- SQL에선 이 뷰로 수정도 되고 검색도 되는데, 마치 참조자 마냥 원래 물리 데이터도 영향을 받는다.

- 다만 뷰의 정의를 수정하는 것만 안되게 막고 있다. 구현하기가 헬이라 그랬나보다.

- locking : 하나의 트랜젝션이 데이터를 접근하고 있는 동안, 다른 트렌젝션이 이 데이터에 접근할 수 없게 하는 병행 제어 기법. 로킹 단위가 커질 수록 제

어기법은 간단해지고(오버헤드가 감소하고), 대신 데이터베이스의 공유도는 감소한다.

- anomaly : 릴레이션의 속성들의 중복과 종속관계로 유발되는 문제들, 현상들

- 삭제 이상, 삽입 이상, 갱신 이상

- 정규화 : 이상현상들을 방지하기 위한 과정, ERD 내에서 중복요소들을 찾아 제거해나간다.

- 1차 정규화 = 1NF : tuple마다 attribute에 해당하는 데이터가 한 개만 있어야함 = atomic value를 가져야 함.

- 함수 종속 : 속성 집합 X, Y에 대해 X의 값에 Y의 값이 하나씩만 연관되어 있으면 Y는 X에 함수 종속이다.( X->Y) 예를 들어 속성이 (배기량, 차량) 일 때, (차량 -> 배기량) 이다. 하지만 (배기량 -> 차량)은 아니다. 같은 배기량을 가진 차량이 있을 수 있다.

- 완전 함수 종속 : X->Y일 때, Y가 X의 진부분집합에는 함수 종속이지 않을 때, Y는 X에 대해 완전 함수 종속이다.

- 부분 함수 종속 : X->Y일 때 Y가 X의 진부분집합에 함수 종속일 때

-2차 정규화 = 2NF : 부분 함수 종속성을 제거한다. 1NF 테이블의 후보 키 K와 K에 속하지 않는 속성 A에 대해, A가 K전체에 종속적이라면 2NF다.

-3차 정규화 = 3NF : 추이 종속성을 제거한다. X->Y 이고 Y->Z 에 의해 X->Z 인 경우가 없게 된다. 2NF 테이블의 모든 속성이 기본키에만 종속이다.

- 병행 제어 = concurrency control : 다중 프로그램에서 여러 트랜젝이 병행수행될 때, 데이터베이스의 일관성이 파괴되지 않게 상호작용을 제어하는 것

- 관계 대수 / 관계 해석 : 결과는 같지만, 전자는 절차적 / 후자는 비절차적, 전자 sql문(union, select, ...) 후자 { t | EMPLOYEE(t) and t.SALARY>5000 }

- 관계 해석은 Predicate Calculus(1차 논리)에 기반하고 있다.

- NOSQL = not only sql : SQL을 유연하게 만들자, 비관계형 DB

- 비정형 데이터도 테이블에 넣을 수 있게 유연한 데이터 모델을 제공한다.

- 성능상의 이점을 위해 단순 검색 등이 최적화되어있음. 불가피하게 일관성에선 타협하였다.

- 회복 : 트랜젝션 중에 장애 발생으로 db를 이전의 상태로 롤백하는 작업.

1. 연기 갱신 기법 = deffered update : 트랜젝션이 정상적으로 완료될 때 까지 db의 갱신을 미룬다. 대신 중간과정을 log에 기록

2. 즉각 갱신 기법 = immediate update : 트랜젝션중 db를 다 갱신해버리고 log에 기록한다. 회복을 log를 활용해 수행.

3. 검사점 기법 = check point : 중간중간 세이브를 해두었다가, 전체과정을 회복할 필요가 없이 세이브포인트를 활용

4. 그림자 페이지 대체 기법 = shadow paging

- 해싱 방법

1. 제산법 : MOD연산하고 주소로 사용

2. 폴딩법 : 키를 몇가지 부분으로 나눠 수학적 지랄한다음 주소로 사용

3. 기수변환법 : 진법을 변환시켜 새로운 주소로 변환해서 사용

4. 숫자 분석법 : 키들의 분포를 보고 영리하게 선택해서 새로운 주소로 변환해서 사용

- OLAP = on-line analytical processing : 온라인 분석 처리, 사용자가 동일 데이터를 여러 기준의 다양한 방식으로 접근하면서 다차원 분석을 하게 해준다.

- roll-up : 요약해준다

- drill-down : 세부적으로 분석해준다

- slicing = dicing : 잘라서 보여준다

- pivoting : 행과 열을 바꿔서 보여준다

다음에 길게 길게 설명하기로 하고,

문제 풀면서 느낌 감상만 먼저 옮기려고 합니당.

학교 수업시간에 배운 두번의 DFS로 SCC들을 구하는 방법과,

한 번의 dfs로 SCC들을 구하는 방법을 비교해 봤는데, 확실히 후자의 방법이 두 배 정도 더 빨랐다.

두 번의 dfs는 간단해서 짜는데 빠르게 짤 수 있는 반면, 한 번의 dfs는 이해한지 얼마 안돼서 그런가 코드가 길긴하다.

간단히 설명하면,

전자의 방법은 먼저 dfs를 돌긴하는데 finish되는 순으로 stack에 push 해두었다가,

pop하면서 역간선 그래프에 대해 dfs를 다시 돌면서 scc로 묶는 방법이다. (a->b로 갈 수 있으면, b->a로도 갈 수 있어야 한다.)

후자의 방법은 dfs 트리를 활용하는데, 방문하는 순서대로 노드들에게 번호를 매기면서 stack에 push하고, 지금의 dfs가 어떤 노드로부터 

시작되었는지를 활용하여 scc로 묶는 방법이다. 후자는 확실히 코드를 봐야 이해가 빠르다.

Strongly Connected Component

https://www.acmicpc.net/problem/2150

1. 2150 은 기본 문제로 scc들을 구하는 문제였다.

도미노

https://www.acmicpc.net/problem/4196

2. 4196은 scc를 구한 다음에 더 풀어야 되는 문제였다.

scc내에선 하나만 무너지면 다른 노드들도 다 넘어진다. 따라서 그래프를 scc들 끼리의 그래프로 재편집한다음에,

scc들의 indegree를 계산하고, indegree가 0인 scc들의 갯수를 세면 풀 수 있다.

ATM

https://www.acmicpc.net/problem/4013

3. 4013은 scc를 구하고 indegree를 구하고 더 풀어야 되는 문제였다.

scc를 구할 때 각 scc들의 value 합을 구해놓고 scc들 끼리의 그래프로 재편집해야 한다.

이후 indegree를 계산한 다음에, 위상정렬로 출발점이 속한 scc에서 레스토랑이 있는 scc까지의 최대 value 합을 각각 구하면 된다.