"정보처리" 태그로 연결된 21개 게시물개의 게시물이 있습니다.

• 정보통신분야 기술사 훑어보기
• 정보통신분야 기술사 출제기준
• 기술사: IT경영
• 기술사: 융합 IT
• 기술사: 프로젝트관리
• 기술사: 소프트웨어 공학
• 기술사: 정보보안
• 기술사: 데이터베이스
• 기술사: 네트워크
• 기술사: 알고리즘
• 기술사: 에세이

알고리즘​

트리​

이진탐색트리​

• Binary search
• $O(\log n)$

균형이진탐색트리​

• AVL Tree: Adelson-Velskii-Landis Tree
• Balance Factor: $BF(T) = H_l - H_r$ = T의 왼쪽 서브트리 높이 - T의 오른쪽 서브트리의 높이
• BF(T)가 -1, 0, 1 중 하나를 만족해야함.
• LL, LR, RR, RL 용어를 보기보단 그림을 보고 이해해야함.
• 최적화되어 $O(\log n)$ 탐색 시간 보장

m-원 탐색트리​

• m-way Search Tree, Multiway Search Tree

B- 트리​

B* 트리​

• B애스터 트리

B+ 트리​

• 모든 키의 값이 단말 노드에 순차 나열된다, 링크드 리스트로

Red Black 트리​

T 트리​

• AVL Tree + B tree

그래프​

• Node: 정점, Edge: 간선
• 신장트리: Spanning Tree
  • 그래프의 모든 정점과 일부 간선을 포함한 트리로 표현
  • $T = (V, F)$

최소 신장 트리​

• Minimal Spanning Tree
• 가장 적은 비용/거리로 그래프의 모든 정점을 연결할 수 있는 구조

프림 알고리즘​

• Prim
• 노드 기준
• $O(n^2)$

크루스칼 알고리즘​

• Kruscal
• 엣지 기준
• 간선 최소 개수: $O(n \log n)$
• 간선 최대 개수: $O(n^2 \log n)$

최단경로 문제​

• Shortest Path

다익스트라​

• Dijkstra
• 노드 수가 n이라면 n-1개의 목적지가 모두 확정될 때까지 반복
• 다익스트라를 노드마다 반복한게 프림 알고리즘

벨만포드​

• 가중치가 음수일 경우, 불이익이 있는 경우 다익스트라 알고리즘으로 최단 경로가 계속 갱신되므로 이를 방어하기 위한 방법

정렬​

선택 정렬​

• Selection Sort
• $O(n^2)$
• 가장 작은 값을 순서대로 찾아내어 첫 번째 배열부터 채워나가며 정렬

버블 정렬​

• Bubble Sort
• $O(n^2)$
• 왼쪽에서 오른쪽으로 비교해가며 오름차순으로 자리를 교환하여 정렬

합병 정렬​

• Merge Sort
• $O(n \log n)$
• 분할 정복
• 데이터 분포의 영향을 덜 받는다, 최악의 경우에도 효율적.

퀵 정렬​

• Quick Sort
• $O(n \log n)$
• 피봇을 정한다. 전체 값을 읽어 중간값이나 몇 개의 값의 평균을 피봇으로 정함.
• 프로그래밍 랭기지에서는 왼쪽에서 큰 값, 오른쪽에서 작은 값을 찾는 방식으로 구현.

삽입 정렬​

• Insert Sort
• $O(n^2)$
• 추가적인 메모리를 안 씀: in-place sort

힙 정렬​

• Heap Sort
• $O(n \log n)$

Max Heap​

Min Heap​

Min-Max Heap​

Deap​

• 왼쪽은 Min Heap, 루트는 비어있음, 오른쪽은 Max Heap
• 왼쪽 서브트리의 임의 노드는 오른쪽 서브트리 같은 위치에 있는 노드와 대응된다.

기수 정렬​

• Radix Sort
• $O(n)$

MSD​

• Most Significant Digit

LSD​

• Least Significant Digit

탐색​

깊이 우선 탐색​

• DFS, Depth First Search
• Solution 을 찾기 위해 Candidate Solution 인 노드들을 순회
• Optimal Path (최적의 해)가 아닐 가능성이 높음, 보장할 수 없음.

너비 우선 탐색​

• Breadth First Search
• Optimal Path를 보장
• 탐색 과정에서 나타나는 모든 상태를 저장해야하기 때문에 메모리 비효율적.

최고 우선 탐색​

• Best-First Search

백트래킹​

• 탐색을 진행하면서 필수적인 부분의 그래프만 유지하여 시간과 공간을 절약.
• 노드 부모로 돌아가서 다음 자식 노드의 검색을 계속.

N-Queen 문제​

0-1 배낭문제​

인공지능​

휴리스틱 탐색​

• Heuristic Search
• 논리적으로, 수학적으로 증명할 수 없으나 경험이나 직관에 의해 효율적으로 해를 얻을 수 있으리라는 기대를 갖게하는 근거에 의한 방법
• 사람처럼 학습을 통해서 직관적으로 탐색

Hill-Climbing 탐색​

• 남은 경로에 대한 비용만 고려
  • 가장 가파른 길이 정상까지 가장 짧으니까
  • 가파른 다음에 내리막일 수도 있고, 평지일 수도 있고, 다음 가파른 길을 찾을 수 없을 수도 있음
• 남은 길 중에 가장 가파른 길을 찾는 평가함수 사용
  • Evaluatio Function, Objetive Function

A* 탐색​

에이전트​

• 특정 목적을 가지고 자동으로 해결해주는 소프트웨어

신경회로망​

K-means 클러스터링​

패턴인식​

딥러닝​

선형회귀​

• Linear Regression
• 기울기: 가중치, Weight
• 절편: 바이어스, Bias
• 최소 제곱법: LSM, Method of Least Squares
• 평균 제곱근 오차: RMSE, Root Mean Square Error
  • 오차의 값이 더 이상 줄어들지 않을 때가 최적화
• 경사하강법

다중선형회귀​

로지스틱회귀​

시그모이드 함수​

• Sigmoid Function

단층 퍼셉트론​

다층 퍼셉트론​

오차 역전파 알고리즘​

• Back Propagation

다중 분류 문제​

• 원 핫 인코딩
• 소프트맥스

과잉 적합, 과소 적합​

• over fitting, under fitting
• 해결방안
  • 조기 종료: Early Stopping
  • 가중치 규제 방법: Weight Regularization
  • 드롭 아웃: Drop out
  • 데이터 증강: data augmentation
  • 앙상블: Ensemble

유전자 알고리즘​

• 재생산: Reproduction
• 교차: Crossover
• 치환
• 교배/돌연변이: Mutation

그래픽 알고리즘​

베지어 곡선​

압축 알고리즘​

Run-Length 코딩​

LZ77​

허프만 코딩​

논리회로​

논리게이트​

불대수​

카노맵​

전가산기​

반가산기​

비교기​

베이즈 이론​

조건부 확률​

베이즈 정리​

• 정보통신분야 기술사 훑어보기
• 정보통신분야 기술사 출제기준
• 기술사: IT경영
• 기술사: 융합 IT
• 기술사: 프로젝트관리
• 기술사: 소프트웨어 공학
• 기술사: 정보보안
• 기술사: 데이터베이스
• 기술사: 네트워크
• 기술사: 알고리즘
• 기술사: 에세이

네트워크의 가치​

• 물리적 구성
  • NIC, 케이블, 허브
  • 라우터, 스위치
  • 기지국, 안테나
• 논리적 구성
  • IP, MAC, Domain
  • 전화번호
  • 프로토콜
• 정보전달의 원리: 멀리, 빠르게, 고품질로
  • 송신자 -> 전달자 -> 수신자
  • 속도 향상의 원리
  • 품질 향상의 원리
  • 먼거리 전달 원리
• 네트워크 분류
  • 유선: PAN, LAN, WAN
  • 무선: WBAN, WPAN, WLAN

• 정보처리시대에서 정보통신시대로 넘어오면서
  • 기회요인: 참여 공유 개방, 글로벌화
  • 위협요인: 개인정보유출, 프라이버시 침해 제거

네트워크 관련 법칙​

멧갈프 법칙​

• Metcalfe's Law, 메칼프 법칙: 이더넷의 창시자
• 네트워킹의 효과는 사용자(가입자, 노드) 수의 제곱에 비례, 네트워크의 외부성
• 예시: SNS

길더의 법칙​

• Gilder's Law: IT칼럼니스트
• 광섬유의 대역폭(Bandwidth)은 12개월마다 세 배씩 증가
  • 트래픽 증가는 통신 속도의 증가라고 볼 수 있음
• 무어의 법칙으로 설명하는 직접회로 및 멤리의 증가 속도를 능가하는 광대역 통신망 설명

섀넌의 법칙​

• Shannon-Hartley theorem, 섀넌의 정리, 샤논의 정리
• 채널용량은 대역폭과 신호 대 잡음비에 비례

• C: 채널 용량
• W: 대역폭
• S: 신호전력
• N: 잡음전력

네트워크 구성​

네트워크의 물리적 구성​

• 교환기: 라우터
  • 가장 중요한 구성요소로 단말기들을 일시적으로 연결시켜주는 기능 제공
  • 회선 교환과 패킷 교환으로 나눠진다.
  • 패킷 교환은 Connection-Oriented 방식(TCP), Connection-Less 방식(UDP)로 나뉜다.
• 중계기
  • 신호의 감쇄 및 왜곡을 보상하기 위해 증폭 및 재생 기능을 가지고 있음
  • 아날로그는 증폭만 가능하나, 디지털통신은 증폭과 재싱이 동시에 가능
• 전송 및 다중화 선로
  • 전화선, 전용선
  • 광시분할 다중화
  • 광파장분할 다중화

네트워크의 논리적 구성​

• Network Address
  • 가입자를 식별하기 위한 식별자
  • 전화번호, IP, MAC, DNS, ENUM (tElephone NUmber Mapping) 등
  • DNS: 망에서는 숫자주소만 인식되나 사람의 사용 편의를 위해 문자주소를 사용함
• 네트워크 프로토콜
  • 물리적 네트워크를 논리적으로 동작하도록 함
  • 사용자로 하여금 네트워크의 투명성 보장
  • 국제표준: OSI 7 Layer
  • 사실상의 표준: TCP/IP (이게 더 먼저 나옴, 인터넷 전용)
  • 하부계층(주로 LAN) 표준: IEEE 802, CSMA/CD, Ethernet

정보전달의 원리​

데이터 통신의 원리​

무선 통신의 원리​

부호화​

• 속도와 품질 향상
• 정보를 이진코드로 변환/압축하는 소스 부호화과정과 이를 처리, 전송하는 과정에서 오류를 줄이는 변환 채널부호화 과정을 총칭

변조​

• 속도, 품질, 전송거리 향상
• 신호 정보를 전송매체의 채널 특성에 맞게끔 신호(정보)의 세기나 변위, 주파수, 위상 등을 적합한 형태로 변환하는 과정
• 변조 이유:
  • 전송 매체에 알맞은 변조방식 사용하여 장거리 전송 가능
  • 변조가 넓은 주파수 대역에 걸치므로 다중화 가능
  • 주파수를 높임에 따라 안테나 길이, 크기의 단축이 가능
  • ISI 등이 존재하는 채널에서 신호 대역폭을 늘려주어, 간섭효과 최소화 가능
    • Inter Symbol Interference: 심볼 간 간섭

네트워크의 분류​

• 유선
  • PAN: Personal Area, USB, HDMI
  • LAN: Local Area
  • MAN: Metro Area
  • WAN: Wide Area
• 무선
  • WVAN: 의료목적
  • WPAN: 블루투스, NFC
  • WLAN
  • WIMAX: WIBRO, 예전에 도심에서 모바일 서비스
  • Radio

프로토콜​

약속의 중요성

• 사람을 위한 식별자: 도메인, 전화번호
• 컴퓨터를 위한 식별자: IPv4, IPv6, MAC
• 최단 거리를 위한 전송경로 설정: 라우팅, 포워딩(스위칭), 상태확인(ICMP)
• 다양한 전송방식:
  • TCP, UDP, SCTP
  • 브로드캐스팅, 유니캐스팅
  • 멀티캐스팅, 애니캐스팅
• 충돌, 지연 방지, 안전, 신속, 정확

통신프로토콜​

통신프로토콜 개요​

통신프로토콜 발전​

통신프로토콜 기능​

OSI​

TCP/IP​

컴퓨터를 위한 식별자​

IP​

ARP​

사람을 위한 식별자​

인터넷 주소 체계​

전화번호, ENUM​

전송 방식​

인터넷 전송 방식​

TCP​

• Transmission Control Protocol

UDP​

• User Datagram Protocol

SCTP​

• Streaming Control Transmission Protocol

라우팅 프로토콜​

라우팅 알고리즘​

Distance Vector Algorithm​

Link State Algorithm​

기업용 네트워크​

LAN​

Inter-Networking 장비​

고속 LAN​

스위치​

MPLS​

WLAN​

차세대 WLAN​

CDN​

가정용 네트워크​

인터넷망​

광가입자망​

케이블망​

홈네트워크​

특수목적 네트워크​

Ad-hoc​

MANET​

VANET​

WMN​

WBAN​

WPAN​

D2D​

이동통신​

발전단계​

이동통신망​

이동통신 원리​

4G​

4G LTE​

• Long Term Evolution

CR​

• Cognitive Radio

Handover​

MIH​

• Media Independent Handover

5G​

6G​

네트워크 품질​

IPv4 주소 효율화​

IPv6​

IPv4 to IPv6​

모바일 IPv4​

흐름 제어​

오류 제어​

ARQ​

• Automatic Repeat Reqeust

H-ARQ​

• Hybrid ARQ

TCP 혼잡제어​

Slow start, Congestion Avoidance​

Fast Retransmit, Fast Recovery​

QoS​

• Quality of Service

최신 이슈​

VoIP​

• Voice over IP

