정보처리기사 - 소프트웨어 개발(1장) 정리

데이터 입●출력 구현

 

자료구조

 

자료 구조의 분류

• 선형 구조 : 배열, 선형 리스트, 스택, 큐, 데크
• 비선형 구조 : 트리, 그래프

 

연결 리스트

• 노드의 삽입, 삭제 작업이 용이하다
• 연결을 위한 링크 부분이 필요하다.
• 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다
• 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.

 

스택

• 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어진다.
• 후입선출(LIFO)
• 스택을 이용한 연산은 '재귀호출, 후위 표기법, 깊이 우선 탐색' 과 같이 왔던 길을 되돌아가는 경우에 사용

 

스택의 응용 분야

• 함수 호출의 순서 제어
• 인터럽트의 처리
• 수식 계산 및 수식 표기법
• 컴파일러를 이용한 언어 번역
• 부 프로그램 호출 시 복귀 주소 저장
• 서브루틴 호출 및 복귀 주소 저장

 

스택의 삽입과 삭제
PUSH로 자료 입력, POP으로 자료 출력

 

큐

• 리스트의 한쪽에서는 삽입 작업이 반대쪽에서는 삭제 작업이 이루어지는 자료구조
• 선입선출(FIFO)

 

데크

• 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료구조
• 입력은 한쪽에서만 출력은 양쪽에서 일어날수 있는 입력 제한과 그 반대의 경우도 가능(출력 제한)

 

방향/무방향 그래프의 최대 간선 수

• N개의 정점으로 구성된 무방향 그래프에서 최대 간선 수 = N(N-1)/2
• N개의 정점으로 구성된 방향 그래프에서 최대 간선 수 = N(N-1)

 

인접행렬을 이용한 그래프 표현 방법

• 방향 그래프에서 방향 간선이 있으면 행렬의 P_ij = 1, 없으면 P_ij = 0
• 무방향 그래프에서 서로 인접하면 P_ij = 1, 인접 하지 않으면 P_ij = 0

 

트리

 

트리의 개요

• 트리는 노드와 브랜치을 이용하여 사이클을 이루지 않도록 구성한 그래프의 트수한 형태
• 디그리(차수) : 각 노드에서 뻗어나온 가지의 수
• 단말 노드 : 자식이 하나도 없는 노드 = 디그리가 0인 노드

 

트리의 운행법

• preorder 운행법은 ROOT → LEFT → RIGHT
• inorder 운행법은 LEFT → ROOT → RIGHT
• postorder 운행법은 LEFT → RIGHT → ROOT

 

수식의 표기법

• prefix 표기법은 연산자 → 피연산자1 → 피연산자2
• infix 표기법은 피연산자1 → 연산자 → 피연산자2
• postfix 표기법은 피연산자1 → 피연산자2 → 연산자

 

정렬

 

삽입 정렬

• 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬
• 복잡도 O(n²)

 

쉘 정렬

• 삽입 정렬을 확장한 개념
• 임의의 레코드 키와 매개변수(h)의 값만큼 떨어진 곳의 레코드 키를 비교하여 순서화되어 있지 않으면 서로 교환하는 정렬 방식
• 복잡도 O(n^1.5) → O(n²)

 

선택 정렬

• n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾는 방식을 반복하여 정렬
• 복잡도 O(n²)

 

버블 정렬

• 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하여 정렬
• 복잡도 O(n²)

 

퀵 정렬

• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법
• 분할과 정복을 통해 자료를 정렬
• 정렬 방식중에서 가장 빠름
• 복잡도 O(nlog₂n) → O(n²)

 

힙 정렬

• 전이진 트리를 이용한 정렬 방식
• 복잡도 O(nlog₂n)

 

2-way 합병 정렬

• 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
• 복잡도 O(nlog₂n)

 

기수 정렬

• 큐를 이용하여 자릿수 별로 정렬하는 방식
• 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배 하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
• 복자도 O(dn)

 

검색-이분검색 / 해싱

 

이분 검색(이진 검색)

• 반드시 정렬된 파일이어야 검색할 수 있다.
• 비교 횟수를 거듭할 때마다 검색 대상이되는 데이터의 수가 절반으로 줄어든다.
• 탐색 효율이 좋고 탐색 시간이 적게 소요된다.
• 중간 레코드 번호(M) : (F+L)/2

 

주요 해싱 함수

• 제산법 : 레코드 키를 해시표의 크기보다 큰 수 중에서 가장 작은 소수로 나눈 나머지를 홈 주소로 삼는 방식
• 제곱법 : 레코드 키 값을 제곱한 ㅎ 그 중간 부분의 값을 홈주소로 삼는 방식
• 폴딩법 : 레코드 키 값을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 xor한 값을 홈 주소로 삼는 방식
• 숫자 분석법 : 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식

 

체이닝
Collision이 발생하면 버킷에 할당된 연결 리스트에 데이터를 저장하여 문제를 해결하는 방법

 

데이터베이스 개요

 

DBMS의 필수 기능

• 정의 기능 : 모든 응용 프로그램들이 요구하는 데이터 구조를 지원하기 위해 데이터베이스에 저장될 데이터의 형과 구조에 대한 정의, 이용 방식, 제약 조건 등을 명시하는 기능
• 조작 기능 : 데이터 검색, 갱신, 삽입, 삭제 등을 체계적으로 처리하기 위해 사용자와 데이터베이스 사이의 인터페이스 수단을 제공
• 제어 기능 : 데이터베이스를 접근하는 갱신, 삽입, 삭제 작업이 정확하게 수행되어 데이터의 무결성이 유지되도록 제어하는 기능

 

스키마 3계층

• 외부 스키마 : 사용자나 응용 프로그래머가 각 개인의 입장에서 필요로 하는 데이터베이스의 논리적 구조를 정의한 것
• 개념 스키마 : 데이터 베이스의 전체적인 논리적 구조로서, 개체 간의 관계와 제약 조건을 나타내고, 데이터베이스의 접근 권한, 보안 및 무결성 규칙에 관한 명세를 정의
• 내부 스키마 : 물리적 저장장치의 입장에서 본 데이터베이스 구조로서, 실제로 데이터베이스에 저장될 레코드의 형식을 정의하고 저장 데이터 항목의 표현 방법, 내부 레코드의 물리적 순서 등을 나타냄