[정처기 필기] 「2」 | 데이터 입 / 출력 구현 - (1.2) 정렬, 검색 - 이분 검색 / 해싱

[정처기 필기] 「2」 | 데이터 입 / 출력 구현 - (1.2) 정렬, 검색 - 이분 검색 / 해싱

「1」 소프트웨어 설계

> 「2」 소프트웨어 개발

- > 데이터 입 / 출력 구현, 통합 구현, 제품 소프트웨어 패키징, 애플리케이션 테스트 관리, 인터페이스 구현

「3」 데이터베이스 구축

「4」  프로그래밍 언어 활용

「5」  정보시스템 구축 관리

 

1 자료구조

2 트리(Tree)

> 3 정렬(Sort)

> 4 검색 - 이분 검색 / 해싱

5 데이터베이스 개요

6 절차형 SQL

3. 정렬(Sort)

삽입 정렬(Insertion Sort)

  

가장 간단한 정렬 방식, 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬

 

- 두 번째 키, 첫 번째 키 비교, 순서대로 나열(1회전), 세 번째 키를 첫 번째, 두 번째 키와 비교해 순서대로 나열(2회전), n번째 키를 n - 1개의 키와 비교하여 알맞은 순서에 삽입

- 평균, 최악 O(n²)

 

초기 상태		8	5	6	2	4
1회전		8	5	6	2	4	→	5	8	6	2	4
2회전		5	8	6	2	4	→	5	6	8	2	4
3회전		5	6	8	2	4	→	2	5	6	8	4
4회전		2	5	6	8	4	→	2	4	5	6	8

 

     : 비교 중       : 교환 발생       : 고정

 

쉘 정렬(Shell Sort)

 

삽입 정렬을 확장 한 개념

 

- 입력 파일이 어떤 매개변수(h) 값으로 서브파일을 구성하고, 각 서브파일을 삽입 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식

- 임의의 레코드 키와 h값만큼 떨어진 곳의 레코드 키를 비교하여 순서화되어있지 않으면 서로 교환하는 것을 반복하는 정렬 방식

- 입력 파일이 부분적으로 정렬 되어있는 경우 유리한 방식

- 평균 O(n ¹·⁵), 최악 O(n²)

 

선택 정렬(Selection Sort)

 

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

 

- 평균, 최악 O(n²)

 

초기상태			8	5	6	2	4
1회전			5	8	6	2	4	→	5	8	6	2	4
								→	2	8	6	5	4	→	2	8	6	5	4
2회전			2	6	8	5	4	→	2	5	8	6	4	→	2	4	8	6	5
3회전			2	4	6	8	5	→	2	4	5	8	6
4회전			2	4	5	6	8
최종			2	4	5	6	8

 

     : 비교 중       : 교환 발생       : 고정

 

버블 정렬(Bubble Sort)

 

- 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교, 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식

- 계속 정렬 여부를 플래그 비트(f)로 결정

- 평균, 최악 O(n²)

 

초기상태			8	5	6	2	4
1회전			5	8	6	2	4	→	5	6	8	2	4
								→	5	6	2	8	4	→	5	6	2	4	8
2회전			5	6	2	4	8	→	5	2	6	4	8	→	5	2	4	6	8
3회전			2	5	4	6	8	→	2	4	5	6	8
4회전			2	4	5	6	8
최종			2	4	5	6	8

 

     : 비교 중       : 교환 발생       : 고정

 

퀵 정렬(Quick Sort)

 

레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나눠가며 정렬, 키를 기준으로 작은 값 왼쪽에, 큰 값 오른쪽 서브파일로 분해시키는 방식

 

- 위치에 관계없이 임의의 키를 분할 원소로 사용

- 프로그램에서 되부름을 이용, 스택 필요

- 분할(Divide), 정복(Conquer)을 통해 자료 정렬

: 분할 - 기준값인 피봇(Pivot)을 중심으로 정렬할 자료를 2개의 부분집합으로 나눔

: 정복 - 부분집합의 원소 중 피봇보다 작은 원소들은 왼쪽, 피봇보다 큰 원소들은 오른쪽 부분집합으로 정렬

- 부분집합의 크기가 더 이상 나눠지지 않을 때까지 반복 수행

- 평균 O(nlog₂n), 최악 O(n²)

 

힙 정렬(Heap Sort)

 

전이진 트리(Complete Binary Tree)를 이용한 정렬 방식

 

- 구성된 전이진 트리를 Heap Tree로 변환, 정렬

- 평균, 최악 O(nlog₂n)

- 전이진 트리의 노드의 역순으로 자식 노드와 부모 노드 비교하여 큰 값 위로 올림

 

17  19  >  19  ⑨                 ↙                              ↘                 ↙                                                    ↘                   ↙                                                                          ↘
↙  14   16  |  18  >  18  ⑧             ↙                    ↘			↘                                 13   19  |  17  >  17  ⑦ ↙          ↘
↙ 15   18  |  16  >  16  ⑥ ↙          ↘		↘                                 16   14  >  14  ⑤	↙ 19   13  >  13  ④	↘                   11  >  11  ③
↙ 18   15  >  15  ②	↘                 12  >  12  ①

 

     : 교환 발생       : 고정

 

2-Way 합병 정렬(Merge Sort)

 

