- SDLC = software development life cycle = 소프트웨어 개발 수명 주기 : 시스템을 개발하는 과정을 뜻한다.

1. 폭포수 모델 

- 단계적, 체계적, 순차적으로 개발하기. 검토하고 검증하고 테스트가 완료되어야 다음 단계를 수행할 수 있다.

2. 프로토타입 모델

- 견본을 만들어 최종 결과를 예측하는 방법.

- 요구 수집 -> 빠른 설계 -> 프로토타입 제출 -> 평가 -> 조정 -> 구현

3. 나선형 모델

- 나선을 돌 듯 여러 번의 개발 과정을 거쳐 점진적으로 완벽한 최종 소프트웨어를 개발하는 것

- 따라서 개발 중의 위험을 최대한으로 관리하고 최소화시키는데 목적을 둔다.

- 가장 현실적이고 대구모 시스템에 적합하지만, 위험이 발견되지 않으면 문제가 발생할 수 있다.

- 계획 -> 위험 분석 -> 개발 -> 평가

- HIPO = hierarchical input process output : 인풋-프로세스-아웃풋 으로 이뤄진 모듈을 계층적으로 나타낸 도표, 시스템을 분석, 설계, 문서화함

+ 가시적 도표  = 도식목차 = visual table of contents : 시스템의 전반적인 흐름을 나타내는 트리형태의 도표

+ 총체적 도표 = 개요 도표 = overview diagram : 프로그램의 기능을 기술, 입력-프로세스-아웃풋의 과정이 한눈에 들어온다

+ 세부적 도표 = 상세 도표 = detail diagram : 총체적 도표를 엄청 자세하게 기술했다.

- 하향식 소프트웨어 개발 = top-down

- 큰 그림먼저 그리기. 블랙박스들로 구성해놓고, 나중에 상세하게 설계한다. 아래 모듈을 대신 할 시험용 모듈(=stub)이 필요하다.

- 상향식 소프트웨어 개발 = bottom-up

- 작은 그림들 더해나가기. 기존 서비스들을 통합해서 써먹는데 사용될법한 기법.

- stub은 필요없다. 낮은 수준의 모듈들을 합쳐(=cluster) 제어 프로그램(=driver)으로 테스트 하면서 진행한다.

- 소프트웨어 테스트 전략

- 검사 기법

1. 화이트박스 : 기초 경로 검사, 루프 검사

2. 블랙박스 

2-1) 동치분할 검사 : 입력 데이터를 맞게 들어오는거 반, 틀리게 들어오는거 섞어서 구성하고 테스트하기

2-2) 경계값 분석 : 정입력과 오입력의 경계선 근처의 데이터들이 오류 발생 가능성이 가장 높으므로 경계값들로 테스트하기

2-3) 원인 효과 그래프 검사 : 입력 데이터들 간의 관계에서 어떤 결과가 나오는지를 자알 분석한다.

2-4) 오류 예측 검사 : 감으로 이러면 터지지 않을까? 테스트 하기.

2-5) 비교 검사 : 여러 버전의 프로그램들에 동일한 입력을 넣어 같은 결과가 나오는지 비교한다.

- 검사 과정

1. 단위 검사 = 코드 검사 = 화이트박스 

2. 통합 검사 : 단위 검사를 마친 모듈들을 합치는 과정. 모듈간에 인터페이스를 검사한다.

- 하향식 : 아래 모듈은 아직 검사안했기 때문에, 아래 모듈들을 대체할 임시모듈 (그루터기 = 스터브 = stub)이 필요하다.

- 상향식 : 하위 모듈부터 합치면서 검사한다.

3. 검증 검사 = 요구사항 검사 = 정당성 검사 : 의뢰인의 요구사항과 소프트웨어가 일치하는지 검사한다.

4. 시스템 검사 : 프로그램 외의 다른 부가요소들을 마지막으로 검사.

- 객체지향 분석

1. 럼바우의 소프트웨어 분석 기법 = OMT = object modeling technique : 소프트웨어의 구성 요소를 그래픽적으로 모델링하기.

1-1. 객체 모델링 : 분석에 사용할 객체를 정의하고, 객체간의 관계를 정함

1-2. 동적 모델링 : 상태도, 전이도 그리기

1-3. 기능 모델링 : 프로세스들 사이에서 자료들이 어떻게 처리되는지 과정을 표현, 자료 흐름도(DFD)

2. Booch 기법

- 미시적 프개발 프로세스와 거시적 프로세스를 모두 사용하는 분석 방식

3. Jacobson

- use case를 강조한대

4. Coad & Yourdon

- E-R 다이어그램 사용

- 소프트웨어 비용 산정 기법

1. LOC = line of code : 각 기능의 원시 코드 라인수로 비용을 산정한다 예측치 = ( 낙관치 + 4*기대치 + 비관치 ) / 6

