뻔뻔한블로그

AVL나무

왼쪽 작은 나무의 높이와 오른쪽 작은 나무의 높이가 같거나 하나 차이나는 나무를 말한다.

AVL나무의 각 노드는 균형도라는 수치를 가지고 있는데 이는 왼쪽 작은 나무의 높이에 오른쪽 작은 나무의 높이를 뺀 값을 의미하며, 이 값의 절대 값이 클수록 나무 모양이 불균형하다는 뜻이 된다.

결국 AVL트리는 이진 검색트리이면서 동시에 균형을 유지하고 있는데, 균형이란 왼쪽과 오른쪽 높이의 차이가 1이하인 상태이다. (-1, 0 ,1)

이런 균형적인 구조를 지켜야 검색 시의 효율성을 보장할 수 있기 때문이다.

위에서 설명한대로 

[균형도 = 왼쪽노드 레벨 - 오른쪽 노드 레벨]

식으로 계산하여 균형도는 절대값이 0과 1사이에 이어야 한다.

두 번째 그림처럼 균형이 무너진 유형중 하나인 LL구조이다.

AVL 불균형 구조는 회전방향과 회전 횟수에 따라 4가지로 구분된다.

1. LL : 균형도가 2인 경우

2. RR : 균형도가 -2인 경우

LL반대로 코드는 생략

3. RL :

4. LR

이분검색

이미 정렬된 배열에 대해서 검색하는 알고리즘이다. 순차 검색과 달리 자료를 정렬이라는 방법으로 조직한다. 그래서 검색은 간단하지만 자료를 삽입하거나 삭제할 때는 자료의 구조를 깨뜨리지 않아야 하는 어려움이 있다.

이분검색방법

1. 자료의 집합은 크기순으로 정렬되어 있어야한다.

2. 이미 정렬된 자료 집합에 대해 이분 검색법은 자료의 중간값을 우선 검사한다. 이 자료의 중간값이 찾는 키값이 아니라면 중간값과 키값의 크기를 비교하여 왼쪽 구간이나 오른쪽 구간을 선택한다.

3. 그리고 그 구간에 대해서 똑같은 방법으로 중간값과 키값의 크기를 비교한다.

검색

[탐색 방법]

① 구간의 중간값을 구한다.

② if(중간값 < 키값) 오른쪽 구간또는 왼쪽 구간을 선택한다.

삽입

[삽입 방법]

① key가 들어갈 위치를 찾는다.

② 삽입할 공간을 만든다

③ 공간에 자료를 삽입하고 자료수를 증가시킨다.

삭제방법은

순차검색알고리즘 삭제방법과 동일

이분 검색은 삽입과 삭제의 어려움 때문에 삽입과 삭제가 적은 거의 고정적인 자료집합에 유리하다.

검색알고리즘

검색이란?

특정한 구조로 구성되어 있는 자료의 집합에서 주어진 키에 해당하는 레코드를 찾아내는 것

단순히 자료를 찾는 것에만 국한되는 것이 아니라 자료가 새로 추가되고 삭제될 때 어떻게 이 자료들의 특정한 구조를 계속 유지하느냐하는 문제도 포함되어있다.

순차검색(선형검색)

주어진 자료 파일에서 처음부터 검색키에 해당하는 레코드를 순차적으로 비교하여 찾는 가장 단순한 검색 방법

장점 : 데이터를 따로 조작할 필요가 없어 단순

단점 : 리스트의 길이가 길면 비효율

시간의 복잡도 : O(n)

1. 별다르게 조직화가 필요없다.

2. N개의 자료에 대해서 평균적으로 N/2번의 비교를 해야한다.

검색

[검색 방법]

① 첫 번째 원소부터 시작하여 마지막 원소까지 순서대로 키 값이 일치하는 원소가 있는지를 비교하여 찾는다.

② 키 값이 일치하는 원소를 찾으면 그 원소가 몇 번째 원소인지를 반환한다.

