🏷️ 2025 정보처리기사 필기 요점정리 2과목 소프트웨어개발(1)
🏷️ 정보처리기사 필기 요점정리
2과목 소프트웨어개발
📢 선형 구조
|
배열
|
동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합
|
|
선형
리스트
|
① 연속 리스트(Contiguous List)
구조간단, 빠르다, 중간 삽입,삭제가 번거롭다
② 연렬리스트(Linked List)
포인터를 이용하여 서로 연결시킨 자료구조.
노드의 삽입,삭제가 용이, 연속적이지 않아도 저장이 가능, 포인터가 필요하기 때문에 공간효율이 좋지 않다
|
|
스택
|
한쪽 끝으로만 삽입,삭제 가능, LIFO(Last In First Out)구조, 삽입-PUSH, 삭제-POP
(부프로그램 호출시 복귀주소, 함수 호출순서 제어, 인터럽트 복귀주소, 수식 계산 및 수식 표기법 등)
|
|
큐
|
한쪽에선 삽입이 다른한쪽은 삭제가. 선입선출 방식 FIFO(First In First Out)
운영체제의 작업 스케줄링에 사용
|
|
데크
|
삽입과 삭제가 리스트의 양끝에서 모두 발생
입력제한 : Scroll, 출력제한 : Shelf
|
📢 비선형구조
|
트리 : 정점, 선분을 가지는 사이클을 이루지 않도록 구성
자료 간 계층 관계를 가진 계층형 자료구조
|
|
그래프 : 정점과 간선의 두 집합으로 이루어짐
방향그래프 : 최대간선수 : n (n-1) , 무방향그래프 : n (n-1) / 2의 최대 간선수를 가진다
|
📢 트리(Tree)
TREE
위 그림의 트리에서 살펴보기
트리의 차수(Degree) : 가지수가 가장 많은 수 : 3
단노드 : 자식이 하나도 없는 노드 ( K, L, F, G, M, I, J )
레벨(Depth) : 4
부모노드 : D, 자식노드 : H, I, J
📢 트리의 운행법
운행방법 : 루트의 위치를 기준으로 in-order (왼- 루트- 오), pre-order(루트-왼-오), post-order(왼-오-루트)
1) Inorder : 루트 A를 기준으로 왼쪽의 B를 기준으로하는 트리와 오른쪽 C를 기준으로 하는 트리로 구분 : 색단계를 기준으로 표현해보면 ( lert - root - right )
DBAGEHCF
2) Preorder : root-left-right
ABDCEGHF
3) Postorder : left-right-root
DBGHEFCA
📢 수식의 표기법
위의 트리 운행법을 산술식에서 Infix, Prefix, Postfix로 표기하는 방법
1) X=A/B*(C+D)+E를 Prefix로 바꾸기
현재 연산자가 가운데 있으므로 Infix표기법인데 이를 Prefix로 바꾸기 위해서는 우선순위를 먼저 생각하기
X = A / B * (C+D) + E
1 +CD
2 /AB * +CD
3 * /AB +CD
*/AB+CD + E 에서
4 +*/AB+CDE
결과) +*/AB+CDE
2) X=A/B*(C+D)+E를 Postfix로 바꾸기 ... 위의 방식대로 바꾸면
1 CD+
2 AB/
3 AB/CD+*
4 AB/CD+*E+
📢 정렬(Sort)
각 레코드를 특정키 항목을 기준으로 오름차순 또는 내림차순으로 재배열하는 작업
1) 버블정렬 : 인접한 노드를 비교하여 서로 교환해가는 형식
1회전 : 5 8
6 8
2 8
4 8
5 6 2 4 8 .... 두개씩 비교하면서 교체하다보면 맨 마직막 값이 결정됨
2회전 :
2) 선택정렬 : 선택된 노드와 다른 노드를 비교하여 교환해 가는 방식
1회전 : 2 5 6 8 4 ... 이때 첫번째 값은 결정 됨
2회전 : 2 4 6 8 5 ... 두번째 값부터 비교하면 자료 결정
3) 삽입정렬 : 두 번째 노드부터 시작하여 앞의 값과 비교하여 적절한 위치에 끼워 넣는 방식
1회전 : 5 8 6 2 4 ......... 교체되는 두값이외의 값은 그대로
2회전 : 5 8 6 2 4 ......... 6을 앞의 두값과 비교해서 해당위치에 배치하고 다른 값은 그대로 ...
4) 2-way merge : 두자료씩 묶어가며 처리하는 방식
1회전 : 2, 71 5, 38, 7, 61, 11, 26, 42, 53
( 2, 71, 5, 38 ) ( 7, 61, 11, 26 ) ( 42, 53 )
2회전 : 2, 5, 38, 71, 7, 11, 26, 61, 42, 53
5) 퀵 정렬(Quick Sort) : 키를 기준으로 작은값은 왼쪽, 키보다 큰값은 오른쪽으로 (분할과 정복을 통해 자료 정렬)
정렬 방식 중에서 가장 빠른 방식. 스택이 필요
1회전 : 2, 4, 3 5 8, 6, 9
이런 방법으로 부분집합의 크기가 더 이상 나눠질 수 없을 때까지 분할과 정복을 반복 수행하기
기분 피봇을 기분으로 분할(Divide)과 정복(Conqure)을 중심으로 ...
📢 검색(Search)
이분검색 : 반드시 순서대로 정렬되어 있어야 함
시작과 끝값을 2로 나눠서 중간값을 비교해서 검색하는 방식 (예: 12찾기)
(예) (1+15)/2 = 8... 8과 검색값 12를 비교해서 찾고자하는 값이 8보다 크기때문에 8부터아래의 값은 버림
(9+15)/2 = 12 찾음
단) 2로 나눈값이 소수점이 있으면 정수값을 이용하게 됨
해싱 : 해시테이블에 해시함수를 이용하여 자료의 저장과 검색을 수행하는 방식
[ 검색방법 ]
키 값에 대해서 해시 함수를 계산하여 주소를 구하고
구한 주소에 해당하는 해시 테이블로 바로 이동
해당 주소에 찾는 항목이 있으면 검색 성공,
없으면 검색 실패
특징)
접근속도는 빠르나 기억공간이 많이 요구
다른 방식에 비해 검색속도가 빠르다
삽입, 삭제 작업의 빈도가 많을 때 유리
키-주소 변환 방법이라고도 함
용어)
. 슬롯 : 한 개의 레코드를 저장할 수 있는 공간
. 버킷 : 하나의 주소를 갖는 파일의 한 구역 ( 버킷의 크기는 같은 주소에 포함될 수 있는 레코드수 )
. Collision(충돌현상) : 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상
. Synonym : 충돌로 인해 같은 Home Address를 갖는 레코드들의 집합
. Overflow : 계산된 Home Addressd의 버킷내에 저장할 공간이 없는 상태
. 재해싱(Rehashing) : Collision이 발생하면 새로운 해싱함수로 새로운 홈 주소를 구하는 방식
해싱함수들
제산법(나머지 연산자 사용), 제곱법, 폴딩법(XOR함수), 기수변환법, 숫자분석법, 대수적 코딩법, 무작위법
모두 모두 응원합니다!!!