- 노력 = 개빌 기간 * 투입인원

- 비용 = 노력 * 비용(월급)

- 개발 기간 = 노력 / 투입인원

- 생산성 = LOC / 노력 = 개발한 라인수 / ( 개발자 수 * 기간 )

2. COCOMO = constructive cost model

2-1) 프로젝트 분류 유형 = mode

- 조직형 = organic : 기관 내부용 소중규모의 소프트웨어, 사무 처리용, 업무용, 과학 기술 계산용

- 내장형 = embeded : 초대형 규모, 미사일 유도 시스템, 실시간 처리 시스템

- 반분리형 = semi-detached : 조직형과 내장형의 가운데, 컴파일러 인터프리터같은 유틸리티 개발용

2-2) 비용 산정 유형

- 기본형 : 소프트웨어 크기와, 프로젝트 유형으로만 비용을 산정

- 중간형 : 기본 유형에, 제품 특성, 컴퓨터 특성, 개발자 특성등의 요인이 추가

- 발전형 : 중간형을 보완해서, 개발 공정별로 자세하고 정확하게 노력을 산출하여 비용을 산정함.

3. putnam 모델

- 전 생명 주기 동안 노력의 분포를 상정하는 모델

- 이 모델로 개발된 자동화 추정 도구 = SLIM

4. 기능 점수( = FP )로 비용 추산하기

- 이 모델로 개발된 자동화 추정 도구 = ESTIMAC

- 프로젝트 일정 계획과 관련해서

- 브룩스의 법칙 : 프로젝트 중간에 새로운 인력 투입시 부작용으로 일정이 오히려 지연된다는 카더라

- 일정 계획 방법

- PERT / CPM = project evalution & review technique : 그래프로 일정 관리

- CPM network = critical path method : 노드는 작업이고, 간선은 작업간의 의존관계를 나타낸다.

- 가장 긴 경로가 크리티컬한 경로다. 이 경로상의 어떤 노드라도 늦어지면 전체 프로젝트가 늦어지므로 관리자의 관심이 필요하다.

- 유지 보수

- 유지 보수의 종류

1. 완전한 보수 : 현재 수행중인 기능 수정, 새로운 기능 추가, 전반적인 기능 개선

2. 적응적 보수 : 하드웨어나 운영체제 변경에 따른 환경변화에 적응하는 개선

3. 예방적 보수 : 미리 겁먹고 보수하기. 미래를 예방하는 수단을 강구한다.

4. 수정적 보수 = corrective : 프로그램 오류를 수정한다. 검사 단계에서 살아남은 잠재적인 오류들을 전부 수정한다.

- 바람직한 설계의 척도

- 결합도 = coupling : 모듈간에 상호 의존하는 정도

1. data coupling : 모듈간에 인터페이스가 자료 요소(매개 변수, 인수)로만 구성될 때 <

2. stamp coupling : 모듈간에 인터페이스가 배열, 레코드등의 자료구조로 구성될 때 <

3. control coupling : 어떤 모듈이 다른 모듈의 내부적 흐름을 제어하는 경우(switch, tag, flag) <

4. external coupling : 한 모듈이 외부선언한 데이터를 다른 모듈에서 참조할 때 <

5. common coupling : 공유되는 공통 데이터 영역을 여러 모듈들이 접근 <

6. content coupling : 한 모듈이 다른 모듈의 내부 기능과 내부 자료를 직접 접근할 수 있을 때

- 응집도 = cohension : 한 모듈 안의 요소들이 서로 관련되어 있는 정도. 독립적인 모듈은 응집도가 강하다.

1. 우연적 = coincidential : 모두 상관없을 정도

2. 논리적 = logical : 유사한 성격이거나 특정 형태로만 하나의 모듈이 생성될 정도

3. 시간적 = temporal : 특정 시간에 처리되는 기능들이 하나의 모듈이 될 때

4. 절차적 = procedural : 모듈의 구성요소들이 모듈의 기능들을 순차적으로 수행할 때

5. 통신적 = communicational : 동일한 입력과 출력을 사용하지만 다른 기능을 수행하는 요소들로 모듈이 이루어짐

6. 순차적 = sequential : 모듈 내에서 한 출력이 다음엔 입력으로 쓰일 때

7. 기능적 = functional : 모듈 내 모든 기능 요소들이 단일 문제와 연관되어 수행할 정도!

- ERM = entity - relation modeling = 개체 관계 모델링 : 개체들과 개체들이 어떻게 연관됐는지를 나타내는 관계로 모델링

- ER diagram : 개체-관계 다이어그램, 모델링의 결과.

- NS chart : 플로우 차트와 같은 일을 한다.

- 화살표가 없다. 입구와 출구가 하나씩이다. (순차, 반복, 선택)만으로 모든 논리를 표현한다. 네모박스로 다 표현한다!