H.323​

SIP​

• Session Initiation Protocol

MGCP​

• Media Gateway Control Protocol

H.248​

• MEGACO, MEdia Gateway Control

VoIP 프로토콜 비교​

LBS 측위기술​

미래 네트워크​

ICN​

• Information Centric Network

SDN​

• Software Defined Network

범정부 프로젝트​

• 기가 코리아 프로젝트
• 국가 재난 안전 통신망: PS-LTE

• 정보통신분야 기술사 훑어보기
• 정보통신분야 기술사 출제기준
• 정보통신분야 기술사 출제기준
• 기술사: IT경영
• 기술사: 융합 IT
• 기술사: 프로젝트관리
• 기술사: 소프트웨어 공학
• 기술사: 정보보안
• 기술사: 데이터베이스
• 기술사: 네트워크
• 기술사: 알고리즘
• 기술사: 에세이

DB 개요​

데이터/정보/지식/지혜​

• 지혜: 지식과 경험이 축적된 상태/능력
• 지식: 의사결정에 이용된 정보, 부가가치 창출, 정보의 추상화, 일반화
• 정보: 관계에 따라 의미가 부여된 데이터, 구조화된 데이터의 집합
• 데이터: 그 자체로는 의미가 없음, 식별 및 기록이 가능한 단순한 사실

데이터 --관계의 이해--> 정보 --패턴의 이해--> 지식 --원리의 이해--> 지혜

DB/DB system​

한 조직의 여러 응용시스템이 공유하기 위해 최소의 중복으로 통합, 저장된 운영 데이터의 집합 통저운공

• 통합 데이터: Integrated Data, 최소 중복, 통제된 중복
• 저장 데이터: Stored Data, 컴퓨터가 접근 가능한 매체에 저장
• 운영 데이터: Operational data, 조직의 운영에 꼭 필요한 필수적인 데이터
• 공유 데이터: Shared Data, 여러 응용 프로그램이 공동으로 접근
• 실시간 접근, 계속적인 변화, 동시 공유, 내용에 의한 참조

기본 구조​

• 외부 단계: Exteranl Level, 외부스키마
• 개념 단계: Coceptual Level, 개념스키마
• 내부 단계: Internal Level, 내부스키마
• 데이터베이스

데이터 독립성​

상위 단계의 스키마 정의에 영향을 주지 않으면서 어떤 단계의 스키마를 변경할 수 있는 것

• 논리적 독립성: 외부 스키마나 응용 프로그램을 변경하지 않으면서 개념 스키마를 변경할 수 있는 성질
• 물리적 독립성: 개념 스키마를 변경하지 않으면서 내부 스키마를 변경할 수 있는 성질

DBMS​

다수의 사용자들이 데이터베이스 내의 데이터를 접근할 수 있도록 해주는 관리 소프트웨어 도구들의 집합

• 데이터 저장과 개발 및 유지보수 측면에서 중복성의 통제
• 사용자 간 데이터 공유
• 권한 관리
• 다양한 사용자에게 다양한 형태의 인터페이스 제공
• 데이터 사양에 존재하는 복잡한 관련성 표현
• 무결성 보장
• 백업 복구 기능 제공

DB 언어​

• DML: Data Manipulation Language,
  • SELECT, INSERT, UPDATE, DELETE
• DDL: Data Definition Language
  • CREATE, ALTER, DROP
• DCL: Data Control Language
  • GRANT, REVOKE

품질관리 R&R​

DB 설계​

키​

릴레이션 튜플을 유일하게 식별할 수 있는 속성들의 집합

• 유일성
• 최소성
• 결정자 도출 --유일성 검증--> 슈퍼키선정 --최소성 확인--> 후보키 선정 --엔티티 대표성--> 기본키 결정

데이터 무결성​

• 개체 무결성: 기본키, 모든 개체는 식별자를 정의하고 식별자 값은 NonNull 및 유일해야함
• 참조 무결성: 외래키, 외래키 값은 기본키로 사용된 릴레이션의 기본키 값이거나 Null
• 속성 무결성: 컬럼, 지정된 데이터 형식 만족, CHAR, DATE
• 사용자 정의: 데이터, 사용자가 Buniness Rule(업무규칙)에 따라 정의, CHECK, DEFAULT, 트리거 등

데이터 모델링​

개논물

• 개념적 설계
• 논리적 설계
• 스키마 정제
• 물리적 설계
• 응용 및 보안 설계

이상현상​

릴레이션 데이터의 중복관리로 인해 데이터를 조작할 때 발생하는 사이드이펙트

• 삽입이상: 릴레이션 내에 하나의 튜플을 삽입하려고 할 때 불필요한 데이터까지 삽입해야하는 현상
• 삭제이상: 릴레이션 내에 하나의 튜플을 삭제하려고 할 때 유지되어야할 정보까지 삭제되는 연쇄 삭제 현상
• 갱신이상: 중복된 튜플 중에서 일부 튜플의 속성을 변경시키려고 할 때 정보의 모순성이 발생하는 현상
• 원인 및 해결방안: 속성들 간의 종속성 분석을 통해 기본적으로 하나의 종속성이 하나의 릴레이션으로 표현되도록 무손실 분해 (Decomposition)

정규화​

이상현상을 야기하는 속성 간의 종속성을 제거하기 위해 릴레이션을 작은 여러 릴레이션으로 무손실 분해하는 과정 데이터 일관성, 중복의 최소화, 구조의 안정성을 최대한 확보하기 위한 방법

각 단계가 끝나면 N차 정규형이 된다.

• 1차 정규화: 도메인 분해
• 2차 정규화: 부분함수 종속성 제거
• 3차 정규화: 이행함수 종속성 제거
• BCNF 정규화: 나중에 추가됨
• 4차 정규화: 다치종속성 제거
• 5차 정규화: 조인종속성 제거

연결함정​

데이터 모델링 시 개체와 개체 사이에 부여하는 관계성 집합의 의미가 모호하여 원하는 결과를 얻을 수 없거나 향후 업무처리에 영향을 미치게 되는 ER모델의 문제점

• 부채꼴 함정: Fan Trap, 개체집합(Entity Set) 사이에 관계성 집합(Relation Set)이 정의되어 있기는하지만 관계성 예시가 모호한 경우
• 균열 함정: Chasm Trap, 개체집합 사이에 관계성 집합이 정의되어 있기는 하지만 일부 개체집합과 개체집합 사이에 관계성이 존재하지 않는 경우

반정규화​

정규화된 엔티티 타입, 속성, 관계를 시스템의 성능향상, 개발과 운영의 편의를 위해 데이터 모델을 통합하는 프로세스

DB 운영​

트랜잭션​

데이터의 정확한 일관성과 무결성을 보장하기 위해 완전히 종료해야하는 데이터베이스 처리의 논리적 작업 단위(Logical Unit of Work)

• 원자성: Atomicity, 분해가 불가능한 수행 단위로 완전히 수행 또는 수행되지 않음
• 일관성: Consistency, 트랜잭션이 성공적으로 완료되면 언제나 모순이 없는 상태 유지, 무결성 제약 조건
• 고립성: Isolation, 트랜잭션 실행 중 중간 연산 결과는 다른 트랜잭션 접근 불가
• 영속성: Durability, 성공적으로 완료된 트래잭션은 어떤 고장에도 손실 되어서는 안됨

트랜잭션 상태 전이​

• 실행 상태: Active
• 부분 완료: Partially Committed
• 완료 상태: Committed
• 실패 상태: Failed
• 철회 상태: Aborted

동시성 제어​

다중 사용자 환경을 지원하는 데이터베이스 시스템에서 여러 트랜잭션들이 성공적으로 동시에 실행될 수 있도록 지원하는 기능

• 트랜잭션 스케쥴: 각 트랜잭션을 구성하는 연산들이 시스템에서 시간에 따라 실행되는 순서
• 직렬가능성: Serializability, 트랜잭션들을 병행처리한 결과가 트랜잭션들을 순차적으로 처리한 결과와 같은 것
• 갱신분실 문제: Lost update problem
  • 트랜잭션이 동일 데이터를 동시에 갱신할 경우 발생하는 문제
  • 이전 트랜잭션이 데이터를 갱신한 후 트랜잭션이 종료하기 전에 이후 트랜잭션이 갱신 값을 덮어 쓰는 경우 오류 발생
• 불일치 문제: Inconsistency analysis problem
  • 다중 사용자 트랜잭션들이 동시에 실행될 때 DB가 일관성 없는 모순된 상태로 남는 문제
• 연쇄복귀 문제: Cascading rollback problem
  • 복수의 트랜잭션이 데이터 공유 시 특정 트랜잭션이 처리를 취소할 경우 다른 트랜잭션이 처리한 부분에 대해 취소 불가능

동시성 제어 기법​

• Locking
  • 트랜잭션이 사용하는 자원에 대해 상호배제(Mutual Exclusive) 기능을 제공하는 기법
  • 상호배제는 특정 트랜잭션이 데이터 항목에 대해 락을 설정하면 잠금을 설정한 트랜잭션이 언락될 때까지 데이터를 독점적으로 사용
• Time-stamp Ordering
  • 트랜잭션이 시스템에 입력될 때 타임스탬프 부여, 트랝개션의 수행 순서를 제어
  • 타임스탬프 값이 나중인 트랜잭션이 타임스탬프 값이 우선인 트랜잭션에 접근하고 있는 데이터 항목에 대한 접근을 요청하는 경우 롤백 당함
  • 직렬성 보장
  • 데드락 방지
• 낙관적 기법
  • 트랜잭션이 수행되는 동안 어떠한 검사도 실행하지 않음
  • 트랜잭션 수행 마지막에 갱신 사항들이 직렬가능성을 위반하는 경우가 있는지만 검사하여 이상이 없을 경우 트랜잭션을 확정
• 낙관적 기법 단계
  • Read Phase: DB를 읽고 개인적인 복사로 갱신, 트랜잭션 갱신은 모두 임시 갱신파일에 기록, 다른 트랜잭션에 의해 접근 불가능
  • Validation Phase: 가해진 변화가 데이터베이스의 무결성과 일관성에 영향을 주지 않을 것이라는 것을 보장하기 위해 검증됨, 이상 있을 경우 트랜잭션 재시작 및 롤백.
  • Write Phase: 변경사항이 영구적으로 DB에 적용됨

Locking 기법​

• Shared Lock: 공유 잠금한 트랜잭션은 데이터 항목에 대해 읽기만 가능, 다른 트랜잭션도 읽기 만 실행 가능
• Exclusive Lock: 전용 잠금한 트랜잭션은 데이터 항목에 대해 읽기와 쓰기 모두 가능, 다른 트랜잭션은 읽기/쓰기 불가.
• DB -> Table -> Row -> Column: Locking overhead 증가, 자료 공유성 높음.

2 Phase Locking​

모든 트랜잭션이 lock과 unlock 연산을 확장단계와 수축단계로 구분하여 수행

• 확장단계: 트랜잭션은 lock만 수행할 수 있고, unlock은 수행할 수 없는 단계
• 수축단계: 트랜잭션은 unlock만 수행할 수 있고, lock은 수행할 수 없는 단계
• 직렬간으성을 보장할 수 있는 규약으로 가장 많이 사용됨.
• 교착상태 발생될 수 있으나 예방과 탐지로 해결.

2 Phase Commit​

분산 데이터베이스 환경에서 원자성을 보장하기 위해 분산 트랜잭션에 포함하는 메커니즘 Prepare와 Commit 단계를 통해 모든 노드가 커밋하지 않으면 롤백하는 기법

• Phase 1: 준비 단계
  • 한 지역노드에서 커밋 요구, Global Coordinator가 Commit Point Site 결정
  • Prepare Message 를 전송하고 원격 노드는 Prepare Message Reply
• Phase 2: 커밋 단계
  • 모든 지역 노드가 커밋 준비되었다는 것을 받은 경우 각 노드에 Commit을 명령함
  • Global Coordinator가다른 지역 노드로부터 에러 보고를 받을 시 롤백 명령

DB 회복​

장애 발생시 데이터베이스를 장애 발생 이전 데이터베이스의 내용에 모순이 없는 일관된 상태로 복원시키는 것을

장애 유형​

• 트랜잭션: Transation Failure, 잘못된 입력, 데이터를 찾을 수 없는경우, 오버플로우, 가용자원 초과 요청 등으로 트랜잭션 동작 불가
• 시스템: System Failure, 교착상태로 트랜잭션이 작업 불가, 하드웨어 오작동으로 휘발성 기어장치의 데이터 손실
• 미디어: Media Failure, 비휘발성 기억장치(하드디슼) 고장으로 디스크 블록이 붕괴

회복 요건​

• 덤프: 데이터베이스 내용을 일정기간마다 다른 저장소에 저장, 백업정책에 의거하여 다른 디스크 또는 특정 가용 공간에 복사
• 로그: 데이터베이스 내용이 변경될 때마다 변경 내용을 로그파일에 실시간 저장

회복 기법​

• 지연갱신
  • 트랜잭션이 부분완료 상태에 이르기 전까지 발생한 모든 변경내용을 로그파일에 기록하고, DB에 저장하는 것을 지연시키는 방법
  • 트랜잭션 실패시 로그파일의 내용만을 폐기하면 되므로 Undo필요없음
• 즉시갱신
  • 변경내용을 DB와 로그파일에 동시에 저장
  • 트랜잭션 수행 도중 실패한 경우 로그파일의 내용을 참조하여 변경 이전 값으로 수정하는 Undo과정 필요
• 검사점: Check Point
  • 변경내용을 로그파일에 기록하고, 일정시간마다 체크포인트를 발생시켜 그때까지의 변경사항을 디스크에 저장, 로그파일에는 체크포인트를 기록
  • 장애시 체크포인트 이전 처리된 트랜잭션은 회복작업에서 제외하고, 이후 처리된 트랜잭션에 대해서만 Redo 또는 Undo 수행.
  • Check point interval 관리 필요
