알고리즘의종류

정렬(Sort)

정렬 알고리즘

정렬 알고리즘은 크게 2가지로 나뉠 수 있다.
간단하지만 느린 알고리즘 , 조금 더 복잡하지만 빠른 알고리즘

• Simple , Slow(간단하지만 느림)
  • Selection Sort(선택 정렬)
  • Bubble Sort(버블 정렬)
  • Insertion Sort(삽입 정렬)
• Fast(위 알고리즘보다 복잡하지만 빠름)
  • Merge Sort(병합 정렬)
  • Quick Sokt(빠른 정렬)
  • Heap Sort(힙 정렬)

Simple , Slow

1. Selection Sort(선택 정렬)

선택정렬의 아이디어는 다음과 같다

1. 배열 중 가장 큰 값을 찾는다
2. 가장 큰 값과 마지막 Index와 Swap
3. 반복이 한 번 끝날때마다 맨 마지막은 Index은 정렬이 완료 따라서 체크 할 필요가 없다.

위 과정을 반복

O(n^2) 알고리즘이며 항상 모든 값을 확인해야 하므로 시간복잡도는 항상 같다.

ex)

 [29, 10, 14, 37, 13]

1. 배열 중 가장 큰 값을 찾는다. Max = 37
2. 가장 큰 값과 마지막 Index를 Swap Max = 37 , Index = 13 -> Swap

   [29, 19, 14, 13, 37]
   

   위 과정 반복

의사코드

Selection Sort 구현

#include <iostream>
#define N 5
using namespace std;

int main(){

int arr[N] = {24, 120, 64, 37, 13};
int max = 0;
int Last = N-1;
int k = 0;
int cnt = 0;

for(int i=0; i<N-1; i++){
    max = arr[0];
    k=i;
    for(int j=0; j<=Last; j++){
        if(max <= arr[j]){
            max = arr[j];
            k = j;
        }
    }
    int temp = arr[Last];
    arr[Last] = arr[k];
    arr[k] = temp;
    Last --;
}

for(int i=0; i<N; i++)
    cout << arr[i] << " " ;
return 0;
}

2. Bubble Sort(버블 정렬)

Selection Sort와 아이디어는 비슷하며 물고기를 몰아서 그물로 잡는거와 비슷하다. (큰 물고기는 그물을 빠져나갈 수 없음)

1. 배열의 현재값과 그 다음 값을 비교하여 더 큰 값을 찾는다.
2. 큰 값을 더 뒤 Index로 Swap
3. 한 사이클 반복이 끝날때마다 맨 마지막 Index는 정렬이 완료

위 과정 반복

O(n^2) 알고리즘이며 항상 모든 값을 확인해야 하므로 시간복잡도는 항상 같다.

ex)

[29, 10, 14, 37, 13]

1. arr[0] 과 arr[1] 중 Max값 비교 Max = 29
2. 더 큰 값의 Index를 더 뒤로 Swap

[10,29,14,37,13]

1. arr[1] 과 arr[2] 중 Max값 비교 Max = 29
2. 더 큰 값의 Index를 더 뒤로 Swap

[10,14,29,37,13]

위 과정 반복…

Bubble Sort 구현

#include <iostream>
#define N 5
using namespace std;

