안녕하세요!


그래프 알고리즘을 배우기 전에 반드시 알아야 할 부분이 있습니다!


바로 그래프의 표현 방법입니다.  그래프 관련 문제를 해결하기 위해서는 주어진 그래프를 표현해야 하고,


그 데이터를 바탕으로 그래프 알고리즘을 적용시켜 해결해야 합니다. 


그럼 이제 본격적인 설명에 앞서, 그래프를 표현하는 방법에는 어떤 것들이 있는지 간단한게 알아보고 가도록 하겠습니다.


그래프를 표현하는 방법은 세 가지가 있습니다.


  • 인접 행렬(Adjacency matrix) : 두 노드간의 엣지 상태를 행렬 형태로 표현
  • 인접 리스트(Adjacency list) : 각 노드 별로 연결되어있는 노드들만 표현
  • 간선 리스트(Edge list) : 위의 방법들과 달리 엣지만을 리스트 형태 혹은 배열 형태로 저장하는 방법입니다.

[그래프1 - 방향이 없는 그래프]

[그래프2 - 방향이 있는 그래프]



이제부터 위 그래프를 각 방법으로 표현해 보겠습니다.


인접 행렬(Adjacency matrix)


[그래프1 - 인접 행렬]

[그래프2 - 인접 행렬]



인접 행렬은 노드와 노드 사이의 관계를 행렬 형태로 표현하는 방법입니다.


위 행렬에서 표현된 값이 0이면 노드 자신을 의미, INF면 직접적으로 연결 X, 나머지 값들은 연결된 엣지의 가중치입니다.


그래프 형태에 따라서 간선의 방향이 없으면 대칭행렬 형태로, 방향이 있다면 일반 행렬처럼 표현하면 되는 방식입니다.


이 특성때문에 인접 행렬 방식은 다음과 같은 특징을 같습니다.


1) 두 노드간의 엣지에 직접 접근할 수 있습니다. 예) g[4][2] : 4번노드와 2번노드의 엣지


2) 모든 노드쌍의 관계를 표현해야 하기 때문에 공간복잡도가 O(V^2) 소요됩니다.


따라서 인접 행렬은 밀집 그래프(엣지수가 많은) 형태에서 좋은 성능을 발휘하고 적절한 공간을 소요한다고 여겨지지만,


희소그래프(엣지수가 적은) 형태에서는 공간낭비가 매우 심합니다.(어떤 문제에서는 이 특성때문에 메모리 초과가 발생하기도 합니다)



인접 리스트(Adjacency list)


 

 [그래프1 - 인접 행렬]

 

[그래프2 - 인접 행렬]


이 방법은 인접 행렬에서 INF와 같은 불필요한 데이터를 제거하고, 실제 존재하는 그래프만을 표현하기 위한 방식입니다.


표현하는 방법은 정점을 기준으로 연결되어 있는 간선을 리스트형태 추가시켜 나가면 됩니다. 


방향이 없는 그래프라면 각 두 노드 리스트에 [상대 노드, 가중치] 형태를 갖는 자료구조를 추가해주면 됩니다.


반면에 방향이 있다면, 출발 노드 리스트에 [목적지 노드, 가중치] 형태를 갖는 자료구조를 추가해주면 됩니다.


이런 리스트적 특징 때문에 인접 리스트에서는 다음 특징을 갖습니다.


1) 두 노드간의 엣지가 존재 여부를 조사하기 위해서는 순차 탐색을 해야하기 때문에 O(V) 시간이 소요됩니다.


2) 인접 행렬과는 달리, 존재하는 엣지만을 표현하기 때문에 O(E) 만큼의 공간이 소요됩니다.


위 특징 때문에 모든 엣지 혹은 적은 엣지를 조사해야하는 그래프 알고리즘에서 유용하게 활용됩니다. 


하지만, 밀집 그래프 형태의 문제에서는 1번 특징으로 인해 시간 초과 문제가 발생할 수 있습니다.



간선 리스트(Edge list)


 

 