• 그림자페이지: Shadow Page Table
  • 트랜잭션 실행 중 현재 페이지 테이블과 그림자 페이지 테이블을 이용
  • 현재 페이지 테이블은 메인메모리, 그림자 페이지 테이블은 하드디스크에 저장
  • 트랜잭션 변경 연산이 수행되면 현재 페이지의 테이블 내용만 변경하고 그림자 페이지 테이블의 내용은 변경하지 않음
  • 트랜잭션이 성공적으로 완료될 경우, 현재 페이지 테이블의 내용을 그림자 페이지 테이블의 내용으로 저장
  • 데이터 단편화 및 그림자 페이지 테이블 복사, 쓰기에 오버헤드 발생

참조​

• DA 가이드: 한국데이터산업진흥원

• 정보통신분야 기술사 훑어보기
• 기술사: IT경영
• 기술사: 융합 IT
• 기술사: 프로젝트관리
• 기술사: 소프트웨어 공학
• 기술사: 정보보안
• 기술사: 데이터베이스
• 기술사: 네트워크
• 기술사: 알고리즘
• 기술사: 에세이

정보보안 개요​

정보보안 정의​

정보보안 FW​

OWASP 10대 취약점​

정보보안 위협​

정보보호 통제 활동​

관리적 보안​

CC 인증​

• Common Criteria 인증

ISO 27001​

ISMS-P​

BCP​

• Business Continuity Planning
• RTO: Recovery Time Objective
  • 서비스 재개를 위한 목표 복구 시간
  • 금융기관: 2h
• RPO: Recovery Point Objective
  • 목표 복구 시점 데이터 손실을 시간으로 환산한 개념
  • 금융기관: 0

DRP​

• Disaster Recovery Planning

물리적 보안​

생체 인식​

• Biometrics

기술적 보안​

기술적 보안 정의​

• 인증, 접근제어, 암호화

암호화 종류​

DES​

• Data Encryption Standard
• Feistal 구조
• 한국 SEED 128bit -> ARIA 128bit SPN 구조

RSA​

• Rivest Shamir Adleman

키교환 방식​

Diffie-Hellman​

KDC 방식​

• Key Distribution Center

전자서명​

이중서명​

2FA​

PKI​

• Public Key Infrastructure

SSO​

• Single Sign On
• SSO --권한관리--> EAM --계정관리--> IAM
  • Enterprise Access Mgmt.
  • Identity & Access Mgmt.

SAML​

• Security Assertion Markup Language

OAuth​

AAA​

• Authentication / Authorization / Accounting

OTP​

• One Time Password

접근제어​

• 벨라파둘라
• Biba Integrity
• 클락 & 윌슨

Firewall​

IDS​

• Instrusion Detection System: 침입탐지시스템

IPS​

• Instrusion Protection System: 침입방지시스템

IPSec​

• Internet Protocol Security Protocol

SSL/TLS​

• Secure socket Layer / Transport Layer Security

VPN​

• Virtual Private Network

NAC​

• Network Access Control

UTM​

• Unified Threat Management

ESM​

• Enterprise Security Management

TMS​

• Threat Management System

융합 보안​

무선네트워크 보안​

단말보안​

DLP​

• Data Loss Prevention

MDM​

• Mobile Device Management

디지털 컨텐츠 보호기술​

DOI​

• Digital Object Identifier

INDECS​

• Interoperability of Data in E-Commerce System: 전자상거래의 정보 교환을 위한 지적 재산권 관련 메타데이터 모델

디지털 워터마크​

핑거프린트​

DRM​

• Digital Right Management

CAS​

• Conditional Access System

Secure OS​

Hardening​

스마트폰 보안​

클라우드컴퓨팅 보안​

컴퓨터 포렌식​

디지털증거개시제​

• e-Discovery

유비쿼터스 컴퓨팅 보안​

개인정보보호​

정보보안 관련 법​

정보보안 응용​

정보보안 목표​

기무가

• 기밀성: Confidentiality, 정보 누출 방지
• 무결성: Integrity, 정보의 변조 및 파괴를 예방하고 방지
• 가용성: Availability, 해킹으로 인한 시스템 동작 불능 예방
• 인증: Authentication, 정당한 사용자 확인
• 책임 추적성: Accountability, 행위를 부인하는 것을 봉쇄

정보보안 분류​

• 물리적 보안: Physical Security
• 기술적 보안: Technical Security (논리적 보안, Logical Security)
• 관리적 보안: Management Security

위험​

• 위험성평가: 위협(Theats) X 자산(Assets) X 취약성 (Vulnerability)
• 위협: 정보시스템에 손상을 끼칠 수 있는 잠재성을 가진 행동이나 의도
• 취약성: 정보시스템이 손상을 당할 수 있는 결함이나 약점
• 자산: 정보시스템과 정보가 가지고 있는 가치

• 정보통신분야 기술사 훑어보기
• 기술사: IT경영
• 기술사: 융합 IT
• 기술사: 프로젝트관리
• 기술사: 소프트웨어 공학
• 기술사: 정보보안
• 기술사: 데이터베이스
• 기술사: 네트워크
• 기술사: 알고리즘
• 기술사: 에세이

SW 공학 개요​

SW 개념​

SW 위기​

SW 공학​

SDLC​

• Software Development Life Cycle.

폭포수모델​

프로토타이핑​

나선형모델​

반복점증모델​

반복적 개발 모델​

• Iteration Model.

점증적 개발 모델​

• Incremental Development Model.

진화모델​

• Evolutionary Development Model.

클린룸공학​

• Clean Room Process Model.

개발 방법론​

구조적기법​

정보공학​

객체지향​

컴포넌트기반​

• CBD: Component Based Development

모델기반​

MDA​

• Model Driven Architenture.

서비스기반​

SOA​

데이터, 애플리케이션을 비즈니스 관점에서 표준 블록단위로 나눠 하나의 서비스로 구성한 뒤 웹 서비스 기술 등을 적용 각 서비스를 조합 또는 재사용함으로써 운영체계와 프로그래밍 언어 등에 무관하게 IT자우너을 통합 관리하는 아키텍쳐/모델링/설계패턴

• Service Oriented Architecture.
• 실패요인
  • 조직 변화 수용의 실패
  • ESB의 부하 중앙 집중 문제

MSA​

하나의 어플리케이션을 여러 개의 서비스로 나누어 이 서비스들을 조합하여 본래의 서비스를 제공하는 것 업무 로직을 마이크로 서비스화 하고, 데이터 저장소를 서비스 단위로 분리하여 배치하고, 업무 단위의 독립성을 확보하여 개별적으로 업데이트하고 배포하고 스케일아웃 가능.

• Micro Service Architecture.
• Saga 패턴
  • DB분산 트랜잭션 처리 기법인 2PC가 장애유발 위험이 커서 서비서별로 분리된 DB의 트랜잭션 처리방안이 별도로 필요
  • Saga Execution Coordinator가 로컬 트랜잭션을 관리해주는 방식
  • 하나의 로컬 트랜잭션 단위로 실행, 트랜잭션이 종료될 때 완료 이벤트를 수신하고 순차적으로 다음 로컬 트랜잭션을 실행
  • 중앙 SEC노드가 다음에 실행할 로컬 트랜잭션을 결정
  • 실패 발생시 원래 트랜잭션에 대한 로그를 남기고, 취소상태를 설정한 후 보상 트랜잭션을 실행, 실패시 일정횟수/일정기간동안 반복적으로 재시도.
  • 각 MSA는 자신의 Local Atomic Transation에만 집중하기 때문에 Pending 상태없음. 따라서 Long-Lived 트랜잭션에 적합.
• Enterprise Gateway: API G/W
  • 다양한 API호출에 대한 첫 번째 관문 역할
  • 전사 차원의 관리가 필요한 보안(IAM) 및 트래픽 관리
• Micro Gateway: 경량 API G/W
  • 사용자/타 시스템 API 호출에 대한 종단 관문 역할 수행
• Service Mesh: 서비스망
  • MSA간 직접 통신하지 않고, 애플리케이션 네트워크를 기능을 제공하는 서비스 메쉬를 통해 수행.
  • MSA의 트래픽 문제 해결 대안
  • 사이드카 패턴
    • 모든 응용 프로그램 컨테이너에 사이드카 컨테이너를 추가하여 배포, 서비스의 모든 네트워크 트래픽을 처리.
    • 서비스가 타 서비스를 직접 호출하는 것이 아닌 프록시를 통해 호출하므로 로깅, 모니터링, 보안, 트래픽 제어 가능.

Agile 방법론​

• ASD: Agile Software Development.

XP​

• eXtreme Programming

TDD​

• Test Driven Development
• Need --> Test --> Refactoring --> Code
• Process
  • 단위테스트 형식으로 스펙 작성
  • 실패하는 테스트를 작성하고 확인
  • 스펙을 만족하는 코드를 작성
  • 테스트 확인
  • 코드와 테스트코드 리팩토링
  • 반복

Scrum​

• Role
  • Product Owner
  • Scrum Master
  • Scrum Team
• Process
  • Product Backlog
  • Sprint Backlog
  • Burndown chart
    • 개발 완료까지 남은 작업량을 보여주는 그래프
    • 각 이터레이션 별로 남아있는 작업량을 스토리 포인트라는 것으로 나타낸 것
• Meeting
  • Sprint Planning
  • Daily Scrum
  • Sprint Review
• 특징
  • Transparency
  • Time boxing: 일일 스크럼은 매일같이 15분이라는 짧은 시간에 진행해야함, 스프린트 리뷰는 매 이터레이션마다 주기적으로 진행.
  • Communication: 플래닝포커, 각 사용자 스토리의 구현 난이도/시간을 토론, 협의하는 절차
  • Inspect & Adapt model: 경험주의 모델, 개개인의 경험에 기반하므로 프로젝트마다 고유한 상황과 특징을 갖고 있음, 팀마다 달라지는 걸 허용함.

LEAN​

• 도요타에서 시작, 파레토 법칙으로 정말 중요한 20%에 집중
• 원칙
  • 낭비 제거하라
  • 품질 내재화하라
  • 지식 창출하라
  • 확정을 늦춰라
  • 전체를 최적화하라
  • 사람을 존중하라
  • 빨리 인도하라

DevOps​

개발자와 비 개발자 사이의 대화와 협동, 통합을 강조하고 담당업무와 직급의 장벽을 허물고 상호 이해를 추구 소프트웨어 개발과 IT운영 간의 상호의존 관계를 개선하기 위해 등장, 소프트웨어 제품 및 서비스를 빠르게 생산하려는 조직을 돕는 것이 목적.

SW 공학 응용​

SW 표준​

• 공식 표준
  • ISO 12207
  • ISO 15504
  • ISO 20000
  • ISO 9126
  • ISO 14143
  • IEEE 1471
• 사실 표준
  • CMMI
  • PMBOK
  • ITIL

ISO 15504​

• SPICE: Software Process Improvement and Capability dEtermination
• 소프트웨어 프로세스를 평가하고 개선함으로써 품질 및 생산성을 높이기 위해 제정한 국제 표준
• 소프트웨어 프로세스와 능력 레벨에 대한 참조 모델을 제시
• 실제로 소프트웨어 프로세스를 평가기 위한 짖침과 심사원 자격 등에 관한 사항 명시
• ISO 12207(소프트웨어 라이프사이클 표준)을 준거하여 소프트웨어 프로세스 영역을 세 영역으로 구분
  • 주요 프로세스, Primary Process
  • 지원 프로세스, Supporting process
  • 조직 프로세스, Organizational process
• 이 프로세스를 정립하여 수행하고 있는 수준에 따라 소프트웨어 개발 조직의 능력을 6단계로 구분
  • 미완성, Incomplete
  • 실행, Performed
  • 관리, Managed
  • 확립, Established
  • 예측, Predictable
  • 최적화, Optimizing

구성도​

상세 프로세스​

• Primary Life Cycle Processes
  • CUS.1 획득
    • CUS.1.1 획득 준비
    • CUS.1.2 공급자 선정
    • CUS.1.3 공급자 감시
    • CUS.1.4 고객 수락
  • CUS.2 공급
  • CUS.3. 요구사항 도출
  • CUS.4. 운영: ITIL
    • CUS.4.1 운영적 사용
    • CUS.4.2 고객 지원
  • ENG.1 개발
    • ENG.1.1 시스템 요구분석 및 설계
    • ENG.1.2 소프트웨어 요구분석
    • ENG.1.3 소프트웨어 설계
    • ENG.1.4 SW 구축
    • ENG.1.5 SW 통합
    • ENG.1.6 SW 시험
    • ENG.1.7 시스템 통합 및 시험
  • ENG.2 시스템과 소프트웨어 유지보수
• Supporting Life Cycle Processes
  • SUP.1 문서화: 이해관계자들의 관점을 공식화
  • SUP.2 형상관리
  • SUP.3 품질보증
  • SUP.4 검증
  • SUP.5 확인
  • SUP.6 합동 검토: 피어리뷰
  • SUP.7 감사: 제 3자 절차 감사
  • SUP.8 문제해결
• Organizational Life Cycle Processes
  • MAN.1 관리
  • MAN.2 프로젝트 관리
  • MAN.3 품질 관리
  • MAN.4 위험 관리
  • ORG.1 조직 정비
  • ORG.2 개선
    • ORG.2.1 프로세스 설정
    • ORG.2.2 프로세스 심사
    • ORG.2.3 프로세스 개선
  • ORG.3 인적자원 관리
  • ORG.4 기반구조: 인프라, 개발환경
  • ORG.5 측정
  • ORG.6 재사용

ISO 9126​

ISO 12119​

ISO 14598​

ISO 25000​

ISO 29119​

ISO 26262​

ISO 61508​

ISO 14143​

IEEE 1471​

PSP/TSP​

SDLC​

4세대 모델​

RAD모델​

컴포넌트 어셈블리 모델​

유지보수/재개발​

SW사업 대가산정 가이드​

