[2022/09/12 복습] 헷갈리는 자료구조론 - 정렬, 검색, 해싱

myu030 (59)in Korea • 한국 • KR • KO • 2 years ago (edited)

매일 공부한 거 복습하는 겸 글 쓰는 게 목표였는데 게을러서 또 엄청 빼먹었네요. 하지만 이제는 진짜 1~2일에 한 번은 꼭 쓰려구요..!!
그리고.. 오늘부터는 원래 오전 6~7시에 스테픈하려 했는데 늦게 인나서 9시쯤 했네요. 그래도 아침으로 스테픈 루틴을 바꾼 거에 의미를 둬야겠어요~😀이제 일찍 일어나서 스테픈 하고 와서 복습 정리하고 하루를 시작하려구요!

4일간 공부량: 몇 문제인지 생각 안나지만 아무튼.. 아무튼 공부량 적음..!!!😥
헷갈리는 자료구조론: 정렬(2원 합병 정렬, 힙 정렬, 퀵 정렬, 기수 정렬), 검색(선형검색, 이진검색, 블록검색), 해싱(개념, 해싱함수 종류, 오버플로 처리)

2원 합병 정렬
▶ 두 개 이상의 서브파일을 합병하여 하나의 정렬된 파일을 생성하는 방법
▶ 퀵 정렬과 마찬가지로 분할정복 방식
힙 정렬
▶가장 큰 키값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬
퀵 정렬

▶ 입력 자료를 특정한 키(제어키, pivot)를 기준으로 2개의 부분 리스트(작은 값을 갖는 자료들과 큰 값을 갖는 자료)로 분리하여 한 개의 파일을 논리적으로 두 개의 파일로 재배열하고 각각 서브 파일에 대해 순환적으로 퀵 정렬을 사용
▶ pivot 원소 선정 방법에 따라 정렬의 수행시간이 달라짐. 최선의 경우는 두 부분으로 나눠어졌을 때 중앙값의 원소가 pivot으로 선정될 경우(= 양쪽 리스트 크기가 같은 경우)
▶순환 알고리즘을 사용해야 하므로 스택 필요
▶분할과 정복 기법
▶이미 정렬된 자료를 퀵 정렬 시
최악의 수행시간: O(n²)
분할 횟수: n-1번
기수 정렬(Radix Sort)

▶ 하나의 레코드를 구성하고 있는 자릿수(digit)만큼의 버킷을 준비하여 각 자릿수들을 해당 버킷에서 순서대로 분류하는 정렬.(비교 정렬X)
▶ 특징
버킷은 큐 사용
큐의 수는 진법(Radix) 수만큼 필요
큐의 길이는 최악의 경우 레코드 수만큼 필요
포인터 필요

검색
▶비교에 의한 분류: 선형검색, 블록검색, 이진트리검색, 제어검색(이분검색, 피보나치검색, 보간검색)
제어검색: 자료 정렬돼 있어야 함.
▶계산에 의한 분류: 해싱
▶평균검색장(Average Search length): 검색 단위 동작의 평균 비교 횟수
평균검색장 = 각 자료를 검색하는 비교횟수의 총합 / 검색을 요구한 비교횟수
검색별 비교
▶선형검색(순차검색): O(n)
▶이진검색: O(log₂n)
▶이진검색트리: O(log₂n)
▶블록검색: √n
선형검색(순차 검색)
▶정렬되지 않은 레코드도 검색 가능한 장점
▶파일 크기가 커질수록 검색시간이 증가하는 단점
▶평균검색장(L) = (n +1)/2
이진 검색(이분 검색)
▶레코드의 집합을 두 부분으로 나눠서 탐색하고자 하는 키를 갖는 레코드가 어느 부분에 속하는가를 결정하여 그 부분에 대하여 순환적으로 탐색을 수행
▶분할정복 탐색 기법
▶알고리즘
(K:검색키, K_m: 중간값
l: 파일의 첫 번째 데이터 위치, h: 파일의 마지막 데이터 위치, m: 파일의 중간 데이터 위치)
K> K_m 이면, l = m+1
K = K_m이면, 원하는 레코드를 찾았으므로 끝냄
K < K_m이면, h= m-1
m = ⌊(l+h)/2⌋
블록검색
▶정렬된 순차 리스트에 삽입, 삭제가 빈번히 발생하는 경우에 제어 탐색을 적용하려면 재정렬해야 하는 번거로움이 생기는데 이를 피하기 위해 고안된 탐색 방법
▶블록 내의 레코드는 순차적일 필요 없지만,
블록과 블록은 일정한 규칙에 따라 정렬되어 있어야 함.
이진트리 검색
▶중위운행 시 항상 오름차순
▶키 결정 위해 나눗셈 사용.
반면, 피보나치 검색은 덧셈과 뺄셈을 이용.
나눗셈은 덧셈, 뺄셈보다 시간이 많이 걸리기 때문에 탐색에 있어서 비효율적.
해싱
▶ 주로 컴파일러나 어셈블러의 심볼테잉블과 빠른 액세스가 필요한 파일 등에서 사용.
▶용어
(1) 충돌: 동일한 버킷 주소 가지는 경우
(2) 오버플로: 해당 주소 버킷이 가득 찼을 때.
충돌이 발생하면 항상 오버플로가 발생하는 것이 아님.
충돌이 발생하면 빈 슬롯에 저장하고, 빈 슬롯이 없으면 오버플로가 발생.
(버킷 수와는 관련X, 슬롯과 관련 O)
(3) 버킷: 해싱함수에 의해 계산된 주소에 자료를 기억시키기 위한 장소
(4) 슬롯: 한 개의 레코드를 저장할 수 있는 것으로 n개의 슬롯이 모여 하나의 버킷을 이룸.
(5) 동의어(Synonym): 서로 다른 심볼이 동일한 버킷주소를 가질 대, 즉, 두 식별자 I₁과 I₂에 대해 h(I₁) = hI₂ 인 경우에 I₁과 I₂를 h에 대한 동거자(동의어)라고 함.
▶ 적재밀도: 적재율이 높으면 오버플로 발생 확률⬆
적재율 = 레코드 크기 / 공간크기 = 식별자수 / (슬롯 수 * 버킷 수)
해싱함수의 종류
▶숫자분석법(Digit Analysis, 계수분석법, 비트추출법)
키가 취할 수 있는 모든 키 값들에서 그 키를 구성하는 자릿수들의 분포를 조사하여 비교적 고른 분포를 보이는 자릿수들을 필요한 만큼 택하는 방법

