인텔리 스토리

트리
-어떤 노드의 레벨이 i이면, 자식노드 레벨은 i+1임
-트리구조에서 간선수 e와 노드수 n 관계: e = n-1


이진트리
-2개이하의 자식노드를 갖는 트리. 즉 0~2개의 자식노드
-n개 노드의 이진트리: n+1개의 nil링크 
-깊이가 k인 2진트리 노드수: k~ 2의k승 -1개
-일반트리와 다르게 왼쪽 오른쪽 서브트리를 구분함

이진트리 종류
1) Full 포화 2진트리
-노드 수: 항상 2의 k승 -1개(k=높이)
-레벨 i(1<=i<=k)에서 가질수 있는 노드 수: 항상 2의 i-1승인 이진트리
-트리높이: 항상 log2(n+1)->루트노드 레벨이 1일때임
-모든 단말노드 높이는 같다
-단말노드 개수: 항상 2의 k-1개. 단말노드가 아닌 노드개수: 2의 k-1승 -1개
-단말노드를 제외한 모든 내부노드는 2개의 자식노드를 갖는다. k-1레벨까지의 모든 노드차수는 2임

2) Complete 완전 2진트리
-포화 이진트리의 단말노드들을 올느쪽으로부터 제거하여 얻어지는 트리.
-포화 full이진트리는 완전complete이진트리에 포함

-노드 개수: 2의 k-1승 <=n<=2의 k승 -10
-레벨 i(1<=i<=k)에서 가질수 있는 노드 수: 최대 2의 i-1승
-트리높이: 항상 log2(n+1) -루트노드 레벨이 1일때임
-모든 단말노드 레벨: k또는 k-1
-단말노드개수: 비단말노드 개수 or 비단말노드개수+1
-모든 노드의 차수: 높이가 k인 완전이진트리에서 루트노드 레벨이 1부터 시작시, k-2레벨까지의 모든 노드차수는 2임

3) Knuth 이진트리
-임의의 모든 노드 차수가 2이하인 트리(노드 차수가 0~2)

4) 엄밀한 이진트리
-모든 노드 차수: 0또는 2
-단말노드개수: 비단말노드개수 +1

5) Skewed 사향 이진트리
-한쪽 방향으로만 뻗은 트리


용어 정리
-노드: 트리를 구성하는 요소. 다른노드로 뻗어진 가지를 포함함
-차수: 파생된 직계 노드의 개수 
-트리의 차수: 각 노드 차수중 가장 큰 값
-레벨= 깊이. 루트의 레벨은 1이고, 아래로 내려갈수록 1씩 증가. 단, 루트레벨이 반드시 1은 아님. 0으로 지정 가능함
-높이: 근노드(트리의 시작정점)에서 가장 큰 레벨

데크 Deque데크 Deque
-스택+큐 운영방식
-리스트 양쪽 끝에서 노드의 삽입/삭제가 모두 가능한 선형 리스트. 즉 큐의 양쪽 끝에서 입출력이 가능하다
-left, right 두개의 포인터를 갖는다.

데크 표현방법
1)두개의 스택을 연결
2)단순 연결리스트, 이중연결리스트
3)1차원 배열

데크 종류
1)입력제한데크: SCROLL, 한쪽으로만 입력가능. 출력은 양쪽 다 가능
2)출력제한데크: SHELF, 한쪽으로만 출력가능. 입력은 양쪽 다 가능
-스택+큐 운영방식
-리스트 양쪽 끝에서 노드의 삽입/삭제가 모두 가능한 선형 리스트. 즉 큐의 양쪽 끝에서 입출력이 가능하다
-left, right 두개의 포인터를 갖는다.

데크 표현방법
1)두개의 스택을 연결
2)단순 연결리스트, 이중연결리스트
3)1차원 배열

데크 종류
1)입력제한데크: SCROLL, 한쪽으로만 입력가능. 출력은 양쪽 다 가능
2)출력제한데크: SHELF, 한쪽으로만 출력가능. 입력은 양쪽 다 가능

QUEUE 큐

-FRONT: 가장 먼저 출력될 노트 포인터. 실제 큐 위치보다 1이 작은 위치다.
초기조건: front = rear = 0
공백조건: front = rear
오버플로우조건: rear = n

이동 큐
-이동큐에서는 빈공간이 있어도 오버플로우가 발생할 수 있다. 
-이경우 데이터를 빈공간으로 이동시켜서 오버플로우가 나지 않도록 해야한다.
-이때 이동이 많이되므로 원형큐를 사용하는게 좋다