- FP = function point = 기능점수 : 소프트웨어의 기능 갯수를 기준으로 소프트웨어의 규모를 측정하는 방법. 내부평가 + 외부평가

- 자료 흐름도 = 자료 흐름 그래프 = 버블 차트 = DFD

-  요구사항을 분석할 때 자료의 흐름 과 변화, 기능을 도형으로 기술하는 방법

- 자료 사전 = data dictionary = DD : 자료 흐름도의 자료를 설명하는 것.

= : is composed of

[ ] :  choose only one of

|   : or

+ : and

{ }: iteration of (밑에 n은 n번 이상 반복, 위에 n은 최대 n번 반복, 밑에 m 위에 n은 m에서 n번 반복

(): optional

**:comment

- CASE = computer aided software engineering : SDLC를 도와주는 컴퓨터 자원, 쏘공의 여러 작업들을 컴퓨터로 자동화하였다.

- 정보저장소 : 처음에는 사람이 다 관리했지만, 요즘엔 디비로 정보저장소를 만들고 관리할 수 있다.

- FTR = formal technical review = 정형 기술검토 : 무슨 위원회처럼 소프트웨어를 평가하는 자리. 참가인원이 제한되고 제품검토에 집중한다.

- CORBA = common object request broker architecture = 공통 객체 요구 매개자 구조

- 프로그램내 객체 간의 메소드 호출에 대한 지침

- 소프트웨어 위험의 특성 = 불확실성, 손실가능

- 프로세스 스케쥴링 : 다중 프로그래밍(multi programming)을 가능케 한다. cpu작업과 입출력 작업을 병행함으로써 이루어진다.

- preemptive : 선점이라는 번역때문에 헷갈리는데, 방해의 의미가 더 크다.

- 비선점형 스케줄링 : 할당받은 자원은 작업이 종료/중단될 때 까지 빼앗기지 않는다.

문맥 교환에 의한 오버헤드가 적은 대신 긴 대기시간으로 처리율은 떨어질 수 있다.

- 문맥 교환 = context switch : cpu가 다른 프로세스를 작업하기 위해 이전 프로세스의 상태를 저장하고 새로운 프로세스의 상태를 적재하는 과정

- 프로세스 제어 블록 = process control block = PCB = task control block = TCB : 프로세스를 표현하는 자료구조

1) pid 2) 프로세스 상태 3) pc 4) 레지스터들 5) 스케줄링 정보 6) 메모리 정보 7) 입출력 정보 8) 기타

일반 사용자가 접근하지 못하는 커널 메모리 영역에 저장된다. 일부 운영체제는 커널 스택에 저장.

- FCFS = first come, first served : 대기 상태 큐에 도착한 순으로 자원 할당. 기아 상태(starvation)를 유발할 수 있다.

- SJF = shortest job first : burst time이 가장 짧은 순으로 자원 할당. 평균 대기 시간을 최소화하는게 목표. 기아 상태를 유발할 수 있다.

- HRN = highest response-ratio next : 우선순위 함수값((대기시간 + burst) / burst)이 가장 높은 순으로 자원 할당. 대기시간이 반영된다.

- 선점형 스케줄링 : 다른 프로세스가 실행중의 프로세스의 자원을 뺏을 수 있다. 시분할 시스템에 적합하다. 즉 응답시간이 빠르다.

- RR = round robin : 시간단위(time quantum)마다 자원을 할당한다. 문맥교환이 잦아지는 대신 응답시간이 짧다.

- SRTF = shortst remaining time first : 최단 잔류 시간 우선. SJF를 선점형으로 바꾼 것.

- 다단계 큐 = multilevel queue : 대기 상태 큐를 우선순위가 부여된 큐들로 나눠서 처리

- 다단계 피드백 큐 : 다단계 큐에선 영구적으로 할당되지만, 프로세스마다 timeout을 추가해 큐들을 옮겨다닐 수 있게 했다.

- 임계 구역 문제 = critical section problem : 프로세스들이 동시에 수행될 수 있기에 발생하는 문제.

- 공유 하는 데이터에 동시적으로 접근하면( = race condition ) 데이터의 일관성을 망칠 수 있기 때문에 임계 구역으로 관리해야 한다.

- 이를 해결하기 위해 = 동기화

1. 특정 프로세스가 공유 자원을 사용하고 있으면 다른 프로세스가 접근하지 못하는 상호배제가 이뤄져야 한다.

2. 임계 구역을 아무도 수행하지 않고 있고, 여러 프로세스가 대기 중이라면, 이들 중의 선택은 무한히 연기될 수 없다.

3. 대기시간에 경계가 존재해야 한다.

1. 피터슨의 해결책 - 두 개의 프로세스에 대해