간선 리스트는 다른 두 방식과는 달리 엣지를 중심으로 표현하는 방법입니다.


즉, 단순하게 [노드1(혹은 출발 노드), 노드2(혹은 도착 노드), 가중치] 형태의 자료구조를 리스트 또는 배열 형태로 저장하는 방식입니다.


따라서 모든 엣지를 살펴보는 알고리즘에서 간편하고 직관적으로 활용할 수 있습니다.




각 방법을 사용해서 주어진 그래프를 표현해 봤습니다.


코드 레벨에서 설명하지는 않았지만, 이는 앞으로 다룰 그래프 관련 알고리즘에서 적어도 한 번씩은 다룹니다.


그때 코드 레벨에서 설명해드리도록 하겠으니 "아! 이런 방식이구나" 정도의 느낌만 알고 가시면 됩니다!

'공부 > 알고리즘' 카테고리의 다른 글

[알고리즘] - 너비 우선 탐색(BFS) #10  (0) 2020.07.26
[알고리즘] - 깊이 우선 탐색(DFS) #9  (0) 2020.01.19
[알고리즘] - 합병 정렬(Merge sort) #7  (2) 2019.02.06
[알고리즘] - 퀵 정렬(Quick sort) #6  (0) 2019.01.31
[알고리즘] - 선택 정렬(Selection sort) #5  (0) 2019.01.16

안녕하세요 고급 정렬 알고리즘 두 번째이자 마지막 시간입니다!


힙 정렬이 하나 더 있기는 하지만 별도의 자료구조가 필요하기 때문에 추후에 다루도록 하겠습니다.


그럼 빠르게 본론으로 들어가보겠습니다!


합병 정렬(Merge sort) - 안정 정렬(Stable sort)


합병 정렬은 데이터를 이분할 하는 작업을 반복하여 크기가 1인 데이터까지 분할하고, 


이 데이터들을 정렬해 나가며 최종적으로 완전 정렬하는 알고리즘입니다.


즉, 분할 정복 기법을 이용한 정렬 방법입니다.


따라서 합병 정렬은 분할, 정복(정렬) 이 두 단계로 이루어져 있습니다.


그림과 함께 조금 더 자세하게 설명해 드리도록 하겠습니다.


- 분할 단계



맨 처음 정렬해야 하는 데이터(7-3-2-1-5-4-6) 가 있습니다.


우선, 주어진 데이터의 인덱스를 0(start)~6(end)번이라고 생각해 보겠습니다.


이를 이분할 하기 위해서 중간점(mid)를 계산해야 하며 mid 는 다음과 같이 계산됩니다.


mid = (start + end) / 2


그렇게 되면 전반부 구간은 start~mid, 후반부 구간은 mid+1~end로 정할 수 있습니다.


이러한 구간 정보를 아래와 같이 분할 함수의 인자로 넘겨주는 작업을 반복(재귀)적으로 수행합니다.


분할(data, start, end){

mid = (start+end) / 2;

분할(data, start, mid);

분할(data, mid+1, end);

}


그렇게 되면 주어진 데이터는 최종적으로 크기가 1인 데이터 까지 분할됩니다.



- 정복(정렬) 단계



정복 단계에서는 분할된 구간을 정렬해 나가면서 부분 문제를 해결합니다.


즉, 분할 이후에 정복 과정을 거치게 되는 것이죠. 간략하게 표현하자면 다음과 같습니다.


분할(data, start, end){

mid = (start+end) / 2;

분할(data, start, mid); //부분 문제 해결로 전반부 정렬 완료

분할(data, mid+1, end); //부분 문제 해결로 후반부 정렬 완료

정복(data, start, mid, end); //전반부와 후반부를 비교하며 정렬

}


이제 정복함수의 간략적인 구성에 대해서 알아보도록 하겠습니다.


정복 함수는 크게 두 단계로 이루어져 있는데, 바로 임시 배열을 채우는 과정과 원래 배열에 임시 배열 값을 복사하는 과정입니다.


1) 전반부와 후반부 데이터를 비교하며 임시 배열 채우기