int main(){

int arr[N] = {10,29,14,37,13};
int len = N-1; 
int max = 0;
for(int i=0; i<N-1; i++){    
    for(int j=0; j<=len-1; j++){
        max = arr[j]; // 앞 Index값 삽입
        if(max>arr[j+1]){ // 앞 Index값이 더 크면 Swap
            int temp = arr[j]; //Swap
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
    len --; // 맨 마지막 정렬은 완료되었으니 1개 축소
}
for(int i=0; i<N; i++)
    cout << arr[i] << " " ;
return 0;
}

3. Insertion Sort(삽입 정렬)

뒤에서부터는 체크해야함 그 이유는 어차피 앞에서부터 확인 해서 들어갈 자리를 확인하더라도 뒤에서 부터 한 자리씩 Shift하는 과정이 필요함

Insert하기 전 Index까지는 이미 정렬이 되었다고 가정

1. Insert하고 싶은 값을 미리 temp변수에 저장
2. Insert값 이전 Index부터 값을 확인 후 temp보다 더 크 한 칸씩 Shift
3. temp 보다 더 작은 값을 만나거나 첫 Index라면 그 자리에 temp 값을 Insert

위 과정을 반복

최악의 경우 O(n^2)의 수행시간
최선의 경우 O(n-1)의 수행시간
최악의 경우를 제외하고 Selection Sort나 Bubble Sort 보다 수행시간이 짧다.

ex)

[29, 10, 14, 37, 13]

#N 1일 때는 이미 정렬 되었다고 가정 1번Index(10)부터 시작

1. 임시 변수temp에 10의 값을 저장
2. arr[0] (현재29) 이 temp(insert)값보다 더 크다면 한 칸 Shift
3. temp 보다 더 작은 값을 만나거나 첫 Index라면 그 자리에 temp 값을 Insert

[10,29,14,37,13]

1. 임시 변수 temp에 14의 값을 저장
2. arr[1] (현재29)이 temp(insert)값보다 더 크다면 한 칸 Shift
3. temp 보다 더 작은 값을 만나거나 첫 Index라면 그 자리에 temp 값을 Insert

[10,14,29,37,13]

위 과정을 반복

Insertion Sort 구현

#include <iostream>
#define N 5
using namespace std;

int main(){

int idx=0;
int arr[N] = {29, 10, 14, 37, 13};
int temp = 0;

for(int i=1; i<N; i++){
    temp = arr[i]; 
    idx = i; //현재 i의 값을 저장
    while(arr[idx] <= arr[idx-1]){ 
        // 제일 처음은 정렬이 되었다고 생각하고 그 다음부터 작은값이 나올때까지 한자리씩 Swap
        arr[idx] = arr[idx-1];
        arr[idx-1] = temp;
        idx --;
    }
}
for(int i=0; i<N; i++)
    cout << arr[i] << " " ;
return 0;
}

Fast (분할정복법)

1. Merge Sort(합병 정렬)

• 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
• 정복 : 각각의 작은 문제를 순환적으로 해결
• 합병 : 작은 문제의 해를 합하여(Merge) 원래 문제에 해를 구함

1. 데이터가 저장된 배열을 절반으로 나눔
2. 각각을 순환 정렬
3. 정렬된 두 개의 배열을 합쳐 전체를 정렬!

ex)

[12,24,63,12,51,2,125,32]

1. 데이터를 절반으로 나누고 순환하여 정렬

   [12,12,24,63] , [2,32,51,125]
      ↓               ↓
   [12,24], [12,63] , [2,51] , [32,125]
   ↓        ↓         ↓         ↓
   [12],[24],[63],[12] ,[51],[2],[125],[32] 
   

2. 합병 후 정렬

   [2,12,12,24,32,51,63,125]
   

정렬된 두 배열을 합쳐야 하므로 추가적인 배열을 이용하여 합병해야 한다

• 1번 배열은 i idx
• 2번 배열은 j idx
• 둘 중 더작은값을 새로운 배열의 맨 처음에 삽입
• 한 쪽 배열의 index가 끝나면 나머지 배열의 값을 전부 추가 배열의 삽입

Mergesort(int Arr[], int left ,int right , int new)

1. left,right 의 중간 지점 계산
2. left정렬
3. right정렬
4. left , right합병

O(nlogn)의 수행시간

Merge Sort 구현

#include <iostream>
#include <algorithm>
#define SIZE 8
using namespace std;

void Merge(int arr[], int start, int mid, int end){
	int i = start;
	int j = mid+1;
	int idx = start;
	int len = SIZE;
	int *temp = new int[len];

	while(i<=mid && j<=end){ // 둘 중 하나라도 끝날때까지
		if(arr[i] <= arr[j])
			temp[idx++] = arr[i++];
		else
			temp[idx++] = arr[j++];
		 
	}	//while	
	while(i<=mid)
		temp[idx++] = arr[i++]; // 앞쪽 데이터가 남아있다면
	while(j<=end)
		temp[idx++] = arr[j++]; // 뒤쪽 데이터가 남아있다면 

	for(int k=start; k<=end; k++)
		arr[k] = temp[k];
	delete[] temp;
}
void Merge_Sort(int arr[], int start,int end){
	if(start < end){ //시작보다 끝이 더 길어야 함 그게 아니라면 길이가 1개
		int mid = (start+end)/2; //시작과 끝의 중간지점
		Merge_Sort(arr, start, mid); //시작과 중간을 정렬
		Merge_Sort(arr, mid+1, end); // 중간과 끝을 정렬
		Merge(arr,start ,mid , end); // 합병 정렬
	}
}