- flag는 진입할 준비에 대해, turn은 순번을 의미한다. 먼저 준비하고 양보하고 busy waiting한다.

- 탈출하려면 j가 임계구역을 다 끝내고 flag를 내리던지, 다시 돌아와서 turn을 넘기던지 둘 중 하나는 이뤄져야 한다. 

2. 데커 알고리즘 = Dekker : 비슷함 ㅎㅎ;

3. 세마포어 : P연산(try)과 V연산(증가)의 원자성이 확보되었으면, 진입전에 p연산을 수행하고, 나오면서 v연산을 수행해 동기화 할 수 있다.

4. 뮤텍스

- acquire()로 키를 얻고 진입한뒤, release()로 키를 반납한다.

4. 모니터

- 세마포어 문법실수를 막기 위해 세마포어 기능을 제공하는 추상화가 이루어진 객체.

- 한 프로세스만 모니터에 진입할 수 있고, 진입부를 반드시 호출해야 하며, 내부에서만 작업이 이루어진다.

- 운영체제 운용 기법

1. 일괄처리 시스템 = batch processing

- 일정기간동안 데이터를 모아서 한꺼번에 처리.

- 효율적인 사용이 가능한데, 사용자가 느끼기엔 응답 시간이 늦지만, cpu 입장에서 진득하니 모든 자원을 독점하기 때문이다.

- 초창기 모델로, 급여 계산, 연말 결산 등의 업무에 사용했다캄.

2. 다중 프로그래밍 시스템 = multi-programming

- 하나의 cpu와 하나의 주기억장치로 여러개의 프로그램을 동시에 처리

3. 시분할 시스템 = time sharing system

- 컴퓨터 자원을 사용자들이 시간적으로 분할하여 사용할 수 있다. 즉 대화식 인터페이스가 제공될 수 있다.

4. 다중 처리 시스템 = multi-processing

- 여러 개의 cpu와 하나의 주기억장치로 여러개의 프로그램을 동시에 처리

- 하나의 cpu가 고장나도 다른 cpu로 처리할 수 있으므로 신뢰성과 안정성이 높다.

- 종류

1. 주/종 처리기 : 주프로세서가 입출력과 운영체제를 운영하고, 종프로세서가 연산만 담당.

2. 분리 실행 : 주/종 처리기의 비대칭성을 해결하기 위해, 프로세서마다 운영체제를 각각 돌린다.

3. 대칭 처리기 : 여러 프로세서가 하나의 운영체제를 공유함

5. 실시간 처리 시스템 = real-time processing

- 자원이 한정된 상황에서 응답을 제한시간 내에 리턴해줘야 함

5-1) 경성 실시간 시스템 = hard : 조건을 만족시키지 못하면 치명적인 시스템, 철도체어, 원전제어

5-2) 연성 실시간 시스템 = soft : 만족시키지 못해도 치명상은 없는 시스템, 동영상 플레이어

6. 다중 모드 처리 시스템 = multi-mode processing

- 여러 모드를 지원한대

7. 분산 / 병렬 처리 시스템

- 네트워크로 연결 / 슈퍼컴퓨터 

- 분산 시스템의 위상구조

1) 성형 연결 = star connected : 각 노드들이 중앙컴퓨터를 경유해야 함

2) 환형 연결 = ring connected : 각 노드들은 서로 이웃을 두개 가짐

3) 완전 연결 = fully connected : 모든 노드 쌍들을 다이렉트로 연결

4) 계층 연결 = hierarchy connected : 구조가 트리. 루트 노드 + 자식 노드

- 프로세스 모델에 따른 분류

1) 서버/클라이언트 모델

2) 프로세서 풀 모델

3) 혼합모델

- 시스템 소프트웨어

1. 매크로 프로세서 : 원시 프로그램에 정의된 매크로를 인식 -> 정의 기억(저장) -> 매크로 호출 인식 -> 확장 및 치환 -> 어셈블러에 전달

- 매크로 = 개방 서브루틴 = opened sub-routine

2. 링커

- 목적 프로그램과 라이브러리를 연결하여 실행 가능한 모듈로 만들어 줌

- 목적 프로그램은 언어 번역 프로그램이 만든다.

- 언어 번역 프로그램 = 어셈플러, 컴파일러, 인터프리터 : 고급 언어로 작성된 원시 프로그램을 목적 프로그램으로 번역

3. 로더 : 프로그램을 주기억장치에 적재함

- 기능

1. 할당 = allocating : 실행 프로그램을 위한 공간을 확보한다.

2. 연결 = linking : 프로그램이 부프로그램을 호출할 경우, 부프로그램의 시작주소를 연결해준다.

- 링커의 기능과 똑같다. 즉 링커는 연결 기능만 수행하는 로더다.