오름차순으로 정렬한다면, 전반부와 후반부의 데이터 중 작은 값을 비교해가며 임시 배열을 채웁니다.


이 과정을 전반부 혹은 후반부의 데이터가 빌 때 까지 진행하고, 이후 남은 데이터를 일괄적으로 채워주면 됩니다.


2) 임시 배열 값을 원래 배열에 복사하기


임시 배열에 정렬된 데이터를 저장했기 때문에 원래 배열에 복사해줍니다!



소스 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
int temp[7]; //정렬을 위한 임시 배열
//병합 함수 정의
void merge(int* a, int start,int mid, int end) {
    int firstPart = start;
    int lastPart = mid + 1;
    int savePoint = start;
 
    //전반부와 후반부를 비교하며 임시배열에 복사
    while ((firstPart <= mid) && (lastPart <=end)) {
        if (a[firstPart] <= a[lastPart])
            temp[savePoint++] = a[firstPart++];
        else
            temp[savePoint++] = a[lastPart++];
    }
 
    //전반부의 값이 남아 있다면
    while (firstPart <= mid)
        temp[savePoint++] = a[firstPart++];
 
    //후반부의 값이 남아 있다면
    while (lastPart <= end) 
        temp[savePoint++] = a[lastPart++];
 
    //임시 배열의 값을 원래 배열에 복사
    for (int i = start; i <= end; i++)
        a[i] = temp[i];
}
//분할 함수 정의
void partion(int * a, int start, int end) {
    int mid;
    if (start < end) {
        mid = (start + end) / 2;
        partion(a, start, mid); //전반부 - 분할 과정
        partion(a, mid + 1, end); //후반부 - 분할 과정
        merge(a, start, mid, end); //병합 - 정복 과정
    }
}
int main() {
    int a[7] = { 7,3,2,1,5,4,6 };
    partion(a,0, 6);
    for (int i = 0; i < 7; i++)
        printf("%d ", a[i]);
    return 0;
}
cs


* 소스코드 라인별 설명은 주석으로 대체하겠습니다! *

시간 복잡도




합병 정렬의 경우에는 퀵 정렬과 달리, 항상  을 보장합니다.


그 이유는 매번 이분할을 하기 때문에 분할된 구간의 크기가 항상 일정하게 형성됩니다.


따라서 위 그림처럼 크기가 N인 데이터를 이분할 했을 경우에는 의 분할이 존재하게 되고,


이 각 분할에 대해서 N번의 비교가 이루어지기 때문에 항상  을 보장합니다.


이러한 특성 때문에 합병 정렬은 안정적인 성능을 보장하는 정렬 방법으로 알려져 있습니다.


다만 합병 정렬의 경우에는 소스 코드에서 볼 수 있듯이, 정렬하기 위한 추가적인 공간이 필요하다는 특징을 가지고 있습니다.




이번 포스팅에서 준비한 내용은 여기까지 입니다!


이제 드디어 정렬이 끝났습니다. 


다음 포스팅 부터는 본격적으로 그래프 관련 알고리즘에 대해서 알아보도록 하겠습니다.


그래프 관련 알고리즘들은 코딩테스트에서도 많이 출제되는 부분이니 더 힘내서 공부해주시기 바라겠습니다!


'공부 > 알고리즘' 카테고리의 다른 글

[알고리즘] - 깊이 우선 탐색(DFS) #9  (0) 2020.01.19
[알고리즘] - 그래프의 표현 방법 #8  (0) 2019.03.13
[알고리즘] - 퀵 정렬(Quick sort) #6  (0) 2019.01.31
[알고리즘] - 선택 정렬(Selection sort) #5  (0) 2019.01.16
[알고리즘] - 삽입 정렬(Insertion sort) #4  (3) 2019.01.15

드디어 고급 정렬에 들어왔습니다.


이번에는 고급 정렬 알고리즘 중 하나인 퀵 정렬에 알아보도록 하겠습니다.


