자료구조_알고리즘

정렬 알고리즘

정렬 - 기억 공간 내의 자료 중에서 레코드의 특정 항목에 따라 오름차순 또는 내림차순으로 자료를 재배치하는 작업

• 내부정렬
   - 데이터의 양이 적을 때 주기억 장치 내에서 장렬하는 방법
   - 외부 정렬에 비해 속도는 빠르지만 데이터의 양이 사용 가능한 주기억 장치 공간보다 많으면 부적합함
• 외부 정렬
   - 많은 양의 데이터를 몇 개의 서비 파일로 나누어 각각 내부 정렬을 한 후 테이프나 디스크 등의 보조 기억 장치 내에서 병합하는 방법
   - 속도는 느리지만 데이터의 양이 많은 경우 효과적

내부 정렬 (주기억 장치)	삽입법	삽입 정렬, 셸 정렬
	교환법	버블 정렬, 퀵정렬
	선택법	선택 정렬, 힙 정렬
	병합법	병합 정렬
	분배법	기수 정렬
외부 정렬 (주기억 장치 + 보조 기억 장치)	병합법	병합 정렬

정렬 알고리즘의 분류

정렬 알고리즘 선택 시 고려 사항

• 작업 공간의 크기 - 메모리(주기억 장치, 보조 기억 장치)가 클수록 효율적
• 정렬할 자료의 양 - 데이터가 수천 개 이상이면 O(n * log₂ n) 계열의 방법으로 정렬하고
• 자료의 이동 횟수 - 역으로 정렬할 때, 즉 오름차순으로 정렬되어 있는 자료를 내림차순으로 정렬하고자 할 때나 그 반대의 경우에는 버블 정렬, 삽입 정렬의 자료 이동 횟수가 가장 많음
• 초기 자료의 배열 상태 - 자료가 초기에 원하는 순서대로 정렬되어 있을수록 버블 정렬, 삽입 정렬, 셸 정렬 순서로 시간이 단축되고 다른 정렬 방법은 차이기 없거나 약간 단축

 -> 사용할 자료인 숫자나 문자의 순서를 얼마나 효과적으로 정렬할 수 있느냐가 정렬 문제의 핵심이다

O(n²) 계열 - 버블 정렬, 선택 정렬, 삽입 정렬

O(n * log₂ n) 계열 - 셸 정렬, 기수 정렬, 퀵 정렬, 힙 정렬, 병합 정렬

정렬 방법	특징	Big O 표기 (시간 복잡도)
버블 정렬	- 정렬이 완료되는 즉시 반복을 멈춘다  - 초기 데이터가 정렬되어 있을수록 교환 횟수는 줄어든다  - 빈번한 데이터 교환으로 데이터 이동이 많아 평균적으로 가장 느리다	O(n²)
선택 정렬	- 초기 데이터 배열 상태에 상관없이 비교 횟수가 일정하다  - 정렬을 위한 비교 회수는 많으나 교환 횟수는 상당히 적다  - 평균 정렬 시간은 가장 느린 버블 정렬에 가깝다	O(n²)
삽입 정렬	- 초기 데이터가 정렬되어 있을수록 비교 및 데이터 이동 횟수는 줄어든다  - 평균 정렬 시간은 선택 정렬에 가까워 느린 편이다	O(n²)
셸 정렬	- 초기 데이터가 정렬이 되어 있을수록 빠르다  - 3중 for를 사용하여 구조가 복잡한 편이다  - 삽입 정렬을 개선한 방법으로 정렬 시간은 퀵 정렬에 가깝다	산술적 : O(n² * log₂ n) 실질적 : O(n * log₂ n)
기수 정렬	- 비교 연산을 하지 않는 정렬 방법이다  - 데이터 수(n) 크기의 버킷 저장소가 추가로 필요하다  - 초기 데이터 나열 상태에 따라 반복 횟수는 일정하다  - 평균 정렬 시간은 힙 정렬과 비슷하여 매우 빠른 편이다	산술적 : O(d * n) 실질적 : O(n * log₂ n)
퀵 정렬	- 반복 횟수와 데이터 이동을 최소화하여 평균적으로 가장 빠른 방법이다  - 초기 데이터가 정렬이 되어 있을수록 반복 횟수가 늘지만, 정렬이 되어 있을수록 반복 횟수가 줄어드는 삽입, 버블 정렬보다 빠르다  - 연속적인 재귀호출이 과다할 경우에 실행이 멈출 수 있어 실무적으로 활용하려면 다른 정렬 방법과 결합하여 코드를 완성한다	O(n * log₂ n)
힙 정렬	- 힙 트리를 이용하는 알고리즘으로 평균 정렬 시간은 퀵 정렬과 비슷하여 배우 빠르다  - 초기 데이터 나열 상태에 관계없이 반복 횟수가 거의 일정하다  - 효과적이면서 단점이 없는 정렬 방법이다	O(n * log₂ n)
병합 정렬	- 병합한 결과를 갖는 임시 저장소가 추가로 필요하다  - 초기 데이터 나열 상태에 관계없이 반복 횟수가 일정하다  - 복사하는 시간 때문에 힙 정렬, 기수 정렬보다 다소 느리다	O(n * log₂ n)

