[문제 링크]



LCS2는 다음 포스트에 있는 내용과 같다.


http://hsp1116.tistory.com/37



#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
vector<char> output;
int cache[1001][1001];
char input[1001],compare[1000];
int LCS(int m,int n){
    memset(cache,0,sizeof(cache));
    for(int i=1;i<=m;i++){
        for(int j=1; j<=n;j++){
            if(compare[i-1] == input[j-1]){
                cache[i][j] = cache[i-1][j-1] +1;
                }
            else{
                cache[i][j] = std::max(cache[i-1][j], cache[i][j-1]);
            }
        }
    }
    return cache[m][n];
}
void backTracking(int m, int n){
    if(m==0 || n ==0) return;
    if(cache[m][n] > cache[m-1][n-1] && cache[m][n] > cache[m][n-1] && cache[m][n] > cache[m-1][n]){
        output.push_back(input[n-1]);
        backTracking(m-1, n-1);
    }else if(cache[m][n] > cache[m-1][n] && cache[m][n] == cache[m][n-1]){
        backTracking(m, n-1);
    }else{
          backTracking(m-1, n);
    }
}
int main(){
    scanf("%s%s",input,compare);
    int m = strlen(compare), n = strlen(input);
    printf("%d\n",LCS(m,n));
    backTracking(m,n);
    for(int i=output.size()-1;i>=0;i--)
        printf("%c",output[i]);
}


'Algorithm > Problems' 카테고리의 다른 글

백준 - 1238 파티  (0) 2016.04.22
백준 - 1753 최단경로  (1) 2016.04.22
백준 - 9251 LCS  (0) 2016.04.17
알고스팟 - KOOGLE  (0) 2016.04.14
백준 - 1725, 6549 히스토그램 / 알고스팟 - FENCE  (0) 2016.03.28


[문제 링크]



LCS는 다음 포스트에 있는 내용과 같다.


http://hsp1116.tistory.com/37




#include <cstdio>
#include <algorithm>
#include <cstring>
int cache[1001][1001];
char input[1001],compare[1000];
int LCS(){
    int n = strlen(compare), m = strlen(input);
    memset(cache,0,sizeof(cache));
    for(int i=1;i<=n;i++){
        for(int j=1; j<=m;j++){
            if(compare[i-1] == input[j-1]){
                cache[i][j] = cache[i-1][j-1] +1;
                }
            else{
                cache[i][j] = std::max(cache[i-1][j], cache[i][j-1]);
            }
        }
    }
    return cache[n][m];
}
int main(){
    scanf("%s %s",input,compare);
    printf("%d\n",LCS());
}

'Algorithm > Problems' 카테고리의 다른 글

백준 - 1753 최단경로  (1) 2016.04.22
백준 - 9252 LCS 2  (0) 2016.04.17
알고스팟 - KOOGLE  (0) 2016.04.14
백준 - 1725, 6549 히스토그램 / 알고스팟 - FENCE  (0) 2016.03.28
백준 - 2493 탑  (1) 2016.03.28

공통 부분 수열이란, 두 문자열이 공통으로 가지고 있는 부분 수열을 말한다.


예를 들어 문자열


문자열 A : CDABE

문자열 B : CDEGT

가 있다면,


공통 부분 수열은

{},{C},{D},{E},{C,D},{D,E},{C,E},{C,D,E}

일 것이다.





1. 최장 공통 부분 수열 길이 구하기

최장 공통 부분 수열은 공통 부분 수열 중에서 길이가 가장 긴 부분 수열을 말한다.

위 예제 최장 공통 부분 수열은{C,D,E}이고, 길이가 3이다.


최장 증가 부분 수열은 또한 다음과 같은 정의를 따른다. 각 점화식을 에제를 들어 확인해보자.





(1) Ai != Bj

두 문자열 CDABE,CDEGT의 최장 공통 부분 수열을 구한다고 해보자.

여기서 맨 마지막 문자인 E와 T가 각각 다르므로 다음과 같은 경우를 고려 할 수 있다.

1. 최장공통부분 수열이 E로 끝나는 경우.

이 경우 K는 최장 공통 부분 수열에 아무련 영향을 끼치지 않으므로 없어도 상관 없다.

즉 LCS(i,j) = LCS(i,j-1)이다.


2. 최장 공통 부분 수열이 T로 끝나는경우

이 경우 E가 최장 공통 부분 수열에 아무런 영향을 끼치지 않으므로 지워도 상관없다.

이 경우엔 LCXS(i,j) = LCS(i-1,j)이다 


3. 둘 다 해당이 되지 않는 경우.

둘 다 지워도, 하나만 지워도 최장 증가 부분 수열에 영향을 끼치지 않는다. 따라서 고려 할 필요가 없다.


두 문자가 일치하지 않을 때, 최소 둘 중 하나는 최장 공통 부분 수열에 영향을 끼치지 않으므로 둘 중 하나를 지워도 상관없다.

즉 둘 중 하나를 지웠을 때의 더 큰 LCS가 LCS(i,j)이다.

따라서 LCX(i,j) = max(LCS(i-1,j),LCS(i,j-1))임을 알 수 있다.



(2) Ai == Bj

두 문자열 CDABE CDE라고 가정해보자. 맨 뒤의 문자 E가 설 일치하는데, 공통 문자인 E는 최장 공통 부분 수열에 반드시 포함될 것이다.

따라서 이 두 문자열을 지운다면, 최장 공통 부분 수열에서 또한 E가 사라질 것이라는 것을 알 수 있다.

즉 최장 증가 부분 수열의 길이 또한 1 감소하므로, LCX(i,j) = LCS(i-1,j-1) + 1이다.





이제 위 공식을 이용하여 구현하면 된다. 각 인덱스는 현재 문자열의 길이라고 생각하면 된다.


 

 

 C (j=1)

 D (j=2)

 E (j=3)

 G (j=4)

 T (j=5)

 

 0

 0

 0

 0

 0

 0

 C (i=1)

 0

 

 

 

 

 

 D (i=2)

 0

 

 

 

 

 

 A (i=3)

 0

 

 

 

 

 

 B (i=4)

 0

 

 

 

 

 

 E (i=5)

 0

 

 

 

 




맨첨 1행, 1열들은 모두 0으로 치워지는데 이는 빈 수열을 뜻한다. 빈 수열과 문자열의 최장 증가 부분 수열은 0이기 때문이다.



밑은 앞서 확인한 공식으로 작성한 테이블이다.


 

 

 C (j=1)

 D (j=2)

 E (j=3)

 G (j=4)

 T (j=5)

 

 0

 0

 0

 0

 0

 0

 C (i=1)

 0

 1

 1

 1

 1

 1

 D (i=2)

 0

 1

 2

 2

 2

 2

 A (i=3)

 0

 1

 2

 2

 2

 2

 B (i=4)

 0

 1

 2

 2

 2

 2

 E (i=5)

 0

 1

 2

