2-way 합병 정렬의 분할은 분할 대상을 반으로 나눈다.

퀵정렬(quick sort)의 분할은 분할 대상에 대하여 피봇(pivot)을 기준으로 나눈다.

합병 정렬과 다르게 퀵정렬에서는 모든 분할이 완료되면 정렬도 완료된다.

합병 정렬은 추가 데이터 저장공간이 필요 없는 제자리 정렬 알고리즘이다.

A → B → E → F → D → C

A → B → D → C → E → F

A → D → B → E → F → C

A → D → F → E → B → C

크루스칼(Kruskal) 알고리즘

0/1 배낭(knapsack) 문제 풀이

플로이드－워셜(Floyd-Warshall) 알고리즘

최장 공통 부분 수열(LCS, Longest Common Subsequence) 구하기

코드 수행 완료 후, A[0]에는 가장 큰 원소가 저장되어 있다.

코드 수행 완료 후, 배열 A의 원소는 오름차순으로 정렬되어 있다.

최선의 경우와 최악의 경우의 수행 시간 복잡도가 다르다.

코드는 삽입 정렬(insertion sort)을 구현한 것이다.

(나) → (다) → (라) → (가)

(나) → (라) → (다) → (가)

(다) → (나) → (라) → (가)

(다) → (라) → (나) → (가)

[6, 4, 2, 1, 3, 8, 5, 7, 9, 10]

[6, 4, 2, 1, 5, 8, 3, 7, 9, 10]

[6, 4, 2, 1, 3, 5, 8, 7, 9, 10]

[6, 4, 2, 1, 5, 3, 8, 7, 9, 10]

98

202

300

331

삽입 정렬

버블 정렬

병합(merge) 정렬

선택(selection) 정렬

깊이 우선 탐색 방식을 이용해서는 구현할 수 없다.

하나의 그래프에 한 개의 위상 정렬만 존재한다.

사이클이 없는 모든 종류의 그래프에 적용할 수 있다.

간선 <i, j>를 가질 때 정점 i는 정점 j를 선행한다.

합병 정렬 알고리즘

라빈 카프(Rabin-Karp) 알고리즘

백트래킹(backtracking) 알고리즘

후위 순회(postorder traversal) 알고리즘

알고리즘의 수행 시간을 대략적으로 나타내는 방법이다.

$\mathrm{O}$(Big-oh) 표기는 최소한의 알고리즘 수행 시간을 나타내기 위해 사용한다.

n개 정수 배열에 대한 순차 탐색 알고리즘은 $\mathrm{O}$(1) 시간 복잡도를 가진다.

증가 함수 $10n^2+3n+2$는 $\mathrm{O}(𝑛)$으로 표기할 수 있다.

유클리드(Euclid) 알고리즘

스트라센(Strassen) 알고리즘

몬테카를로(Monte Carlo) 알고리즘

플로이드－워샬(Floyd-Warshall) 알고리즘

통 채우기(bin packing) 문제

정점 커버(vertex cover) 문제

그래프 색칠하기(graph coloring) 문제

여행자 문제(TSP, Traveling Salesman Problem)

ㄴ, ㄷ

ㄴ, ㄹ

ㄱ, ㄴ, ㄷ

ㄱ, ㄷ, ㄹ

선택 정렬(selection sort)

버블 정렬(bubble sort)

합병 정렬(merge sort)

기수 정렬(radix sort)

힙 정렬의 시간 복잡도는 $O(n^2)$이다.

퀵 정렬은 정렬할 전체 원소에 대해 정렬을 수행한 후 기준값을 중심으로 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다.

삽입 정렬은 입력에 민감한 알고리즘으로, 입력이 거의 정렬되어 있을 때 처리시간이 느리고, 입력이 역으로 정렬되어 있을 때는 최선의 경우로 빠르다.

병합 정렬은 크기가 n인 입력을 n/2 크기로 분할하고, 각각에 대해 같은 방식으로 정렬을 수행한 후, 2개의 각각 정렬된 부분을 합병한다.