▶제산법(Division)
버킷의 크기에 근접하는 수로 키값을 나눈 나머지를 홈주소로 사용
h(x) = x % M
해싱 테이블의 크기보다 약간 작은 소수를 M의 값으로 선택하는 것이 좋음

▶접지법(Folding)

➖이동접지(shift folding): 마지막을 제외한 모든 부분들을 이동시켜 최하위 비트가 마지막 부분의 자리와 일치하도록 맞춘 뒤, 서로 다른 부분들을 더하여 주소를 얻음.
➖경계접지(boundary folding): 식별자의 각 부분들을 종이 접듯이 경계에서 겹치게 한 후, 같은 자리에 위치한 수들을 더하여 함수를 얻음. 각 부분들을 하나씩 건너서 반대로 만든 다음 더하는 것과 같음.

▶중간제곱법(Mid-Square)
키 값을 제곱하여 그 수의 중간 일부분을 추출하여 홈주소로 사용

▶기수 변환법(Radix Conversion)
키 값의 진법으르 다른 진법으로 변환한 결과에서 홈주소를 구함

▶무작위법(Pseudo Random)
난수 발생시켜 홈주소 구함. 충돌이 발생하면 다음 난수 이용.

▶대수적 코딩법(Algebraic coding)
키의 각 자리수를 다항식의 계수로 보고, 이 다항식을 해시표 크기에 의해 정해진 다항식으로 나눈 나머지 다항식의 계수를 홈주소로 하는 방식
해싱에서 오버플로 처리
▶선형조사법(Linear Probing)
➖충돌이 일어난 자리에서 그 다음 버킷들을 차례로 하나씩 검색하여 최초로 나오는 빈 버킷에 그 데이터를 저장
후속 주소: h₁(k) = h₀(k) + 1
➖오버플로 발생 시 색인의 증가를 1
➖키 값들이 어느 한 곳에 모이는 제1밀집(First clustering) 현상이 발생.

▶2차 조사법(Quadratic Probing)
➖오버플로 발생 시 색인의 증가를 이차함수로 하여 빈 버킷 조사
➖제2밀집현상 발생

▶2차계수조사법(Quadratic Quotient Probing)
➖제2밀집 현상 제거 위한 방법
➖키 k로부터 산출되는 몫을 i²에 곱하여 후속 주소로 함.

▶연결체인법(Linked Chaining)
➖폐쇄 주소법
➖해싱 테이블 자체를 포인터의 배열로 만들고 같은 버킷에 배당되는 데이터들을 체인(마지막 레코드의 링크 필드가 NULL인 연결리스트)으로 만들어서 연결
➖삽입, 삭제 시 큰 어려움이 없다는 장점이 있지만, 포인터 연산 수행 위해 동적인 기억장소 할당 필요
➖레코드에 링크 필드를 마련하여 동거자(동의어)끼리 연결리스트를 구성하는 방법으로 가장 많이 사용되는 충돌 해결방법 중 하나

▶이중 해싱(Double hashing)
➖충돌 발생시 두번재 해싱함수 적용.
첫 번째 해싱함수는 홈주소, 두번째 해싱함수는 조사간격.

▶재 해싱(Rehasing)
오버플로가 발생하면 다른 해싱함수로 홈주소를 다시 구함.
계속해서 오버플로 발생시 또 다른 해싱함수를 계속 적용시킴.

▶오버플로 공간 처리법
별도의 오버플로 공간을 마련해 두고, 오버플로 발생 시 해당 레코드를 모두 오버플로 공간에 저장

▶난수방법
➖난수 발생시킨 후 더해서 주소를 결정
h₁(k) = h₀(k) + 난수
➖해싱함수의 무작위법과 구분됨.