③ 마지막 원소까지 비교하여 키 값이 일치하는 원소가 없으면 찾은 원소가 없는 것이므로 검색 실패

개선 :검색한 키를 선두로 옮기는 과정

삭제

[삭제 방법]

① 삭제하려는 키가 어디에 있는지 탐색한다.

② 찾으려는 키가 나올때 까지 한칸씩 당기고 배열의 자료수를 하나 감소 시킨다

삽입

[삽입 방법]

① 배열의 인덱스를 하나 증가하고 배열의 제일 뒤에 key를 덧 붙인다.

② 그런 뒤 삽입위치를 리턴

퀵정렬

빠른속도와 간단 원리

연속적인 분할에 의해서 정렬한다.

축값을 중심으로 왼쪽은 이 축값보다 작은 값으로 오른쪽은 모두 이 축값보다 큰 값으로 배열시키는 것이다.

이 과정을 분할의 크기가 1이 될 때까지 반복하면 전체적으로는 정렬이 완료된다.

퀵 정렬의 전략

<퀵 정렬 알고리즘 (a, N)>

1.만약 n > 1이면

1.1 N의 크기의 a 배열을 분할하여 축값의 위치를 mid로 넘긴다.

1.2 퀵 정렬 알고리즘(a,mid)

1.3 퀵 정렬 알고리즘(a+mid+1,N-mid-1)

왼쪽구간 부터 우선적으로 분할을 하고, 그 다음에 오른쪽 부분에 대해서 분할을 시작한다.

쉘 정렬 처럼 멀리 떨어져 있는 요소끼리 교환을 하기 때문에 빨리 정렬된 상태로 변화된다.

난수나, 반쯤 정렬된 배열에 대해서는 빠른 속도를 보이지만 이미 정렬된 배열이나 역순 배열에 대해서는 성능이 매우 떨어진다.
(빠른 알고리즘이란 최대한 적은 비교와 교환이다. 퀵정렬은 피벗에 모두 순차적으로 비교하게 되므로)

퀵소트 비재귀 버전

쉘정렬

삽입정렬은  정렬된 배열에 대해서는 매우 뛰어난 성능을 보이지만 그렇지 않은 경우에는 속도가 매우 느리다

ex) 역순 배열의 경우 제일 작은 키값이 제일 뒤에 있으므로 N번의 비교와 이동을 해야한다.

이 문제를 해결하기 위해 h만큼의 간격으로 떨어진 레코드를 삽입하는 정렬

4중 루프가 된 것을 제외하고는 삽입 정렬과 비슷하다.

쉘 정렬의 개선

h = (h-1)/3은 풀어쓰면 h = h/3 -1/3이 되며 1/3으로 취급하기 때문에 h = h/3

<결과>

쉘정렬은 O(NlogN)을 가지는 알고리즘들에 비해서는 속도면에서는 약간 떨어지지만 10,00이하의 자료 정도라면 쉘 정렬이 오히려 더 빠를 수가 있다.

O(NlogN)을 가지는 다른 알고리즘처럼 추가적인 메모리가 필요 하지 않는다.

학습참고 : C로배우는 알고리즘

삽입정렬

많은 비교와 적은 교환으로 특징인 선택 정렬과 반대로 적은 비교와 많은 교환이 이루어지는게 특징이다.

삽입 정렬의 전략

이미 정렬이 된 부분에 새로운 키를 적절한 장소에 삽입하는 동작을 반복적으로 하는 정렬 방법이다.

[루프안에 a[i]보다 t를 쓰는것이 더 빠르다(단순히 t의 값만 읽어 오기 때문)]

삽입정렬은 안정성이 있는데, 항상 그런것은 아니다. (>=t 경우)

이미 정렬된 배열일 경우 매우 빠른 속도를 가진다.

이미 정렬된 경우에는 삽입 정렬의 실행 시간은 N에 비례하는 선형적인 특성을 가진다.

둘째로 삽입 정렬은 역순의 경우 최악의 경우가 된다. 이동과 비교의 횟수는 N*(N-1)/2가 되어서 선택 정렬보다 속도가 떨어진다.