3

 3

 3


LCS(5,5)=3으로, 최장 공통 부분 수열의 길이는 3임을 알 수 있다.


int LCS(string& input, string& compare){
    int cache[1001][1001];
    memset(cache,0,sizeof(cache));
    for(int i=1;i<=compare.length();i++){
        for(int j=1; j<=input.length();j++){
            if(compare[i-1] == input[j-1]){
                cache[i][j] = cache[i-1][j-1] +1;
                }
            else{
                cache[i][j] = max(cache[i-1][j], cache[i][j-1]);
            }
        }
    }
    return cache[compare.length()][input.length()];
}



1. 최장 공통 부분 수열 구하기


이는 우리가 구한 2차원 배열을 역추적 하여 구할 수 있다.


 

 

 C (j=1)

 D (j=2)

 E (j=3)

 G (j=4)

 T (j=5)

 

 0

 0

 0

 0

 0

 0

 C (i=1)

 0

 1

 1

 1

 1

 1

 D (i=2)

 0

 1

 2

 2

 2

 2

 A (i=3)

 0

 1

 2

 2

 2

 2

 B (i=4)

 0

 1

 2

 2

 2

 2

 E (i=5)

 0

 1

 2

3

 3

 3



최장 증가 부분 수열을 찾는 공식을 잘 고려해 보자.


우리가 찾아야 하는건 Ai == Bi인 문자이다.


Ai == Bj일 때 LCS(i,j) = LCS(i-1,j-1) + 1였는데. 이를 고려해 역추적 해나가면 된다.

다만 또 고려할 것이 있는데, LCX(i,j) = max(LCS(i-1,j),LCS(i,j-1))의 경우이다.

Ai != Bj일 지라도, LCS(i,j) = max(LCS(i-1,j),LCS(i,j-1))를 통해 LCS(i-1,j-1) + 1가 도출 될 수 있다.

따라서 LCS(i-1,j), LCS(i,j-1)이 둘 다 LCS(i,j)보다 작으면서, LCS(i-1,j-1)이 LCS(i,j)보다 작은 경우가 Ai==Bj일 때이다. 

즉 LCS[i][j] > LCS[i-1][j-1] && LCS[i][j] > LCS[i][j-1] && LCS[i][j] > LCS[i-1][j])를 조건으로 코드를 구현하면 된다.


밑은 해당 코드이며, output에 최장 공통 부분 수열 문자열이 저장된다.


string output;
void backTracking(int m, int n){
    if(m==0 || n ==0) return;
    if(cache[m][n] > cache[m-1][n-1] && cache[m][n] > cache[m][n-1] && cache[m][n] > cache[m-1][n]){
        //문자열 인덱스는 캐시 인덱스보다 1씩 더 작다. 
        output = input[n-1] + output;
        backTracking(m-1, n-1);
    }else if(cache[m][n] > cache[m-1][n] && cache[m][n] == cache[m][n-1]){
        backTracking(m, n-1);
    }else{
          backTracking(m-1, n);
    }
}



[문제 링크]



문제 자체는 입력을 문자열로 받아 문자의 아스키코드로 문자,숫자만 체크하면 되는 간단한 문제다.


다만 이 문제에서 주의해야할 점은 입력받는 문자열의 길이가 최대 1000개라는 점이다


문제를 제대로 읽지 않고 그냥 제곱연산을 했다가 오답이 떴는데 Strength(x) = 26^A * 10^B이므로 숫자로만 1000개 채워졌다고 해도, 10^1000이다.


크게 봐줘서 64비트 정수형을 쓴다고 해도 2^64-1은 아득히 넘어버린다.(Big Integer 라이브러리를 써도 안될거같다.)


그래서 이 문제는 그냥 pow로 구하기엔 자료형 범위를 초과하는 값은 정확한 비교가 되질 않는다.


하지만 이 문제는 암호의 강도가 정확히 몇인지를 알아야 하는 문제가 아니고, 뭐가 더 강한지만 고려하면 되기 때문에 그냥 log를 씌워서 계산한 후 비교하면 된다.




#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
int testcase,n;
string str;
long double Strength(const string& str){
    int num=0,chr=0;
    for(int i = 0; i<str.length(); i++){
        if(str[i]>=97 && str[i]<=122) chr++;
        else num++; 
    }
    return chr*log(26) + num*log(10);
}
int main(){
    cin>>testcase;
    while(testcase--){
        string maxStr;
        long double maxValue = 0;
        cin>>n;
        for(int i = 0; i<n; i++){
            cin>>str;
            long double cur = Strength(str);
            if(cur > maxValue){
                maxStr = str;
                maxValue = cur;
            }
            else if(cur == maxValue && maxStr.compare(str)>0) maxStr = str;
        }
        cout << maxStr << endl;
    }
}


위도 accept는 되지만 밑은 메모리와 시간을 좀 더 줄인 코드이다. 


#include <cstdio> #include <cmath> #include <cstring> int testcase,n; char str[1001]; long double Strength(char* str){ int num=0,chr=0; for(int i = 0; i<strlen(str); i++){ if(str[i]>=97 && str[i]<=122) chr++; else num++; } return chr*log(26) + num*log(10); } int main(){ scanf("%d",&testcase); while(testcase--){ char maxStr[1001]; long double maxValue = 0; scanf("%d",&n);getchar(); for(int i = 0; i<n; i++){ scanf("%s",str); long double cur = Strength(str); if(cur > maxValue){ strcpy(maxStr,str); maxValue = cur; }else if(cur == maxValue &&strcmp(maxStr,str)>0)strcpy(maxStr,str); } printf("%s\n",maxStr); } }


'Algorithm > Problems' 카테고리의 다른 글

백준 - 9252 LCS 2  (0) 2016.04.17
백준 - 9251 LCS  (0) 2016.04.17
백준 - 1725, 6549 히스토그램 / 알고스팟 - FENCE  (0) 2016.03.28
백준 - 2493 탑  (1) 2016.03.28
백준 - 10799 쇠막대기  (2) 2016.03.28


해쉬란?


해쉬는 임의의 크기를 가진 데이터를 고정된 데이터의 크기로 변환시키는 것을 말한다.

즉 해쉬 알고리즘은 해쉬를 하는 방법에 대해 절차적으로 명세한다.


이를 이용해 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다.

기존에 사용했던 자료 구조들은 탐색이나 삽입에 선형시간이 걸리기도 했던것에 비해, 