SW 직접 구매​

• 구, 분리발주

SW 단계별 발주​

• 구, 분할발주

GS 인증​

• Good Software

SP 인증​

• 프로세스 품질 인증, Software Process

SW 안전​

요구공학​

형상관리​

테스트공학​

도메인공학​

프로덕트라인공학​

SW설계​

SW아키텍처​

UML​

디자인패턴​

참조​

• 전자정부프레임워크 교육신청

• 정보통신분야 기술사 훑어보기
• 정보통신분야 기술사 출제기준
• 기술사: IT경영
• 기술사: 융합 IT
• 기술사: 프로젝트관리
• 기술사: 소프트웨어 공학
• 기술사: 정보보안
• 기술사: 데이터베이스
• 기술사: 네트워크
• 기술사: 알고리즘
• 기술사: 에세이

프로젝트 관리 개요​

프로젝트 실패 현황​

프로젝트 실패 원인분석​

프로젝트 성공 요인​

PMBOK​

• Project Management Body Of Knowledge.
• 프로젝트 관리의 사실항 표준.

프로젝트 관리 프로세스​

PM​

• Project Manager

역할과 책임​

이해관계자들​

조직체계​

관리통제 스킬​

사회, 경제, 환경​

PMO​

• Project Management Office

정의와 필요성​

PMO Model​

PMO Framework​

PMO 사례​

전자정부 PMO​

도입시기별 장단점​

전자정부 PMO Framework​

수행단계별 세부 업무​

프로젝트 단계별 활동 사례​

핵심 성공 요소​

KA​

• Knowledge Area

프로젝트 통합관리​

프로젝트 범위관리​

프로젝트 일정관리​

프로젝트 원가관리​

프로젝트 품질관리​

프로젝트 자원관리​

프로젝트 의사소통관리​

프로젝트 위험관리​

프로젝트 조달관리​

프로젝트 이해관계자관리​

참조​

• Youtube: IT 전문가 - 프로젝트관리 시리즈

• 정보통신분야 기술사 훑어보기
• 정보통신분야 기술사 출제기준
• 기술사: IT경영
• 기술사: 융합 IT
• 기술사: 프로젝트관리
• 기술사: 소프트웨어 공학
• 기술사: 정보보안
• 기술사: 데이터베이스
• 기술사: 네트워크
• 기술사: 알고리즘
• 기술사: 에세이

융합 IT 개요​

디지털 컨버전스​

융합복잡도​

주요 영역​

가트너​

산업 적용​

서비스 융합​

서비스 정의​

SOA​

• Service Oriented Architecture

ESB​

• Enterprise Service Bus

EDA​

• Event Driven Architecture

Web Service​

SOA 트렌드​

Grid computing​

Utility computing​

SBC​

• Server Based Computing

Cloud computing​

컨텐츠 융합​

컨텐츠 정의​

Web2.0​

Semantic Web​

Lod​

• Linked Open Data

Open API​

Mash up​

HTML5​

디바이스 융합​

N-screen service​

DLNA​

• Digital Living Network Alliance

Mobile Office​

GPGPU​

• General-Purpose computing on Graphics Processing Units

CUDA​

Device API​

Hybrid App​

융합 IT 응용​

4차 산업혁명​

• 3차: 자동화, Automation, 인터넷 기반 연결성 강화
• 4차: 자율화, Autonomisation, 사람-사물-공간의 초연결, 초지능화, 융합과 연결성 극대화
• 주요기술: 사물인터넷, 로봇공학, 3D 프린팅, 빅데이터, 인공지능
  • 미래창조과학부 기준: 스마트공장, 자율주행자동차 & 스마트교통, 스마트홈, 스마트 헬스케어, 스마트인프라

자율주행 자동차​

• ICT 플랫폼 기업이 높은 생선성과 많은 가입자를 토재로 산업 생태계 변화를 주도, 기존 기업들도 플랫폼 사업자로의 변화를 시도
• 기술 아키텍쳐
  • 환경정보인지: ADAS 센서, V2X (Vehicle to Everything), 정밀지도
  • 판단: 주행전략 결정, 주행경로 생성
  • 제어: 차량제어 (조향각, 가감속 제어)
  • HMI (Human Machine Interface)로 운전자와 통신
  • ITS: Intelligent Transport Systems
• 정의
  • 자율주행자동차 시스템은 정보수집, 판단, 주행전략, 차량제어로 이어짐.
  • 각종 센서와 GPS, V2X 통신기술을 통해 주변 환경과 경로를 탐색.
  • 딥러닝, 데이터 분석 등 알고리즘을 통해 판단/주행 전략 수립.
  • 차량 제어

센서​

ADAS​

• 에이다스: Advanced Driver Assistant System
  • 전방 충돌방지 보조(FCA, Forward Collision-Avoidance Assist)
  • 차로 이탈방지 보조(LKA, Lane Keeping Assist)
  • 후측방 충돌방지 보조(BCA, Blind-Spot Collision-Avoidance Assist)
  • 안전 하차 보조(SEA, Safety Exit Assist)
  • 운전자 주의 경고(DAW, Driver Attention Warning)
  • 후측방 모니터(BVM, Blind-spot View Monitor)
  • 스마트 크루즈 컨트롤(SCC, Smart Cruise Control)
  • 차로 유지 보조(LFA, Lane Following Assist)
  • 고속도로 주행 보조(HDA, Highway Driving Assist)
  • 서라운드 뷰 모니터(SVM, Surround View Monitor)
  • 후방 교차 충돌방지 보조(RCCA, Rear Cross-Traffic Collision-Avoidance Assist)
  • 후방 주차 충돌방지 보조(PCA, Parking Collision-Avoidance Assist)
  • 원격 스마트 주차 보조(RSPA, Remote Smart Parking Assist)
• 운전자 졸음 경고: 영상인식, HVI
• 사각지대 감시(BSM, Blind Spot Monitoring): 근거리 RADAR, 초음파센서
• 주차 보조 장치(IPAS, Intelligent Parking Assist System): 초음파센서, 근거리 RADAR
• 적응형 상향등 제어(AHBD, Adaptive High Beam Control): 영상인식, RADAR
• 야간 시각(NV, Night Vision): 적외선 카메라

모바일 플랫폼​

Android​

• Activity: User Interface를 가지는 하나의 화면
• Service: 백그라운드에서 동작하는 컴포넌트
• Content Provider: Application Data를 공유하기 위한 컴포넌트
• Broadcast Receiver: System-wide 브로드캐스트 알림에 반응하기 위한 컴포넌트

참조​

• Gartner Top 10 Strategic Technology Trends for 2023
• Gartner Top 10 Strategic Technology Trends for 2024
• Gartner Hype Cycle 2023
• Youtube: IT 전문가 - 융합IT 시리즈
• IT 경영

• 정보통신분야 기술사 훑어보기
• 정보통신분야 기술사 출제기준
• 기술사: IT경영
• 기술사: 융합 IT
• 기술사: 프로젝트관리
• 기술사: 소프트웨어 공학
• 기술사: 정보보안
• 기술사: 데이터베이스
• 기술사: 네트워크
• 기술사: 알고리즘
• 기술사: 에세이

BITA, PDCA, 이사회와 경영진

IT경영 기본​

IT기획 및 조직화​

Computer paradox​

• 컴퓨터 성능의 발달 대비 상대적으로 느린 경제전반의 생산성, 명백산 상반성을 할하며, 개인회사와 특정 응용프로그램에 있어서도 마찬가지이다.
• Productivity paradox: 컴퓨터 시대라는 것을 어느 곳에서나 볼 수 있지만 생산성 통계에서만큼은 아니다. (Robert Solow)
  • 의미 있는 경제적 센스 측면에서는 어떠한 곳에서도 컴퓨터를 볼 수 없다.
  • 컴퓨터를 볼 수 있는 대부분의 산업분야에서는 결과가 엉망인 것으로 측정된다.

CIO​

• Chief Information Officer

IT Governance​

COBIT​

• Control Objectives for Information and Related Technologies

ISO 38500​

IT BSC​

• IT Balanced Score Card

IT portfolio​

IT 투자평가기법​

ISP​

• Information Strategy Planning

EA​

• Enterprise Architecture

ISMP​

• Information SYstem Master Plan

IT도입​

• System Integration

ISO 12207​

PMBOK​

• Project Mangement Body of knowledge

PRINCE2​

• Project In Controlled Environment

CMMI​

• Capability Maturity Model Integration

IT운영​

• System Management

ITSM​

• IT Service Management

ISO 20000​

ITIL​

• ITIL V2
• ITIL V3
• ITIL V4

IT경영 응용​

IT아웃소싱​

• 요즘엔 클라우드가 일종의 자원 아웃소싱 예시
• 기대효과: 비용절감, 핵심역량집중 (비용구조의 유동성 확보, 시장대응속도향상, 자산보존, 품질향상, 혁신)
• 위험요소: 숨은 비용, 불가능한 계약취소, 계약 관리 및 경험결여, IT운영통치권 상실

아웃소싱 유형​

• Total ITO: 전체를 아웃소싱
• Selective ITO: 일부를 아웃소싱
• 결합형
  • SI + ITO: 시스템 통합(SI) 후 운영 아웃소싱
  • Consulting + ITO: 전사적인 IT 계획수립을 위한 컨설팅 및 아웃소싱
  • BPO + ITO: 회계, 인사 등의 특정 업무 자체를 이관하고 관련된 ITO 수행
• 사업형태
  • 자사 단독인수
  • Joint Venture: 아웃소싱 서비스 회사와 고객이 지분을 공유하는 Joint Venture 설립

아웃소싱 절차​

• 타당성분석
• 사전조사
• 사업자선정
• 협상 및 계약
  • Due Diligence: 기업 실사
• 전환 및 계약관리

e-SCM​

• e-Sourcing Capability Model
• 서비스 제공의 핵심 구성 요소 또는 서비스 제공의 수단으로 정보 기술 사용

eSCM-SP​

• eSCM Service Provider: 84개 프랙티스
• 목적
  • 서비스 제공자의 평가
  • 서비스 제공자의 개선
  • 경쟁적 차별화
• 차원구성
  • Sourcing life-cycle: 소싱 생명주기
  • Capability areas: 능력 영역
    • 반복적인 역량과 일회성인 역량으로 나눠져있다.
  • Capability Levels: 능력 레벨
• 역량단계

발주관리​

• SW 사업 발주·관리 표준 프로세스 프레임워크: 소프트웨어 도입을 위한 전체 수명주기 과정 중 일련의 기본적인 프로세스·활동·작업을 규정한 상위 수준의 틀로 핵심, 지원, 조직 수명주기 프로세스 등으로 구성.
  • ISO12207을 많이 참조했다.

SLM​

• Service Level Management
  • SLA와 관련 활동들의 반복적 사이클로 지속적 개선을 통한 서비스 수준의 제고를 지향
  • 제약요인: 아웃소싱 이후에도 여전히 비용 및 서비스 품질 경쟁력 측면에서 많은 이슈 발생
• SOW: Statement of Work, Scope of Work, 업무 기술서
  • 서비스 공급자가 고객에 제공하는 서비스 내역 및 서비스 환경에 대해 정의한 문서 (할 일)

SLA​

• Service Level Agreement
  • IT서비스의 수준을 정량적으로 측정하여 서비스 성과를 평과하고, 그 결과로 서비스 수준을 지속적으로 개선하기 위한 서비스 성과 관리 방식에 관한 계약서
• 특징
  • 고객과 서비스 제공 업체 간의 커뮤니케이션 도구
  • 분쟁 예방 도구
• 적용대상
  • Internal SLA: Business Users <-> IT department
  • External SLA: IT <-> Service Provider <--Underpinning Contracts--> Solution Providers

IT Compliance​

• IT관점의 기업투명성, 위험관리 제고
• 등장배경: 회계책임 부과 대처 위한 IT시스템 필요, 각종 규제강화로 인한 대처 필요
• 개념: 기업 투명성 강화, 위험관리 강화 및 정부, 관련기관의 권고안, 규제법안의 요건 충족을 위해 IT관점 시스템, 프로세스 정비 활동
• 주요유형
  • 기업투명성 관련: IFRS, 국제회계기준
  • 정보보호 및 보안 관련:
    • GLBA: Gramm-Leach-Bliley-Act, 금융서비스 현대화 법률, 고객보호, 보안, 백업, 재해관리 규정
    • HIPAA: Health Insurance Portability & Accountability Act, 보험관련 고객정보보호 규정
  • 기업업무 연속성 관련: 금감원지침, 국내 금융권 재해복구 지침
  • 환경 관련: RoHS, WEEE
• 대응방안
  • 기업투명성 관련: 금융권 운용리스크관리시스템, ARM (Asset Risk Mgt), FAD (Fraud Auto Detection), 보고서 내부 통제시스템, 경영인증시스템
  • 정보보호: ISMS (Information Security Management System), 관물기, ILM (Information Lifecycle Management), DRM (Digital Right Management)
  • 업무연속성: BCP (Business Continuity Planning), DR (Disaster Recovery)
  • 환경관련: 유해물질 검수, 유통 관리시스템 구축

CSR​

• Corporate Social Responsibility, 기업의 사회적 책임
• 요즘은 ESG 로 바뀜
• 기업의 사회적 영향력이 커지면서, 경제적/법적/윤리적/자선적 책임을 포괄하는 개념으로 범위가 확장

• 윤리적 소비자: 소비자가 환경과 사회에 미치는 영향을 고려하여, 바람직한 방향으로 소비
  • 공정무역, 1인미디어의 발달, SNS에 응징
• 분야:
  • 환경경영
  • 정도경영
  • 사회공헌

ESG​