정렬 시간이 빠른 순서 : 퀵 정렬, 힙 정렬, 기수 정렬, 쉘 정렬, 병합정렬, 삽입 정렬, 선택 정렬, 버블 정렬

추가로 저장 공간이 필요한 방법 : 기수 정렬, 병합정렬

초기 데이터 나열 상태에 따라 반복횟수가 일정한 방법 : 병합 정렬, 기수 정렬, 선택 정렬

 

검색 알고리즘

비정렬 검색

 - 데이터 집합의 정렬 여부에 관계없이 조건에 맞는 데이터를 찾는 것을 비정렬 검색이라고 한다.

 - 비정렬 검색 방법에는 순차 검색과 해시 검색이 있다

 

순차 검색

 - 주어진 데이터 집합에서 원하는 데이터를 처음부터 순차적으로 비교하면서 찾는 방법

 - 검색 실패 확인

 -> 정렬되지 않은 데이터 집합 검색 시 : 마지막 데이터 비교 후 검색을 종료

 -> 정렬된 데이터 집합 검색 시 : 검색 대상 킷값보다 비교 대상 값이 큰 경우 더 이상 검색하지 않고 검색을 종료한다

 - 시간 복잡도는 O(n)이다

 

해시 검색

 - 직접 접근(Direct Access)하여 검색하는 방법이다

 - Hashing 함수에 키(key)를 넣어 계산된 값을 데이터를 저장하고 검색할 주소로 사용한다

 - 한 번의 주소 계산으로 원하는 데이터를 찾고자 함이 목표이다

 - 속도는 가장 빠르나 충돌을 해결하여야 하는 문제가 발생한다
 - 시간 복잡도는 O(1)이다

 - 고려 사항

• 버킷의 크기
• 적재율
  - 70%, 최대 80%
• 해시 함수
• 오버플로 해결 방법

 - 해시 함수

• 중간 제곱 합수
   - key²의 중간값(주소 공간이 0~9999라면 4자리, 0~999라면 3자리)
• 제산 함수
   1단계 : '버킷의 크기보다 큰 값 + 소수 또는 소수에 가까운 숫자'로 나눈 나머지
   2단계 (보정 작업) : 1단계 결과 * 버킷크기 / 선택한 숫자
• 접지 함수
   - 접지 방법으로 킷값을 접어 주소를 구하는 방법
• 기수 변환 함수
   - key를 다른 진수로 변환 -> 초과하는 높은 자리 수를 절단 -> 주소 범위에 맞도록 조정
  ex. 172,148을 11진수로 변환하면 266,373 -> 6,373 -> 6,373 * 0.7 = 4, 461 
•  계수 분석 함수
   - 자릿수별 빈도수를 파악해 균등한 분포를 가지는 자릿수부터 선택해 주소로 사용
   ex. key값 중 100, 10, 10000의 자리 순서대로 많은 분포라면 key값 31,879 = 873

 - 충돌 해결 조사

• 선형 조사
   - 충돌 발생 시 다음 빈 공간을 찾아서 저장
   - 비효율적인 방법
• 독립 오버플로 구역
   - 충돌 발생시 별도의 저장 공간에 선형으로(앞에서부터 순서대로) 저장
• 이중 해싱
   - 1차 해싱에서 충돌 발생하면 2차 해싱 하는 방법
• 해시 체인
   - 각 버킷을 연결 리스트로 구현해 충돌이 발생하면 동일 버킷에 저장되어야 할 데이터를 연결리스트로 연결하는 방법

 

정렬된 데이터 검색

 - 정렬된 자료에 대하여 검색하는 방법으로, 이진 검색, 보간 검색, 피보나치 검색이 있다

 

이진 검색

 - 전체 데이터 중에서 가운데 위치의 데이터와 비교하여 같으면 완료하고, 찾는 데이터가 가운데 데이터보다 작으면 앞부분, 그렇지 않으면 뒷부분을 비교하며 범위를 반으로 줄이며 비교, 검색하는 방법이다

 - 정렬된 데이터들을 분할하여 검색하므로 속도가 빠르다

 - 시간 복잡도는 O(log₂ n)이다

 

보간 검색

 - 근접 위치를 구하여 찾는 방법으로, 동작 방식은 이전 검색과 비슷하지만 검색 위치를 정하는 방식이 다르다

 - 이진 탐색과의 가장 큰 차이점은 이진 탐색은 데이터들의 중간 값을 찾아 줄여 나가는 것이고, 보간 탐색은 중간이 아니고 찾는 값이 상대적으로 작다면 앞쪽에서, 크다면 뒤쪽에서 찾아 줄여 나가는 방식이다
 mid = left + ( right - left ) * ( key - a[left] ) / ( a[right] - a[left] )

 - 시간 복잡도는 등차수열에 가까우면 O(1)에, 같은 크기의 데이터가 많으면 O(n)에 가깝고, 평균 O(log₂ n)이다

 

