상세 컨텐츠

본문 제목

알고리즘 -2 퀵 정렬, 머지정렬, 이진탐색, 이진탐색트리 ···

Tips/1-2

by 코보소 2019. 10. 16. 23:36

본문

반응형

- Quick Sort

 

평균적으로 볼 때 가장 좋은 성능인 O(nlogn)을 갖는 비교 기반 알고리즘이다.

특정한 킷값을 기준으로 주어진 입력 리스트의 원소를 적당히 이동시키면서 다음의 두 조건이 만족하도록 왼쪽과 오른쪽의 두 개의 서브리스트로 분할한다.

 

피벗(Pivot) : 퀵 정렬에서 리스트의 분할을 위한 특정한 키.

대게 가장 왼쪽의 원소를 피벗으로 정함.

 

퀵 정렬의 핵심은 주어진 리스트를 피벗을 기준으로 두 개의 서브리스트로 분할하는 것이다.

피벗이 제자리를 잡도록 하여 정렬하는 방식

 

 

1. L은 오른쪽으로 이동하며 R은 왼쪽으로 이동한다.

2. L은 피벗보다 작은 값이 위치하며, R은 피벗보다 큰값만 위치한다.

3. 만약 L > R 경우 LR값의 위치를 바꾸어 준다.

4. R의 인덱스값이 L보다 작을 경우 예) R[index] < L[index] R과 피벗을 바꾸어준다.

5. 1 cycle 종료,

 

Quick sort 분할정복 형식이다.

 

분할 : 정렬할 n개 원소를 피벗을 중심으로 두 개의 서브리스트로 분할한다.

정복 : 두 서브리스트에 대해 퀵 정렬을 각각 순환적으로 적용하여 두 서브리스트를 정렬한다.

결합 : 이 과정에서 결합은 필요 없다.

 

리스트 분할 과정은 단순히 리스트의 크기에 비례하여 O(n)의 수행 시간을 갖는다.

서브리스트의 크기는 까지 다양하게 나올수 있다.

최선의 수행시간은 O(nlogn)이 된다.

최악의 경우 : 피벗이 리스트에서 항상 최대값, 최소값이 되는 경우

 

 

 

 

 

- Merge sort

 

쪼갤 수 없을 때 까지 리스트 원소를 쪼갠다. 그리고 인접한 원소 간 비교하여 작은 값은 좌측 큰 값은 우측으로 정렬 한다.

 

 

합병 정렬(Merge Sort)의 분할정복 방법은 아래와 같다.

 

분할 : 정렬할 n개의 원소를 n/2의 원소를 갖는 두 서브리스트로 분할한다.

정복 : 두 서브리스트에 대해 합병 정렬을 각각 순환 적으로 적용하여 두 서브 리스트를 정렬한다.

결합 : 정렬된 두 서브리스트를 합병하여 원래의 정렬된 리스트를 만든다.

평균 수행 시간모두 O(nlogn)이다.

 

 

탐색 알고리즘

 

원하는 데이터를 효율적으로 찾기위한 방법

 

1. 순차 탐색

 

- 리스트에 데이터가 연속적으로 저장되어 있는 경우 일반적으로 적용되는 방법이다.

 

크기가 n인 선형 리스트에서 순차 탐색의 최악의 시간복잡도는 O(n)이고, 평균 비교 횟수는 (n+1)/2가 되기 때문에 데이터의 양이 많은 경우 비효율적이다.

 

단 입력이 리스트이지만 하면 언제라도 적용 가능한 탐색알고리즘이고, 데이터가 정렬되지 않은 경우에 적합하다.

 

2. 이진탐색

 

이진탐색은 주어진 데이터가 Key 값에 미리 정렬되어 있는 경우에 적용할 수 있다.

 

탐색키 = 중앙원소값 탐색 성공

탐색키 > 중앙원소값 이진탐색(리스트 전반부, 우측)

탐색키 < 중앙원소값 이진탐색(리스트 후반부, 좌측)

 

탐색 되는 대상의 데이터 개수가 1/2 로 줄어들기 때문에 시간복잡도는 O(nlogn)이다.

 

데이터가 정렬된 경우 우수한 성능을 보이지만, 삽입/삭제 연산과 같은 동적 연산이 많은 응용분야에는 적합하지 않다.

 

3. 이진 탐색 트리

 

이진탐색트리는 어떤 노드에 대해서도 다음의 두가지 성질을 만족하는 이진트리이다.

한 노드의 왼쪽 서브트리에 있는 모든 킷값은 그 노드의 Key 값보다 작다.

한 노드의 오른쪽 서브트리에 있는 모든 Key 값은 그 노드의 Key 값보다 크다.

 

3.1 탐색

   

루트에서부터 원하는 킷값을 갖는 원소를 찾아나가는 방식이다.

3.2 삽입

 