원형큐 
- queue가 full이 되는 경우, 데이터 이동이 많이 일어날 때의 이동큐의 과부하 문제를 해결한다. 
-오버플로우 발생시, 데이터를 이동하지 않고, 비어있는 맨 처음 노드에 데이터를 입력한다. 
->하나의 빈공간은 아무위치나 상관이 없다. 즉 0번지에도 데이터를 입력할 수 있다. 
-front = rear: 큐가 비어있는 경우 = 가득 찬 경우. 즉 오버플로우, 언더플로우 구분이 불가능함. 
->구분방법: 큐의 최대원소스를 maxsize -1 로 설정하면 된다. 그러면 초기값은 front=rear=0이다. 

-원형큐 삽입 순서
1)rear위치 증가 시킨 후 :rear = rear+1 %MAX_QUEUE_SIZE
2)큐가 만원인지 체크: front ==rear //인 경우는 queue가 full인상태
3)front != rear 이면 값을 삽입: queue[rear] = item

-원형큐 삭제 순서
1)큐가 공백인지 체크: front == rear  //인 경우는 queue가 empty상태
2)front != rear 이면 front값 증가 : front = (front +1)%MAX_QUEUE_SIZE
3)원소 삭제: queue[front]

연결 큐
-큐를 연결리스트로 구현하면 메모리방식이 동적이므로 이동큐,원형큐 방식이 필요 없다. 

SQL
1.SQL데이터 정의문
-종류: CREATE, ALTER, DROP


(1)스키마, 카탈로그
(2) 도메인 정의문
(3)기본 테이블 생성
*SQL은 대소문자를 구별하지 않는다. 단 따옴표에서는 대소문자 구분한다.
(4) 기본테이블 제거, 변경

열을 삭제할 때에는 ALTER TABLE 테이블이름 DROP 열이름 [CASCADE/RESTRICT]; 
->ALTER을 쓴 후 DROP을 쓴다


2.SQL 데이터 조작문(DML)
-종류: SELECT, INSERT, DELETE. UPDATE
-처리대상: 기본 테이블, 뷰

(1)데이터 검색
-검색 수행시 또다른 테이블이 만들어짐 (=폐쇄 시스템)
-기본구조: SELECT 열 FROM 테이블 WHERE 조건
-SQL은 한 테이블에 똑같은 행이 중복될 수 있다. 
-SQL에는 기본키가 없어도 된다. 집합이 아니기 때문이다. 
-그래서 SQL SELECT문에서 중복을 없애려면(집합과 같은 결과를 만들려면) DISTINCT를 명세해야한다.

-SQL 검색문 형식
SELECT [ALL/DISTINCT] 열
FROM 테이블
[WHERE 조건]
[GROUP BY 열
[HAVING 조건]]
[ORDER BY 열 [ASC/DESC]];

*주의사항: NULL을 검색 조건 속에 명세할 때에는  열 IS [NOT] NULL 로 검색해야한다. 
열 = NULL은 허용하지 않는다. 

*UNION 사용시에는 중복되는 튜플은 제거된다.

(2)데이터 갱신
-기본구조: UPDATE 테이블 SET{열 =산술식/NULL} [WHERE=조건];

(3)데이터 삽입
-기본구조: 
->행을 직접 삽입하는 경우 : 
INSERT INTO 테이블[(열 이름)] VALUES(열 값);
->SELECT를 실행하여, 그 결과를 테이블에 삽입하는 경우: 
INSERT INTO 테이블[(열 이름)] SELECT문;

(4)데이터 삭제
-기본구조: DELETE FROM 테이블 [WHERE 조건];

만일 삭제하는 조건이 다른테이블의 외래키에 속한 조건이라고 한다면 CASCADE로 수행된다.
즉 참조한 그 테이블의 내용도 삭제 연산이 수행된다.참조 무결성 때문임

DELETE를 한다고 해서 테이블 자체가 없어지는 것은 아님. 빈 테이블로 남아있다.
데이터베이스에 남아있지 않게 하려면 DROP을 사용해야한다.


3.SQL 뷰
(1)뷰 생성
-기본구조: CREATE VIEW 뷰이름[(열 이름)] AS SELECT문(SELECT-FROM-WHERE) [WITH CHECK OPTION];
WITH CHECK OPTION의미는 뷰에 대한 갱신, 삽입 연산 실행시, 뷰 정의조건을 위반하면 실행이 거부됨을 의미한다.

(2)뷰 제거
뷰 제거에는 ALTER안쓴다. DROP쓴다.
기본구조: DROP VIEW 뷰이름 {RESTRICT/CASCADE};