3. 재배치 = relocating : 목적 프로그램을 실제 주기억 장치에 맞게 재배치한다. 상대주소를 절대주소로 바꿔준다.

4. 적재 = loading : 실제로 프로그램을 할당된 기억공간으로 옮김.

- 종류

1. 컴파일 즉시 로더 = comile and go : 번역기가 로더질까지 한다. 따라서 실행할 때 마다 번역도 다시해야한다.

2. 절대 로더 = absolute : 상대주소질을 할 줄 모르는 아주 간단한 로더.

3. 상대 로더 = relative = direct linking : 4가지 기능을 다 수행하는 일반적인 로더

- 자원 보호 기법 : 권한 부여의 방법

1) 접근 제어 행렬 = access control matrix : 행이 유저, 열이 파일

2) 접근 제어 리스트 = access control list : 파일마다 <영역(유저, 프로세스), 권한내용>의 리스트를 갖게 됨

3) 권한(자격) 리스트 = capability list : 반대로 영역(유저, 프로세스) 마다 <파일, 권한내용>의 리스트를 갖게 됨 

- 프로세서 연결 방법

1) 시분할 공유 버스 : 각종 장치들을 단일 경로(버스) 로 연결함, 경제적이며 나중에 추가가 쉽지만 한 시점에 한 가지 전송만 가능

2) 크로스바 교환 행렬 : 공유 버스 방법에서 버스를 장치 수만 큼 늘렸다. 각 장치마다 다른 버스를 쓸 수 있지만, 확장과 연결이 복잡해졌다.

3) 하이퍼 큐브 : 1차원(선분, 2개, 서로 이웃) 2차원(사각형, 4개, 서로 2개가 이웃) 3차원(육면쳬, 8개, 서로 3개가 이웃), ...

4) 다중포트 메모리 : 1과 2를 혼합한 형태, 프로세서와 장치 쌍으로 각각 버스를 가짐

- 순차 파일 = sequential file : 입력되는 레코드들을 논리적 순서에따라 연속된 물리적 공간에 저장

 -> 메모리의 효율적인 사용, 기록은 빠르지만, 데이터 추가, 삭제, 검색은 느리다. (링크드 리스트를 생각하면 될 듯)

- 색인 순차 파일 = indexed sequential file : 레코드들의 키 값들을 정렬하여 논리적 순서대로 기록하고, 키 항목을 모은 색인을 구성하는 방법

= ISAM = indexed sequential access method -> 색인에서 검색한 이후 포인터로 참조할 수 있다., 랜덤 처리와 순차 처리가 모두 가능함.

1) 기본 구역 = prime area : 실제 레코드를 저장하는 구역

2) 색인 구역 = index area : 색인을 저장하는 구역

3) 오버플로 구역 = overflow area : 기본 구역이 모자랄 상황을 대비한 예비 구역

- 직접 파일 = 랜덤 파일 = directed access method = DAM : 레코드를 임의의 저장공간에 기록하는 방법

- 레코드엔 키가 할당되고, 해시(키)로 주소를 알 수 있다. 기록순서에 대한 제약같은건 없어졌지만, 해시의 단점(충돌을 고려해야함, 변환시간)이 존재

- 디렉토리 : 파일에 대한 여러 정보를 가지고 있는 파일, 캐비넷

1. 1단계 디렉토리 : 모든 파일이 한 폴더내에서 관리된다. 따라서 다른 유저라도 같은 이름의 파일 사용 불가.

2. 2단계 디렉토리 : 사용자별로 1단계 디렉토리를 가진다. 다른 유저라면 같은 이름의 파일 사용 가능. MFD(master file dir) - UFD(user file dir)

3. 트리 디렉토리 : 윈도우즈와 유닉스에서 쓰는 트리형 구조, 루트와 서브

4. 비순환 그래프 디렉토리 : 트리와 비스무리. 다만 디렉토리들이 한 파일을 공유할 수 있게 되었다. 공동 사용이 가능해짐.

5. 일반 그래프 디렉토리 : 비순환은 비순환 보장이 문제다. 그래서 파일에 대한 링크를 허용했다.

- 다중 링 파일 : 레코드들을 그룹화하고 포인터로 연결해 표현

- 커널 : 하드웨어 할당, 프로세스 제어(=태스크 매니징), 메모리 제어, 시스템 콜 응답, 파일 시스템 관리

- 시스템 콜 : 사용자가 커널에 접근하기 위한 인터페이스, 보통 api로 제공된다.

- 유닉스

- 파일 시스템

1) 부트 블록 : bootstrap시 사용함. 부트로더 등

2) 슈퍼 블록 : 파일 시스템의 정보

3) inode 블록 : 파일(디렉토리 포함)의 정보

- 메타 데이터

- 파일 모드, 링크 갯수, 소유자 id, 그룹 id, 파일 크기, 마지막 접근 시간, 마지막 수정 시간, 생성일