이진 탐색 트리에서 새로운 원소의 삽입은 삽입할 원소를 탐색하다가 비교할 노드가 없으면(탐색 실패한 경우) 그 위치에 새로운 노드를 삽입한다.

 

3.3 삭제

 

이진탐색 트리에서 원소의 삭제는 삭제할 원소를 탐색한 후 찾은 노드를 삭제하고 남은 노드들의 위치를 조절해주어야한다.

 

조절하기 위해선 이진트리의 성질에 만족하여야한다.

 

후속자 노드(Successor Node) : 어떤 노드의 바로 다음 킷값을 갖는 노드.

 

후속자 노드

7 15 22 30 35 40 44 5588

 

7의 후속자 (Successor Node)15

15의 후속자(Successor Node)22

...

 

 

 

 

 

 

 

 

 

 

삭제되는 노드의 자식의 개수에 따라 다음과 같이 구분한다.

 

. 자식이 없는 리프(Leaf)노드 일 경우 위치 조절이 필요 없다. 7, 22, 40, 88은 리프 노드이므로 그냥 삭제해주면 된다.

 

. 자식이 하나만 있으면 자식노드를 삭제하고 노드의 위치를 위로 올리면 서브트리도 그냥 따라 올라오게 된다.

 

자식이 두 개 모두 있다면, 후속자 노드를 삭제되는 노드의 위치로 올리면 서브트리도 따라 올라온다.

 

15를 지울 경우 15의 후속자 노드인 22를 위로 올리면 된다.

 

 

3.4 문제점

 

전체 노드의 개수가 n개 일 때, 탐색과정은 최대 logn번의 노드를 비교 하여 최선, 평균 탐색시간 O(logn)을 갖는다.

 

경사진 이진트리가 형성되면 최악의 탐색시간인 O(n)을 갖는다.

 

 

 

 

4. 해싱

 

해싱은 데이터의 키 값을 이용해서 데이터의 저장 장소를 계산하고, 이를 이용해서 데이터를 저장/탐색 하는 방법이다.

키가 주어지면 이에 대응되는 함수가 필요로하면 이를 해시함수(hash Function)이라고 한다,

 

충돌 : 서로 다른 키 값을 가진 데이터임에 불구하고 같은 저장주소에 대응되는 경우가 발생 하는 것

   

 

4.1 계산 잔여법(Division remainder hashing, modulo division)

 

저장 공간 크기를 m 이라할 때

m의 선택의 주의

m에 따라서 해시 테이블의 크기가 자동으로 결정됨.

충돌 발생 가능성을 최소화 하도록 선점

- 해시 테이블의 크기보다 작은 소수로 선택하는 것이 바람직하다.

 

바람직한 해시 함수

계산이 용이 해야 한다.

각 키 값을 테이블의 각 슬롯에 균등하게 사상 시킬수 있어야함.

 

4.2 중간 제곱법

- 키 값은 제곱한 결과에서 중간 부분의 적당한 크기 자릿수를 취하는 방법

 

4.3 폴딩법

 

키 값 K 0001110111010000

중간으로 반으로 나눈다.

00011101 11010000

 

연산을 한다. (예 덧셈, XOR , AND)

00011101

11010000

ADD -----------

11101101 237 연산된 곳을 주소로 사용한다.

 

 

4.4 기수 변환법

 

어떤 진법으로 표현된 키를 다른 진법으로 표현 된다고 간주하고 키를 변환하는 방법

 

1370 주소값에 저장

 

4.5 자릿수 추출법

- 키 가 취할수 있는 모든 키 값들에게서 그 키를 구성하는 자릿수들의 분포를 조사하여 비교적고른 분포로 보이는 자릿수 들을 필요한 만큼 택하는 방법

 

모든 킷값을 알고 있는 경우 에만 사용

빈번한 삽입 삭제의 경우에는 킷값 분포를 다시 조사해야 하기 때문에 비효율적

 

- 충돌 해결법

 

연쇄법 : 데이터들을 연결리스트를 사용하여 연결시키는 방법

 

개방주소법 : 충돌이 발생하면 새로운 데이터를 위치 할 수 있는 빈 공간을 찾는 것

선형 탐사법, 이차형 탐사, 이중 해싱 이 있다.

 

선형 탐사법

충돌이 발생한 인덱스와 인접한 다음 인덱스에 빈 공간에 데이터를 저장하는 방법

1차 클러스터링 문제가 발생

 

클러스터링 문제 : 점유된 위치가 연속적으로 나타내어 탐색속도를 느리게 하여 발생하는 성능저하 문제

 

이차형 탐사

충돌이 발생한다면 빈 공간을 찾기위해 2차원 함수를 사용하여 빈공간을 계산한다.

2차 클러스터링 문제 발생한다.

 

이중 해시

충돌이 발생하였을 때, 또 다른 해시 함수를 사용하여 두 번째 이후 탐사 위치를 결정하여 첫 번째탐사 위치와 독립성을 이룬다.

 

 

 

반응형

관련글 더보기

댓글 영역