(3)뷰 조작 연산
뷰는 SELECT문 말고도 INSERT, DELETE, UPDATE문을 쓸수 있다. 단 제한이 많다.
예를 들면 INSERT 사용시에는, 기본키가 정의되어 있지 않은 뷰는 INSERT를 실행할 수 없다.
왜냐하면 뷰에 정의되지 않은 열의 값은 NULL이 되는데, 기본키가 뷰에 정의되어 있지 않다면 기본키 자리에 NULL이 들어가야하기 때문이다.

-뷰 변경 허용안되는 조건
1) 뷰의 열이 상수, 산술 연산자, 함수가 사용된 산술식으로 만들어진 경우 변경 허용 안됨
2)COUNT, SUM,AVG, MAX,MIN이 정의된 뷰는 변경 안됨
3)DISTINCT,GROUP BY, HAVING이 사용된 뷰는 변경 안됨
4)2개 이상 테이블이 관련된 뷰는 변경 안됨


4.삽입SQL

네트워크 보안공격

1. 스니핑(Sniffing)
-허브환경에서 스니핑
-스위치 환경에서 스니핑

2. 스푸핑(Spoofing)
-ARP스푸핑
-IP스푸핑
-ICMP스푸핑
-DNS스푸핑

3. DoS(서비스 거부 공격 Denial of Service)
-TCP SYN Flooding 공격
-ICMP플러딩 ->Smurfing 공격
-LAND 공격
-Teardrop 공격
-Ping of Death
-HTTP Get Flooding

4. DDoS(분산 서비스 거부 공격 Distributed Denial of Service)
5. 세션 하이재킹 공격(Session Hijacking)
6. APT 공격(Advanced Persistent Threat)

데이터베이스 시스템 구성요소
-데이터베이스
-데이터베이스 관리 시스템
-시스템과의 인터페이스 제공하는 도구로서의 데이터 언어
-데이터 언어를 사용해 데이터베이스를 접근하려는 사용자
-데이터베이스관리와 운영을 책임지는 데이터베이스 관리자
-데이터베이스 관한 연산을 전담해 효율적으로 실행시키는 데이터베이스 컴퓨터


[관계대수]
1.일반 집합연산
->카티션 프로덕트 빼고는 서로 합병이 가능함. 
->차집합 뺴고는 서로 결합적, 교환적이다.

-합집합
-교집합
-차집합
->R-S: R에는 있지만 S에는 없는 튜플로만 구성됨
-카티션 프로덕트

2.순수 관계연산
-셀렉트: 주어진 조건을 만족하는 튜플들을 선택하는 연산
-프로젝트: 릴레이션 애트리뷰트 연산을 대상으로 함
->프로젝트 연산 후 똑같은 튜플이 나오면, 하나만 제외하고 나머지는 모두 제거한다. 
-조인
->동일 조인을 해서 중복되어 나온 애트리뷰트를 제거하기 위해 자연조인을 한다. 
-디비젼


[관계 해석]
1.튜플관계 해석
1)튜플변수
2)한정 애트리뷰트
3)원자식
4)정형식


2.도메인 관계 해석
1)도메인 변수
2)원자식
3)정형식


[QBE- Quary By Example]

보안모델 3가지

1. 벨 라파듈라 모델
-객체의 기밀성 유지에 중점을 둠.
-NRU(No Read Up); 높은 등급의 데이터를 읽을 수 없음 ->상향 읽기 금지 보안 정책. 
주체 등급>=객체 등급 ->주체 등급이 객체 비밀분류를 지배하는 경우(읽기 권한을 가진 경우)
-NWD(No Write Down): 낮은 등급 데이터에 쓸수 없음.


2. 비바 모델
-주체에 의한 객체 접근의 항목으로 무결성을 다룸.
-비인가자들의 데이터 변형 방지를 해결함.
-비바모델은 벨 라파듈라 모델의 비밀등급에 대응하는 무결성 등급을 가짐.

-NRD(No Read Down): 낮은 등급의 데이터를 읽을 수 없음 ->객체A>=객체B인 경우, 객체A에 대해 write 접근권한 가짐
-NWU(No Write Up): 높은 등급의 데이터에 쓸 수 없음 ->객체A<=객체B인 경우, 객체 A에 대해 write 접근권한 가짐


3. 클락 윌슨 모델
-무결성 중심의 상업절 모델
-무결성 3가지 목표를 만족하는 접근제어 모델
->무결성 3가지 목표: 비 인가자들의 데이터 변형방지, 내/외부 일관성 유지, 합법적인 사람에 의한 불법적인 수정방지
-구성요소 3개
1)잘 구성된 트랜잭션
2)직무 분리
3)사용자 주체의 직접적인 객체 접근 금지=응용프로그램을 통한 데이터 접근