$c_{i,j}=\{\begin{array}{cc}0& ifi=j\\ {\min }_{i\le k\le j-1}\{c_{i,k}+c_{k+1,j}+p_{i-1}{p}_k{p}_j\}& ifi<j\end{array}$

$c_i,j=\{\begin{array}{cc}0& ifi=j\\ {\min }_{i\le k\le j-1}\{c_i,k+c_k,j+p_i-1p_k-1p_j\}& ifi<j\end{array}$

$c_i,j=\{\begin{array}{cc}0& ifi=j\\ {\min }_{i\le k\le j-1}\{c_i,k-1+c_k,j+p_i-1p_k-1p_j\}& ifi<j\end{array}$

$c_i,j=\{\begin{array}{cc}0& ifi=j\\ {\min }_{i\le k\le j-1}\{c_i,k+c_k,j+p_i-1p_k{p}_j\}& ifi<j\end{array}$

Diffusion Model

DQN(Deep Q-Network)

GANs(Generative Adversarial Networks)

VAEs(Variational Autoencoders)

인공지능 개발의 목적, 윤리, 가치 등에 대해 23가지 원칙을 제시했다.

인공지능 시스템은 반드시 인간의 직접적인 통제 없이 자율적으로 작동해야 한다.

연구 목표는 방향성이 없는 지능이 아니라 인간에게 유용한 지능 개발이어야 한다.

인공지능 시스템의 실패 원인을 이해할 수 있도록 투명성과 설명 가능성이 확보되어야 한다.

내용 기반 추천은 메모리 기반 방법과 모델 기반 방법이 있고 콜드 스타트(cold start) 문제가 발생한다.

아이템 기반 추천은 이전에 구매한 아이템을 기반으로 그 상품과 유사한 다른 상품을 추천하는 방법이다.

사용자 기반 추천은 나와 비슷한 성향을 지닌 사용자의 데이터를 기반으로 상품을 추천하는 방법이다.

추천 시스템은 콘텐츠의 내용에 기반하거나 사람들의 성향 정보를 취득한 후 개인화된 맞춤 항목을 추천한다.

CNN

KNN

MLP

RNN

P(간다)

P(간다 | 나는)

P(간다 | 학교에)

P(간다 | 나는, 학교에)

경합 해소(conflict resolution)는 여러 규칙을 동시에 실행할 경우 모순이 발생할 수 있기 때문에 실행 가능한 규칙들 중에서 한 개를 선택하는 것을 의미한다.

전향 추론(forward chaining)은 규칙의 조건부를 만족시키는 사실이 있을 때 규칙의 결론부를 실행하거나 처리한다.

후향 추론(backward chaining)은 특정 사실을 확인하기 위해 해당 사실을 결론부에 포함하는 규칙의 조건부가 만족하는지 확인해 가는 방식으로 추론한다.

추론 엔진(inference engine)은 경합 해소 → 패턴 매칭(pattern matching) → 규칙 실행(rule execution)의 과정을 반복하여 추론한다.

맹목적 탐색은 문제의 상태 공간 정보를 이용한다.

깊이 우선 탐색은 너비 우선 탐색에 비해 메모리에 대한 부담이 적지만 최단 경로를 찾는다는 보장이 없다.

너비 우선 탐색은 목표 상태를 찾을 때까지 생성된 모든 노드를 메모리에서 관리하기 때문에 메모리 비용이 크다.

반복적 깊이 심화 탐색은 탐색 깊이 한계를 0부터 점차 증가시키면서 깊이 우선으로 탐색하는 방법이고 최단 경로 찾는 것을 보장한다.

(가) → (다) → (라) → (나)

(가) → (라) → (다) → (나)

(다) → (가) → (라) → (나)

(다) → (라) → (가) → (나)

정제되지 않은 대용량의 데이터로부터 의미 있는 상관관계, 패턴, 추세 등을 발견한다.

트랜잭션에서 항목 간의 불순도를 표현하기 위해 최소지지도와 최소신뢰도를 사용한다.

저장된 데이터를 정제(cleaning), 통합(integration)하여 잡음과 불일치를 제거하고 데이터 웨어하우스에 저장한다.

대규모 데이터에서 암묵적인, 이전에 알려지지 않은, 잠재적으로 유용할 것 같은 정보나 지식을 추출하는 체계적인 과정이다.

학습 데이터를 추가하여 검증 손실값을 학습 손실값에 근접시킬 수 있다.

신경망 학습 모델이 학습 데이터 세트의 패턴을 적절히 학습하지 못했다는 의미이다.

신경망의 은닉층 개수, 뉴런의 개수 등 학습 매개 변수가 과도하게 많으면 발생할 수 있다.

신경망에서 검증 손실값이 다시 상승하는 현상을 완화하기 위하여 가중치 규제 방법이 사용될 수 있다.

0.25

0.48

0.52

1

사전훈련을 통해 텍스트 데이터를 학습해 놓은 모델인 트랜스포머 언어 모델을 기반으로 한다.

이미지와 텍스트를 각각 임베딩 공간에 표현하고, 서로 대응하는 이미지와 텍스트의 유사도가 높아지도록 대조 학습(contrastive learning)을 수행한다.

제로 샷(zero-shot) 예측과는 달리, 클래스를 추가하고 모델을 재학습하여 새로운 입력 이미지를 분류할 수 있다.

시각 정보와 언어 정보 사이의 대응 관계를 학습한 멀티 모달 모델로 이미지 검색, 이미지 설명 생성, 시각 질의응답 등 다양한 작업으로 확장할 수 있다.

퍼셉트론의 하이퍼 매개 변수(hyper parameter)를 정하는 것은 사람이 해야 한다.

단층 퍼셉트론이 해결할 수 있는 문제는 비선형 영역을 포함한다.

퍼셉트론은 다수의 신호를 입력으로 받아 하나의 신호를 출력한다.

단층 퍼셉트론의 구성 요소 중 임곗값은 바이어스(bias)로 대체할 수 있다.

분기점(branch point)

임계점(critical point)

전환점(turning point)

특이점(singularity)

0.33

0.5

0.57

0.75

약 0.01

약 0.05

약 0.95

약 0.99

주성분 분석법

선형 판별 분석법

최소우도법

최소제곱법

SSO

OTP

PIN

RADIUS

개인정보 보호법

전자금융거래법

정보보호산업의 진흥에 관한 법률

정보통신망 이용촉진 및 정보보호 등에 관한 법률

사용자가 악의적인 웹 사이트에 접속하도록 하는 공격이다.

공격자는 사용자의 DNS 질의에 대해 위조된(spoofed) 응답이 사용자에게 전달되게 한다.

DNS 캐시 포이즈닝(poisoning)은 위조된 DNS 응답이 로컬 DNS 서버의 캐시에 저장되므로 일정 기간 사용자에게 피해를 줄 수 있다.

디지털 서명으로 DNS 데이터그램의 진위 여부를 확인할 수 있는 SSH(Secure Shell)가 DNS 캐시 포이즈닝 공격을 방지하기 위해 설계되었다.

금융보안원(FSI)

한국정보통신진흥협회(KAIT)

한국정보통신기술협회(TTA)

개인정보보호협회(OPA)

SPN 구조를 사용한다.

128비트 블록 단위로 암호화한다.

암호화 함수와 복호화 함수가 동일하다.

키 길이에 따라 10, 12, 14 라운드로 구성된다.

32비트의 보안 매개변수 색인(security parameter index) 필드에는 같은 보안연관(security association)에 속하는 각 패킷에 대해 서로 다른 보안 매개변수 색인값이 주어진다.

32비트의 순서 번호(sequence number) 필드에는 데이터그램의 순서를 나타내는 카운터 값이 저장된다.

8비트의 다음 헤더(next header) 필드는 IP 데이터그램에 의해 전달되는 페이로드의 데이터 유형을 나타낸다.

ICV(Integrity Check Value) 필드에는 IP 헤더와 ICV를 제외한 전체 패킷에 대해 계산한 인증 데이터가 저장된다.

범죄의 예방 및 수사를 위하여 필요한 경우

시설의 안전 및 관리, 화재 예방을 위하여 정당한 권한을 가진 자가 설치ㆍ운영하는 경우

교통정보의 수집ㆍ분석 및 제공을 위하여 정당한 권한을 가진 자가 설치ㆍ운영하는 경우

촬영된 영상정보를 저장하지 아니하는 경우로서 개인정보보호위원회가 정하는 경우

기밀성

인증성

무결성

가용성

첫 번째 필드는 그룹의 이름을 나타낸다. groupadd 명령을 이용하여 새로운 그룹을 생성할 수 있다.

두 번째 필드는 그룹 패스워드를 나타내는 부분이지만 /etc/gshadow 파일에서 별도 관리하는 경우에는 ‘x’로만 표기된다.

세 번째 필드는 리눅스에서 그룹에 부여한 번호로 그룹 생성 이후에는 변경할 수 없다.

네 번째 필드에 해당 그룹에 속한 사용자의 로그인 ID가 기록된다.

악성 스크립트가 웹 서버에서 실행된다.

악성 스크립트는 웹 서버 측 데이터베이스에 저장된다.

공격자가 보낸 악의적 링크를 사용자가 클릭하게 한다.

사용자와 웹 서버 간의 신뢰 관계를 악용하여 공격자가 원하는 서버 동작을 발생시킨다.

명령: find / -name '*.c'

설명: 확장자가 c인 파일을 모두 찾는다.

명령: find / -mtime -2

설명: 최근 48시간 이내에 마지막으로 수정된 파일을 모두 찾는다.

명령: find / -user user1

설명: 소유자가 user1인 파일을 모두 찾는다.

명령: find / -type 4755

설명: 권한 설정이 4755로 설정된 파일을 모두 찾는다.

무결성(integrity)

일방향성(one-way property)

강한 충돌 저항성(strong collision resistance)

약한 충돌 저항성(weak collision resistance)

다중 인증(Multi-factor Authentication)

챌린지 핸드셰이크 인증 프로토콜(Challenge Handshake Authentication Protocol)

제로 트러스트 보안 모델(Zero Trust Security Model)

임의적 접근 통제 모델(Discretionary Access Control Model)

Identification

Authorization

Authentication

One-Time Password

ㄱ, ㄴ

ㄱ, ㄷ

ㄴ, ㄷ

ㄱ, ㄴ, ㄷ

한국인터넷진흥원은 클라우드컴퓨팅서비스에 대한 보안인증 기관의 하나이다.

국가기관 등이 이용하는 클라우드컴퓨팅서비스의 보안인증 기준은 국가정보원장이 정한다.

보안인증의 유효기간은 5년이다.

보안인증의 유효기간은 연장할 수 있다.

공개키 암호 알고리즘은 트랩도어 단방향 함수에 기반을 둔다.

대칭키 암호 알고리즘은 공개키 암호 시스템에 비해서 암호화 및 복호화 속도가 빠르다.

공개키 암호 알고리즘의 대표적인 알고리즘은 DES이다.

공개키 암호는 전자서명에 사용된다.

AES는 키 길이를 증가시켜도 더 이상 안전성을 유지할 수 없다.

양자 키 분배 프로토콜을 사용하면 안전하게 암호키를 공유할 수 있다.

양자내성암호(PQC)는 양자 알고리즘을 이용하여 양자 컴퓨터에서만 동작하도록 설계된 암호이다.

인수분해의 어려움에 의존하는 RSA는 쇼어(Shor) 알고리즘을 이용한 양자 컴퓨터의 공격에도 안전성을 유지할 수 있다.

TrustZone

SIEM(Security Information & Event Management)

TEE(Trusted Execution Environment)

TPM(Trusted Platform Module)

SELECT 이름, 제품번호, 개수

FROM 고객 OUTER JOIN 주문

ON 번호 = 고객번호

ORDER BY 이름, 제품번호;

SELECT 이름, 제품번호, 개수

FROM 고객 RIGHT OUTER JOIN 주문

ON 번호 = 고객번호

ORDER BY 이름, 제품번호;

SELECT 이름, 제품번호, 개수

FROM 고객 LEFT OUTER JOIN 주문

ON 번호 = 고객번호

ORDER BY 이름, 제품번호;

SELECT 이름, 제품번호, 개수

FROM 고객, 주문

WHERE 번호 IN (SELECT 고객번호 FROM 주문)

ORDER BY 이름, 제품번호;

참조 무결성 제약조건은 외래키는 참조할 수 없는 값을 가질 수 없다는 규칙이다.

개체 무결성 제약조건은 기본키를 구성하는 모든 속성은 NULL 값을 가지면 안 된다는 규칙이다.

기본키로 정의된 속성은 중복된 값이 허용되지 않는다.

참조 무결성 제약조건에서 자식 릴레이션은 부모 릴레이션의 제약을 받지 않는다.

일반 애플리케이션 함수와 달리 매개변수를 전달할 수 없다.

데이터베이스 서버에서 실행되어 클라이언트와 서버 사이의 데이터 전송량을 줄일 수 있다.

SQL 외에 다른 언어로 작성될 수 있다.

CALL 문장을 가진 대화형 SQL에서 호출될 수 있다.

ㄱ, ㄴ

ㄱ, ㄷ

ㄴ, ㄷ

ㄱ, ㄴ, ㄷ

로그 레코드가 상당 기간 메인 메모리에 있으면 시스템 장애 시 해당 로그 레코드가 손실될 수 있다.

트랜잭션의 원자성을 보장하기 위한 회복 기법으로 로그 우선 기록 규약(write-ahead log protocol)을 지원해야 한다.

시스템 장애 시 복구를 위해 변경 사항을 즉시 디스크에 기록하며, 이는 시스템의 성능을 최적화하는 데 중요한 역할을 한다.

트랜잭션이 수행되는 동안 발생하는 변경 사항을 일시적으로 메모리 버퍼에 저장하여, 디스크 출력 횟수를 줄이고 시스템 성능을 향상시킨다.

SELECT e.이름, s.이름 AS 추천인이름

FROM 회원 e LEFT OUTER JOIN 회원 s

ON e.추천인아이디 = s.아이디;

SELECT e.이름, s.이름 AS 추천인이름

FROM 회원 e, 회원 s

WHERE e.추천인아이디 = s.아이디;

SELECT 이름, 추천인이름

FROM 회원 e

WHERE EXISTS

(SELECT 이름 AS 추천인이름 FROM 회원 WHERE e.아이디 = 추천인아이디);

SELECT e.이름, s.이름 AS 추천인이름

FROM 회원 e, 회원 s

WHERE e.추천인아이디 = s.아이디

AND e.추천인아이디 IS NOT NULL;

ㄱ, ㄴ

ㄱ, ㄹ

ㄴ, ㄷ

ㄷ, ㄹ

원자성(Atomicity)을 보장하기 위한 ROLLBACK 처리

지속성(Durability)을 보장하기 위한 TRIGGER 처리

고립성(Isolation)을 보장하기 위한 SAVEPOINT 처리

일관성(Consistency)을 보장하기 위한 START TRANSACTION 처리

속성의 데이터 타입

테이블에 저장된 레코드 값

데이터에 대한 다양한 제약 조건

테이블 이름, 인덱스(index) 이름, 뷰(view) 이름

ㄱ, ㄴ

ㄱ, ㄷ

ㄴ, ㄷ

ㄱ, ㄴ, ㄷ

SELECT 사번, 월급

FROM 직원

ORDER BY 월급;

SELECT *

FROM 직원

WHERE 이름 LIKE '김%';

SELECT AVG(월급)

FROM 직원

WHERE 부서 = '인사팀';

SELECT SUM(부서, 월급)

FROM 직원

GROUP BY 부서;

외부/개념 사상은 외부 스키마의 데이터가 개념 스키마의 어떤 부분에 해당하는지 대응 관계를 정의한 것이다.

개념/내부 사상은 개념 스키마의 데이터가 내부 스키마를 통해 물리적 장치에 저장되는 대응 관계를 정의한 것이다.

내부 스키마가 변경되어도 개념/내부 사상을 수정하면 개념 스키마가 영향을 받지 않는다.

개념 스키마가 변경되어도 외부 스키마에 영향이 없는 성질을 물리적 데이터 독립성이라 한다.

E1(A1, A2, RA2)

E2(A3, A4, RA1)

E1(A1, A2, RA1, RA2)

E2(A3, A4)

E1(A1, A2, RA1, RA2)

E2(A1, A3, A4)

E1(A1, A2, RA2)

E2(A1, A3, A4, RA1)

GROUP BY 팀번호;

GROUP BY 선수번호;

GROUP BY 팀번호 HAVING AVG(점수) >= 15;

GROUP BY 팀번호 HAVING MAX(점수) >= 20;

SQL문에서 조인 연산에 자주 사용되는 속성은 인덱스로 적합하다.

클러스터링(clustering) 인덱스는 검색 효율을 위해 테이블당 2개 이상 활용된다.

밀집(dense) 인덱스는 데이터 파일의 레코드 그룹에 대해 생성되는 하나의 엔트리이다.

인덱스를 구성하기 위한 자료구조로는 이진 탐색 트리(binary search tree)가 가장 많이 활용된다.

{상태번호} → {재고위치} {부품번호, 수량} → {상태}

{부품번호} → {상태번호} {상태번호, 부품번호} → {상태}

{부품번호} → {수량} {상태번호, 상태} → {부품번호}

{상태번호} → {상태, 재고위치} {상태번호, 부품번호} → {수량}

관계대수: σ_{(B < 10)}(R) _R.A=S.A S

SQL 문: SELECT DISTINCT R.A, R.B, S.C, S.A

FROM R INNER JOIN S

WHERE R.B < 10;

관계대수: R _N S

SQL 문: SELECT DISTINCT R.A, R.B, S.C

FROM R, S

WHERE R.A IN (SELECT S.A FROM S);

관계대수: R S

SQL 문: SELECT DISTINCT R.A, R.B

FROM R, S

WHERE R.A = S.A;

관계대수: R S

SQL 문: SELECT DISTINCT R.A, R.B, S.C

FROM R, S

WHERE R.A = S.A;