삽입 정렬의 최적화

a[0]값에 -1을 집어넣고 실제 값들은 이후의 저장하도록 하자

그러면 while문에 루프의 판단문에서 j>0과 같은 비교문을 하나 없앨 수 있다.

이런 방법을 사용하게 되면 정렬의 실행시간이 약간 단축되고 N이 클 경우 더 단축

(키값의 최소값을 정하지 못하는 경우가 있기 때문에 신중히 사용해야한다.)

간접정렬

교환이 많은 삽입정렬이기에 간접정렬이 고려된다.

레코드의 배열은 전혀 손대지 않고 따로 만든 인덱스의 배열을 조작하는 방법

비교는 실제 배열a이 하지만 while루프 내의 교환 작업은 index배열을 사용한다.

a에는 아무 변화가 없지만 index배열에는 정렬된 순서가 저장되어 있다.

제일 첫 번째 레코드가 무엇인지 알려면 a[index[0]]와 같이 접근 하면 알 수 있다.

실제로 a 배열을 정렬 하려면 아래와 같은 함수가 필요할 것이다.

학습참고 : C로배우는 알고리즘

정렬알고리즘

정렬이란 임의의 순서대로 배열되어 있는 자료의 집합을 일정한 순서대로 재배열하는 것을 의미

정렬의 방법론

= > 판단과 교환을 어떻게 적절히 조합하는가에 대한 방법론.

정렬을 하는 대상을 파일이라고 하며, 이 파일은 정보의 단위인 레코드의 나열이다.

아래 정보를 가지고 있는 인사기록 카드를 정렬하려고 했을 경우 카드 각 한장은 레코드, 레코드의 정보를 가지고 있는 사번, 성별,나이 등은 필드라고 한다.

정렬을 하려면 키가 있어야한다. ‘비교’의 대상이 되는 것은 레코드 중에서 키값이며, ‘교환’의 대상이 되는 것은 레코드 자체가 된다. 사원번호 정도가 ‘키’가 될 수 있겠다.

선택 정렬(Selection Sort)

순서대로 정렬하는 가장 간단한 정렬 알고리즘.

선택 정렬 알고리즘

선택정렬 특징:

첫 번째  배열의 앞 부분부터 정렬을 차례로 해나간다.

두 번째 정렬을 아직 하지 않은 부분은 n의 변함이 없다.

선택 정렬의 비교 횟수는 최소값을 찾기 위해서 N2/ 2 정도로 많지만 교환 횟수는 많아야 N번이다.

안정성 문제

안정성이란 같은 키의 상대적 순서가 정렬 후에도 변함이 없음을 뜻한다.

하지만 선택 정렬은 안정성이 없다.

인접한 배열 요소를 교환하는 것이 아닌 뚝 떨어진 요소와도 교환이 되기 때문이다.

병합정렬(merge sort)

병합의 개념 : 두개 이상의 정렬된 자료집합을 하나의 정렬된 자료집합으로 합치는 것

병합의 방법 : 대상 자료집합이 정렬된 상태이므로 순차적으로 작은 자료를 뽑아서 놓으면됨

데이터의 분포에 영향을 덜 받는다.

즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일)

실제로 숫자들이 정렬되는 과정

거품 정렬

배열의 인접 요소를 비교하여 교환하는 모양이 보글보글하다고 해서 붙여진 이름이다.

거품 정렬은 인접한 배열의 요소를 비교 교환하여 전체적으로는

대충 정렬을 하면서 최대값을 배열의 제일 뒤로 보내는 것을 반복한다.

거품 정렬의 개선

아래 함수를 추가하여 정렬이 되어있는 체크

정렬이 되어 있다면 바로 빠져 나오도록

(but 정렬이 되어있을때는 시간이 적지만 그렇지 않을 경우는 더 시간이 느려진다.

s=0과 if s인지 판단하는 문장이 추가 됐기 때문)