시나공 정보처리기사 필기 자료 - 값만 다르게 매번 출제되는 필수 계산 41문제
릴레이션 : 표
카디널리티 : 튜플의 수
차수(Degree) : 속성 수
도메인 : 하나의 속성이 취할 수 있는 (원자)값들의 집합
<기억장치 관리 - 배치 전략>
First Fit(최초 적합) : 배치 가능한 빈 영역 중 첫 번째 분할 영역에 배치시키는 법
Best Fit(최적 적합) : 배치 가능한 빈 영역 중 내부 단편화를 가장 작게 남기는 분할 영역에 배치시키는 법
Worst Fit(최악 적합) : 배치 가능한 빈 영역 중 내부 단편화를 가장 많이 남기는 분할 영역에 배치시키는 법
* 내부 단편화 : 프로그램이 할당된 후 사용되지 않고 남아 있는 빈 공간
<정렬>
Bubble Sort(버블 정렬) : 앞에서부터 인접한 두 개의 레코드 키 값을 비교하여 크기에 따라 작은 값을 앞에 배치하기 위해 위치를 서로 교환하는 정렬 방식
| ex) 초기 상태 : 85624 1회전 - 85624 => [58624 -> 56824 -> 56284 -> 56248] 결과 : 56248 2회전 - 56248 => [52648 -> 52468] 결과 : 52468 3회전 - 52468 => [25468 -> 24568] 결과 : 24568 4회전 - 24568 |
Selection Sort(선택 정렬) : n회전마다 n번째 레코드와 n번째 레코드 뒤에 값을 차례대로 비교하면서 최소값을 n번째 레코드에 위치치키는 정렬 방식
| ex) 초기 상태 : 85624 1회전 : 85624 => [58624 -> 58624 -> 28654 -> 28654] 결과 : 28654 2회전 : 28654 => [26854 -> 25864 -> 24865] 결과 : 24865 3회전 : 24865 => [24685 -> 24586] 결과 : 24586 4회전 : 24586 => [24568] 결과 : 24568 |
Insert Sort(삽입정렬) : n+1번째 레코드를 앞의 값과 비교하여 삽입위치 지정 후 다른 레코드를 한 칸씩 밀고 해당 위치에 삽입하는 정렬 방식
| ex) 초기 상태 85624 1회전 : 85624 -> 58624 ( 5를 8과 비교 후 5를 8 앞으로 삽입) 2회전 : 58624 -> 56824 (6을 5,8과 비교 후 6을 8 앞에 삽입) 3회전 : 56824 -> 25684 (2를 5,6,8과 비교 후 2를 5 앞으로 삽입) 4회전 : 25684 -> 24568 (4를 2,5,6,8과 비교 후 4를 5 앞으로 삽입) * 만약 n회전 때 n+1번째 레코드 위치 변화가 없으면 바로 다음 회전으로 넘어감 |
<프로젝트 일정 계획 기법>
CPM(Critical Path Method, 임계 경로 기법)
: 프로젝트 완성에 필요한 작업을 나열하고, 작업에 필요한 소요 기간을 예측하는데 사용하는 기법
○ 원형노드 - 각 작업 의미
○ 박스 노드 - 이정표 의미
○ 간선 - 작업 사이의 전후 의존 관계
* 이전 작업이 완료된 후 다음 작업을 진행할 수 있
○ 임계 경로 : 최장 경로 의미
PERT(Program Evaluation and Review Technique, 프로그램 평가 및 검토 기술)
: 프로젝트에 필요한 전체 작업의 상호 관계를 표시하는 네트워크로 각 작업별로 낙관적인 경우, 가능성이 있는 경우, 비관적인 경우로 나누어 각 단계별 종료 시기를 결정하는 방법
○ 작업 예측치 = (비관치 + 4*기대치 + 낙관치) / 6
○ 평방 편차 = {(비관치 - 낙관치) / 6}^
○ 원 노드 - 각 작업 의미
○ 간선 - 낙관치, 기대치, 비관치를 순서대로 표시
○ 과거에 경험이 없어 소요 기간 예측이 어려운 소프트웨어에서 사용
간트 차트(Time-Line Chart, 시간선 차트)
: 프로젝트 작업 일정을 막대 도표를 이용하여 표시하는 프로젝트 일정표
○ 중간 목표 미달성 시 그 이유와 기간 예측 가능
○ 다양한 형태로 변경하여 사용할 수 있어 자원 배치나 인원 계획에도 유용하게 사용 가능
○ 작업 경로 표시 X, 계획의 변화에 대한 적응성 약함
○ 이정표, 작업 일정, 작업 기간, 산출물로 구성
○ 계획 수립 또는 수정 때 주관적 수치에 기울어지기 쉬움
○ 사용자와의 문제점이나 예산의 초과 지출 등도 관리할 수 있음
<세그먼트>
세그먼트 : 프로그램을 배열이나 함수 등과 같은 논리적인 크기로 나눈 단위, 각 세그먼트는 고유한 이름과 크기 존
세그먼테이션(Sagmentation) 기법 : 가상기억장치에 보관되어 있는 프로그램을 다양한 크기의 논리적인 단위로 나눈 후 주 기억장치에 적재시켜 실행시키는 기법
○ 주소 변환을 위해서 세그먼트가 존재하는 위치 정보를 가지고 있는 세그먼트 맵 테이블이 필요
○ 내부 단편화는 발생하지 않으나 외부 단편화는 발생할 수 있음
물리 주소 = 세그먼트의 시작주소 + 변위값
논리 주소(세그먼트 번호, 변위값) 으로 표시
<페이지 교체 알고리즘>
LRU(Least Recently Used) : 최근에 가장 오랫동안 사용하지 않은 페이지를 교체
LFU(Least Frequently Used) : 사용 빈도가 가장 적은 페이지를 교체
OPT(OPTimal replacement, 최적 교체) : 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체
FIFO(First In First Out) : 가장 오래 있었던 페이지를 교체
SCR(Second Chanve Replacement, 2차 기회 교체) : FIFO 기법의 단점 보완하는 기법, 가장 오래 있었던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것
NUR(Not Used Recently) : 최근에 사용하지 않은 페이지를 교체, LRU에서 나타나는 시간적인 오버헤드 줄임, 최근 사용 여부 확인을 위해 각 페이지마다 참조 비트와 변형 비트가 사용됨
* 페이지 결함 - 참조 페이지가 페이지 테이블에 없을 경우 페이지 결함(부재) 발생
<블랙박스 테스트>
블랙박스 테스트 : 소프트웨어가 수행할 특정 기능을 알기 위해 각 기능이 완전히 작동되는 것을 입증하는 테스트
○ 소프트웨어 인터페이스에서 실시되는 기능 테스트
○ 테스트 과정의 후반부에 적용
-종류
동치 분할 검사(Equivalence Partitioning Testing, 동치 클래스 분해)
: 입력 자료에 초점을 맞춰 테스트 케이스를 만들어 검사하는 방법,
타당한 입력 자료와 타당하지 않은 입력 자료를 통해 해당 입력자료에 맞는 결과가 출력되는지 확인하는 기법
경계값 분석(Boundary Value Analysis)
: 입력 조건의 경계값을 테스트 케이스로 선정하여 검사하는 기법, 입력 자료에만 치중한 동치 분할 검사 기법 보완
원인-효과 그래프 검사(Cause-Effect Graphing Testing)
: 입력 데이터 간의 관계와 출력에 영향을 미치는 상황을 체계적으로 분석한 다음 효용성이 높은 테스트 케이스를 선정하여 검사하는 기법
오류 예측 검사(Error Guessing)
: 과거의 경험이나 확인자의 감각으로 테스트하는 기법, 보충적 검사 기법이며 데이터 확인 검사라고도 함
비교 검사(Comparison Testing)
: 여러 버전의 프로그램에 동일한 테스트 자료를 제공하여 동일한 결과가 출력되는지 테스트하는 기법
<관계대수>
관계대수 : 관계형 데이터베이스에서 원하는 정보를 검색하기 위한 절차적인 언어
○ 피연산자도 릴레이션, 결과도 릴레이션임
-종류
순수 관계 연산자
Select(σ) - 튜플 중에서 선택 조건을 만족하는 튜블의 부분합을 구하여 새로운 릴레이션을 만드는 연산
Project(π) - 속성 리스트에 제시된 속성 값만을 추출하여 새로운 릴레이션을 만드는 연산, 단 중복 제거
릴레이션의 열(세로)에 해당하는 속성을 추출하는 것이므로 수직 연산자라고도 함
Join(▷◁) - 공통 속성을 중심으로 두 개의 릴레이션을 하나로 합쳐서 새로운 릴레이션을 만드는 연산
Division(÷) - R의 속성이 S의 속성값을 모두 가진 튜플에서 S가 가진 속성을 제외한 속성만을 구하는 연산
일반 집합 연산자
Union(합집합,∪) - 두 릴레이션의 합집합을 구하되 중복되는 튜플은 제거되는 연산
Intersection(교집합,∩) - 두 릴레이션의 교집합을 구하는 연산
Difference(차집합, -) - 두 릴레이션의 차집합을 구하는 연산
Cartesian Product(교차곱, ×) - 두 릴레이션에 있는 튜플들의 순서쌍을 구하는 연산
<리눅스>
umask : UNIX에서 파일이나 디렉터리의 초기 권한을 설정할 때 사용하는 값
파일의 경우 666에서 umask를 뺀 값이 초기 접근 권한
디렉토리의 경우 777에서 umask를 뺀 값 초기 접근 권한
<주요 스케줄링 알고리즘>
프로세스 스케줄링
FCFS(First Come First Service, 선입 선출)
: 준비상태 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 기법
SJF(Shortest Job First, 단기 작업 우선)
: 준비상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU 할당하는 기법
HRN(Hightest Response-ratio Next)
: 대기 시간과 서비스(실행) 시간을 이용하여 우선순위를 정해 CPU를 할당하는 기법
○ 우선순위 계산식 = (대기 시간 + 서비스 시간) / 서비스 시간
디스크 스케줄링
SSTF(Shortest Seek Time First)
: 현재 위치에서 가장 가까운 거리에 있는 트랙의 요청을 먼저 서비스하는 기법
<LOC 기법>
LOC(원시 코드 라인 수, source Line Of Code) 기법
: 소프트웨어 각 기능의 원시 코드 라인 수의 비관치, 낙관치, 기대치를 측정하여 예측치를 구하고 이를 이용하여 비용을 산정하는 기법
○ 노력(인월) = 개발기간 X 투입 인원 = LOC / 1인당 월평균 생산 코드 라인 수
○ 개발 기간 = 노력(인월) / 투입인원
○ 개발 비용 = 노력(인월) X 단위 비용(1인당 원평균 인건비)
○ 생산성 = LOC / 노력(인월)
노력(인월)
-----------------------------
개발 기간 * 투입 인원
< 트리>
트리 : 노드와 선분을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태
노드(Node): 트리의 기본 요소, 자료 항목과 다른 항목에 대한 가지를 합친 것
근 노드(Root Node) : 트리의 맨 위에 있는 노드
디그리(Degree, 차수) : 각 노드에서 뻗어 나온 가지의 수
단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 디그리가 0인 노드
자식 노드(Son Node) : 어떤 노드에 연결된 다음 레벨의 노드들
부모 노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드들
형제 노드(Bother Node, Sibling) : 동일한 부모를 갖는 노드들
트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수
<트리 운행법>
- Preorder(전위 순회) 운행 : Root -> Left -> Right 순으로 운행
순서 : ABDGHECFIJ
- Inorder(중위 순회) 운행 : Left -> Root -> Right 순으로 운행
순서 : GDHBEAIFJC
- Postorder(후위 순회) 운행 : Left -> Right -> Root 순으로 운행
순서 : GHDEBIJFCA
<방향/무방향 그래프의 최대 간선 수>
무방향 그래프 - n(n-1)/2
방향 그래프 - n(n-1)
<수식 표기법>
- PreFix(전위 표기법) : 연산자 -> Left -> Right
- InFix(중위 표기법) : Left -> 연산자 -> Right
- PostFix(후위 표기법) : Left -> Right -> 연산자
○ 수식 표기법 전환 방법
- Infix를 Prefix나 Postfix로 변환하기
ex) X = A / B * (C + D) + E
○ Prefix로 변환하기
① 연산 우선순위에 따라 괄호로 묶기 => ( X = ( ( ( A / B ) * ( C + D ) ) + E ) )
② 연산자를 해당 괄호 앞으로 옮기기 => = ( X + ( * ( / ( A B ) + ( C D ) ) E ) )
③ 괄호 제거하기 => = X + * / A B + C D E
○ Postfix로 변환하기
① 연산 우선순위에 따라 괄호로 묶기 => ( X = ( ( ( A / B ) * ( C + D ) ) + E ) )
② 연산자를 해당 괄호 뒤으로 옮기기 => ( X ( ( ( A / B ) * ( C + D ) ) + E ) )
③ 괄호 제거하기 => X A B / C D + * E + =
-Postfix나 Prefix를 Infix로 변환하기
○ Prefix를 Infix로 변환하기
ex) = X + * / A B + C D E
① 인접한 피연산자 두 개와 왼쪽의 연산자를 괄호로 묶기 => ( = X ( + ( * ( / A B ) ( + C D ) ) E ) )
② 연산자를 두 피연산자 가운데로 이동 => ( X = ( ( ( A / B ) * ( C + D ) ) + E ) )
③ 필요 없는 괄호 제거하기 => X = A / B * (C + D) + E
○ Postfix를 Infix로 변환하기
ex) X A B / C D + * E + =
① 인접한 피연산자 두 개와 오른쪽의 연산자를 괄호로 묶기 => ( X ( ( ( A B / ) ( C D + ) * ) E + ) = )
② 연산자를 두 피연산자 가운데로 이동 => ( X = ( ( ( A / B ) * ( C + D ) ) + E ) )
③ 필요 없는 괄호 제거하기 => X = A / B * (C + D) + E
<팬인/팬아웃>
팬인(Fan-In) : 모듈을 제어(호출)하는 모듈의 수
팬아웃(Fan-Out) : 모듈에 의해 제어(호출)되는 모듈의 수
ex) F의 팬인 : 2 팬 아웃 : 1
<스택>
스택 : 리스트의 한 쪽 끝으로만 자료의 삽입, 삭제 작업가 가능한 자료 구조
○ 스택은 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출방식으로 자료 처리
○ 오버플로(Overflow) : 스택의 모든 기억 공간이 꽉 채워져 있는 상테에서 데이터가 삽입될 때 발생
○ 언더플로(Underflow) : 삭제할 데이터가 없는 상태에서 데이터를 삭제할 때 발생
<순환복잡도>
순환복잡도(Cyclomatic) : 한 프로그램의 논리적인 복잡도를 측정하기 위한 소프트웨어의 척도
계산법 ① 내부 영역(n)과 외부영역(1)의 합 ② 화살표 수 - 노드 수 + 2
<그래프 탐색 방법>
DFS(Depth First Search, 깊이 우선 탐색)
: 시작 노드의 인접한 노드 중 자식 노드 방향으로 운행하며 형제 노드와 자식 노드가 있을 때 자식 노드를 우선 탐색하는 기법
BFS(Breadth First Search, 너비 우선 탐색)
: 시작 노드에서 간선이 1개인 가장 가까운 노드들부터 우선 탐색 후 다음 노드를 탐색하는 기법
Tree 구조에서 같은 Level의 노드부터 탐색 후 다음 레벨의 노드 탐색
<이분 검색>
이분 검색(Binary Search, 이진 검색) : 첫 번째 값과 마지막 값의 중간 값과 찾으려는 값을 비교하는 검색방식
○ 순서화된 파일에서만 사용 가능
○ M(중간 레코드 번호) = { F(첫 번째 레코드 번호) + L (마지막 레코드 번호) } / 2
CIDR(Classless Inter-Domain Routing, 클래스 없는 도메인간 라우팅 기법)
: IP 주소와 함께 슬래시(/) 뒤에 숫자를 추가하여 네트워크 주소와 서브넷 마스크를 결합한 형태
○ 슬래시(/) 뒤에 있는 숫자가 서브넷 마스크 1의 개수를 뜻함
서브넷 마스크(Subnet Mask) : 4바이트의 IP 주소 중 네트워크 주소와 호스트 주소를 구분하기 위한 비트
○ 서브넷 마스크를 변경하여 네트워크 주소를 여러 개로 분할하여 사용 가능
○ 서브넷 마스크는 각 클래스마다 다르게 사용됨
○ 서브넷 마스크는 0~255사이의 4개의 숫자와 각 숫자 사이에 온점(.)으로 구성 ex) 255 . 255 . 255 . 192
○ 앞에 세개의 숫자는 네트워크 주소, 뒤에 마지막 숫자는 호스트 주소를 나타냄
| 8비트 | 10진수 |
| 00000000 | 0 |
| 10000000 | 128 |
| 11000000 | 192 |
| 11100000 | 224 |
| 11110000 | 240 |
| 11111000 | 248 |
| 11111100 | 252 |
| 11111110 | 254 |
| 11111111 | 255 |
IPv4 CIDR 표기법에 대한 이해 - CIDR 계산기