취업을 위해 알고리즘 문제를 풀게 되는데, 정렬은 이러한 문제를 푸는 데 많이 사용됩니다.


저도 문제를 풀다가 정렬을 해야할 경우 퀵 정렬을 많이 사용하곤 합니다. (왜냐하면 이름처럼 빠르기 때문이죠!)


그럼 이제부터 본격적으로 퀵 정렬에 파헤쳐 보도록 하겠씁니다.



퀵 정렬(Quick sort) - 불안정 정렬(Unstable sort)


퀵 정렬은 전체를 분할 중심보다 작은 구간, 큰 구간 으로 나누는 작업을 재귀적으로 수행하여 정렬하는 알고리즘입니다.


즉, 분할 정복 기법을 활용하는 방법입니다.


동작 하는 과정은 다음과 같습니다.




1) 분할 중심(Pivot)값 을 정합니다.

(분할 중심을 정하는 방법은 여러 가지가 있는데, 저는 마지막 원소를 분할 기준으로 정하는 방법을 사용하도록 하겠습니다.)




2) 주어진 데이터 구간을 분할 중심을 기준으로 대소 관계에 따라 두 구간으로 나눕니다.




3) 분할된 구간 중 기준 값보다 큰 구간의 첫 번째 값과 분할 중심 값을 교환합니다.




4) 나누어진 두 구간 각각에 대해서 1~3 번 과정을 반복(혹은 재귀적)으로 수행합니다.



이렇게 나누고 정렬하는 작업을 분할할 공간이 없을 때 까지 진행하면 정렬은 끝입니다!



 

소스 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#define SWAP(x,y,temp) ((temp)=(x),(x)=(y),(y)=(temp)) 
 
//분할
int partion(int * a, int left, int right) {
    //마지막 값을 분할 기준으로 설정
    int pivotValue = a[right];
    int temp;
    int i = left;
    //주어진 구간을 탐색하며 두 구간으로 분리
    for (int j = left; j < right; j++) {
        if (a[j] < pivotValue) {
            SWAP(a[j], a[i], temp);
            i++;
        }
    }
    //작은 구간과 큰 구간 사이에 분할기준 삽입
    SWAP(a[i], a[right], temp);
    return i;
}
 
//퀵 정렬
void quicksort(int * a, int left, int right) {
    int newPivotIndex;
    if (right > left) {
 
        //분할의 결과로 a배열은 pivot을 기준으로 좌측에는 작은 값 우측에는 큰 값이 위치
        newPivotIndex = partion(a, left, right);
 
        //작은 구간에 대해서 재귀적으로 퀵 정렬 진행
        quicksort(a, left, newPivotIndex - 1);
 
        //큰 구간에 대해서 재귀적으로 퀵 정렬 진행
        quicksort(a, newPivotIndex + 1, right);
    }
}
int main() {
    int a[7] = { 7,3,2,1,5,4,6 };
 
    quicksort(a, 0, 6);
 
    for (int i = 0; i < 7; i++)
        printf("%d ", a[i]);
 
    return 0;
}
cs

배열 a : 정렬하고자 하는 데이터 원본 입니다.

Line 11 - 16 : 분할 중심을 기준으로 작은 구간과 큰 구간으로 분리합니다. ( 2) 에 해당하는 과정)

Line 18 : 큰 구간의 첫 번째 값과 분할 중심을 교환합니다. ( 3) 에 해당하는 과정)

Line 19 : 분할 중심의 Index 값을 반환합니다.

Line 28 : 주어진 배열에 대해서 구간을 분리하는 Partion 함수를 호출하고 분할 중심의 Index 값을 구합니다.

Line 31 : 작은 구간에 대해서 재귀적으로 수행합니다.

Line 34 : 큰 구간에 대해서 재귀적으로 수행합니다.



시간 복잡도


우선, 앞서 설명했던 알고리즘 들과 같이 최악의 경우를 고려한 시간 복잡도를 말씀 드리겠습니다.


퀵 정렬에서 최악의 경우는 분할 기준이 매번 제일 크거나 작은 값으로 선택되는 상황입니다.