이미 정렬 돼 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식

 

- 두 개의 키들을 한 쌍으로, 각 쌍에 순서를 정함

- 순서대로 정렬된 각 쌍의 키들을 합병하여, 하나의 정렬된 서브리스트 만듦

- 정렬된 서브리스트들을 하나의 정렬된 파일이 될 때까지 반복

- 평균, 최악 O(nlog₂n)

 

초기상태	71	2	38	5	7	61	11	26	53	42
1회전	(  2	71  )	(  5	38  )	(  7	61  )	(  11	26  )	(  42	53  )
2회전	(  2	5	38	71  )	(  7	11	26	61  )	(  42	53  )
3회전	(  2	5	7	11	26	38	61	71  )	(  42	53  )
4회전	(  2	5	7	11	26	38	42	53	61	71  )
최종	2	5	7	11	26	38	42	53	61	71

 

     : 비교 중       : 교환 발생       : 고정

 

기수 정렬(Radix Sort) == Bucket Sort

 

Queue를 이용하여 자릿수(Digit)별로 정렬하는 방식

 

 - 레코드의 키 값을 분석하여, 같은 수 또는 같은 문자끼리 순서에 맞는 버킷에 분배하였다가, 버킷의 순서대로 레코드 꺼내어 정렬

- 평균, 최악 O(dn)

4. 검색 - 이분 검색 / 해싱

이분 검색(Binary Search)

 

- 이분 검색(이진 검색)은 전체 파일을 두 개의 서브파일로 분리, Key 레코드 검색하는 방식

- 반드시 순서화된 파일이어야 검색 가능

- 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교해 가며 검색

- 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로 탐색 효율 좋고, 탐색 시간 적게 소요

- 중간 레코드 번호 M = (F + L) / 2 (F : 첫 번째 레코드 번호, L : 마지막 레코드 번호)

- 첫 번째 값(F), 마지막 값(L)을 이용하여 중간값 M을 구하여 찾으려는 값을 비교

 

ex) 1 ~ 100 중 15를 찾는데 걸리는 횟수?

 

M = (1 + 100) / 2  = 50 (정수만 취함) : 1회 비교

> 50은 찾으려는 값보다 큼, 1 ~ 49 사이

M = (1 + 49) / 2 = 25 : 2회 비교

> 25는 찾으려는 값보다 큼, 1 ~ 24 사이

M = (1 + 24) / 2 = 12 (정수만 취함) : 3회 비교

> 12는 찾으려는 값보다 작음, 13 ~ 24 사이

M = (13 + 24) / 2 = 18 (정수만 취함) : 4회 비교

> 18은 찾으려는 값보다 큼, 13 ~ 17 사이

M = (13 + 17) / 2 = 15 : 5회 비교

> 15는 찾으려는 값과 같음, 총 5회 비교

 

해싱(Hashing)

 

해시 테이블(Hash Table)이라는 기억 공간을 할당, 해시 함수(Hash Function)를 이용하여 레코드 키에 대한 해시 테이블 내의 홈 주소(Home Address)를 계산, 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행

 

해시 테이블(Hash Table)

레코드 한 개 이상 보관할 수 있는 버킷들로 구성된 기억 공간, 보조기억장치이나 주기억장치에 구성

 

- 버킷(Bucket) : 하나의 주소를 갖는 파일의 한 구역, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수

- 슬롯(Slot) : 한 개의 레코드를 저장할 수 있는 공간, n개의 슬롯이 모여 하나의 버킷 형성

- Collision(충돌 현상) : 서로 다른 두 개 이상의 레코드가 같은 주소 가짐

- Synonym : 충돌로 같은 홈 주소를 갖는 레코드들의 집합

- Overflow : 계산된 홈 주소의 버킷 내에 저장할 기억 공간이 없는 상태, 버킷을 구성하는 슬롯이 여러 개일 때 Collision은 발생해도 Overflow는 발생하지 않을 수 있음

 

해싱 함수(Hashing Function)

- 제산법(Division) : 레코드 키(K)를 해시 테이블의 크기보다 큰 수 중 가장 작은 소수(Prime, Q)로 나눈 나머지를 홈 주소로 삼는 방식, h(K) = K mod Q

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

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

- 기수 변환법(Radix) : 키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단, 주소 범위에 맞게 조장

- 대수적 코딩법(Algebraic Coding) : 키 값을 이루는 각 자리 비트 수를 한 다항식의 계수로 간주, 다항식을 해시표의 크기에 의해 정의된 다항식으로 나눠 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식

- 숫자 분석법(Digit Analysis, 계수 분석법) : 키 값을 이루는 숫자의 분포를 분석, 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식

- 무작위법(Random) : 난수를 발생시커 나온 값을 홈 주소로 삼는 방식

 

>Collision(충돌 현상) 해결 방법<

 

- 체이닝(Chaining) : 버킷에 할당된 연결리스트에 데이터를 저장하는 방법

- 개방 주소법(Open Addressing) : 순차적으로 그다음 빈 버킷을 찾아 데이터를 저장하는 방법

- 재해싱(Rehashing) :  새로운 해싱 함수로 새로운 홈 주소를 구하는 방법

 

 

 

 

 

 

 

 

 

 

출처 | <시나공> 정보처리기사 필기 2024 기본서 (길벗알앤디)