int main(){
	int arr[] = {12,24,63,12,51,2,125,32};
	int start = 0;
	int end = SIZE-1;

	Merge_Sort(arr,start,end);
	for(int i=0; i<=end; i++)
		cout << arr[i] << " ";
	cout << endl;
	return 0;

}

마지막 Merge하는 부분이 ..상당히 어려웠다.

2.Quick Sort(빠른정렬)

• 분할 : 조건을 이용하여 두 부분으로 분할
• 정복 : 각각의 문제를 순환적으로 해결
• 합병 : 합병과정은 없음

Pivot(기준)을 이용하여
Pivot보다 작은 수<- Pivot -> Pivot보다 큰 수
두 부분으로 분할 후 정렬
Merge Sort와는 다르게 합병하는 과정이 없다.

ex)

[12,24,63,12,51,2,125,32]

맨 마지막 값을 기준으로 정렬

[12,24,12,2] <- [32] -> [63,51,125] 

왼쪽데이터와 오른쪽데이터 정렬

[2,12,12,24,32,51,63,125]

최악의 경우를 제외하고는 O(nlogn)의 수행속도
최악의 경우는 이미 배열이 정렬된 경우이고 O(n^2)의 수행속도

최악을 제외하고 이름처럼 가장 빠른 정렬 알고리즘이며 <algorithm>의 sort()함수가 QuickSort이다.

의사코드

# Pivot을 맨 처음 또는 맨 마지막을 설정하는건 별로 좋지 못한 방법이다. 따라서 중간값 또는 랜덤값을 설정하자

구현

#include <iostream>
#include <ctime>

using namespace std;


int Quick_partition(int arr[], int start, int end){
    srand(time(NULL));
    //int p_idx = rand()%end;
    int p = arr[end]; // Pivot을 랜덤값으로 지정
    int i = start-1; //배열의 밖을 지정
    int j = start; // 시작 부분 지정

    while(j<end)
    {
    if(arr[j]>=p) 
        j = j+1;  // 기준보다 크면 그냥 넘어감 
    else{  //기준보다 작다면 값을 스왑
        i = i+1;
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
        j = j+1;
        }
    }
    int temp = arr[i+1];  //마지막 기준값을 위치에 맞게 재배치 이후 Index를 return
    arr[i+1] = p;
    arr[end] = temp;
    return (i+1);
}

void Quick_Sort(int arr[], int start, int end){
    if(start<end){
        int pivot = Quick_partition(arr, start, end);
        Quick_Sort(arr,start, pivot-1);
        Quick_Sort(arr, pivot+1, end);
    }
}
int main(){
    int arr[] = {12,24,63,12,51,2,125,32};
    int size = 8;
    int start = 0;
    int end = size-1;
    Quick_Sort(arr,start, end);
    
    for(int i=0; i<=end; i++)
        cout << arr[i] << " ";
    cout << "\n";
    return 0;
}

3.Heap Sort(힙정렬)

이진 Heap이라는 자료구조를 이용하여 정렬하는 방법으로 시간복잡도가 O(Nlog2N)으로 상당히 빠른속도의 정렬이 가능하며 추가배열이 필요하지 않아 저장공간을 적게 차지한다는 장점이 있다.

Heap ?

Heap이 되기위해서는 2가지 조건이 필요하다.

1. Complete binary tree
2. Heap property를 만족

첫 번째로는 Complete binary tree이다.
Complete binary tree(계층적관계)

• Full binary tree : 모든 Level의 Node가 꽉 차있는 형태
• Complete binary tree : 마지막 Level을 제외하고 모든 Node가 다 있으며 마지막 Level에서 오른쪽부터 노드가 없을 수 있다.

# Root node: Tree의 제일 윗 부분

# Leaf node: 자식이 없는 마지막 level Node

# binary tree(이진트리) : 각각의 Node가 최대 2명의 자식을 가질 수 있다.

# Full binary tree는 Complete binary tree조건도 만족

두 번째로는 Heap property만족이다
Heap property(힙의 특성) 다음 중 하나를 만족해야 한다.

• Max Heap Property
  • 부모노드는 자식노드보다 크거나 같다
• Min Heap Property
  • 부모노드는 자식노드보다 작거나 같다

Heap은 Complete binary tree 이면서 Max Heap property 또는 Min Heap property를 만족하면 된다.

Heap의 1차원 배열로 표현

다음과 같은 조건으로 힙을 1차원 배열로 표현을 할 수 있다.