해쉬를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더욱 빠른 속도로 처리할 수 있다.




1. Direct Addressing Table






Direct Addressing Table은 key-value쌍의 데이터를 배열에 저장할 , key값을 직접적으로 배열의 인덱스로 사용하는 방법이다.

예를 들면 키 값이 400인 데이터가 있다면, 이는 배열의 인덱스가 400인 위치에 키 값을 저장하고 포인터로 데이터를 연결한다.

똑같은 키 값이 존재하지 않는다고 가정하면, 삽입 시에는, 각 키마다 자신의 공간이 존재하므로 그 위치에다 저장을 하면 되고, 

삭제 시에는 해당 키의 위치에 NULL값을 넣어주면 된다.탐 색 시에는 해당 키의 위치를 그냥 찾아가서 참조하면 된다.

찾고자 하는 데이터의 key만 알고있으면 즉시 위치를  찾는 것이 가능하므로 탐색,저장,삭제,갱신은 모두 선형시간인 O(1)로 매우 빠른 속도로 처리가 가능하다.

다만 key값의 최대 크기만큼 배열이 할당 되기 때문에, 크기는 매우 큰데, 저장하고자 하는 데이터가 적다면 공간을 많이 낭비할 수 있다는 단점이 있다.





2. Hash Table




Hash Table은 key-value 쌍에서 key값을 테이블에 저장할 때, Direct Addressing Table 달리 key값을 함수를 이용해 계산을 수행 한 후,

그 결과값을 배열의 인덱스로 사용하여 저장하는 방식이다. 여기서 key값을 계산 하는 함수는 해쉬 함수(Hash Function)이라고 부르며,

해쉬 함수는 입력으로 key를 받아, 0부터 배열의크기-1 사이의 값을 출력한다. 해쉬에 대한 첫 정의대로 임의의 숫자를 배열의 크기 만큼으로

변환 시킨 것이다.

이 경우 k값이 h(k)로 해쉬되었다고 하며, h(k)는 k의 해쉬값이라고 한다.


위 그림을 참조하면 각 k값들의 해쉬값인 h(k)값들이 배열의 인덱스로 사용됨을 확인 할 수 있다. 

해쉬 테이블은 Direct Addressing Table에 비해 공간 낭비가 매우 적은데 이는 key값의 크기에 테이블의 크기가 좌우되는 것이 아니고,

h(k)만큼의 공간에 저장되기 때문이다. 



2.1 충돌(Collusion)


하지만 해쉬 테이블은 '충돌'이 일어 날 수 있다는 큰 문제점이 있다. 충돌이란, 다른 k값이 동일한 h(k)값을 가져 동일한 slot에 저장되는 경우를 말한다.

예를 들자면 k1과 k12을 해쉬하였더니 h(k1) = h(k12)인 경우를 들 수 있다. Direct Addressing Table에서는 이를 방지 하기 위해 모든 key값이 다르다고 전제하였지만

해쉬 테이블에서는 key값이 달라도 해쉬의 결과가 같을 수 있기 때문에 이를 방지하기 위한 방법이 필요하다.

하지만 해쉬 함수를 짜더라도 충돌을 '완전히' 방지한다는 것을 보장하기는 힘드므로, 충돌을 방지하기 위한 방법으로

충돌을 어느정도 허용하되 이를 최소화 하는 방법도 사용하기도 한다..



2.1.1 Chaining 방법 - 충돌을 허용하되 최소화 하는 방법





충돌을 허용하지만 이를 최소화 하기 위한 방법중 하나인 체이닝 방식이다. 체이닝이란 이름 그대로 데이터들을 포인터를 이용해 서로 체인 형태로 엮어 나가는 것을 뜻하며, 해쉬 테이블에선 동일한 해쉬값이 출력되 충돌이 일어나면, 그 위치에 있던 데이터에 key값을 포인터로 뒤이어 연결한다.

따라서 최초로 h(k)위치에 저장된 데이터를 시작으로 그 이후의 h(k)값이 출력되는 데이터는 모두 연결 리스트의 형태를 취한다.

그렇기 때문에 최초의 위치를 탐색하는 해쉬 과정을 제외하고, 모든 탐색, 삽입, 삭제 과정은 연결리스트와 유사한 방식으로 진행한다. 


Chaing 방법에서의 수행시간은 삽입 시에는 해쉬값을 이용해 바로 slot에 저장하면 되므로 상수시간에 일어나고, 삭제는 연결리스트의 삭제와 동일하게 상수시간에, 탐색 시에는 연결리스트를 따라 가기 때문에 리스트의 길이 만큼 발생하지만, 최악의 경우, 즉 모든 데이터의 해쉬값이 일치하여 한 인덱스에 저장됬을 경우엔 연결리스트의 탐색 시간과 동일한 선형시간을 가지게 된다.


2.1.2 적재률


하지만 이 최악의 경우는 극단적인 예료, 평균적인 경우엔 O(a+1)의 시간이 걸린다. a는 적재율을 뜻하며 적재율이란 현재 저장된 key값 갯수(K), 전체 테이블의 갯수(N)을 서로 나눈 값(K/N)이다. 즉 현재 저장된 데이터가 많으면 많아질수록 충돌 확률이 높아져 연결 리스트 탐색 확률도 증가하며, 적을수록 리스트 탐색 확률이 적어진다는 것이다.




2.1.3 Simple uniform hash


충돌을 최소화 하는 방법 중에 충돌이 적은 좋은 해쉬 함수를 만드는 방법도 있다. 좋은 해쉬 함수의 조건은 Simple uniform hash 함수를 만드는 것으로, 이 조건은 다음과 같다.


1. 계산된 해쉬값들은 0부터 배열의 크기-1 사이의 범위를 '동일한 확률'로 골고루 나타날 것.

2. 각각의 해쉬값들은 서로 연관성을 가지지 않고 독립적으로 생성될 것.


첫 번째 조건을 충족하면 충돌이 일어날 확률이 적어질 것이며, 두 번째 조건은 해쉬값들이 서로 연관이 있을 경우 연관성이 있으면 해당 해쉬값이 등장하는 패턴이나 순서가 존재 할 수 있고, 이는 반복적인 충돌을 일으 킬 확률이 있기 때문이다.



2.1.4 divison method


해쉬 함수는 정말 다양하지만 대표적인 해쉬 함수로는 divison method가 있는데, modular 연산 방법을 이용하는 방법이다. 특정 key를 어떤 수로 나눈 나머지를 해쉬값으로 사용한다.

예를 들어 m=100이면 k mod m은 0부터 99까지의 범위를 가진다. 이 범위의 m은 해쉬 테이블의 성능을 크게 좌우하는데, m의 크기는 보통 키의 수의 3배가 적당하다고 한다. (적재율이 30%쯤까지 충돌이 거의 일어나지 않는다고 한다.)

