2024 정보 처리 기사 필기 요약(9)

 

소프트웨어 개발 - 2

 

필수암기 363선

 

81. 퀵 정렬(Quick Sort)

● 레코드의 만은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법으로, 키를 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽 서브파일로 분해시키는 방식으로 정렬한다.

● 분할(Dicide)과 정복(Conquer)을 통해 자료를 정렬한다.

 

82. 삽입 정렬(Insertion Sort)

예) 8, 5, 6, 2, 4를 삽입 정렬로 정렬하시오.

● 1회전 : 두 번째 값 5를 첫 번째 값과 비교하여 첫 번째 자리에 삽입하고 8을 한 칸 뒤로 이동시킨다.

● 2회전 : 세 번째 값 6을 첫 번째, 두 번째 값과 비교하여 8자리에 삽입하고 8을 한 칸 뒤로 이동시킨다.

● 3회전 : 네 번째 값 2를 처음부터 비교하여 맨 처음에 삽입하고 나머지를 한 칸씩 뒤로 이동시킨다.

● 4회전 : 다섯 번째 값 4를 처음부터 비교하여 5자리에 삽입하고 나머지를 한 칸씩 뒤로 이동시킨다.

 

83. 선택 정렬(Select Sort)

● n 개의 레코드 중에서 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1) 개 중에서 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬한다.

 

84. 버블 정렬(Bubble Sort)

● 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환한다.

 

85. 힙 정렬(Heap Sort)

● 전이진 트리를 이용한 정렬 방식이다.

● 평균과 최악 모두 시간 복잡도는 O(nlog2 n)이다.

 

86. 2-Way 합병 정렬(Merge Sort)

● 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식이다.

● 평균과 최악 모두 시간 복잡도는 O(nlog2 n)이다.

 

87. 테스트와 디버깅의 목적

● 테스트(Test)를 통해 오류를 발견한 후 디버깅(Debugging)을 통해 오류가 발생한 소스 코드를 추적하며 수정한다.

 

88. 이분 검색(이진 검색)

● 반드시 순서화(정렬)된 파일이어야 검색할 수 있다.

● 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어든다.

● 탐색 효율이 좋고 탐색 시간이 적게 소요된다.

● 중간 레코드 번호(M) : (F+L)/2

(단,  F : 첫 번째 레코드 번호, L :  마지막 레코드 번호)

 

89. 주요 해싱 함수

● 제산법(Division) : 레코드 키(K)를 해시표(Hash Table)의 크기보다 큰 수 중에서 가장 작은 소수(Prime, Q)로 나눈 나머지를 홈 주소로 삼는 방식

● 제곱법(Mid-Square) : 레코드 키 값(K)을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식

● 폴딩법(Fording) : 레코드 키 값(K)을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합)한 값을 홈 주소로 삼는 방식

● 숫자 분석법(Digit Analysis) : 키 값을 이루는 숫자의 분호를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식

 

90. 스키마 3 계층

● 외부 스키마 : 사용자나 응용 프로그래머가 각 개인의 입장에서 필요로 하는 데이터베이스의 논리적 구조를 정의한 것

● 개념 스키마 : 데이터베이스의 전체적인 논리적 구조로서, 개체 간의 관계와 제약 조건을 나타내고, 데이터베이스의 접근 권한, 보안 및 무결성 규칙에 관한 명세를 정의함

● 내부 스키마 : 물리적 저장장치의 입장에서 본 데이터베이스 구조로서, 실제로 데이터베이스에 저장될 레코드의 형식을 정의하고 저장 데이터 항목의  표현 방법, 내부 레코드의 물리적 순서 등을 나타냄