• Environmental · Social · Governance, 기업의 비재무적 요소인 환경, 사회, 지배구조.
• 기업이 환경, 사회적 책임을 고려하고, 지배구조를 개선해야 재무적인 위험을 줄이고 지속가능한 발전이 가능하다는 철학
• 투자자에게 기업의 비재무성과(지속가능보고서, 이사회보고서)를 커뮤니케이션하는 프레임이자 틀.
• 특징:
  • 명확한 타겟
  • 거버넌스, 성과관리체계
  • 공시, 커뮤니케이션
  • 측정, 평가를 통한 성과의 입증
  • 균형 잡힌 지표, 관리체계
  • Value Chain 상의 더 큰 책임
  • 차별화, 경쟁력 포인트
• 필요성: 소비자의 인식 변화, 정부의 정책 규제, ESG금융
• 평가 종류 및 체계:
  • 플랫폼 기반, 공시정보 기반으로 나뉜다.
  • 공시정보 기반인 MSCI (Morgan Stanley Capital International Index) 평가가 유명

ESG 택소노미​

• Taxonomy: 분류체계 (분류 + 법과학)
• 녹색금융의 기준, 그린워싱을 방지하는 기준을 제공
• 금융기관, 투자자, 정책입안자 등이 활용

SAM​

• Software Asset Management

      Best Practice                                    Standard
+------------------- IT Service Management --------------------------+
|     ITIL                                        ISO/IEC 20000      |
| +----------------- IT Asset Management --------------------------+ |
| | +------------ Software Asset Management ---------------------+ | |
| | | ITIL SAM                                  ISO/IEC 19770-1  | | |
| | | +-------------- License Management ----------------------+ | | |
| | | |                                                        | | | |
| | | +--------------------------------------------------------+ | | |
| | +------------------------------------------------------------+ | |
| +----------------------------------------------------------------+ |
+--------------------------------------------------------------------+

• 프로그램 리스트 모니터링 -> 라이센스 불법 확인 -> 수요 조사 -> 자산관리

경영 전략​

참조​

• Youtube: IT 전문가 - IT경영 시리즈
• 융합 IT
• ITSQC: eSCM-SP v2
• SWIT: 공공 SW사업 제안요청서 작성을 위한 요구사항 가이드

운영체제​

• 사용자와 하드웨어 간의 인터페이스 제공

목적​

• 하드웨어를 효율적 사용하도록 성능 향상
• UI 제공
• 성능요소
  • 처리율
  • 응답시간
  • 사용가능도
  • 신뢰도

제어프로그램​

• 감시 프로그램
• 데이터 관리 프로그램
• 작업 제어 프로그램

처리 프로그램​

• 언어번역 프로그램
• 서비스 프로그램
• 문제 프로그램

구성 요소​

• 프로세스 관리
• 주기억장치 관리
• 보조기억장치 관리
• 입출력 관리
• 파일 관리

프로세스 기능​

• 생성 및 소멸
• 동기화
• 일시중지 및 재실행
• 프로세스 간 통신
• 보호 시스템
• 네트워크 관리
• 명령해석 시스템

종류​

• 일괄처리 시스템
• 실시간 시스템
• 시분할 시스템
• 다중 프로그램 시스템: 여러 개의 프로갦이 동시에 실행되는 것처럼 처리하는 방식
• 다중 처리 시스템: 동시에 프로그램을 수행할 수 있는 CPU를 여러 개 두고 각각 분담하여 처리하는 방식
• 분산처리 시스템
• 결함허용 시스템: 시스템 일부가 고장나더라도 전체 시스템은 계속 가동할 수 있는 시스템

발달 과정​

• 50년대: 일괄 처리 시스템
• 60년대: 다중 프로그래밍, 멀티 프로그래밍, 시분할, 실시간 처리 시스템
• 70년대: 멀티모드 시분할 시스템
• 80년대: 병렬 프로그램 실행, 펌웨어
• 90년대: GUI
• 00년대: 64bit

입출력장치 발전추세​

프로그램에 의한 입출력​

• CPU에서 실행되는 프로그램에 의해 입출력을 직접 제어
• CPU는 입출력장치에 명령을 보낸 후 동작이 완료될 때까지 대기
• CPU는 주기적으로 주변장치의 상태를 반복적으로 검사하는 폴링 방식
• 자원낭비가 발생

인터럽트 처리에 의한 입출력​

• 입출력 인터페이스가 주변장치의 상태를 검사하여 준비상태가 되면 인터럽트 신호 발생
• 프로그램 상태를 스택에 저장한 후 문맥교환 과정을 통해 인터럽트 서비스 프로그램을 수행
• 주변장치에 명령을 보낸 후 결과가 올 때까지 CPU는 다른 작업을 수행할 수 있어 효율이 높다.

DMA​

• 직접 메모리 접근 입출력
• CPU는 상태정보, 제어정보만을 교환하게 하고 데이터 전송은 주변장치와 기억장치 간에 직접 교환하게 하는 방식
• 시스템 버스상에 모듈이 하나 추가되어야 한다.
• CPU를 통하지 않고 한 번에 한 단어씩 직접 기억장치로부터 모든 데이터 블록을 전송한다.
• 전송이 완료되면 DMA모듈은 CPU에게 인터럽트 신호를 보내고 CPU는 전송의 시작과 끝 부분에만 관여한다.
• 사이클 스틸링: 버스를 사용하기 위해 CPU의 동작을 일시적으로 중단시키는 기법

채널​

• DMA 개념을 확장하여 구현한 입출력만을 위한 전용 처리장치
• CPU처럼 독자적으로 주기억장치에 저장된 명령어를 처리할 수 있는 프로세스

종류​

• 선택 채널: 채널 하나를 하나의 입출력장치가 독점해서 사용하는 방식
• 멀티플렉서 채널: 한 채널에 여러 개의 입출력장치를 연결하여 시분할 공유방식으로 입출력하는 저속 입출력 방식
• 블록 멀티플렉서 채널: 셀렉터 채널과 멀티플렉서 채널 방식을 결합한 방식

기억장치 인터리빙​

• 인접한 메모리 위치를 서로 다른 뱅크에 둠으로 동시에 여러 곳에 접근할 수 있게 한다.
• 주기억장치의 구조적 개선으로 접근속도를 개선시키는 방법
• MAR과 MBR을 연결한 것을 기억모듈이라고 한다.
• 블록단위 전송이 가능하므로 DMA에서 많이 사용한다.

재배치 레지스터​

• 수행 중인 프로그램을 다른 곳으로 옮길 수 있도록 하는 레지스터
• 주기억장치 내 프로그램의 기준 주소가 이 레지스터에 기억된다.
• 기준 레지스터 = 재배치 레지스터

폴링​

• CPU가 특정 이벤트를 처리하기 위해 그 이벤트가 발생할 때까지 모든 연산을 모니터링하는데 쓴다.
• 단일 이벤트에 대해서는 유용하지만 프로그램이 길어지게 되면 그만큼 CPU 자원을 낭비하게 된다.

버퍼링​

• 속도 차를 줄이기 위해 중간에서 데이터를 일시적으로 기억장소에 축적하는 방법
• CPU와 저속 입출력장치의 작동속도를 조정한다.

단일 버퍼링​

• 주기억장치 일부를 버퍼로 사용한다.
• 버퍼가 채워지거나 비워지는 동안 CPU는 다른 작업을 할 수 없다.

이중 버퍼링​

• 2개의 버퍼를 이용해 단일 버퍼링의 단점을 보완하고 입출력과 CPU의 처리성능을 높이는 방법
• 입출력작업과 처리작업을 동시에 처리할 수 있다.

환형 버퍼링​

• 여러 개의 버퍼를 원형으로 구성하여 수행하는 방식
• CPU와 채널은 동시에 버퍼를 채우거나 비우는 일을 독립적으로 수행한다.
• 버퍼의 생산과 소비를 위해 버퍼의 수를 결정하는 게 성능에 매우 중요하다. (환형이기에)

보조기억장치​

• SASD: 순차 기억장치 => 테이프
• DASD: 직접 접근 기억장치 => 나머지

광디스크​

• CD-ROM: 650MB
• DVD: 4.7~17GB
• WORM Disk: write once read memory => CD-R

디스크 용어​

• 트랙: 디스크의 회전축을 중심으로 만들어진 동심원
• 섹터: 트랙을 몇 개의 부채꼴 모양으로 나눈 구간
• 실린더: 디스크의 중심축으로부터 동일선상에 위치한 동일 트랙들의 모임
• 클러스터: 여러 개의 섹터를 하나로 묶은 단위, 하드디스크에서 데이터를 저장하기 위한 기본 단위
• 파일할당 테이블: 디스크에 저장되어 있는 각각의 파일들에 대한 정보를 저장한 테이블
• TPI: Track per Inch, 1인치 당 트랙의 수

보조기억장치 속도​

• 레지스터 > 캐시 > 주기억장치 > 보조기억장치
• 자기드럼 > 하드디스크 > 광디스크 > 플로피디스크 > 자기테이프

입출력 채널​

• IOP: Input Output Processor
• 입출력작업이 끝나면 CPU에게 인터럽트로 알려주며 입출력장치와 주기억장치 간의 속도 차이를 해결

채널의 기능​

• 입출력 명령 해독
• 각각의 입출력장치에 명령 지시
• 지시된 입출력 명령의 실행을 제어

채널의 종류​

셀렉터 채널​

• 고속 입출력장치에 적합한 채널
• 입출력장치를 1:1로 전담
• 블록 단위 전송

멀티플렉서 채널​

• 저속의 입출력장치 여러 개를 동시에 제어하는 채널
• 바이트 단위의 전송

블록 멀티플렉서 채널​

• 여러 대의 고속 입출력장치를 블록단위로 처리

DMA​

사이클 스틸링​

• CPU가 메모리에서 명령어를 fetch하여 execute cycle 중에 있을 때 CPU가 메모리를 사용하지 않는 시간을 이용해 DMA를 행한다.
• 상태보존을 하지 않는다.

폴링은 주변장치의 상태보존을 하지 않음, 프로그램 제어하의 직접 입출력 방식

주소 지정방식​

• 묵시적
• 즉시 주소 지정: 데이터가 명령어에 바로 있음
• 레지스터 주조 지정: 오퍼랜드가 메인 메모리의 주소가 아닌 레지스터를 참조
• 직접 주소 지정: 오퍼랜드에 실제 주소
• 레지스터 간접 주소 지정: 메모리 위치가 기억된 레지스터를 참조
• 인덱스 주소 지정: 오퍼랜드와 인덱스 레지스터의 내용이 더해져 유효번지가 결정
• 베이스 레지스터 주소 지정: 오퍼랜드와 베이스 레지스터 내용이 더해져 유효번지가 결정
• 상대 주소 지정: 오퍼랜드와 프로그램 카운터가 더해져 유효번지 결정
• 간접 주소 지정: 오퍼랜드가 메모리 내의 주소를 참조하여 유효번지를 계산해 메모리에 접근, 2번 메모리 참조

가상 기억장치​

• 보조기억장치의 일부분을 주기억장치처럼 사용하는 것
• 매핑이 필요하다.

가상기억장치 구현방법​

페이징​

• 내부단편화 발생 가능

세그먼테이션​

• 논리적 단위
• 기억장치 보호키 필요
• 외부단편화 발생 가능

스풀링​

• 입출력할 데이터를 직접 I/O 장치로 보내지 않고 디스크에 모았다가 한꺼번에 입출력을 처리하는 방식
• CPU와 입출력장치의 처리속도 차이에서 오는 대기 시간을 줄이기 위해 고안
• 버퍼와 비슷한 개념

컴파일러​

• 고급 언어 프로그램을 목적프로그램으로 번역한 후 링킹작업을 통해 컴퓨터에서 실행 가능한 실행프로그램을 생성

인터프리터​

• 고급 언어 프로그램을 한 줄 단위로 받아들여 번역하고 번역과 동시에 프로그램을 한 줄 단위로 즉시 실행시키는 프로그램
• 컴파일러에 비해 느리다.

절대로더​

• 번역된 목적프로그램을 입력으로 받아들인 간단한 로더
• 기억장소 할당이나 연결을 사용자가 직업 지정
• 프로그래머가 절대 주소를 기억해야 한다.
• 다중 프로그래밍 방식에서 사용할 수 없음
• 소규모
• 모듈, 라이브러리 사용 불가

재배치 로더​

• 주기억장치의 상태에 따라 재배치 가능한 목적프로그램을 주기억장치의 임의 공간에 적재할 수 있도록 하는 로더

링킹 로더​

• 프로그램 적재 시에 필요한 프로그램들을 결합하여 2진 프로그램 이미지를 주기억장치에 적재

객체지향 운영체재​

• OOOS
• 운영체재 개발에 객체지향 프로그래밍 적용
• 객체: 모든 프로시저와 데이터를 묶어놓은 추상적 존재

펌웨어​

• 마이크로 명령어로 작성된 프로그램
• 기계어 하부에 프로그래밍층을 형성

에뮬레이션​

• 일종의 한 하드웨어 시스템에 부가장치를 부착하여 다른 하드웨어를 모방하는 것
• 하나의 컴퓨터가 다른 컴퓨터와 똑같이 행동하도록 만들어진 마이크로프로그래밍의 소프트웨어를 이용하는 기법

마이크로 다이어그노스틱스​

• 시스템의 고장진단을 마이크로 프로그래밍에 의해 수행하는 것

마이크로 커널​

• 운영체제의 커널 중에서 가장 기본적이고 핵심적인 기능만을 수행하는 부분만을 따로 구성한 모듈
• 높은 수준의 모듈화 제공

바인딩

• 프로그램 내에서 변수 등을 실제 값으로 배정하는 것
• 명령문과 데이터를 주기억장치에 특정 위치로 옮기는 것

기억장치 구성​

단일 프로그래밍 시스템​

• 주기억장치는 운영체제가 상주할 영역과 현재 수행될 사용자 프로그램이 적재될 영역으로 나뉜다.

다중 프로그래밍 시스템​

• 여러 개의 프로세스를 처리
• 주기억장치 관리 기법이 필요하다.

연속 적재 방법​

• 연속된 공간에 할당