• 루트 노드 : Arr[1]
• Arr[i]의 부모 노드 : Arr[i/2]
• Arr[i]의 왼쪽 자식 : Arr[2*i]
• Arr[i]의 오른쪽 자식 : Arr[(2*i)+1]

1. 정렬할 데이터를 Complete binary tree로 생각
   -> 아직 Heap이 아님 따라서 Heap특성을 만족시켜야 함

   # 현재 예제에서는 MAX특성을 이용 MIN또한 구현 가능

2. MAX_HEAPIPY()을 이용하여 Heap특성을 만족시킴
   두 가지 방법이 존재
   • Recursive Version
     • Base case : Arr[i] 의 자식 노드가 없을 때
     • Recursive Case : i 의 자식노드 중에서 최댓값 K를 찾고 Arr[i] 부모노드와 Arr[K] 최대 자식노드를 Swap MAX_HEAPIPY(Arr, K)
   • Iteractive Version
     While -> Arr[i]의 자식노드가 있는동안
     i의 자식노드의 Max 값을 찾아 -> K 삽입
     Arr[i] 부모노드와 Arr[K] 최대 자식노드를 Swap

MAX_HEAPIPY 구현

int Arr = [12,24,63,14,51,2,125,32]

입력받은 배열

void HEAP_BUILD(int Arr[], int sz)
// size/2 -> Root MAX_HEAPIPY

1. 힙 구조를 만들기 위해서 자식노드가 존재하는 1번째 노드부터 루트까지 반복해주는 HEAP_BUILD함수를 만든다.

void MAX_HEAPIPY(int arr[], int N, int sz)
//재귀적으로 구현

1. 자식노드가 없을때까지 자식노드 중 큰값을 찾아서 스왑을해줌
   위 2가지 과정이 끝나면 MAX_HEAP 구조가 완성된다,

A = [125 51 63 32 24 2 12 14]

Heap_Sort(int arr[], int sz)
// 루트는 항상 최대값이므로 루트와 마지막을 교환 이후 마지막값을 정렬이 되었으므로 마지막을 제외하고 루트를 MAX_HEAPIPY

1. 마지막으로 MAX_HEAP의 루트와 마지막인덱스를 교환하고 마지막 인덱스를 제외 -> 다시 MAX_HEAPIPY 반복!

A = [2 12 14 24 32 51 63 125]
// 결과값

MAX_HEAP_SORT 구현

#include <iostream>
#include <vector>

using namespace std;


void MAX_HEAPIPY(int arr[], int N, int sz)
{
    int left = (N*2) +1;
    int right = left +1;
    int max = 0;
    if(left>=sz){ //자식이 없는경우
        ;
    }
    else{
        if(right>=sz){
            right = 0;
            max = left;
        } //우측 노드가 없는경우 
        else{
            max = arr[left]<=arr[right]?right:left;
        }
        if(arr[N]<= arr[max]){
            int temp = arr[max];
            arr[max] = arr[N];
            arr[N] = temp;
            MAX_HEAPIPY(arr,max,sz); //반복
        }
    }
}

void HEAP_BUILD(int arr[], int sz){
    int len = sz;
    for(int i=(len/2)-1; i>=0; i--){
        MAX_HEAPIPY(arr,i,sz); //i는 원하는 노드 
    }
}

void Heap_Sort(int arr[], int sz)
{   
    if(sz==1){
        cout << "ROOT\n";
    }
    else{
    int len = sz-1; 
    int temp = arr[0];
    arr[0] = arr[len];
    arr[len] = temp;
    MAX_HEAPIPY(arr,0,len);
    Heap_Sort(arr, len);
    }

}

int main(){
    int A[] = {12,24,63,14,51,2,125,32};
    int len = sizeof(A)/sizeof(int);
    HEAP_BUILD(A,len);
    for(int i=0; i<len; i++){
        cout << A[i] << " " ;
    }
    cout << "\n";

    Heap_Sort(A,len);
    for(int i=0; i<len; i++){
        cout << A[i] << " " ;
    }
    cout << "\n";

    return 0;
}

==========================================================

검색(Serach)

트리(Tree) 와 이진트리(Tree)

용어

용어

• 루트(Root)
  • 트리의 가장 위쪽에 있는 노드
• 부모-자식 관계
  • 하나의 노드와 그 노드의 연결된 바로 아래 노드
• 형제관계
  • 같은 레벨의 있는 노드
  • 루트를 제외한 모든 노드들은 유일한 부모 노드를 가진다.
• 리프(leaf)노드
  • 자식이 없는 노드