다시 말해, 이미 정렬된 데이터에 대해서 퀵 정렬을 수행하는 경우입니다.


이럴 때, 분할은 결국 N-1 번 발생하고 각 분할당 최소 1번부터 최대 N-1 번까지 비교하게 됩니다.


그렇게 된다면 결국 퀵정렬의 최악의 경우는 복잡도를 가지게 됩니다.


그럼에도 퀵 정렬을 사용하는 포인트는 다음과 같습니다.


1) 평균적인 경우를 고려하자!







우선 분할의 가장 이상적인 경우는 반반씩 나뉘는 것입니다.


다시 말해, 매 분할마다 정렬해야할 데이터의 크기가 반씩 줄어든다는 의미입니다.


따라서 그럴 경우에는  만큼 분할이 발생하고 각 분할마다 최대 N번의 데이터 비교가 발생합니다.


이런 경우에는 분할 깊이 * 비교 횟수인  시간 복잡도를 가집니다.


2) 분할 기준이 다음 정렬의 대상이 아니다!


퀵 정렬의 경우에는 분할 기준이 다음 정렬에서 정렬 대상이 포함되지 않습니다.


그렇기 때문에,  만큼의 깊이를 가져가는 정렬 방법에서 매우 효과적입니다.



왜 불안정 정렬인가?


선택 정렬이 불안정 정렬임을 보였을 때 처럼 아주 간단한 예시를 보여드리겠습니다.

(이번에도 제가 자주 사용하는 카드를 통해서 알아보겠습니다!)


우선 아래와 같이 스페이스3 - 하트5 - 클로버5 있다고 생각해 봅시다!



원본 데이터가 정렬되어 있지만, 보통 우리는 데이터가 정렬되있다고 판단하기 어렵습니다.


그렇기 때문에 데이터의 정렬 상태를 파악하지 않고 정렬을 진행하게 되는 것이죠!


이제 위 카드를 퀵 정렬 수행하게 된다면,  작은 구간(스페이스 3) / 큰 구간(하트 5) /정렬기준(클로버 5) 분리 됩니다.




그리고 나서 분할 기준(클로버 5)을 큰 구간의 첫 번째 값(하트 5)과 교환하게 됩니다.


교환 후에, 재귀적으로 수행하기 위해서 인덱스 위치를 살펴보니 더 이상 정렬할 구간이 없으므로 종료하게 됩니다.



결과를 살펴보면 기존에는 숫자 5를 가진 카드는  하트5 - 클로버5 순서로 존재했지만,


정렬 후에는 클로버 5 - 하트 5 순서로 존재함을 확인 할 수 있습니다.


따라서 퀵 정렬은 불안정 정렬이 됩니다.


여기서 추가적으로 분할 기준을 다르게 잡으면 가능할까? 라는 생각을 가지신 분들이 있을 수도 있습니다.


하지만, 퀵 정렬의 경우에는 분할 기준과의 값에 대한 교환이 필연적으로 나올 수 밖에 없기 때문에 불안정 정렬이 됩니다. 



퀵 정렬에 대한 내용은 여기까지입니다! 다음 포스팅에서는 퀵 정렬과 가장 많이 비교되는 병합 정렬에 대해서 알아보겠습니다!


개인적인 일 때문에 이번 포스팅이 많이 늦어졌는데 다음 포스팅 부터는 최대한 노력해서 빨리 올려볼게요!


감사합니다 : ) 

'공부 > 알고리즘' 카테고리의 다른 글

[알고리즘] - 그래프의 표현 방법 #8  (0) 2019.03.13
[알고리즘] - 합병 정렬(Merge sort) #7  (2) 2019.02.06
[알고리즘] - 선택 정렬(Selection sort) #5  (0) 2019.01.16
[알고리즘] - 삽입 정렬(Insertion sort) #4  (3) 2019.01.15
[알고리즘] - 버블 정렬(Bubble Sort) #3  (1) 2019.01.10

+ Recent posts

티스토리툴바