분산 적재 방법​

• 필요한 부분만 주기억장치에 적재하는 방법
• 페이지나 세그먼트로 구성

단일 사용자 연속기억장치 할당​

• 주기억장치에 항상 한 프로그램만 적재된 가장 단순한 기법

상주모니터​

• CPU의 유휴시간을 극복하기 위해 작업의 묶음들을 자동으로 처리할 수 있는 운영체제
• 한 프로그램에서 다른 프로그램으로 제어가 자동적으로 넘어가도록 하기 위해 기억장치에 상주
• 입출력 시간동안 CPU는 유휴상태
• 사용자 공간보다 큰 프로그램은 실행이 불가능

오버레이 기법​

• 주기억 장치 용량보다 더 큰 프로그램을 분할해 그 분할 된 프로그램을 순차적으로 같은 영역에 적재해 실행하는 방법
• 디스크에 프로그램을 유지하고 운영체제에 의해 기억장치로 교체시키는 방법
• 프로그램을 여러 개의 분할된 조각으로 나누는 일은 프로그래머가 담당

교체 기법​

• swipping
• 충분하지 못한 주기억장치를 가진 시스템에서 여러 개의 프로그램이 하나의 메모리에서 실행될 수 있도록 하기 위해 사용하는 기법
• swap out: 보조기억장치로 이동
• swap in: 주기억장치로 이동
• 오버레이 기능이 없으면 기억공간보다 작은 프로그램만 실행 가능

내부 단편화​

• 하나의 분할에 작업을 할당하고 남은 공간

외부 단편화​

• 대기 중인 작업보다 분할영역이 너무 적어 분할 전체가 빈 공간이 될 때

기억장치 통합​

• 인접된 공간을 하나의 공간으로 만드는 것

기억장치 집약​

• 여러 개의 기억공간들을 하나의 큰 기억공간으로 만드는 것

기억장치 배치 기법​

• 최적 적합
• 최초 적합
• 최악 적합

블록 사상​

• 가상기억장치 내의 작업을 블록단위로 사상하는 것

페이징 기법​

직접사상​

• 페이지 사상테이블의 시작점 레지스터에 페이지 번호를 더해 주기억장치에서 그 페이지 시작주소를 구한 다음 변위를 더함으로 실주소를 계산한다.
• 프로세스의 가상기억장치를 구성하는 모든 페이지에 대한 항목은 페이지 테이블에 존재

연관사상​

• 빠른 주소변환을 위해 고속의 연관기억장치를 이용해 페이지 사상표 전체를 넣는 방법

연관/직접사상​

• 연관기억장치에는 페이지 사상테이블 중 지역성 있는 페이지를 넣고, 나머지는 직접사상

세그먼테이션 기법​

• 가상주소를 분할형태가 일정한 배열이나 함수와 같은 논리적인 다양한 크기의 가변 단위로 주기억장치의 연속적인 공간에 적재하는 방법
• 외부단편화 발생 가능
• 순수 세그먼테이션 기법에서 가상주소 양식: 세그먼테이션 번호, 변위, 가상 주소
• 세그먼 테이블 사상테이블 형식: R, W, E(xecute), A(append)

페이징/세그먼테이션 혼용​

• 세그먼트를 페이지화 하는 것
• 가상주소형식이 3차원 요소로 구성: V = (s, p, d)
• 세그먼트 번호, 페이지 번호, 변위
• 세그먼트의 사상테이블의 항이 세그먼트 주소를 가지고 있지 않고 페이지 사상테이블의 기준주소를 가지고 있다.

페이지 사상테이블 항목

• 페이지 존재 비트
• 보조 기억장치 주소
• 페이지 프레임 번호

페이지 호출 기법​

요구 페이지 호출기법​

• 수행 중인 프로세스에 의해 호출된 페이지나 세그먼트를 주기억장치로 옮기는 전략
• 호출된 페이지는 실제로 참조되는 페이지
• 페이지를 할당받기 위해 대기시간이 길다.

예상 페이지 호출기법​

• 프로세스에 의해 요청될 페이지나 세그먼트를 미리 예측하여 프로세스가 요구하기 전에 주기억장치로 적재시키는 전략
• 예측 결정이 올바라야 실행시간이 감소한다.

페이지 교체 기법​

OPT​

• 최적 교체
• 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법
• 실현 가능성이 없다.

무작위 페이지 교체​

• 무작위로 교체
• 오버헤드가 적다.

FIFO​

LRU​

• Least Recently Used
• 최근에 가장 오랫동안 사용하지 않은 페이지를 교체
• 계수기나 스택을 두어 계산한다.
• 스택 알고리즘

LFU​

• Least Frequently Used
• 사용빈도가 가장 적은 페이지를 교체하는 기법
• 프로그램 실행 초기에 많이 사용된 페이지가 나중에도 프레임을 계속 차지할 수 있다.

NUR​

• Not Used Recently
• 최근에 사용하지 않은 페이지를 교체하는 기법
• 각 페이지마다 참조 비트와 변형 비트를 사용

클록 페이지 교체​

• 원형 리스트를 사용해 페이지를 배열시켜 놓고 리스트의 포인터가 시계바늘이 돌아가는 것처럼 그 원형 리스트로 돌아가게 되는 것

SCR​

• 2차 기회 페이지 교체
• 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것
• FIFO 기법의 단점을 보완한 기법
• Second Chance 기법
• 각 페이지마다 참조 비트를 두고 1일 경우 참조 비트를 0으로 바꿔 FIFO 리스트의 맨 마지막으로 이동시킨다.

시간 국부성​

• 참조되는 기억장소가 가까운 미래에 계속 참조될 수 있다.
• 반복, 서부루틴, 스택, 계산, 집계

공간 국부성​

• 하나의 기억장소가 참조되면 그 근처의 기억장소가 계속 참조될 수 있다.
• 배열 순회, 순차적 실행, 변수 집합

워킹 세트​

• 지역성(국부성)을 이용해 페이지 부재율을 감소시키기 위한 개념
• 일정 시간 동안 자주 참조하는 페이지의 집합

스레싱​

• 페이지 부재가 비정상적으로 많이 발생하여 프로그램이 처리보다 페이지 교체에 많은 시간을 소비함으로 시스템 처리량이 급격히 저하되는 현상

페이지 부재​

• 프로세스 실행 시 참조할 페이지가 주기억장치에 없는 현상

페이지 크기​

작을 경우​

• 효과적인 워킹세트 확보
• 사상 테이블 크기 증가
• 기억공간 낭비
• 기억장치 효율을 좋다.

클 경우​

• 페이지 부재 수 최소화
• 페이지 단편화 현상 초래
• 사상 테이블 크기 감소
• 입출력 효율 증가

요구 페이징 기법​

• 페이지의 요구가 있을 때 주기억장치에 적재하는 기법
• 유효 또는 무효를 나타내는 비트가 페이지 사상테이블의 각 항목에 추가된다.

전역 교체​

• 프로세스가 교체할 프레임을 그 프레임이 현재 다른 프로세스에 할당되어 있어도 그에 상관없이 전체 프레임 중에서 하나를 선택하여 그 프레임을 사용할 수 있도록 해준다.
• 한 프로세스에 할당된 프레임 수는 증가한다.
• 자신의 페이지 부재율을 조정할 수 없다.

지역 교체​

• 각 프로세스가 그 프로세스에 할당된 프레임 중에서 하나를 선택해서 그 프레임을 사용할 수 있도록 해준다.
• 프로세스에 할당된 프레임 수는 변하지 않는다.

프로세스​

• PCB를 가진 프로그램
• 실기억장치에 저장된 프로그램
• 프로시저가 활동 중인 실체
• 비동기적 행위를 일으키는 주체
• 운영체제가 관리하는 실행 단위

프로세스 스케줄러​

• 둘 이상의 프로세스가 적절히 실행될 수 있도록 컨트롤 한다.

작업 스케줄러​

• 작업의 운선순위, 리소스의 할당 등을 판단해 처리율을 높이는 작업을 한다.

프로세스 상태​

• 제출상태: submit
• 보류상태: hold, 스풀러에 의해 디스크에 수록되어 있는 상태
• 준비상태: ready, CPU가 사용가능한 상태, 처리를 기다리고 있는 상태
• 실행상태: running, 프로세스를 수행 중
• 대기상태: blocked, 입출력 처리가 끝날 때 까지 대기 큐에서 대기하는 상태
• 완료상태: complete

프로세스 관리 모듈​

• 스풀러: 제출된 작업을 디스크에 수록하여 보류상태로 변환
• 작업스케줄러: 보류 상태 작업들 중 실행될 작업을 선정
• 프로세스 스케줄러: 여러 프로세스 중에서 실행될 프로세스를 선정
• 트래픽 제어기: 모든 프로세스의 상태를 파악하고 프로세스 관리 및 상태변환을 수행하며 프로세스 간의 통신과 동기화를 조정

프로세스 제어 블록​

• PCB
• 프로세스 생성시 만들어지며 모든 프로세스는 각기 고유의 PCB를 가진다.
• 프로세스 식별자
• 프로그램 카운터
• 우선순위
• 처리기 레지스터
• 기억장치 관리정보
• 입출력 정보
• CPU 사용 시간, 시간 범위, 계정번호, 작업 번호 등

스레드​

• 프로세스는 스레드를 담는 공간
• 실행점이 여러개
• CPU가 하나인 시스템에서 병행실행 가능

스케줄러​

장기 스케줄러​

• 작업 스케줄러
• 디스크공간에 제출된 프로세스들을 선택하여 주기억장치로 적재하며 실행 빈도수가 적어 장기 스케줄링
• 프로세스가 종료되어 시스템을 떠날 때만 새로운 프로세스를 생성하기 위해 호출

단기 스케줄러​

• CPU 스케줄러, 디스패쳐
• 실행되어 있는 프로세스 중에서 한 프로세스를 선택하여 CPU를 할당

중기 스케줄러​

• CPU를 경쟁하는 프로세스들의 수를 줄여서 다중 프로그래밍의 정도를 완하하는 것

선점 스케줄링​

• 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 자신이 CPU를 차지할 수 있는 기법
• SRT, RR, 선점 우선순위, 다단계 큐, 다단계 피드백 큐
• 시분할 시스템에 유용

비선점 스케줄링​

• 한 프로세스가 CPU를 할당 받으면 다른 프로세스는 CPU를 점유하지 못하는 기법
• 우선순위, FIFO, SJF, HRN, 기한부 알고리즘
• 모든 프로세스에 공정하고 응답시간이 예측 가능

스케줄링 알고리즘​

기한부 스케줄링​

• 처리기 할당시간을 제한하여 작업 할당시간안에 반드시 종료되도록 하는 기법

우선순위 스케줄링 알고리즘​

• 우선순위가 높은 것에 먼저 CPU를 할당하는 방식
• FIFO 원리
• 기아현상 발생을 방지하기위해 우선순위를 높이는 에이징 기법이 있다.

FCFS​

SJF​

• Shortest Job First
• 작업 수행시간이 가장 짧다고 판단되는 것을 먼저 수행

SRT​

• 비선점 스케줄링인 SJF를 선점형태로 변경한 기법
• Short Remaining Time
• 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행
• 더 짧다고 판단되는 프로세스가 큐에 들어오면 언제라도 선점된다.
• 시분할 시스템에 유용

RR​

• 각 프로세스는 같은 크기의 CPU 시간을 할당받는다.
• 시분할 방식에 효과적이다.
• 할당시간이 크면 FCFS와 같고, 작은면 문맥교환 및 오버헤드가 자주 발생한다.

HRN​

• Highest Response Ratio Next
• 실행시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것
• 대기시간과 서비스 시간을 사용한다.
• 우선순위 = (대기시간 + 서비스시간) / 서비스 시간

FSS​

• Fair Share Scheduling
• 프로세스들 집합 간에 프로세스의 스케줄링을 지원하며 UNIX 환경에서 서로 관계있는 사용자들에게 한정된 비용으로 시스템 자원을 사용할 수 있게 개발
• 사용자들은 그룹 짓는데 우선순위 RR 프로세스 스케줄러를 사용한다.

다단계 피드백 큐 스케줄링​

• Multi-level Feedback Queue Scheduling
• 여러 개의 큐를 두고 시간이 지나면 우선순위가 떨어지는 큐로 밀려나게 하는 것과 같이 실행시간이 긴 작업에 벌칙을 주는 방식
• 각 큐의 CPU 할당시간을 정할 수 있어 적응력이 커진다.

병행 프로세스​

• concurrent process
• 두 개 이상의 프로세스들이 동시에 존재하며 실행상태에 있는 것

우선순위 그래프​

• precedence graph
• 각 노드가 개개의 문에 대응하는 방향성 비순환 그래프
• 어떤 연산의 일부분이 가지는 우선순위 제약조건을 정의하는데 유용하다.
• 프로그래밍 언어에서는 사용이 곤란하다.

Fork/join​

• 최초로 병행 프로그램을 언어적으로 표현
• Fork: 단일 연산을 2개의 독립적인 연산으로 분할시키는 방법
• Join: 병행하는 2개의 연산을 하나로 재결합시키는 방법

병행문​

• parbegin/parend 표현방법을 사용하는 기법
• 1개의 프로세스가 여러 가닥의 병렬 프로세스로 분할되었다가 다시 한 가닥의 프로세스로 결합하는 것

Master/Slave​

• Master는 연산 + 입출력
• Slave 연산

약결합 시스템​

• 각 프로세스마다 독립된 메로리를 가진 시스템
• 분산 처리 시스템
• 각 시스템마다 독립적인 운영체제
• 프로세스 간의 통신은 메세지 전달이나 원격 프로시저 호출을 통해 이뤄진다.

강결합 시스템​

• 여러 개의 프로세스가 하나의 메모리를 공유하여 사용하는 시스템
• 다중처리 시스템
• 하나의 운영체제가 모든 프로세스와 시스템 하드웨어를 제어
• 프로세스 간의 통신은 공유메모리를 통해서 이뤄진다.