그리고 m으로 2^p값을 사용하는 것엔 큰 주의를 요한다. 왜냐하면 m이 2^3이면, 2진수로 00001000이고, 4번째 이하의 숫자만 해쉬값에 영향을 끼치기 때문이다.

예를 들어 k1과 k2가 각각 10110100,10120100이면 둘 다 같은 해쉬값을 출력한다. 이를 방지하기 위해서 m은 보통 2^p에 근접한 소수를 선택한다고 한다.


즉 가장 최적의 m의 크기는 키의 갯수의 3배이며 2의 지수승에 근접한 소수이다.




3. Open Addressing



Open Addresing은 key값을 테이블에 저장하는 Direct Addressing Table과는 다르게, 모든 데이터(key+데이터)를 테이블에 저장하는 방법이다.

장점으로는 데이터를 직접 모두 읽어 오기 때문에, 포인터를 쓸 일이 없어 포인터를 사용함으로서 발생 할 수 있는 오버헤드를 방지 할 수 있다는 점이다.

포인터가 필요 없어 구현이 훨씬 용이해졌으며, 포인터 접근에 필요한 시간이 없기 때문에 큰 성능 향상이 있다.


3.1.1 Liner probing


포인터를 사용하지 않기 때문에, 앞서 설명한 Chaing 방법은 사용 할 수 없다. 따라서 다른 방법으로 충돌시에 대처해야 하는데 그 중 하나가 Liner probing이다.

Liner probing은 key값으로 인덱스를 계산할 때, 만약 충돌이 발생한다면 바로 다음 인덱스에 데이터를 저장하는 방식이다. 다음으로 이동한 이후에도 충돌이 발생했다면 또 다시 바로 다음 인덱스에 저장한다.

즉 충돌이 일어나지 않을 때 까지 다음 인덱스로 이동을 해가며 빈 공간을 찾으면 그 위치에 저장한다.



위는 하나의 예제이다. m의 크기는 11로 해쉬 함수는 k mod 11로 계산한다.

1. h(54) = 10, h(77) = 0, h(94) = 6, h(89) = 1, h(14) = 3으로 충돌이 일어나지 않는다.

2. h(45) = 1인데, 이미 1의 위치에는 h(89)=1이 저장되어 있어 충돌한다. 따라서 다음 위치에 저장한다

3. h(35) = 2인데, 여기엔 방금 충돌이 일어났던 45가 저장되어 있어 충돌한다, 빈 위치가 저장할 때 까지 이동하여 저장한다.

4. h(76) = 10이며, 저장은 3번과 같이 한다.


매 충돌시마다 한칸씩 이동하므로 해쉬함수는 다으모가 형태를 취하게 된다.


h(k,i) = (k+i) mod m


i는 충돌시마다 증가하여 한칸씩 이동한다.



Liner probing은 정말 구현이 용이하지만, primary clustering이라는 문제점을 가지고 있다. primary clustering은 충돌이 나면, 뒤 슬롯에 데이터를 넣어 하나의 데이터 덩어리를 이루기 때문에, 데이터들의 특정 위치에만 밀집하는 현상을 말한다. 이 현상으로 slot이 많아지면 많아질수록 탐색 시간에 엄청 늘어나게 된다.



3.1.2 Quadratic probing


primary clustering을 방지하기 위해 hash함수를 다음과 같이 2차식의 형태로 만드는 것이다.