피보나치 검색

 - 정렬된 데이터 집합에서 피보나치수열을 이용하여 검색하는 방법이다

 - 시간복잡도는 O(log₂ n)이다

 

그래프 알고리즘

깊이 우선 탐색

 - 그래프나 트리에서 사용되는 탐색 알고리즘으로, 스택 구조를 이용하여 현재 정점에서 한 방향으로 갈 수 있는 최대한의 깊이까지 내려간 뒤, 더 이상 갈 곳이 없을 경우 옆으로 이동하여 다음 경로를 탐색하는 방식이다

 - 시간 복잡도는 연결리스트로 O(V+E), 인접 행렬로 O(n²)이다

 

너비 우선 탐색

 - 그래프나 트리에서 사용되는 탐색 알고리즘으로, 큐 구조를 이용하여 현재 정점에 인접한 모든 정점들을 우선 방문하는 방법이다

 - 인접한 정점 중 더 이상 방문하지 않는 정점이 없을 때 다음 정점으로 이동하여 다음 경로를 탐색하는 방식이다

 - 시간 복잡도는 연결리스트로 O(V+E), 인접 행렬로 O(n²)이다

 

다익스트라 최단 경로

 - 모든 정점에서 도착점까지 최단 경로 및 거리를 구해나가는 방법이다

 - 가중치가 있는 그래프에서 동작한다

 

순열과 조합

#include <stdio.h>
#define R 3

int b[R] = {0, }, cnt=0;

 

중복 순열

 - n개의 데이터 중 r개를 중복하여 사용하여 순서에 따라 배열하는 것이다

 - 경우의 수는 n^r이다

 - 데이터를 교환하는 알고리즘과 교환하지 않는 알고리즘이 있다

void PrintRePer(){
	cnt++;
    for(int i=0; i<R; i++) printf("%d ", b[i]);
    printf("\n");
}

void exchange(int* a, int* b){
	int temp = *a;
    *a = *b;
    *b = temp;
}

void RePermutation(int a[], int n, int r){
	int i;
    if(r >= R) PrintRePer();
    else 
    	for(i = 0; i<n; i++){
        	exchange(a+0, a+i);
        	b[r] = a[i];
            RePermutation(a, n ,r+1);
            exchange(a+0, a+i);
            // 111, 112, 113, 114, 115, 122, 121, 123, 124, 125, 133, 132, 131, 134, 135
        }	// 중복 순열 : 125개
}

int main(){
	int a[] = {1, 2, 3, 4, 5};
    int n = sizeof(a) / sizeeof(int);
    
    RePermutation(a, n, 0);
    printf("중복 순열 개수 : %d\n", cnt);
    return 0;
}

 

순열

 - n개의 데이터 중 r개를 중복 없이 순서대로 배열하는 것이다

 - 경우의 수는 n! / (n - r)! 이다

void RePermutation(int a[], int n, int r){
	int i;
    if(r >= R) PrintRePer();
    else 
    	for(i = r; i<n; i++){
        	exchange(a+r, a+i);
        	b[r] = a[r];
            RePermutation(a, n ,r+1);
            exchange(a+r, a+i);
            // 123, 124, 125, 132, 134, 135, 142, 143, 145, 152, 153, 154, 213, 214, 215 
        }	// 순열 : 60개
}

 

조합

 - n개의 데이터 중 r개를 순서에 의미를 두지 않고 배열하는 것으로, 중복을 허용하지 않는다

 - 경우의 수는 n! / (n - r)!r! 이다

void PrintCom(){
	cnt++;
    for(int i=0; i<R; i++) printf("%d ", b[i]);
    printf("\n");
}

void Combination(int a[], int n, int r, int ii){
	if(r >= R) PrintCom();
    else
    	for(int i = ii+1; i<n; i++){
        	b[r] = a[i];
            Combination(a, n, r+1, i);	// 123, 124, 125, 134, 135, 145, 234, 235, 245, 345
        }	// 조합 : 10개
}

 

중복 조합

 - 데이터 중복을 허용하여 조합을 만드는 방법이다

 - 경우의 수는 (r + n - 1)! / (n-1)!r! 이다

void PrintCom(){
	cnt++;
    for(int i=0; i<R; i++) printf("%d ", b[i]);
    printf("\n");
}

void Combination(int a[], int n, int r, int ii){
	if(r >= R) PrintCom();
    else
    	for(int i = ii; i<n; i++){
        	b[r] = a[i];
            Combination(a, n, r+1, i);	
            // 111, 112, 113, 114, 115, 122, 123, 124, 125, 133, 134, 135, 144, 145, 155, 222
        }	// 중복 조합 : 35개
}