대칭 다중처리 구조​

• 모든 프로세스가 동등한 입장의 대칭성을 가지고 있으며 구현 및 수해이 매우 복잡한 형태의 가장 강력한 시스템
• 한 운영체제를 동시에 수행할 수 있게 재진입 코드와 상호배제가 필요하다.

비동기 병행 프로세스​

• 독립적 프로세스: 시스템에서 실행 중인 다른 프로세스에 영향을 받지 않고 주지도 않는 프로세스
• 유기적 프로세스: 프로세스가 가지는 동일한 입력에 대해 반드시 동일한 결과를 갖지는 않는다.

동기화 기법​

• Synchronization
• 두 개 이상의 프로세스를 한 시점에 동시에 처리할 수 없으므로 각 프로세스에 대한 처리 순서를 결정하는 상호배제의 한 형태
• 세마포어와 모니터 기법이 있다.

상호 배제

• 공유자원을 어느 시점에서 단지 한 개의 프로세스만이 사용할 수 있도록 하며 다른 프로세스가 공유자원에 대해 접근하지 못하게 하는 기법

임계구역​

• Critical Section
• 다중 프로그래밍 운영체제에서 여러 개의 프로세스가 공유하는 데이터 및 자원에 대하여 어느 한 시점에서 하나의 프로세스 자원 또는 데이터를 사용하도록 지정된 공유 자원을 의미하며 이를 보호구역이라 한다.

Test and set​

• 동시성을 제어하기 위한 동기화 명령어 중 하나로 하드웨어의 도움을 받아 수행
• 함수 조건을 비교할 때엔 한 프로세스가 점령을 하면 다른 프로세스가 개입을 할 수 없도록 선점해서 사용하는 개념
• 상호배제를 하는 기법

세마포어​

• semaphore
• 다익스트라가 제안
• P와 V라는 2개의 연산에 의해 동기화를 유지
• 상호배제 원리 보장

시간종속 오류​

• 프로세스들이 임의적으로 변수들을 공유할 때 발생하며 어떤 특정 순서로 실행이 될 때만 발생
• 프로세스가 자원에 대한 접근허가를 얻지 않고 그 자원을 연산하는 경우
• 프로세스가 자원 접근을 허용받고 나서 그 자원을 결코 해제하니 않는 경우
• 프로세스가 요청하지 않은 자원을 해제하는 경우
• 프로세스가 동일한 자원을 반복해서 요청하는 경우

생산자 소비사 문제​

• 여러 개의 프로세스를 어떻게 동기화할 것인가에 대한 고전적인 문제
• 한정 버퍼 문제, Bounded-Buffer Problem
• 생산자는 데이터를 인덱스를 통해 배열에 저장하는 식으로 데이터를 생성하며 소비자는 데이터를 증가시키며 배열에 있는 데이터를 인덱스로 접근하여 소비

판독기/기록기 문제​

• 다수의 프로세스가 하나의 데이터 객체를 공유하는 경우 한쪽 프로세스는 판독을 하려하고 다른 한쪽 프로세스는 기록을 하려고 할 때 발생하는 문제
• 기록기가 공유객체에 배타적 접근을 하도록 하는 것

병행 프로그래밍 언어​

• Ada: 구조화되고 통계학적 형태를 가지고 명령적, 객체지향적인 고급수준의 컴퓨터 프로그래밍 언어
• CSP: 처음으로 병행시스템에서 상호작용 패턴을 표현하는 언어

프로세스 간의 통신​

• 직접통신
• 간접통신: 메일 박스를 통해 메세지를 보내거나 받는다, 단방향 양방향 모두 가능

교착상태​

필수조건​

• 상호배제 조건: 자원은 한 번에 한 프로세스만 사용해야 한다.
• 점유와 대기 조건: 각 프로세스가 이미 자신에게 할당된 자원을 갖고 있으면서 다른 자원을 더 요구하고 있다.
• 비중단 조건: 프로세스에 할당된 자원은 스스로 반납하기 전에는 빼앗지 못한다.
• 환형대기 조건: 프로세스 간 환형사슬이 존재하여 각 프로세스는 다음 프로세스가 요구하는 자원을 가지고 있다.

자원할당 그래프​

• 프로세스와 자원 간의 관계를 나타내는 그래프를 의미한다.

교착상태 확인방법​

• 자원할당 그래프의 사이클이 존재하는지 확인한다.
• 사이클이 지원 유형에 하나라도 있으면 교착상태다.

교착상태 회피​

• 프로세스 시작 거부
• 자원할당 거부: 은행원 알고리즘

교착상태 탐지​

교착상태 복구​

디스크 접근 시간​

• Access Time = Seek Time + Rotational Latency + Transfer time
• 탐색시간: 헤드를 적정 트랙으로 이동하는데 걸리는 시간
• 회전지연시간: 데이터가 현재 위치에서 디스크 헤드까지 회전하는 데 소요되는 시간
• 전송시간: 실제 바이트가 이동하는데 소요되는 시간

디스크 스케줄링​

FCFS​

SSTF​

• Shortest Seek Time First
• 탐색거리가 가장 짧은 트랙에 대한 요청을 먼저 서비스하는 기법
• 일괄 처리 시스템에 유용
• 대화형 시스템에는 부적합

SCAN​

• SSTF가 갖는 탐색시간의 편차를 해소하기 위한 방법
• 현재 진행 중인 방향으로 가장 짧은 탐색거리에 있는 요청을 먼저 서비스
• Denning이 개발
• 대부분의 디스크 스케줄링에서 기본 전략
• 진행하면서 들어온 요청도 처리
• 오버헤드가 작을 경우 가장 효율적

N-step SCAN​

• 진행하면서 들어온 요청은 따로 모아 반대방향 진행 때 처리

C-SCAN​

• 항상 바깥쪽에서 안쪽으로 움직이면서 가장 짧은 탐색거리를 갖는 요청을 서비스
• 안쪽 끝까지 이동하면 가장 바깥쪽 끝으로 이동하고 다시 안쪽으로 들어온다.

C-LOOK​

• 안쪽 끝까지 이동 후에 가장 바깥쪽 요청 트랙으로 이동한다.

SLTF​

• Shortest Latency Time First
• 섹터 큐잉
• 회전 시간의 최적화를 위해 디스크 대기 큐에 있는 여러 요청을 섹터 위치에 따라 재정렬하고 가장 가까운 섹터를 먼저 서비스

RAM 디스크​

• 빠른 속도로 자료를 처리할 필요가 있을 때 주기억장치인 RAM의 일부를 보조기억장치인 디스크처럼 사용하는 것

블로킹​

• 레코드의 입출력 효율을 높이기 위해 여러 개의 논리 레코드를 하나의 블록으로 묶는 것

버퍼링​

• 주기억장치의 일부에 큐 방식으로 동작하는 버퍼
• 하나의 프로그램에서 CPU 연산과 I/O 연산을 중첩시켜 처리하는 방식

파일 구조​

순차 파일​

• 물리적 순서에 따라 저장

인덱스 순차파일​

• 레코드를 키에 따라서 논리적 순서대로 저장하고 시스템은 각 레코드의 실제 주소가 저장된 색인을 관리
• 디스크에 적용되는 방식, 테이프 사용 불가

인덱스 순차파일 구성​

• Prime
• Index
  • 마스터
  • 실린더
  • 트랙
• Overflow

직접 파일​

• 물리적 주소를 통해 직접 액세스되는 파일
• 해싱 함수를 이용해 물리적 상대주소를 계산한 후 해당주소에 레코드를 저장
• DASD의 물리적 주소를 통해 파일의 각 레코드에 직접접근이 가능하여 접근 및 기록의 순서에 제약이 없다.

파일 접근방식​

• queued access method: 레코드 순서를 미리 예상 가능할 때 사용
• basic access method: 물리적 블록의 RW는 액세스 방식이 담당하고 블로킹 및 해체는 사용자가 담당한다.

디스크 공간할당​

연속할당​

• 집약 작업이 필요하다.
• 단편화가 발생할 수 있다.

불연속할당​

섹터지향 할당​

• 동일한 파일에 속하는 섹터들을 연결리스트로 구성하여 할당하는 방식
• 논리적 연결을 탐색하는데 오랜 시간이 필요하고 포인터를 저장할 공간이 필요하다.

블록할당​

• 파일에 액세스할 때 해당 블록을 결정한 후 해당 섹터를 결정해야하는 기법
• 블록체인 기법
• 인덱스 블록체인 기법
• 블록지향 파일사상기법: 포인터 대신 FAT(할당 테이블)에 있는 블록번호를 사용하는 기법

파일 서술자​

• file desriptor, FCB
• 파일이름
• 파일구조
• 보조기억장치에서 파일 위치
• 보조기억장치 유형
• 액세스 제어정보
• 파일 유형
• 생성 일시, 제거 일시
• 최종 수정 일시
• 액세스 횟수

접근제어​

접근제어 행렬​

• 시스템 보호기법으로 행은 사용자 영역, 열은 객체를 나타낸다.

접근제어 리스트​

• ACL
• 각 객체에 댛나 리스트는 영역, 권한, 집합의 순서쌍으로 구성

자격 리스트​

• capability list
• 각 사용자 영역에 대한 자격들로 구성되며 객체와 그 객체에 허용된 연산 리스트

분산파일시스템​

• DFS, Distributed File System
• 여러 대의 서버에 걸쳐 분산되어 저장될 수 있는 계층형 파일시스템

데이터 압축​

비손실 압축​

• Run Length: 문자의 반복을 줄임
• 동적 사전법: 출현빈도에 따라 이진트리나 해시테이블 구성 후 포인터로 대체

손실압축​

• 이미지 압축
• 오디오 압축
• 비디오 압축

프로세스 테이블 정보​

• 프로세스 고유번호, 상위 프로세스 고유번호 (PID, PPID)
• 사용자 이름, 사용자 그룹 이름 (UID, GID)
• 프로세스 현재 상태

장치 드라이버​

• 장치드라이버 디렉터리는 /dev
• 시스템의 각종 디바이스들에 접근하기 위한 디바이스 드라이버들이 저장되어 있는 디렉터리
• 하드디스크에 차지하는 공간이 없는 가상 디렉터리

UNIX의 장치 분류​

• 블록 지향적: 입출력이 버퍼화되고 물리적인 입출력이 블록단위로 수행
• 문자 지향적: 입출력이 버퍼화되지 않고, 물리적 입출력이 문자 단위로 수행, Raw 인터페이스

UNIX의 파일​

• 일반 파일
  • 데이터 파일: 텍스트 데이터 파일, 이진 데이터 파일
  • 실행가능 프로그램 파일
• 디렉터리 파일
• 특수 파일: 주변장치들을 파일이름을 통해 접근 가능
• 파일이름에 공백이 와서는 안 된다.
• 255자까지 가능하다.

파일접근 자료구조​

• 부트 블록
• 슈퍼 블록
• i-node 블록: 각 파일에 대한 metadata가 기록된 고정된 크기의 구조체 블록
  • 파일 소유자 사용번호, 그룹번호
  • 파일의 종류
  • 데이터 블록의 주소
  • 파일의 크기
  • 파일이 생성, 사용, 변경된 시간
  • 파일의 링크 수
• 데이터 블록: 실제 파일블록을 저장하는 데 이용하는 블록

리디렉션​

• 명령어 처리 시 입출력 방향을 지정할 때 사용

UNIX 시스템의 3가지 구성요소

• 쉘
• 커널
• 어플리케이션

자료​

• 현실세계로부터 관찰이나 측정을 통해서 수집된 사실이나 값
• 자료형태는 숫자로 표현되는 수치값이나 문자들로 구성되는 스트링을 포함

정보​

• 어떤 상황에 대한 적절한 의사결정을 할 수 있게 하는 데이터의 유효한 해석이 나 상호 관계
• 자료가 처리되어 발생하는 결과
• 한시성
• 비소모성
• 공공성
• 독점성

자료구조​

• 데이터를 효율적으로 사용할 수 있도록 자료의 특성에 따라 분류하여 구조를 만들어서 저장해 둔 것
• 단순 자료구조: integer, float, char 등 단일자료
• 선형 자료구조: 리스트, 스택, 큐
• 비선형 자료구조: 트리, 그래프
• 파일구조: 보조기억장치에 저장되는 대용량의 자료구조

알고리즘​

• 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법
• 입력, 출력, 명확성, 정확성, 유한성, 효율성, 일반성

순서도​

• 사다리꼴 입출력
• 타원 터미널
• 마름모 비교, 판단
• 육각형 준비

추상​

• 자세한 정보는 감추고 사용자가 자료를 사용하는 데 필요한 정보만 인터페이스를 통해 외부로 노출하는 것

프로시져​

• 추상화 제공
• 재사용 가능
• 여러 프로그래머가 같은 문제를 해결할 수 있게 도와줌
• 구조 파악이 쉽다

프로시져 간 자료 전달 방법​

• Call By Value: 값에 의한 호출, 프로시저를 호출하기 전에 실인수의 값을 계산하고 값을 호출시에 대응되는 국소적 변수인 가인수에 대입함으로써 전달하는 방식
• Call By Reference: 참조에 의한 호출, 주소와 포인터 등 실인수를 참조하기 위한 정보가 가인수에 전달되어 동일한 데이터를 참조하게 되어 호출된 프로시저에서 참조하는 값이 변경되면 실인수의 값도 동일하게 변경된다.

재귀​

• 함수가 직접 자신을 호출하는 방식

공간 복잡도​

• Space Complexity, 프로그램을 실행시켜 완료하는 데 필요로 하는 공간의 양

고정 공간​

프로그램 입출력의 횟수나 크기와 관계없는 공간 요구

가변 공간​

• 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들이 필요로 하는 공간

시간 복잡도​

• 프로그램의 기능을 수행하기 위해 프로그램이 취한 단계수로 표현하는 것

빅오​