- 데이터 블록 포인터들

4) 데이터 블록 : 실제 파일 내용

- 교착 상태 = deadlock : 한 자원에 대해 두 프로세스가 싸우느라 둘 다 대기 상태에서 헤어나오지 못하는 상황

- ( safe ) / ( unsafe ( deadlock ) )

- 조건

1) 상호 배제 조건 = mutual exclusive : 한 자원은 동시에 한 프로세스만 쓸 수 있다.

2) 점유와 대기 = hold and wait : 싸우는 프로세스중 한 놈은 갖고 있으면서 추가로 원하는 파렴치한 놈이어야 한다.

3) 비선점 = no preemption : 중간에 강탈은 없다.

4) 순환 대기 = circular wait : p0은 p1껄 대기하고, p1은 p2껄 대기하고, ... , 화살표로 그렸을때 사이클이 생김

- 해결 방법

1) 예방 : 조건들을 다 반대로 -> 공유 자원, 실행 전에 모두 할당해버리기, 선점 허용, 자원의 번호를 메기고 번호 순대로 요구하게 하기

- 따라서 자원 소비가 크다.

2) 회피 : 은행원 알고리즘 : 할당한 이후에도 안정상태인지 미리 검사해서 회피한다. 맞으면 할당해주고, 아니면 자원이 돌아올 때 까지 대기한다.

3) 탐지 : 현재 교착상태에 빠졌는지 그래프적으로다가 탐지하여 해결할 수 있다.

4) 회복 : 교착 상태의 프로세스들을 중단시키거나, 자원들을 선점하는 방법(빼앗어서 다른애 한테 줘버리기)

- 기억장치 관리 전략

- 반입에 대해 = fetch : 보조기억장치에 저장중인 데이터 / 프로그램을 언제 주기억장치로 반입할 것인지를 결정해야 한다.

1. 요구 반입 : 요구당할 때만 보조기억장치에서 반입한다.

2. 예상 반입 : 언제 요구당할 지 예측하여 미리 반입한다.

- 배치에 대해 = placement : 반입되는 데이터 / 프로그램을 주기억장치의 어디에 반입할 것인지를 결정해야 한다.

1. 최초 적합 = first fit : 맞는 영역중에 가장 첫번째 영역에 배치

2. 최적 적합 = best fit : 맞는 영역중에 가장 단편화가 적게 이뤄지는 영역에 배치

3. 최악 적합 = worst fit : 맞는 영역중에 가장 단편화가 크게 이뤄지는 영역에 배치

- 단편화  = fragmentation: 프로그램에 주기억장치를 할당하고 반납받는 과정에서, 낭비되는 빈 공간이 생기는 현상

1. 내부 단편화 : 프로그램이 쓸 영역보다 더 큰 영역이 할당되어서 낭비되는 공간

2. 외부 단편화 : 메모리 공간이 영역으로 나눠지다보면 내부 단편화가 생기고, 이를 다합친 공간 크기가 충분한데도 할당못하는 상황

- 단편화 해결 방법

1. 통합하기 : 인접한 단편화된 공간들을 통합해준다.

2. 압축하기 : 재배치를 통해 공간들을 압축해서 연속된 빈공간을 만들어낸다.

3. 페이징

4. 세그멘테이션

5. 메모리 풀 : 미리 저수지를 만들어 대비하고, 할당 요청이 들어올때마다 제공해준다.

- 필요한 만큼만 제공해주기 때문에 내부단편화 X, 제공이 풀 내에서만 이뤄지기 때문에 외부단편화 X

- 가상 기억 장치 = virtual memory : 주기억장치와 보조기억장치의 효율저인 사용을 위해 논리적으로 통합해 가상의 기억장치로 운용한다.

- 이제 프로그램에는 가상의 주소 = 논리주소 가 할당된다.

- 논리주소를 물리주소에 매핑할 전략이 필요하고, 이를 memory management unit = MMU가 수행한다.

1. 페이징 기법 : 가상주소공간과 물리주소공간을 같은 크기로 나누고(페이지 / 프레임), 프로그램에겐 페이지를 할당해준다.

- 이제 페이지별로 관리되므로 외부단편화는 없지만, 페이지 전체를 쓰지 않는 경우 꼴랑 mod 페이지크기의 내부 단편화가 발생.

- 쓰레싱 = Thrashing : 다중 프로그래밍의 정도가 너무 높아져서 페이지 교체가 빈번해지고, cpu 사용율이 저하되는 현상

- 페이지 교체 알고리즘

1. OPT : 앞으로 가장 오래 사용되지 않을 놈

2. FIFO

3. LRU : 사용된지 가장 오래된 놈

4. LFU : 사용빈도가 가장 낮은 놈