h(k,i) = (h'(k) + c1*i + c2*i^2) mod m


Liner probing과는 달리 i가 2차식의 형태를 취해, 한칸씩 이동하는 것이 아닌 c1*i + c2*i^2만큼 이동한다.




위는 간단한 예제이다. 해쉬 함수는 h(k,i) = (k+i^2) mod m 의 형태를 취한다.

3번째에서 h(48,0) = 6으로 기존의 76과 충돌이 일어났다. 그래서 i를 하나 증가시켜 h(48,1) = (48+1^2) mod 7 = 0의 위치에다가 저장하였다. 여기선 충돌이 한번 일어난 경우만 있는 예제이지만. 만약 0에서도 충돌이 일어났다면 h(48,2) = (48+2^2) mod 7로 3의 위치에 저장되었을 것이다.


하지만 Quadratic probing에도 secondary clustering이라는 단점이 있다. 이는 처음 시작 해쉬값이 같을 경우, 그 이후의 해쉬값들도 모두 동일한 값으로 계산되어 충돌이 반복적으로 일어나 것을 말한다.





3.1.3 Double hashing


Quadratic probing의 secondary clustering를 해결하기 위해서 사용하는 방법이다. 원리는 간단한데 해쉬 함수를 해쉬 함수 2개로 구성하는 것이다.

해쉬 함수는 다음과 같은 형태를 가진다.


h1(k) = k mod m
h2(k) = k mod m2

h(k,i) = (h1(k) + i*h2(k)) mod m


밑은 dobule hasing의 간단한 예제이다.



dobule hashing을 테스트를 위해 간단하게 코드를 작성했다. 실무에서 쓰는 해쉬처럼 공간이 자동적으로 확장되거나 탐색 삭제를 위한 함수는 구현하지 않았고


그냥 삽입시 충돌이 얼마나 일어나는지를 체크하기 위한 코드이다. 테이블의 크기와 입력값의 크기를 조절해가며 충돌을 테스트 할 수 있다



#include <cstdio>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;

vector<int> v,h;
int n,k,m1,m2;

int myrandom (int i) { return std::rand()%i;}
void randGenerator(vector<int>& v, int n,int k){
    srand(time(NULL));
    for(int i=1;i<=2*n;i++){
        v.push_back(i);
    } 
    random_shuffle(v.begin(),v.end(),myrandom);
}

//더블 해싱을 위한 해싱함수 1 
int hashFunc1(int k){
    return k%m1;
}

//더블 해싱을 위한 해싱함수 2 
int hashFunc2(int k){
    return 1+k%m2;
}

//더블 해싱 함수 
int doubleFunc(int k,int i){
    return (hashFunc1(k)+i*hashFunc2(k))%m1;
}

void hashing(vector<int>& v,vector<int>& h, int (*hashFunc)(int,int)){
    int coll, first = -1,count = 0;
    double rate;     
    for(int i=0; i<k; i++){
        int c = 0;
        while(true){
            int key = hashFunc(v[i],c);
            if(h[key] == -1){
            //  printf("%d가 %d 에 저장!\n",v[i],key);
                h[key] = v[i];
                break;  
            }
            else{
            //  printf("%d번쨰 %d가 %d 에서 충돌! 적재율 : %lf\n",i,v[i],key,(double)i/n*100);
                if(first == -1) {   
                    first = v[i];
                    rate = (double)i/n*100;
                }
                count++;
                c++;
            }
            
        }
            
    }
    
    printf("첫 충돌 값 : %d\n",first); 
    printf("총 충돌 수 : %d\n",count);
    printf("첫 충돌 시 적재율 : %lf%%\n",rate);
}

int main(){
    printf("키 값 범위의 크기 :");
    scanf("%d",&k);
    printf("해시테이블 크기(1~n) : ");
    scanf("%d",&n);
    printf("m1, m2 입력 : ");
    scanf("%d %d",&m1,&m2);
    //해시테이릅 크기 증가
    
    printf("\n\n");
    randGenerator(v,n,k);
    for(int i=0;i<n;i++){
        h.push_back(-1);
    }
//  for(int i = 0; i<n; i++){
//      printf("%d ",v[i]);
//  }
    printf("\n");
    hashing(v,h,doubleFunc);
    printf("\n");
//  for(int i = 0; i<h.size(); i++){
//      printf("%d ",h[i]);
//  }
}


<실행 화면>





이 테스트를 위해 먼저 0부터 n까지 중복되지 않는 섞여있는 배열을 만들어내는 함수를 작성하였다.

이는 0부터 n까지 배열에 숫자를 삽입 후, 이를 셔플로 섞는 방법으로 구현하였다. 

그 코드는 다음과 같다.


//난수 배열 생성기 
int myrandom (int i) { return rand()%i;}
vector<int> randGenerator(int n){
    vector<int> v;
    srand(time(NULL));
    for(int i=0;i<=n;i++){
        v.push_back(i);
    } 
    random_shuffle(v.begin(),v.end(),myrandom);
    return v;
}


입력으로 배열의 크기를 받고, 벡터를 반환한다.



먼저 바로 전 포스트에서 작성한 알고리즘이 정상적으로 작동하는지 확인하겠다.




5개의 정렬이 모두 정상적으로 작동함을 확인 할 수 있었다.


모두 정상적으로 작동하는것을 확인 했으니 이제 모든 정렬의 성능을 테스트 해보도록 하겠다.


이 테스트는 10부터 시작하여 배열 범위를 10배씩 증가시키며 진행하였다.



1. n = 10, n = 100



둘 다 수행 시간이 0으로 측정되었다. 100까지 정도의 범위로는 어떤 정렬을 사용해도 크게 상관 없다는 것을 알 수 있다.



2. n = 10,00



1000개 부터는 속도 차이가 눈에 보이기 시작한다.

선택 정렬, 삽입 정렬, 버블 정렬은 모두 시간 복잡도가 n^2이었다. 그에 따라 셋의 시간이 유사하게 나올줄 알았으나.

삽입 정렬은 삽입 하고자 하는 위치를 찾았을 경우 더이상 비교하지 않으며, 최선의 경우 O(n)에 수행되기 때문에 더 빠른 속도를 보였다.

선택 정렬과 버블 정렬은 둘 다 모든 배열을 비교하는 정렬 알고리즘으로 시간이 유사하게 나옴을 알 수 있다.


그리고 합병 정렬과 퀵 정렬은 둘 다 nlgn에 수행되지만, 앞서 말했다 싶이 퀵 정렬이 조금 더 빠른 성능을 보인다.



3. n = 10,000


각 정렬 별로의 시간은 2번에서 설명한 바와 같다.

그리고 하나 더 알수 있는게, t선택,삽입,버블 정렬의 수행 시간이 이전보다 약 100배정도 증가했다는 사실이다.

 이로 시간 복잡도가 O(n^2)이므로 n이 10배 증가하면 100배한다는 것으로 시간 복잡도의 타당성을 알 수 있다.


또한 합병 정렬의 시간복잡도가 nlgn이다. 1000과 10000는 약 13배 정도 차이 나는데 미세한 값으로 변수가 발생하는 부분이 있기 때문에

정확한 증명을 위해서는 더욱 큰 값을 적용할 필요가 있어보인다.


이 와중에도 퀵 정렬은 시간 측정이 안될 정도로 정말 빠른 성능을 보여주었다. 



3. n = 100,000


선택,삽입,버블 정렬은 앞과 같다.



합병 정렬은 숫자가 커질수록 nlgn의 증가율과 점점 가까워지고 있음을 확인하였다. 

(시간 측정은 어느정도 변수가 있기 때문에 정확한 측정값은 확인하기 힘들었다)

퀵 정렬은 정렬 갯수가 10만이 넘어서야 측정이 되었다.


4. n = 1,000,000



선택,삽입,버블 정렬의 시간이 말도안되게 길어지기 시작했기 때문에 저 셋은 테스트하지 않았다.

사실은 시도는 하였지만 지금까지 측정 시간으로 볼 때 이론상 선택, 버블은 9000초, 삽입은 4000초로 약 2시간 반, 1시간 정도 걸리기 때문에 포기하였다.




5. n = 10,000,000



합병정렬은 유사한 증가율을 보이는데 퀵 정렬은 왜인지 갑자기 30배 가까이 증가했다.

그래도 여전히 합병 정렬보다 빠른 속도를 가지고 있다.




1억개부터는 저 둘로도 마냥 빠르게 측정되지 않기 때문에 여기까지만 테스트하였다. 

지금까지 테스트로 퀵 정렬이 상대적으로 높은 성능을 보임을 알 수 있었고, 합병 정렬은 퀵 정렬에 미치지는 못하지만 그래도 나머지 정렬에 비해 상당한 성능임을 확인 할 수 있었다.


또한 버블 정렬과 선택 정렬, 삽입 정렬은 데이터 10만개 이상부터는 실제로 쓰기엔 어려운 성능을 보였다. 그 이하의 데이터에선 합병, 퀵 정렬보단 느리지만 사용해도 크게 무방할것 같다는 생각이 든다.


밑은 이 테스트를 위해 작성한 코드이다.





#include <cstdio>
#include <algorithm>
#include <vector>
#include <ctime>
using namespace std; 

//난수 생성기 
int myrandom (int i) { return rand()%i;}
vector<int> randGenerator(int n){
    vector<int> v;
    srand(time(NULL));
    for(int i=0;i<=n;i++){
        v.push_back(i);
    } 
    random_shuffle(v.begin(),v.end(),myrandom);
    return v;
}

//선택 정렬 
void selectionSort(vector<int> v){
    for(int i=0;i<v.size()-1;i++){
        for(int j=i+1;j<v.size();j++)
            if(v[i]>=v[j])
                swap(v[i],v[j]);
    }
//  printf("--선택 정렬 결과--\n");
//  for(int i = 0; i<v.size();i++)
//      printf("%d ",v[i]);
//  printf("\n\n");
}

// 삽입 정렬 
void insertionSort(vector<int> v){
    for(int i=1;i<v.size();i++){
        int key = v[i], j = i-1;
            while(j>=0 && key <v[j]){
                swap(v[j], v[j+1]);
                j--;
            }
            v[j+1] = key;
    }
//  printf("--삽입 정렬 결과--\n");
//  for(int i = 0; i<v.size();i++)
//      printf("%d ",v[i]); 
//  printf("\n\n");
}

//버블 정렬 
void bubbleSort(vector<int> v){
    for(int i=0;i<v.size()-1;i++){
        for(int j=1; j<v.size()-i;j++)
            if(v[j-1] > v[j])
                swap(v[j-1],v[j]);
    }
//  printf("--버블 정렬 결과--\n");
//  for(int i = 0; i<v.size();i++)
//      printf("%d ",v[i]);
//  printf("\n\n");
}


//병합 정렬 
void merge(vector<int>& v, int s, int e, int m) {
    vector<int> ret;
    int i = s, j = m + 1, copy = 0;
    
    //결과를 저장할 배열에 하나씩 비교하여 저장한다. 
    while (i <= m && j <= e) {
        if (v[i] < v[j])ret.push_back(v[i++]);
        else if (v[i] > v[j])ret.push_back(v[j++]);
    }

    //남은 값들을 뒤에 채워넣어준다. 
    while (i <= m)  ret.push_back(v[i++]);
    while (j <= e)  ret.push_back(v[j++]);
    
    //원래 배열에 복사해준다. 
    for (int k = s; k <= e; k++) {
        v[k] = ret[copy++];
    }
}

void mergeSort(vector<int>& v, int s, int e){
    if(s<e){
        int m = (s+e)/2;
        /*divide, 분할*/
        mergeSort(v,s,m);//s부터 m까지
        mergeSort(v,m+1,e); //m+1부터 e까지 
        /*conquer, 병합*/
        merge(v,s,e,m);
    }
}



//퀵 정렬 
void qsort(vector<int>& v, int s, int e) {
    int pivot = v[s];
    int bs = s, be = e;
    while (s<e) {   
        while (pivot <= v[e]&&s<e) e--;
        if (s>e) break;
        while (pivot >= v[s]&&s<e) s++;
        if (s>e) break;
        std::swap(v[s], v[e]);
    }
    std::swap(v[bs], v[s]);
    if(bs<s)
        qsort(v,bs, s-1);
    if(be>e)
        qsort(v,s+1, be);

}


int main(){
    clock_t start,end;
    int n;// 숫자 갯수
    printf("랜덤 숫자 범위(1~n) : ");
    scanf("%d",&n);
    vector<int> v = randGenerator(n);
    
//  printf("정렬 전 : ");
//  for(int i=0;i<n;i++)
//      printf("%d ",v[i]);
    printf("\n\n");
    start = clock();    
    selectionSort(v);
    end = clock();
    printf("선택 정렬 수행시간 : %lf\n",(double)(end-start)/CLOCKS_PER_SEC);
    
    start = clock();
    insertionSort(v);
    end = clock();
    printf("삽입 정렬 수행시간 : %lf\n",(double)(end-start)/CLOCKS_PER_SEC);
    
    start = clock();
    bubbleSort(v);
    end = clock();
    printf("버블 정렬 수행시간 : %lf\n",(double)(end-start)/CLOCKS_PER_SEC);
    
    vector<int> v2 = v; 
    
    start = clock();
    mergeSort(v2,0,v.size()-1);  
    end = clock();
//  printf("--병합 정렬 결과--\n");
//  for(int i=0;i<v2.size();i++)
//      printf("%d ",v2[i]);
//  printf("\n\n"); 
    printf("병합 정렬 수행시간 : %lf\n",(double)(end-start)/CLOCKS_PER_SEC);


    start = clock();
    qsort(v,0,v.size()-1); 
    end = clock();
//  printf("--퀵 정렬 결과--\n");
//  for(int i=0;i<v.size();i++)
//      printf("%d ",v[i]);
//  printf("\n"); 
    printf("퀵 정렬 수행시간   : %lf\n",(double)(end-start)/CLOCKS_PER_SEC);
    
}


정렬 알고리즘은 n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘이다.

예를 들어 n개의 숫자가 저장되어있는 배열을, 오름차순의 조건으로 작성하여 입력하면 오름차순으로 정렬된 배열을 출력으로 구할 수 있다.

정렬 알고리즘은 정말 다양한데, 이에 따라 각각의 수행시간도 천차 만별이다.

여기서는 우선 O(N^2), O(NlgN)인 알고리즘을 보려고 한다.


1. 선택 정렬(Selection Sort)


선택 정렬은 이름에 맞게 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 현재 위치에 저장 될 값의 크기가 작냐, 크냐에 따라 최소 선택 정렬(Min-Selection Sort)와 최대 선택 정렬(Max-Selection Sort)로 구분 할 수 있다.

최소 선택 정렬은 오름차순으로 정렬될 것이고, 최대 선택 정렬은 내림차순으로 정렬될 것이다.


기본 로직은 다음과 같다.

① 정렬 되지 않은 인덱스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다.

(정렬되지 않은 인덱스의 맨 앞은, 초기 입력에서는 배열의 시작위치일 것이다.)

② 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.

③ 다음 인덱스에서 위 과정을 반복해준다.


이 정렬 알고리즘은 n-1개,n-2개,..,1개씩 비교를 반복한다.

배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 O(n^2)이다.


공간복잡도는 단 하나의 배열에서만 진행하므로 O(n)이다.



<선택 정렬>


선택 정렬 C++ 소스코드


(이전에는 temporary 변수에 해당 키 값을 저장하지 않고 그냥 그때그때 스왑하도록 하였으나.

다른 분들의 피드백으로 수정하였습니다)

void selectionSort(vector<int> v){
    for(int i=0;i<v.size()-1;i++){
        int tmp = i;
        for(int j=i+1;j<v.size();j++){
            if(v[tmp]>=v[j]) tmp = j;
        }
        swap(v[i], v[tmp]);
    }
}



2. 삽입 정렬(Insertion Sort)


삽입 정렬은 현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 배열 알고리즘이다.


기본 로직은 다음과 같다.

① 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장해주고, 비교 인덱스를 현재 인덱스 -1로 잡는다.

② 별도로 저장해 둔 삽입을 위한 변수와, 비교 인덱스의 배열 값을 비교한다. 

③ 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복한다.

④ 만약 삽입 변수가 더 크면, 비교 인덱스+1에 삽입 변수를 저장한다.


이 정렬 알고리즘 또한 최악의 경우(역으로 정렬되어있을 경우)엔 n-1개,n-2개,..,1개씩 비교를 반복하여 시간복잡도는 O(n^2)이지만.

이미 정렬되어 있는 경우에는 한번씩 밖에 비교를 하지 않아 시간 복잡도는 O(n)이다.
하지만 상한을 기준으로 하는 Big-O notation은 최악의 경우를 기준으로 평가하므로 삽입 정렬의 시간복잡도는 O(n^2)이다.

공간복잡도는 단 하나의 배열에서만 진행하므로 O(n)이다.


<삽입 정렬>

삽입 정렬 C++ 소스코드

//삽입 정렬
void insertionSort(vector<int> v){
    for(int i=1;i<v.size();i++){
        int key = v[i], j = i-1;
            while(j>=0 && key <v[j]){
                swap(v[j], v[j+1]);
                j--;
            }
            v[j+1] = key;
        }   
}


위 코드는 위키피디아 이미지를 통해 좀 더 이해를 쉽게하고자 swap 함수를 이용하였으나, 사실 swap이 아닌 대입연산을 사용하는 것이 조금 더 적합하다.

swap(v[j], v[j+1]) => v[j+1] = v[j]


3. 버블 정렬(Bubble Sort)


버블 정렬은 매번 연속된 두개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법이다. 

오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 이동하여, 1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장된다.

맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장 되기 때문에, (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼만 반복해 주면 된다.


기본 로직은 다음과 같다.

① 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스 값과, 바로 이전의 인덱스 값을 비교한다.

② 만약 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다. 

③ 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열값을 비교한다.

④ 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.


이 정렬 알고리즘은 1부터 비교를 시작하여, n-1개,n-2개,..,1개씩 비교를 반복하며,

선택 정렬과 같이 배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 O(n^2)이다.

공간복잡도도 이 또한 단 하나의 배열에서만 진행하므로 O(n)이다.


<버블 정렬>


버블 정렬 C++ 소스코드

//버블 정렬 
void bubbleSort(vector<int> v){
    for(int i=0;i<v.size()-1;i++){
        for(int j=1; j<v.size()-i;j++)
            if(v[j-1] > v[j])
                swap(v[j-1],v[j]);
        
    }
}




4. 합병 정렬(Merge Sort)


합병 정렬은 분할 정복(Divide and conquer) 방식으로 설계된 알고리즘이다. 분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해 나가는 방식으로,

분할은 배열의 크기가 1보다 작거나 같을 때 까지 반복한다.


입력으로 하나의 배열을 받고, 연산 중에 두개의 배열로 계속 쪼게 나간 뒤, 합치면서 정렬해 최후에는 하나의 정렬을 출력한다.


합병은 두 개의 배열을 비교하여, 기준에 맞는 값을 다른 배열에 저장해 나간다.

오름차순의 경우 배열 A,배열 B를 비교하여 A에 있는 값이 더 작다면 새 배열에 저장해주고, A인덱스를 증가시킨 후 A,B의 반복을 진행한다.

이는 A나 B중 하나가 모든 배열값들을 새 배열에 저장할 때 까지 반복하며, 전부 다 저장하지 못한 배열의 값들은 모두 새 배열의 값에 저장해준다.


분할 과정의 기본 로직은 다음과 같다.

① 현재 배열을 반으로 쪼깬다. 배열의 시작 위치와, 종료 위치를 입력받아 둘을 더한 후 2를 나눠 그 위치를 기준으로 나눈다.

② 이를 쪼갠 배열의 크기가 0이거나 1일때 까지 반복한다.


합병 과정의 기본 로직은 다음과 같다.

① 두 배열 A,B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 i,j로 가정하자.

② i에는 A배열의 시작 인덱스를 저장하고, j에는 B배열의 시작 주소를 저장한다.

③ A[i]와 B[j]를 비교한다. 오름차순의 경우 이중에 작은 값을 새 배열 C에 저장한다. 

    A[i]가 더 컸다면 A[i]의 값을 배열 C에 저장해주고, i의 값을 하나 증가시켜준다.

④ 이를 i나 j 둘중 하나가 각자 배열의 끝에 도달할 때 까지 반복한다.

⑤ 끝까지 저장을 못한 배열의 값을, 순서대로 전부 다 C에 저장한다.

⑥ C 배열을 원래의 배열에 저장해준다.


이 정렬 알고리즘은 분할 과정과 합병 과정이 나뉘어진다.


합병 과정은 두 배열 A,B를 정렬하기 때문에, A배열의 크기를 N1, B배열의 크기를 N2라고 할 경우

O(n1+n2)와 같다. 배열 A와 배열 B는 하나의 배열을 나눈 배열들이기 때문에 전체 배열의 길이가 N이라고 할 경우

N = N1 + N2이므로 O(N)이라고 할 수 있다.


분할 과정은 lgN만큼 일어나는데, 이 이유는 간단하다. 크기가 N인 배열을 분할하면, 한번 분할하면 N/2,N/2 2개, 그다음 분할하면 N/4,N/4,N/4,N/4 4개.

즉 분할 과정은 매번 반씩 감소하므로 lgN만큼 반복해야 크기가 1인 배열로 분할 할 수 있다.


각 분할별로 합병을 진행하므로, 합병정렬의 시간 복잡도는 O(NlgN) 이다.

사용하는 공간은 정렬을 위한 배열을 하나 더 생성하므로 2N개 사용한다. 


<합병 정렬>

합병 정렬 C++ 소스코드

//합병 void merge(vector<int>& v, int s, int e, int m) { vector<int> ret; int i = s, j = m + 1, copy = 0; //결과를 저장할 배열에 하나씩 비교하여 저장한다. while (i <= m && j <= e) { if (v[i] < v[j])ret.push_back(v[i++]); else if (v[i] > v[j])ret.push_back(v[j++]); } //남은 값들을 뒤에 채워넣어준다. while (i <= m) ret.push_back(v[i++]); while (j <= e) ret.push_back(v[j++]); //원래 배열에 복사해준다. for (int k = s; k <= e; k++) { v[k] = ret[copy++]; } } //합병 정렬 void mergeSort(vector<int>& v, int s, int e){ if(s<e){ int m = (s+e)/2; /*divide, 분할*/ mergeSort(v,s,m); //s부터 m까지 mergeSort(v,m+1,e); //m+1부터 e까지 /*conquer, 합병*/ merge(v,s,e,m); } }




5. 퀵 정렬(Quick Sort)


퀵 정렬 또한 분할 정복(Divide and conquer)을 이용하여 정렬을 수행하는 알고리즘이다. 

pivot point라고 기준이 되는 값을 하나 설정 하는데, 이 값을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬을 진행한다.

이를 반복하여 분할된 배열의 크기가 1이되면 배열이 모두 정렬 된 것이다.


기본 로직은 다음과 같다.

① pivot point로 잡을 배열의 값 하나를 정한다. 보통 맨 앞이나 맨 뒤, 혹은 전체 배열 값 중 중간값이나나 랜덤 값으로 정한다.

② 분할을 진행하기에 앞서, 비교를 진행하기 위해 가장 왼쪽 배열의 인덱스를 저장하는 left 변수, 가장 오른쪽 배열의 인덱스를 저장한 right변수를 생성한다. 

③ right부터 비교를 진행한다. 비교는 right가 left보다 클 때만 반복하며. 비교한 배열값이 pivot point보다 크면 right를 하나 감소시키고 비교를 반복한다.

    pivot point보다 작은 배열 값을 찾으면, 반복을 중지한다.

④ 그 다음 left부터 비교를 진행한다. 비교는 right가 left보다 클 때만 반복하며. 비교한 배열값이 pivot point보다 작으면 left를 하나 증가시키고 비교를 반복한다.

    pivot point보다 큰 배열 값을 찾으면, 반복을 중지한다.

⑤ left 인덱스의 값과 right 인덱스의 값을 바꿔준다.

⑥ 3,4,5 과정을 left<right가 만족 할 때 까지 반복한다.

⑦ 위 과정이 끝나면 left의 값과 pivot point를 바꿔준다.

⑧ 맨 왼쪽부터 left - 1까지, left+1부터 맨 오른쪽까지로 나눠 퀵 정렬을 반복한다.


퀵 정렬은 분할과 동시에 정렬을 진행하는 알고리즘이다.

각 정렬은 배열의 크기 N만큼 비교하며, 이를 총 분할 깊이인 lgN만큼 진행하므로 총 비교횟수는 NlgN, 즉 시간 복잡도는 O(NlgN)이다.

다만 퀵 정렬에는 최악의 경우가 존재하는데, 이는 배열이 이미 정렬이 되어있는 경우이다. 이 경우 분할이 N만큼 일어나므로 시간 복잡도는 O(N^2)이다.

이를 방지 하기 위해 앞서 언급했던 전체 배열 값 중 중간값이나나 랜덤 값으로 pivot point를 정하는 방법을 쓰기도 한다.


최악의 경우 때문에 합병 정렬보다 느린 알고리즘이라 생각하기 쉽지만, 발생하기 쉽지 않은 경우이고, 일반적으로 퀵 정렬이 합병정렬보다 20%이상 빠르다고 한다.

이는 바로 다음에 포스트할 정렬의 성능 측정 부분에서 보도록 하겠다.


<퀵 정렬>


퀵 정렬 C++ 소스코드

//퀵 정렬 
void qsort(vector<int>& v, int s, int e) {
    int pivot = v[s];
    int bs = s, be = e;
    while (s<e) {   
        while (pivot <= v[e]&&s<e) e--;
        if (s>e) break;
        while (pivot >= v[s]&&s<e) s++;
        if (s>e) break;
        std::swap(v[s], v[e]);
    }
    std::swap(v[bs], v[s]);
    if(bs<s)
        qsort(v,bs, s-1);
    if(be>e)
        qsort(v,s+1, be);

}



그 외 똑같이 NlgN에 작동하는 힙 정렬, 선형 시간에 작동하는 Count 정렬, Radix 정렬 등등이 있다. 이것 또한 나중에 정리해보도록 하겠다.




<이미지 출처 : 위키피디아>

모듈은 다른 언어에서 사용하는 라이브러리, API와 같다.

node.js에서는 global 모듈 외에 모든 필요한 기능을 사용하고자 할 때는 모듈(라이브러리)를 로딩하여 사용해야 한다.


모듈은 기본적으로 require함수를 이용하여 로딩한다.

(require은 global 모듈에 있는 함수이기 때문에, 어디서든지 사용 가능한 함수이다.)

만약 http 모듈을 로딩한다면 다음과 같이 입력하면 된다.

var http = require('http');

http 변수 내에 http 모듈이 로딩된다.


node.js에서 설치 시 자동적으로 기본 모듈이 설치된다.

기본적으로 제공되는 모듈은 node.js의 공식 홈페이지에서 제공하는 문서에서 확인 할 수 있다.


node.js api 문서 : https://nodejs.org/dist/latest-v5.x/docs/api/


기본 모듈을 제외한 모듈들은 (ex, nodeman, formidable, multer 등등) npm이라는 패키지 관리자 도구를 이용해 설치해야 한다.


기본적으로 제공되는 모듈은 다음과 같다.


process : 프로세스에 대한 정보를 담고 있는 전역 객체

utility : 타입 검사, 포메팅 등의 유틸리티 함수 제공

events : 이벤트 관련 함수 제공

buffers : 바이너리 데이터의 옥텟 스트림(octet stream)을 다루는 모듈  streams :스트림을 다루기 위한 추상 인터페이스

crypto : 암호화에 대한 함수 제공

TLS/SSL : 공개키, 개인키 기반인 TLS/SSL 에 대한 함수 제공

File System : 파일을 다루는 함수 제공

Path : 파일 경로를 다루는 함수 제공

Net : 비동기 네트워크 통신 기능 제공

UDP : UDP의 데이터그램 소켓 (Datagram Sockets) 통신 기능 제공

DNS : 도메인 네임 서버를 다루는 함수 제공

TTP : HTTP 서버 및 클라이언트 기능 제공

HTTPS : HTTPS 서버 및 클라이언트 기능 제공

URL : URL을 다루는 함수 제공

Query Strings : URL의 쿼리 문자열을 다루는 함수 제공

Readline : 스트림에서 라인 단위로 읽는 기능을 제공

Vm : 자바스크립트 실행 기능 제공

Child Processes : 자식 프로세스 생성과 관련된 함수 제공

Assert : 유닛 테스트를 위한 단언문을 제공

TTY : 터미널이나 콘솔 관련 기능을 제공

Zlib : zlib 압축, 해제 함수 제공

OS : 운영체제에 대한 정보를 구하는 함수 제공

Cluster : 여러 노드 프로세스를 실행하는 클러스터 기능을 제공 

(출처 : T아카데미 node.js 자료)




'Javascript > node.js' 카테고리의 다른 글

비동기 흐름 제어를 위한 모듈 - async  (0) 2016.09.18
node.js 시작하기  (0) 2016.03.01

+ Recent posts