• 조상-자손 관계
  • 부모-자식 관계를 확장한 것
• 부트리
  • 전체 트리의 일부또한 트리이다.
• 레벨
  • 루트-> Level1
• 높이
  • 트리의 높이는 서로다른 Level의 개수

트리

• 계층적인 구조를 표현
  • 조직도
  • 폴더와 하위폴더
  • 가계도
• 기본적인 성질
  • 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다.
  • 트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 유일하다

이진트리

• 이진 트리에서 각 노드는 최대 2개의 자식 을 가진다.

• 각각의 자식 노드는 자신이 부모의 왼쪽 자신인지 오른쪽 자신인지가 결정된다.

• ex
  • Expresion Tree
    • (X+Y) * ((a+b) / c)
  • Huffman Code(허프만 코드)
    • 어떤 데이터를 인코딩하는 알고리즘(파일압축과 관련)
  • Full and Complete Binary Trees
    • 링크(HEAP_SORT)
• 이진트리의 구조
  • 연결구조(Linked Structure)
  • 각 노드에 하나의 데이터 필드와 왼쪽자시(left), 오른쪽(right), 그리고 부모노드(p)의 주소를 저장
• 이진트리의 표현
  • 연결리스트로 구현한다.
  • 데이터필드 1개와 링크필드3개 필요
  • 루트노드의 주소는 따로 보관
• 이진트리 알고리즘

순회(Traversal)

순회 : 이진 트리의 모든 노드를 방문하는 일

#연결리스트는 선형적인 구조라 하나의 방법밖에 존재하지 않지만 이진 트리는 다양한 방법이 존재

중순위(Inorder)순회

이진트리의 중순위(Inorder)순회

1. 먼저 TL(트리의 왼쪽노드)을 inorder로 순회

2. Root(트리의 루트)를 순회

3. 마지막으로 TR(트리의 오른쪽노드)을 inorder로 순회

TL -> ROOT -> TR

Recursive하게 구현

선순위(Preorder)순회

이진트리의 선순위(Preorder)순회

1. Root(트리의 루트)를 순회

2. 먼저 TL(트리의 왼쪽노드)을preorder 순회

3. 마지막으로 TR(트리의 오른쪽노드)을 preorder순회

ROOT -> TL -> TR Recursive하게 구현

후순위(Postorder)순회

이진트리의 후순위(Postorder)순회

1. 먼저 TL(트리의 왼쪽노드)을 postorder 순회

2. TR(트리의 오른쪽노드)을 postorder 순회

3. 마지막으로 Root(트리의 루트)를 순회

TL -> TR -> ROOT Recursive하게 구현

레벨오더(Level_order)순회

이진트리의 레벨오더

1. 레벨 순으로 방문, 동일 레벨에서는 TL -> TR

2. 큐(Queue)를 이용하여 구현

검색트리

검색트리 (Dynamic Set, Dictionary, Search Structure)

Dinamic Set을 트리의 형태로 구현

일반적으로 SEARCH, INSERT, DELETE 연산은 트리의 높이에 비례하는 시간복잡도를 가짐

이진검색트리 ,레드-블랙 트리, B-트리 등이 존재

• 여러 개의 키(Key)를 저장
• 다음과 같은 연산들을 지원하는 자료구조
  • INSERT - 새로운 키 삽입
  • SEARCH - 키 탐색
  • DELETE - 키 삭제 ex) 심볼 테이블

자료구조	정렬여부	삽입(insert)	탐색(serach)	삭제(delete)
배열	정렬(O)	O(logn)	O(n)	O(n)
	정렬(X)	O(1)	O(n)	O(1)
연결리스트	정렬(O)	O(n)	O(n)	O(1)
	정렬(X)	O(1)	O(n)	O(1)

#정렬된 혹은 정렬되지 않은 배열/연결리스트를 사용하여 INSERT , SERACH, DELETE를 할 경우 적어도 하나 이상은 O(n)의 시간복잡도를 가진다.

• 이를 해결하기 위한 다양한 방법
  • 이진탐색트리 , 레드-블랙 트리, AVL-트리등의 트리 기반 구조
  • Direct Address Table, 해쉬 테이블 등

이진검색트리(BST)

이진검색트리(BST)

1. 이진 트리
2. 각 노드에 하나의 키(Key)를 저장
3. 각 노드 V에 대해서 그 노드의 왼쪽 부트리(subtree)에 있는 키들은 Key[V]보다 작거나 같고, 오른쪽 부트리에 있는 값은 크거나 같다.