• f(n) = O(g(n))은 모든 n, n >= n0에 대해 f(n) <= cg(n)인 조건을 만족하는 두 양의 정수 c와 n0이 존재하기만 하면 f(n) = O(g(n))이다.

배열​

• 같은 자료형과 같은 크기를 가진 원소가 순서를 가지고 만들어진 집합
• 인덱스에 의해 참조

순서 리스트​

• 나열한 원소들 간에 순서를 가지고 있는 리스트
• 평균 이동 횟수 (n+1)/2, 삭제 시 (n-1)/2
• 삽입 삭제시 전체를 밀어야되지만, 기억장소 효율은 가장 좋다.

연결 리스트​

• 공간 제약이 없다.
• 삽입 삭제가 효율적이다.

주소 저장​

• 행 우선: 시작주소 + (행 전체 열 크기 + 열) 원소 크기
• 열 우선: 시작주소 + (열 전체 행 크기 + 행) 원소 크기

희소행렬​

• 행렬의 대부분 원소가 0일 경우 기억공간의 낭비가 발생하므로 0이 아닌 원소만 추출하여 [행 번호, 열 번호, 원소] 쌍으로 2차원 배열에 저장하는 방식
• 연산 측면에선 반복적인 패턴을 찾을 수 없어 비효율적

전치행렬​

• 행과 열을 바꾼 것, B = A^T로 표현
• A^T = A면 대칭행렬

스택​

• 한 끝에서 삽입과 삭제가 일어나는 순서 리스트
• LIFO

시스템 스택​

• 함수가 호출될 때마다 프로그램은 활성 레코드 또는 스택이라는 구조를 생성하고 시스템 스택의 top pointer에 적재한다.

스택의 적용​

• 부프로그램 호출 시 복귀 주소 저장
• 함수 호출의 순서 제어
• 인터럽트 복귀 주소 저장
• 중위 표기식을 후위 표기식으로 변환
• 후위 표기법으로 표현된 산술식 연산
• 0-주소 지정방식의 명령어 자료 저장소
• 재귀 프로그램의 순서 제어
• 컴파일러를 이용한 언어 번역

큐​

• 리스트의 한 쪽에선 원소를 삽입하고 다른 쪽에서는 삭제만 하는 구조
• FIFO
• front pointer: 가장 먼저 삽입된 자료의 포인터
• rear pointer: 가장 나중에 삽입된 자료의 포인터
• 초기 조건: front == rear = -1
• 공백: front == rear = 1 && front == rear
• 가득참: rear = n - 1

원형큐​

• 큐가 가득 찬 후에 첫 번째 큐를 Q[0]에 위치하게 조정하는 배열 이동은 시간이 많이 걸려 원형으로 만듦
• 초기 조건: front == rear == 0
• 삽입 위치: rear = (rear + 1) % n
• 삭제 위치: front = (front + 1) % n
• 공백: front == rear
• 가득참: front == (rear + 1) % n

큐의 적용​

• 작업 버퍼 큐
• 프로세스 스케줄링
• 큐잉 시뮬레이션

데크​

• 원소의 삽입과 삭제가 리스트의 양쪽 끝에서 이뤄지는 자료구조
• 스택과 큐의 결합
• Double Ended Queue

스크롤​

• 입력 제한 테크
• 한 쪽에선 삭제만 가능

셀프​

• 출력 제한 데크
• 한 쪽에선 삽입만 가능

스택 수식 계산​

• 우선순위: 승제 > 가감 > 시프트 > 비교 > 등가 > 비트 > 논리

연결 리스트​

순서 리스트의 문제점

• 삽입 삭제시 많은 이동
• 할당 공간 부족시 재할당
• 표현방법과 기억 공간의 크기가 달라지면 컴파일부터 다시 실행

비사용 기억공간​

• 기억 공간이 필요하여 요청하는 경우 할당해 줄 수 있는 공간

연결 리스트의 응용​

• 다항식 표현

이중 연결 리스트​

• 링크의 방향을 양방향으로 이동할 수 있어 검색 효율성이 좋다.

원형 연결 리스트에서 헤드 노드를 사용하는 이유 모든 원소가 환형으로 연결되어 있기 때문에 무한 루프에 빠질 수 있어 헤드 노드를 두어 리스트의 시작을 알린다.

트리​

• 정보의 검색 및 자료 보관을 위해 널리 사용되고 있는 자료구조
• 사이클을 포함하지 않는 연결 그래프의 일종
• 계층적 자료구조
• 노드와 각 노드를 연결하는 간선으로 구성
• 임의의 노드에서 다른 노드로의 연결은 하나만 가능하다.
• 루트 노드는 하나만 존재
• 트리의 부분 집합은 하나의 트리, 이 것을 서브 트리라고 한다.
• 노드 연결에 순환이 존재하지 않는다.

균형트리​

• B-tree, AVL tree, Red-black tree

용어​

• 노드: 자료를 담는 영역
• 간선: 노드 간의 연결 선
• 차수: 하위 노드의 개수
• 레벨: 계층 구조의 노드의 위치 값
• 높이 또는 깊이: 루트에서 터미널 노드까지의 레벨의 개수
• 터미널 노드: 최하위 노드
• 포리스트: 루트 노드를 제거하고 생기는 서브 트리들

이진 트리​

• 모든 노드의 차수가 2 이하인 특수한 형태의 트리
• 순서트리의 특성을 가지므로 노드의 위치 또는 순서가 중요한 의미를 가진다.
• 편향 이진 트리: 단말노드를 제외한 트리의 구성 노드들이 왼쪽 또는 오른쪽 자식 노드만을 가지는 형태의 트리
• 전 이진 트리: 단말노드를 제외한 노드들이 왼쪽 자식과 오른쪽 자식 노드를 모두 가지고 있는 형태의 트리
• 포화 이진 트리: 단말노드를 제외한 모든 노드의 차수가 2이면서 최하위 자식 노드들이 모두 차여 있는 형태의 트리
• 완전 이진 트리: 루트 노드에서부터 하위 레벨로 순차적으로 왼쪽 자식, 오른쪽 자식 노드 순으로 추가된 트리의 형태
• 균형 이진 트리: 단말 노드의 레벨 값의 차이가 1 이하인 형태 (완전 이진 트리와 포화 이진 트리를 포함)
• 일차원 배열(완전 이진트리로 가정)과 연결 리스트로 표현하는 방법

이진 트리 순회​

• 중위 순회: 좌 루트 우
• 후위 순회: 좌 우 루트
• 전위 순회: 루트 좌 우

이진 트리 정렬​

• 루트부터 비교하면서 작으면 왼쪽 자식, 크면 오른쪽 자식
• 완성되면 중위 순회

스레드 이진 트리​

• 터미널 노드의 null 값의 링크를 조상 노드에 연결해 알고리즘 성능을 향상시키는 방식

히프​

• 완전 이진 트리의 자료구조
• 가장 큰 값이나 가장 작은 값이 완전 이진 트리의 루트에 항상 존재하는 자료구조
• 데이터 목록에서 가장 작은 값이나 가장 큰 값을 빠르게 찾을 수 있도록 구성된 자료구조

우선순위 큐​

• FIFO를 지키면서 우선순위가 부여된 원소는 큐에서 위치와 상관 없이 먼저 출력되는 구조
• 배열, 연결리스트, 히프로 표현이 가능하다.
• 히프 사용시 O(logn)의 복잡도

이진 탐색 트리​

• 이진 트리의 구조로 자료 검색 삭제 및 삽입에 효율적인 자료구조
• 원소들은 유일한 키 값을 가지며 좌측 서브 트리는 루트 값보다 작은 값들로 구성된 이진 탐색트리고 우측 서브 트리는 루트의 값보다 큰 값들로 구성된 이진 탐색 트리로 구성
• 중간 노드 삭제시 왼쪽 서브트리의 최대 원소와 오른쪽 서브트리의 최소 원소를 비교하여 중간 노드 값으로 올린다.
• 최대 높이는 n, 최소 높이는 log₂(n)

선택 트리​

• N개의 원소를 임의의 개수로 나눈 원소를 가진 K개의 목록을 합병 정렬할 목적으로 구성

승자 트리​

• 2개의 자식 노드 중 값이 작은 노드가 승자가 되어 상위 부모 노드로 올라가는 트리

패자 트리​

• 승자 대신 패자 원소를 나타내고 승자는 상위 부모 노드에 올린다.

포리스트​

• 서로 연결되지 않은 여러 개의 서브 트리로 구성된 구조
• 자료 접근에 어려움이 있어 이진 트리로 변환해야 한다.

• 이진트리에서 루트 레벨이 1로 시작할 때 레벨 i에서 최대 노드의 수는 2^(i-1) 개 이다.
• 이진트리에서 깊이가 i라면 최대 노드 수는 2^i-1개다.

그래프​

• 공집합이 아닌 정점들의 유한집합과 공집합도 허용하는 간선들의 유한집합으로 구성
• 완전 그래프: 최대 수의 간선을 가지는 그래프
• 가중 그래프: 간선에 가중치가 할당된 그래프

그래프의 표현​

• 인접 행렬: 간선이 있으면 1 없으면 0
• 인접 리스트: vertex와 link로 표현

그래프 순회​

• 깊이 우선 탐색: 스택
• 너비 우선 탐색: 큐
• 신장 트리: 그래프의 간선들로만 구성되고 그래프의 모든 정점을 포함하는 트리, 사이클이 포함되면 안된다.

최소 비용 신장 트리​

• 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 트리
• 비용은 거리 및 시간을 의미한다.
• Prim, Kruskal, Sollin 알고리즘이 있다.

Prim​

• 가중치가 적은 간선을 선택해 가는 방식

Kruskal​

• 탐욕적 방법
• 매번 선택마다 전체에서 가장 좋다고 생각하는 간선을 선택

그래프의 응용​

PERT/CPM​

• Program Evaluation and Review Technique / Critical Path Method
• PERT: 프로젝트에 필요한 전체 작업의 상호관계를 표현하는 방법
• CPM: 프로젝트 완성에 필요한 작업을 나열하고 작업에 필요한 소요 기간을 예측하는 데 사용하는 기법
• 상세 계획을 수립하기 쉽고 변화나 변경에 대해 바로 대처할 수 있고 네트워크상 문제점을 파악할 수 있고 중점관리가 가능하나 작성에 많은 시간이 든다.

최단 경로​

• Dijkstra 알고리즘: 첫 번째 정점 a에서 최단 경로의 길이인 두 번째 정점을 찾는 알고리즘

탐색​

• 주어진 리스트에서 원하는 키를 찾는 것
• 비교 탐색방법: 탐색 대상의 키를 비교하여 탐색하는 방법, 순차 탐색, 이진 탐색, 이진 트리 탐색
• 계산 탐색방법: 계수적인 성질을 이용하여 계산으로 탐색을 하는 방법, 해싱

순차 탐색​

• 주어진 리스트에서 탐색키와 같은 레코드를 검색하는 방법
• O(n)

이진 탐색​

• 이미 정렬되어 있는 리스트에서 절반을 쪼개가며 값을 찾는 방식
• O(logn)

피보나치 탐색​

• 피보나치 수열을 이용해 중간 값을 계산해 속도가 빠르다.

정렬​

• 내부 정렬: 리스트가 작아 주기억장치에서 모두 정렬이 가능
• 외부 정렬: 외부 기억장치를 이용해 정렬
• 비교식 정렬: 비교하고자 하는 각 키 값들을 한 번에 2개씩 비교하여 교환하는 방식
• 분산식 정렬: 키 값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하여 각 부분집합을 정렬함으로써 전체를 정렬하는 방식

삽입 정렬​

• 정렬되어 있는 값들을 삽입하고자 하는 값과 비교하여 큰 값들은 뒤로 이동한 후 삽입하는 방법
• O(n^2)
• 두번 째 원소를 기준으로 이전의 레코드들과 비교하여 적절한 위치를 찾아 삽입하는 방식

쉘 정렬​

• 매개변수 값을 정하여 매개변수의 값만큼 간격을 가지는 레코드들을 여러 개의 서브 파일로 구성하면서 각 서브 파일을 삽입 정렬방식으로 배열하는 과정을 반복하는 것
• interval은 전체 레코드의 개수의 절반인 interval = n/2에서 시작해 매번 interval = interval / 2로 interval 값이 0보다 큰 경우에 반복 수행한다.
• O(n^1.25)

퀵 정렬​

• 기준값인 피벗을 중심으로 큰 원소들은 오른쪽 부분집합으로 분할하여 정렬하는 방법
• 분할 정복기법
• 정렬할 자료들을 기준값을 중심으로 2개의 부분집합으로 분할하는 작업과 기준값보다 작으면 왼쪽 부분집합으로 크면 오른쪽 부분집합으로 정렬하는 정복 작업을 부분 집합의 크기가 1 이하가 될 때까지 반복한다.
• O(nlog₂n), 최악 O(n^2)

버블 정렬​

• 인접한 2개의 레코드를 비교하여 위치를 서로 교환하는 방식
• 한 회전을 거치면 리스트의 마지막의 가장 큰 레코드가 남게 된다.
• O(n^2)

2원 합병 정렬​

• 이미 정렬된 2개 이상의 배열이 있을 때 이들을 합쳐서 하나의 정렬된 배열을 만드는 것
• O(nlogn)

히프 정렬​

• O(nlogn)
• 히프 트리를 이용해 정렬하는 방식으로 항상 가장 큰 원소가 루트 노드가 되고 삭제 연산을 수행하면 항상 루트 노드의 원소를 삭제하여 반환하게 된다.

선택 정렬​

• 단순한 정렬방법
• 이동하면서 가장 작은 값을 앞으로 보낸다.
• O(n^2)
• 데이터 양이 적을 때 아주 좋은 성능을 낼 수 있다.

기수 정렬​

• 큐를 이용하여 자릿수 (digit) 별로 정렬하는 방식
• 부동소숫점 정렬 불가능
• O(dn)