5. NUR = not used reccently : 참조비트와 변형비트로 우선순위를 나눴다.

참조0 변형0 >> 참조0 변형1 >> 참조1 변형0 >> 참조1 변형1

6. SCR = second chance replacement : FIFO에 참조 비트 추가 -> 참조비트가 1이면 살려준다. 두번의 기회.

- 워킹 셋 = working set : 프로세스가 일정 기간 동안 자주 참조하는 페이지들 집합. 지역성을 이용한 것이다.

2. 세그멘테이션 기법 : 가상 메모리를 여러 다른 타입의 세그먼트들로 나누고 할당해주기

- 커널 영역 / 스택 영역(지역변수, 매개변수) / 힙 영역(동적할당) / 데이터영역(전역, static 변수) / 등등

- 영역내에서 딱 원한 크기만큼 할당해주기 때문에 내부단편화는 없다.

- 하지만 영역의 타입이 다르면 아무리 공간이 있어도 못주기 때문에 외부단편화는 발생함.

- 디스크 스케쥴링 : 디스크상에 데이터가 여러 곳에 나뉘어 저장되어 있을 때, 디스크 헤더가 움직이는 경로를 결정하는 기법

1. FCFS : 디스크 대기 큐에 들어온 수대로 이동하기. 공평성은 보장된다.

2. SSTF = shortest seek-time first : 현재 헤드의 위치에서 가장 가까운 거리의 트랙으로 이동

- 한 쪽에 편중되어 기아 현상이 발생할 수 있다. 일괄처리 시스템에 적합.

3. SCAN : 한 쪽으로 쭈욱 처리, 역방향으로 쭈욱 처리

4. C-SCAN : 바깥쪽에서 안쪽으로만 움직이면서 처리. 안쪽을 다 처리했으면 바깥으로 이동해서 재개. 기아발생 가능성.

5. N-step : 이동하기 시작했을 때 대기였던 애들만 처리하고, 나중에 도착한 애들은 나중에 반대 방향 처리과정에서 처리한다.

6. 에션바흐 기법 : C-SCAN과 같으나, 모든 실린더는 실린더에 요청이 없더라도 한바퀴 돌려야 한다. 대신 한바퀴로 모두 처리되게 재배열한다.

7. SLTF = shortest latency time first

- 회전을 줄이기 위해(회전시간의 최적화) 요청들을 섹터 위치에 따라 재정렬한다. 고정헤드장치용

- 섹터 큐잉이라고도 한다.

8. LOOK : SCAN과 같으나 요청이 없어도 끝까지 가는 SCAN과 다르게, LOOK은 없으면 바로 역방향으로 진행한다.

- 집적 회로

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

- 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 합을 각각 구하면 된다.

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

예산

아 parametric search 구나

라고는 빨리 알았지만, 이분탐색의 늪에 빠졌다가 뭔가 깨달음을 얻어서 여기에 옮기고자 한다.

k번째 숫자(https://www.acmicpc.net/problem/7469)를 parametric search로 풀고, 이 문제도 parametric search로 풀었다.

전자는

후자는

와 같다.

전자의 경우 mid가 성공했다면, 그 값을 포함한채 오른쪽을 좁혀야 하고,

(k번째 숫자를 찾아야 하므로, 더 큰 값은 의미가 없고, mid는 정답일 수 있으므로 버리면 안된다.)

후자의 경우 mid가 성공했으면, 그 값을 포함한채 왼쪽을 좁혀야 한다.

(최대 예산액을 찾아야 하므로, 작은 값은 의미가 없으며, mid는 정답일 수 있으므로 버리면 안된다.)

따라서 left와 right로 mid를 정하는 기준이 달라지는데, 이유를 말로 하긴 복잡하니까 그림으로 설명해보겠다.

mid 를 (left + right) / 2 로 하느냐, (left + right + 1) / 2로 하느냐의 차이점은, (성공했을 때 좌우를 변경하는 로직이 완벽했을 때)

결국엔 range가 2일 때 선명하게 드러나는데,

이번 예산 문제의 경우 mid 를 (left + right) / 2 로 하고 성공했을 경우, 

위 그림과 같이 무한루프에 빠지게 된다. 

반대로 k번째 숫자 문제는,

mid 를 (left + right + 1) / 2 로 한다면 성공했을 경우 무한루프에 빠지게 된다.

따라서 좌우를 버리는 로직을 완벽히 세워놨다면, 모든 parametric search를 위 두 케이스 중에 알맞은 케이스로 풀면 된다

라는게 내린 결론인데, 평소 while(left <= right)인 코드를 많이 봐왔던지라 차이점이 궁금해지긴 한다.

정파말고 사파식 공부를 하는 중이라 깊이가 모자른걸 요새 크게 통감하고 있다 ㅎㅎ;

풀 코드는 다음과 같다.

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

Blocks

n=1일때와 n=2일때 어떻게 전개되는지를 생각해보니 금방 풀 수 있었다.

따라서 n개일 때 경우의 수들에 행렬을 곱해 n=1일 때 경우의 수들을 구할 수 있다.

그래서 결국 4*4 행렬을 구하는 문제로 바뀌는데, n이 십억까지므로, 2^x승들의 행렬들을 미리 구하는 분할정복으로 풀 수 있다.

잘못 구현한 에라토스테네스의 체

첨엔 거지같이 풀어서 다른 분의 깔삼한 코드에 감명받아 여기에 옮기고자 한다.

cubelover님 감사합니다 ㅜㅜ

N = 12 인 경우에 답은 41인데, 과정을 표로 그려보면 다음과 같다.

아래서 부터 과정을 살펴보면,

1부터 12칸씩 뛰는데 한번도 나아갈 수 없다.

1부터 11칸씩 뛰는데 한번만 나아갈 수 있다.

...

횟수에 초점을 맞춰보면, 약수처럼 횟수가 늘어남을 알 수 있다. 따라서 횟수들의 종류 사이마다 i가 몇개씩 있는지만 알면,

n의 약수 갯수와 비스무리한 시간에 풀릴 것이다!

밑에서 부터 간격을 점프해보자.

1부터 시작하므로 최대 점프길이는 11이다. 11/12 = 0 이고, 1을 더하면 1회가 계산된다.

다음 i를 계산하는데는 직관적으로 계산된다. 11 / 1회 = 11이므로 다음 i는 11이다.

이는 1회 = 1번 점프 = 1부터 11까지 최대한 멀리 점프할수 있는 수 = 11 같이 이해하면 될 것 같다.

i = 11일 때 j는 두 번 등장한다. = 2회

다음 i = 11 / 2회 = 5이다.

즉 횟수가 달라지는 i들은(횟수들의 최대 i값들은) 12->11->5->3->2->1 순이다.

점프 횟수와 i들의 간격도 모두 구할 수 있으니 다음 처럼 간단한 코드로 풀이가 마무리된다.

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

정수 배열에 대해, 각 인덱스로 자신이 부분수열의 끝이고 길이가 L인 부분수열을 만들 수 있다.

각 부분수열의 최소값을 구해야 한다. (정수 배열의 길이 <= 오백만)

처음엔 세그먼트 트리 풀이만 생각이 났다. 근데 오백만이라 nlogn만 해도 오억이라 시간안에 풀 수 없었다.

복잡한 세그먼트 트리로만 헤매고 있었던 이유는,

각 부분수열의 최소값을 구할 때, 전 인덱스로 구한 최소값을 활용하는게 어려웠기 때문이다.

최소값이 부분수열의 맨 처음에 있었다면, 이번에 최소값을 구할 땐, 이전의 최소값은 구간에 포함이 안되고 새로 구해야 했다.

이러한 최악의 경우는 계속 일어날 수 있고(오름차순 정렬된 배열이라면), 좋은 풀이가 아니었다.

결국 이렇게 최악의 경우에서, 다음으로 작은 최소값을 알고 있으면 해결할 수 있다.

이 최소값도 다시 구간에서 벗어날 수 있으므로, 최소값들 후보를 죄다 갖고 있으면 된다!

이러한 자료구조를 고민하다가 덱을 쓰기로 했다.

덱의 맨 앞은 최소값을 가지고, 뒤로 갈수록 다음 최소값 후보들이 이어진다.

따라서 덱의 front에선 최소값들을 활용하고, 뒤로는 최소값 후보들을 집어넣으면 된다.

작업후에는 L-i ~ i 까지 최소값들 후보들이 덱에 들어가 있을 것이다.

뱀

뱀이 머리, 꼬리 이동과 몸에 박아버리는 경우를 어떻게 관리할지 아이디어만 있으면 후다닥 풀린다.

뱀처럼 덱을 만들어서(이중 연결 리스트) 머리에 머리좌표를 넣고, 꼬리에 꼬리좌표를 넣으면 상수시간에 이동이 구현된다.

사과를 먹고, 몸에 박는 경우는 평소처럼 맵에 표시만 하면 된다.

방향이 현재 방향 기준으로 왼쪽 오른쪽으로 주어지는 터라, 현재 방향을 저장하면서,

모듈러 연산을 통해 나침반 돌아가는 것마냥 관리해주면 편하다.

대부분의 뱅뱅 도는 문제들에선 통용되는 아이디어다.

문제가 조금 불친절한데, x초에 c로 방향전환하라는 얘기는 이동 다하고 다음 이동에 c가 영향을 준다는 얘기다.

x가 같은 입력이 여러번 주어질수 도 있어서 방향 전환 정보를 한 번 보고 말게 아니다.