오늘 다루어볼 정렬 주제는 바로 퀵정렬입니다. 이름만에서도 알 수 있듯이 빠른 속도를 자랑합니다.
하지만 다른 정렬 알고리즘에 비해서 병합정렬과 더불어 까다로운 정렬 알고리즘인데요. 사실 이해만 정확히 한다면 그리 어려운 알고리즘은 아니지요.
개념
퀵 정렬에서 우선 pivot이라는 개념부터 알아야합니다. 뭐 어렵지 않습니다. 그냥 비교할 기준이라고 생각하면 되겠네요.
배열의 원소들은 피봇보다 작으면 왼쪽, 피봇보다 크면 오른쪽에 놓이는데요.
바로 아래 그림을 보면서 이해하도록 합시다.
정렬되지 않은 배열 arr= {5,6,7,3,4,2,1,9}가 있다고 하겠습니다. 이 배열에서 피봇은 1번째 원소인 5라고 가장하겠습니다.
퀵 소트를 한번 돌게 된다면 5를 기준으로 작은 원소들은 모두 왼쪽에, 큰 원소들은 모두 오른쪽에 놓이게 됩니다.
이제 이런 짓을 계속하다가 보면 어느 순간 정렬된 형태가 나오는 것이죠. 병합정렬을 배운 분이라면 뭔가 보이지 않나요?
퀵정렬의 분할정복
퀵 정렬은 병합정렬과 마찬가지로 분할 정복의 아주 대표적인 예입니다. 하지만 정직하게 2로 나누는 병합정렬과는 다르게 퀵정렬은 비대칭으로 두동강을 내버립니다. 내 얼굴
아래 그림에서 일부를 쪼개고 다시 합치는 과정이 보이세요? 이것이 분할-정복의 개념입니다.
분할퀵정렬은 우선 피봇을 기준으로 2개로 나누지요. 나누고 쪼개는 것이 바로 분할입니다. 분할을 통해서 큰 문제를 여러개의 문제로 조각을 내서 더 쉽게 문제를 푼다는 개념입니다.
정복분할 이후에 다시 정렬의 과정을 거치게 됩니다.
병합정복 이후 다시 합치는 과정을 병합이라고 합니다. 원래의 커다란 문제를 풀기 위해서는 해결했던 조각난 문제들을 다시 합쳐야하기 때문에 병합이라는 과정이 필요하죠.
구현
다음의 코드가 바로 퀵소트를 구현한 것입니다.
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
void quickSort(int left, int right, int *arr) {
int pivot = arr[left];
int less = left;
int more = right+1;
if (left < right) {
do {
do
less++;
while (less <= right && arr[less] < pivot);
do
more--;
while (more >= left && arr[more] > pivot);
if (less < more)
swap(&arr[less], &arr[more]);
} while (less < more);
swap(&arr[left], &arr[more]);
quickSort(left, more - 1,arr);
quickSort(more + 1, right, arr);
}
}
소스코드를 보면 가장 왼쪽의 원소가 피봇이라는 것을 알 수 있네요. 이 피봇값을 기준으로 작다면 배열에 왼쪽으로 놓고 크다면 오른쪽으로 놓는 것이죠. 그 후에 피봇의 위치를 찾고 다시 피봇의 위치 기준으로 배열을 쪼개서 재귀호출을 하게 됩니다.
우리는 do ~ while 문으로 위 코드를 쓰기 때문에 more은 right의 한칸 더 뒤에 있어야합니다. do ~ while문의 특징은 우선 한번은 실행시키기 때문입니다.
역시 less 그렇습니다. 가장 첫번째 left의 위치부터 시작해야 피봇 다음 원소부터 비교할 수 있는 것입니다.
어려울 수 있으니 다시 그림과 함께 이 코드를 봅시다.
우선 초기 상태는 이렇습니다. 그림에서도 볼 수 있듯이 less는 left의 위치에 있고, more은 right의 다음번째에 있습니다. 이제 do ~ while문을 실행하는 거죠.
less는 5보다 큰 원소가 있으면 멈추고 more은 5보다 작은 원소가 있으면 멈춥니다.
자, 6과 1이 걸리게 되겠죠? 6은 5보다 크니까 오른쪽에 있어야하고 1은 5보다 작으니 왼쪽에 있어야합니다. 그러니까 less와 more의 원소를 교환합시다. 그 후 계속 이 과정을 반복할 겁니다.
이제는 7과 2가 걸리게 되겠네요. 역시 교환합시다.
3과 4는 5보다 작으니까 지나가고 less는 7을 만나게 되면 멈춥니다. 그리고 more은 4를 만날때까지 왼쪽으로 가게 되죠. 하지만 이때 more과 less가 교차하게 됩니다. 이때 우리는 more과 less 사이의 지점, 그 지점이 바로 피봇이 위치하게 되는 지점이 되는 겁니다. 그러니 피봇이 있는 위치 left와 more과 swap하게 되면 5를 기준으로 작은 원소는 왼쪽에, 큰 원소들은 오른쪽에 위치하게 되는 것이죠.
최종상태는 위와 같습니다. 이제 5(pivot)을 기준으로 다시 이러한 과정을 반복하게 됩니다.
이제 이해가 되셨나요?
시간복잡도
위의 분할 정복의 그림에서 봤듯이 계속 두개로 쪼개 n번 비교하게 되므로 시간 복잡도는 평균적으로 O(nlogn)이 됩니다.
하지만 이미 정렬된 배열에서도 O(nlogn)이 나오게 될까요? 이 경우에는 O(n^2)이 됩니다. 피봇의 위치가 항상 왼쪽이라면 항상 2개로 쪼개지는 것이 아니라 pivot을 제외한 배열을 정렬하게 되는 샘이지요.
하지만 퀵소트가 빠른 점은 바로 pivot은 정렬에 포함시키지 않기 때문이죠. 그러므로 병합정렬보다 빠릅니다. 그러니까 이름이 Quick Sort이지요.
그리고 퀵 정렬은 배열의 공간외에는 다른 공간을 쓰지 않기 때문에 공간복잡도는 O(n)입니다.
배열에서 어떤 원소를 찾을때 그 원소가 있는지 어떻게 찾을 수 있을까요?b가장 간단한 방법은 아무래도 for루프를 실행하면서 하나하씩 일치하는지 검색하는 방법이겠죠?
너무 쉽습니다.
int arr[10] = { 3,5,6,8,9,11,14,15,18,20 };
int i;
int data = 18;
int found = -1;
for (i = 0; i < sizeof(arr); i++)
if (arr[i] == data) found = arr[i];
printf("found:%d\n", found);
이러한 탐색시간은 O(n)에 해당합니다. 배열원소를 하나하나씩 전부 일치하는지 확인하기 때문이죠.
이보다 빠르게 찾을 수는 없을까요? 이 탐색시간을 O(logn)으로 수행할 수 있는 방법이 바로 이진탐색(Binary Search)입니다.
개념
이진탐색은 우선 정렬된 배열에서만 사용가능합니다. 정렬되지 않았다면 정렬을 해주어야하지요.
또한 이진탐색은 3개의 변수가 사용이 됩니다. 바로 left, mid, right이지요. 초기상태에서 배열의 가장 첫번째를 가리키고 있는 left, 배열의 가장 끝을 가리키고 있는 right, left와 right의 중간을 가리키고 있는 변수가 mid입니다.
우리가 찾는 원소를 data라고 합시다. 우리는 mid의 값을 중요하게 생각해야 돼요. mid자리에 있는 원소가 data와 같다면 그 원소를 찾게 된 것이죠.
만약 mid자리에 있는 원소보다 data가 크다면 left~mid까지 범위는 탐색할 필요가 없게 되지요. 반대로 mid자리 원소보다 data가 작다면 mid~right까지의 범위는 탐색할 필요가 없습니다.
찾지 못 한다면 범위를 바꾸어줘야합니다. left~mid까지의 범위를 탐색할 필요가 없다면 이제 left=mid+1이 되고 mid 역시 left, right의 중간값인 (left+right)/2가 됩니다. 그 반대도 역시 마찬가지죠. 정리하자면 이렇습니다.
우선 초기에 left=0, mid=4, right=9입니다. mid의 값은 (left+right)/2로 계산된 값입니다. arr[mid]와 data를 비교해보니 data가 더 크군요. 그러니까 left와 mid까지의 범위는 볼 필요가 없습니다. 정렬된 배열이기 때문에 18보다 작은 것들은 left~mid까지이니까요.
이제 범위를 옮기도록 하지요. left=mid+1이 되고 mid는 그 중간 값인 (left+right)/2가 됩니다. 이제 다시 arr[mid]와 data를 비교해보니 data가 더 크지요? 다시 범위를 바꿉니다
이제 left와 mid는 같은 값이 되고 다시 arr[mid]와 data를 비교해보니 일치합니다. data가 배열에 있다는 것을 알게 됐습니다.
만일 data를 찾지 못한다면 left와 right는 서로 뒤집히게 됩니다. 그러니까 left가 right보다 더 크게 변한다는 의미입니다.
구현
아래코드는 원소가 존재한다면 몇번째에 위치하는지 인덱스를 구해냅니다. 구현을 통해서 위의 결과를 확인해보세요.
int binarySearch(int *arr,int size,int data) {
int left = 0;
int right = size - 1;
while (left<=right) {
int mid = (left + right) / 2;
if (arr[mid] == data)
return mid;
if (arr[mid] > data)
right = mid - 1;
else
left = mid + 1;
}
return -1;
}
초기 left=0, right=size-1입니다. 가장 처음과 끝을 가리키고 있지요. while루프의 탈출조건은 left가 right보다 같거나 작을때까지 입니다.
while루프에서는 우선 mid의 값을 구하고 이 mid 원소와 data를 비교하여 같은지 확인합니다. 원소를 찾지 못하면 left와 right의 값을 바꿉니다.
간단하죠?
이진탐색은 재귀함수로도 간단하게 구현이 가능합니다.
int binarySearch(int *arr,int left,int right,int data) {
if (left > right) return -1;
int mid = (left + right) / 2;
if (arr[mid] == data) return mid;
if (arr[mid] > data)
return binarySearch(arr, left, mid - 1, data);
return binarySearch(arr, mid + 1, right, data);
}
재귀함수도 너무 간단하죠? 기자사례는 위의 while루프와 같다는 것을 알 수 있습니다. 재귀함수의 종료 조건이되지요.
그 후 내부 코드는 while루프의 내부 코드와 유사하다는 것을 알 수 있습니다. 그렇죠?
아참, 주의할것은 호출할때 binarySearch(arr,0, (sizeof(arr)/sizeof(int))-1, data)로 호출해야합니다. 만약 arr의 크기가 10이라면 9를 right의 매개변수로 전달하는 것이죠. 왜냐면 크기가 10인 배열의 마지막 인덱스는 9이기 때문이죠.
시간복잡도
결국 이진탐색은 반으로 계속 줄여가면서 원소를 탐색하기 때문에 시간복잡도는 O(logn)이라는 사실을 알 수 있습니다. O(n)에 비해서는 훨씬 빠른 속도입니다.
하지만 배열이 정렬된 상태여야 된다는 점이 조금 아쉬운 부분이기는 하지만 하나의 배열에서 검색을 자주하는 상황이라면 한번 정렬만 하면 다음부터는 계속 O(logn)의 속도로 원소를 찾을 수 있죠.
네트워크에서 아주 기본적인 지식은 OSI7 계층입니다. OSI7계층은 국제 표준기구인 ISO(International Organization for Standardization)으로부터 탄생합니다.
처음 네트워크 장치는 중구난방이었습니다. 때문에 회사의 장비마다 호환이 되지 않으며 복잡했었죠. 이에따라 네트워크를 7계층으로 분리하면서 표준을 만들게 되었습니다. 그것이 바로 OSI 7 계층입니다.
OSI 7 계층 구조
이렇게 생겨먹었습니다. 딱 7개로 나뉘어져 있지요?
그림을 보면 알겠지만 응용계층에서 내려온 데이터부터 시작해서 계속 헤더가 붙는 것을 알 수 있습니다. 이 헤더에는 그 계층에 대한 정보가 기록되어있지요.
우리가 이메일을 보낸다고 가정할때 처음 응용계층에서 헤더를 붙여 하위 계층으로 넘겨줍니다. 표현계층은 응용계층에서 내려온 헤더와 이메일 데이터를 하나의 데이터로 간주하게 됩니다. 그래서 다시 자신의 헤더를 붙이게 되지요. 이런 과정은 Encapsulation이라고 합니다.
이런식으로 물리계층까지 내려오게 되면 그때부터 0과 1의 이진 비트가 전송되게 되는 것입니다.
받은 수신자는 거꾸로 물리계층부터 시작해 헤더의 정보를 확인하고 떼어냅니다. 그리고 난 후 상위 계층으로 데이터를 전달하는 것이죠. 이렇게 헤더를 떼어내는 과정은 Decapsulation이라고 합니다.
지금부터 응용계층부터 물리계층까지 간략하게 설명하도록 하지요.
물리계층(Physical Layer)
7계층 중 최하위 계층입니다. 주로 전기적, 기계적, 기능적인 특성을 이용해 데이터를 전송하게 됩니다. 데이터는 0과 1의 비트열, 즉 On, Off의 전기적 신호 상태로 이루어져있지요.
이 계층은 단지 데이터를 전달하기만 합니다. 어떤 에러가 있는지 등 그런 기능에는 전혀 관여하지 않습니다.
데이터링크 계층(Data-Link Layer)
물리 계층에서 송수신되는 정보의 오류와 흐름을 관리하여 안전한 정보의 전달을 수행할 수 있도록 도와주는 역할을 합니다.
데이터 링크 계층의 데이터 전송은 Point-To-Point 간 입니다.
안전한 정보의 전달이라는 것은 오류나 재전송하는 기능을 갖고 있다는 이야기죠. 또한 우리가 언젠가 한번 들었을 MAC주소를 갖고 있습니다. 그래서 통신을 할 수 있지요.
이 계층에서 부르는 데이터의 단위는 프레임(Frame)이라고 합니다.
네트워크 계층(Network Layer)
네트워크 계층은 네트워크에서 아주 중요합니다.
중요한 기능 중 한가지는 바로 라우팅이라고 하는데요. 목적지까지 가장 안전하고 빠르게 데이터를 보내는 기능을 말합니다. 따라서 최적의 경로를 설정해야하지요.
이런 라우팅 기능을 맡고 있는 계층이 네트워크 계층입니다.
또한 어느 컴퓨터에게 데이터를 전송할지 주소를 갖고 있어서 통신을 합니다. 우리가 자주 듣는 IP 주소가 바로 네트워크 계층 헤더에 속해있습니다.
네트워크 계층에서 부르는 데이터 단위는 패킷(Packet)이라고 합니다.
전송 계층(Transport Layer)
전송 계층 역시 네트워크에서 중요한 계층입니다. 전송 계층은 양 끝단의 사용자들이 신뢰성있는 데이터를 주고 받게 해주는 역할을 합니다.
송신자와 수신자 간의 신뢰성있고 효율적인 데이터를 전송하기 위하여 오류검출 및 복구, 흐름제어와 중복검사 등을 수행합니다.
중요한 것은 데이터 전송을 위해서 Port 번호가 사용이 됩니다. 대표적인 프로토콜로는 TCP와 UDP가 있습니다. 이 계층에서 사용하는 데이터 단위는 세그먼트(Segment)라고 합니다.
세션 계층(Session Layer)
세션 계층은 응용 프로세스가 통신을 관리하기 위한 방법을 정의합니다.
이 계층은 세션을 만들고 없애는 역할을 하고 있지요.
표현 계층(Presentation Layer)
데이터를 어떻게 표현할 지 정하는 역할을 하는 계층으로 일종의 확장자라고 이야기하면 편하겠네요.
표현 계층은 세가지의 기능을 갖고 있습니다.
1. 송신자에서 온 데이터를 해석하기 위한 응용계층 데이터 부호화, 변화
2. 수신자에서 데이터의 압축을 풀수 있는 방식으로 된 데이터 압축
3. 데이터의 암호화와 복호화
MIME 인코딩이나 암호화 등의 동작이 표현계층에서 이루어집니다. EBCDIC로 인코딩된 파일을 ASCII 로 인코딩된 파일로 바꿔주는 것이 한가지 예이지요.
응용 계층(Application Layer)
사용자와 가장 가까운 계층이 바로 응용 계층입니다. 우리가 사용하는 응용 서비스나 프로세스가 바로 응용계층에서 동작합니다.
최소 스패닝 트리의 크루스칼 알고리즘과 프림 알고리즘의 동작 방법을 알아보았으니 이제 코드로 구현해 볼 차례입니다.
그때 썼던 그래프를 다시 가져다가 써보도록 하죠.
우리는 이 그래프의 최소 스패닝트리를 프림알고리즘으로 구하는 원리는 알고 있으니 위의 그래프를 코드로 구해보도록 합시다. 여기서는 C++을 사용하여 보다 쉽게 구현할 겁니다.
int prim(vector<pair<int, int> > &selected) {
selected.clear();
vector<bool> added(V, false);
vector<int> minWeight(V, INF), parent(V, -1);
int ret = 0;
minWeight[0] = parent[0] = 0;
}
우선 필요한 변수들을 선언했습니다.
selected 변수에는 우리가 선택한 간선의 정점 정보가 저장될 겁니다. 일단 selected.clear()로 벡터를 비워주도록 합시다.
added변수는 현재 트리에 어떤 정점이 있는지 체크하기 위한 변수입니다.
만약 정점 3이 트리에 포함되어 있다면 added[3]=true이지요. 처음에는 어떤 정점도 트리에 포함되지 않으므로 added 벡터는 전부 false로 초기화가 됩니다.
minWeight에는 트리에 붙어있는 정점 중 가장 가까운 정점이 들어있습니다. 초기에는 선택된 정점이 아직 없으므로 가장 큰 값을 설정합니다.
parent에는 정점의 부모를 나타냅니다. 만일 어떤 정점 u가 있다면 그 부모 정점은 parent[u]가 되는 것이죠.
ret는 최소 스패닝 트리의 모든 간선의 값을 나타냅니다.
이제 우리는 정점 0을 기준으로 트리를 만들어 나갈건데 0의 부모는 자기 자신이고, 자기 자신까지의 거리는 0입니다.
for (int iter = 0; iter < V; iter++) {
}
위의 for 루프는 모든 정점까지 반복하는 루프입니다. 이 안이 우리가 구현해야 할 부분이지요.
이제 이 for루프를 구현해보도록 하죠.
int u = -1;
for (int v = 0; v < V; v++) {
if (!added[v] && (u == -1 || minWeight[u]>minWeight[v]))
u = v;
}
if (parent[u] != u)
selected.push_back(make_pair(parent[u], u));
u라는 변수는 초기에 -1을 지정합니다. 이미 트리에 저장되지도 않았고, 트리의 가장 가까운 정점을 찾는 것이죠.
만약 u의 부모가 u가 아니라면 u의 부모와 u로 구성된 정점 쌍을 selected에 저장합니다.
u==-1일 경우에는 언제일까요? u가 첫 시작점(첫 스타트를 끊었을때)일 때 -1이라는 것이죠. 가장 처음으로 시작하기 때문에 아직 추가된 정점이 없고, 가장 처음에 시작했기 때문에 u==-1이지요.
ret += minWeight[u];
added[u] = true;
추가를 했으니 ret에 값을 추가하고 트리에 추가되었다는 표시를 해야되겠죠??
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i].first, weight = adj[u][i].second;
if (!added[v] && minWeight[v]>weight) {
parent[v] = u;
minWeight[v] = weight;
}
}
이제 다음 후보 정점들을 찾아야하는데요. v에는 u와 인접한 정점이 저장되고 weight에는 그 정점과 u까지의 간선 값을 나타냅니다.
이미 추가된 정점이면 추가하면 안되겠죠? 사이클이 발생하니까요.
그림을 보면서 이 코드를 더 자세히 보도록 합시다.
만일 u와 인접한 정점 v3가 있다고 칩시다. 이 정점은 트리에 추가되지도 않았을 뿐더러 minWeight[v3]=3 입니다. 하지만 u와는 2의 거리에 놓여있으므로 minWeight[v3]=2로 수정해주는 것이죠. 그리고 v3의 부모는 u가 되는 것입니다.
이제 끝났습니다. ret를 반환하면 최소 스패닝 트리의 값이 나오게 되지요.
전체 소스코드
아래는 프림알고리즘을 CPP로 구현한 전체 소스코드랍니다.
#include <iostream>
#include <vector>
using namespace std;
const int MAX_V = 100;
const int INF = 987654321;
int V=6;
vector<pair<int, int> > adj[MAX_V];
int prim(vector<pair<int, int> > &selected) {
selected.clear();
vector<bool> added(V, false);
vector<int> minWeight(V, INF), parent(V, -1);
int ret = 0;
minWeight[0] = parent[0] = 0;
for (int iter = 0; iter < V; iter++) {
int u = -1;
for (int v = 0; v < V; v++) {
if (!added[v] && (u == -1 || minWeight[u]>minWeight[v]))
u = v;
}
if (parent[u] != u)
selected.push_back(make_pair(parent[u], u));
ret += minWeight[u];
added[u] = true;
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i].first, weight = adj[u][i].second;
if (!added[v] && minWeight[v]>weight) {
parent[v] = u;
minWeight[v] = weight;
}
}
}
return ret;
}
int main() {
adj[0].push_back(make_pair(1, 5));
adj[1].push_back(make_pair(0, 5));
adj[1].push_back(make_pair(2, 3));
adj[2].push_back(make_pair(1, 3));
adj[2].push_back(make_pair(3, 4));
adj[3].push_back(make_pair(2, 4));
adj[1].push_back(make_pair(4, 3));
adj[4].push_back(make_pair(1, 3));
adj[0].push_back(make_pair(3, 7));
adj[3].push_back(make_pair(0, 7));
adj[2].push_back(make_pair(4, 2));
adj[4].push_back(make_pair(2, 2));
adj[3].push_back(make_pair(5, 1));
adj[5].push_back(make_pair(3, 1));
adj[4].push_back(make_pair(5, 4));
adj[5].push_back(make_pair(4, 4));
vector<pair<int, int> > selected;
int mst=prim(selected);
printf("mst:%d\n", mst);
for (int i = 0; i < selected.size(); i++) {
printf("%d-%d\n", selected[i].first, selected[i].second);
}
printf("\n");
}
main함수에서는 각 간선을 연결해주고 weight도 부여합니다.
예를 들어
adj[4].push_back(make_pair(5,4))
adj[5].push_back(make_pair(4,4))
라는 것은 4와 5의 정점을 연결하는데 그 간선의 weigt는 4라는 것입니다. 또한 그래프가 무향 그래프이기 때문에 거꾸로도 연결해야하는 것이죠.
그래서 각각 짝을 맞추어서 간선을 연결해주어야합니다.
mst는 최소스패닝트리의 간선값의 합을 나타냅니다. 따라서 단지 최소스패닝트리의 값만 보고 싶다면 mst를 쓰면 되구요.
우선 어떤 무향 그래프가 있다고 해보도록 가정하겠습니다. 스패닝 트리는 말 그대로 그래프에서 트리의 상태를 유지해야합니다. 그러니 사이클이 있으면 안되지요. 반드시 부모와 자식 관계로 이루어져 있지 않아도 됩니다.
다음의 그림은 올바른 스패닝 트리와 그렇지 않은 스패닝 트리를 보여줍니다.
왼쪽의 그림의 선택된 간선(굵은 선)은 사이클을 이루지 않지요.
반면 오른쪽 그림은 빨간선 때문에 사이클을 이루게 됩니다.
어때요? 간단하지요?
스패닝 트리는 그래프에서 여러개가 존재할 수도 있지만 우리가 눈여겨 볼 것은 스패닝 트리의 간선들이 가장 최소의 값을 갖는 것으로 바로 최소 스패닝 트리(Minimum Spanning Tree)라고 합니다.
대표적인 알고리즘에는 대표적으로 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 있는데요. 이 두가지 알고리즘을 함께 보도록 하지요.
크루스칼 알고리즘 개념(Kruskal's Algorithm Concept)
우리는 아래의 그래프의 최소 스패닝 트리를 구할 겁니다. 이제 이 그래프를 가지고 크루스칼 알고리즘이 어떻게 동작하는지를 확인해 보도록 할게요.
원리는 이렇습니다.
1. 스패닝 트리에 포함되지 않는 가장 작은 값의 간선을 찾는다.
2. 그 간선이 이미 만들어진 트리에 포함되어 있는지 확인한다.
3. 그 간선이 추가된다면 이미 만들어진 트리에서 사이클을 이루는 지 확인한다.
4-1. 그 간선이 트리에 포함되어 있고 사이클이 있다면 다른 간선을 확인한다.
4-2. 그 간선이 위의 두 조건에 성립되지 않으면 스패닝 트리에 포함시킨다.
우리는 위의 조건들을 가지고 최소 스패닝 트리를 찾는 겁니다.
우선 가장작은 간선의 값인 1, 즉 3-5의 간선을 봅니다. 현재 선택된 간선은 없으므로 3-5의 간선을 추가합니다. 그 다음 작은 간선을 보면 2인데, 이 간선은 현재 추가된 간선이 없으므로 2-4의 간선도 추가합니다.
이제 추가된 간선은 3-5, 2-4의 간선(파란색)입니다. 그 후 가장 작은 간선을 보면 1-2인데 이 간선은 추가된적이 없으므로 추가합니다. 그 후 역시 3인 간선이 있는데요. 이 간선을 추가하게 되면 사이클을 이루게 됩니다. 그러니까 다음 간선으로 넘어가게 되지요.
그 다음 작은 간선은 2-3입니다. 값은 4인데, 이 간선은 현재 추가한적이 없지요?(파란색 간선이 추가한 간선입니다.) 그러니 이 간선을 포함시키도록 합니다.
그 후 4-5 간선을 보게 되면 현재 선택되지는 않았지만 추가하게 되면 사이클을 이루게 됩니다. 그러니 넘어가죠.
이후 간선 0-1의 간선을 추가합니다. 다음으로 큰 수가 5이니까요.
이제 모든 정점이 트리에 포함되었으니 종료합니다.
따라서 최종 최소 스패닝 트리는 아래의 그림과 같습니다.
어떻습니까??
가장 최소의 값으로 스패닝 트리를 완성했다는 것을 알 수 있습니다.
프림 알고리즘 개념(Prim's Alogorithm Concept)
이번에는 최소 스패닝 트리의 다른 알고리즘, 프림 알고리즘을 보도록 하지요. 프림 알고리즘은 트리에 연결된 간선 중 가장 작은 것을 차례차례 선택해나갑니다. 크루스칼 알고리즘과 같은 점은 역시 사이클을 이루는 간선을 선택하지 않는다는 것이죠.
어느 정점에서 시작하든 상관없습니다. 우리는 3번의 정점부터 계속 트리에 정점을 추가할 것입니다. 3과 가장 가까운 정점은 5가 되겠네요. 3과 5를 트리에 추가합니다. 3, 5 정점 중 가장 작은 간선은 2-3과 4-5네요. 구현에 따라 다를수 있으므로 둘 중에 아무거나 선택하면 됩니다. 2-3의 간선을 선택하지요. 따라서 트리에는 2가 추가가 됩니다.
이제 2, 3, 5에 붙어 있는 간선 중 가장 작은 간선 2-4를 선택합시다.
그렇다면 현재 트리에는 2, 3, 4, 5가 됩니다. 이제 이 정점에서 가장 작은 간선을 선택해보도록 하지요. 후보는 1-2 간선과 1-4 간선이 됩니다. 아무거나 선택합시다.
1-2의 간선을 선택하지요.
그 후 트리에 속해있는 정점과 붙어있는 가장 작은 간선은 1-4의 간선이 되는 군요. 하지만 선택할 수 없습니다. 사이클을 이루니까요. 그러니 버립시다.
다음 가장 작은 간선은 4-5의 간선입니다. 이것 역시 사이클을 이루게 되죠? 그러니 그냥 버리도록 합시다.
다음으로 가장 작은 간선은 0-1의 간선입니다. 이 간선을 포함해도 사이클을 이루지 않으니 선택하도록 하지요.
그렇다면 이제 모든 정점이 트리에 포함되어 있습니다. 여기서 종료합니다.
프림 알고리즘과 크루스칼 알고리즘이 동작하는 방식은 다르나 최소 스패닝 트리를 구할 수 있다는 것을 알 수 있습니다. 두 알고리즘 다 15의 값을 갖는 최소 스패닝 트리를 만들어 낼 수 있었습니다. 최소 스패닝 트리는 여러개 존재할 수는 있지만 그 값은 같다는 것을 잊지마세요.
다익스트라 알고리즘은 한 시작점에서 다른 정점까지의 최단 거리를 구하는데 반해 플로이드 알고리즘은 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구할 수 있습니다!
단, 플로이드 알고리즘은 음수 가중치가 없는 무조건 양수의 그래프에서 동작합니다.
경유점
어떤 정점 a와 b가 연결되어 있다고 할때 이 정점 사이에 c가 있다고 하지요. a와 b로 연결되어 있는 간선의 비용이 5라고 하구요.
하지만 a와 c의 비용은 2, b와 c의 비용은 2라고 한다면 a와 b로 가는데 c를 거쳐가는 것이 더 효율적이라는 것을 알 수 있습니다. a-c-b의 비용은 4이기 때문에 a-b의 비용 5보다 비용이 더 적습니다.
c와 같이 경로가 거쳐가는 정점이 경유점이라고 하지요.
플로이드 알고리즘은 두 정점 사이의 어떤 경유점이 존재한다면 경유점을 거쳐가는 것을 확인하면서 더 짧은 것을 선택하게 됩니다.
구현
아래와 같은 그래프가 있는데 모든 쌍의 최단거리는 어떻게 될까요?
1-4까지의 최단 거리?
0-3까지의 최단 거리?
...
이런 물음을 빈번하게 묻는 문제가 나올땐 다익스트라 알고리즘을 모든 정점에 대해서 구할 수 있지만 플로이드 알고리즘을 쓰면 보다 쉽고 또 빠르게 구할 수 있다는 장점이 있지요.
이제 본격적으로 구현해보도록 합시다.
그래프의 초기화
위의 그래프를 우선 배열로 구현해야합니다. 조건이 있는데, 초기에 직접적으로 연결되어 있지 않은 경로는 아주 큰 값으로 설정해야한다는 것이죠. 그리고 자기 자신까지의 비용은 0으로 만들어 줍니다.
정점
0
1
2
3
4
0
0
2
3
INF
INF
1
2
0
INF
INF
10
2
3
INF
0
1
4
3
INF
INF
1
0
2
4
INF
10
4
2
0
플로이드 알고리즘 적용
이제 플로이드 알고리즘만 적용시켜주면 되지요.
시작점은 i, 끝점을 j, 경유점을 k라고 했을때 구하는 식은 다음과 같습니다.
adj[i][j]=MIN(adj[i][j], adj[i][k]+adj[k][j])
이 경유점 k를 지나는 모든 i, j에 대해서 확인해주면 됩니다.
adj[i][j]와 adj[i][k]+adj[k][j] 중 항상 작은 값만을 갖게 되므로 직접적으로 연결이 되지 않는 간선은 INF로 처음에 초기화 한 이유를 아시겠어요?
만일 경유점 k가 0이라고 할때 adj[1][2] = MIN(adj[1][2], adj[1][0] + adj[0][2]) = MIN( INF, 5) = 5 가 됩니다. 결국 1-2까지의 경로는 5로 더 작은 값이 됨을 알 수 있죠.
그 후 경유점이 k=2가 되었다고 할때 adj[1][3] = MIN(adj[1][3], adj[1][2] + adj[2][3]) = MIN(INF, 6) = 6이 됩니다. 왜냐면 방금전 adj[1][2]를 구해냈기 때문이지요. 그래서 1-3까지의 비용은 6이 되는 것을 알 수 있습니다.
이렇게 모든 경유점을 확인하면서 비용이 작은 값만을 선택합니다.
이제 전체 코드를 보면서 결과를 확인해보세요.
#include <stdio.h>
#define MAX_V 10
#define MIN(a,b) a<b ? a:b
#define INF 987654321
int V,E;
int adj[MAX_V][MAX_V];
void initAdj() {
int i, j;
for (i = 0; i < V; i++)
for (j = 0; j < V; j++) {
adj[i][j] = INF;
if (i == j)adj[i][j] = 0;
}
}
void floyd() {
int k,j,i;
for (k = 0; k < V; k++)
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
adj[i][j] = MIN(adj[i][j], adj[i][k] + adj[k][j]);
}
int main() {
int i, j;
printf("정점 개수:");
scanf("%d", &V);
printf("간선 개수:");
scanf("%d", &E);
initAdj();
printf("정점 연결( 정점1 정점2 비용) \n");
for (i = 0; i < E; i++) {
int v1, v2, cost;
scanf("%d %d %d", &v1, &v2, &cost);
adj[v1][v2] = adj[v2][v1] = cost;
}
floyd();
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++)
printf("%d~%d까지의 최단거리:%d\n", i, j, adj[i][j]);
printf("\n\n");
}
}
경유점 k의 순서가 꼭 0부터 V까지 순차적일 필요는 없습니다. 경유점을 어느 순서로 해도 상관이 없다는 것이죠.
복잡도
위 코드의 시간복잡도는 O(V^3)이 되고 공간복잡도는 O(V^2)가 됩니다. 플로이드 알고리즘은 V가 작고 모든 정점의 최단 거리를 구할때 아주 유용하고 쉽게 구현할 수 있기 때문에 기억해둘만한 가치가 충분히 있습니다.
시그널에 대해서 이야기하는 3번째 시간이 되겠네요. 지난 번에는 시그널 개념과 시그널 관련함수까지 다루어 봤습니다.
시그널 개념과 시그널 핸들러와 시그널 관련 함수(sigfillset, sigemptyset, sigaddset, sigdelset, sigprocmask)는 지난 번 포스팅을 참고하시기 바랍니다.
이번에는 시그널에 대한 sigpending과 sigismember에 대해서 알아보도록 하겠습니다.
sigpending
int sigpending(sigset_t *set);
현재 블록되어 대기중인 signal들을 set에 담게 됩니다. 만일 블록될 signal들이 {SIGINT, SIGTSTP} 라고 하고 SIGTSTP가 블록된 상태라면 set에는 {SIGTSTP}가 들어가게 되지요. 이 함수가 성공했다면 0, 실패했다면 -1을 반환합니다.
sigisempty
int sigismember(sigset_t *set, int signo);
현재 set에 signo(시그널 번호)가 포함되어 있는지 알아냅니다. 만약 set에 해당하는 시그널 번호가 존재한다면 1, 없다면 0을 반환하게 됩니다. -1을 반환할때도 있는데 이 경우는 시그널을 확인할 수 없다는 의미랍니다. 간단하죠?
이제 간단하게 예제를 보도록 합시다.
#include <stdio.h>
#include <signal.h>
#include <unistd.h>
int main(){
sigset_t pendingset;
sigset_t set;
sigemptyset(&set);
sigemptyset(&pendingset);
sigaddset(&set,SIGQUIT);
sigaddset(&set,SIGINT);
sigaddset(&set,SIGTSTP);
sigprocmask(SIG_BLOCK,&set,NULL);
printf("SIGQUIT, SIGINT, SIGTSTP를 발생시켜보세요.\n");
sleep(3);
if(sigpending(&pendingset)==0){
printf("\n\nBlock되어 대기중인 SIGNAL\n");
if(sigismember(&pendingset,SIGQUIT))
printf("SIGQUIT\n");
if(sigismember(&pendingset,SIGINT))
printf("SIGINT\n");
if(sigismember(&pendingset,SIGTSTP))
printf("SIGTSTP\n");
}
sleep(3);
sigprocmask(SIG_UNBLOCK,&set,NULL);
printf("SIGQUIT OR SIGINT OR SIGTSTP 신호를 발생시켰으면 이 메
시지가 보이지 않습니다.\n");
return 0;
}
이 프로그램은 set에 있는 시그널들이 발생하면 블록하고 만약 이 중 시그널이 발생하면 블록된 시그널의 목록을 보여주는 프로그램입니다. 우선 set에는 SIGQUIT, SIGINT, SIGTSTP라는 시그널이 들어있고 sigprocmask로 블록시키라고 명령합니다. 이 후 3초가 지난후 sigpending으로 블록되어 대기중인 signal을 pendingset에 설정합니다. 함수가 성공적으로 호출되었다(반환값 0)면 sigismember에서 어떤 시그널이 대기중인지 확인합니다.
시그널을 BLOCK시킴과 동시에 대기합니다. sigprocmask같은 경우 how를 SIG_BLOCK이나 SIG_SETMASK로 설정하면 블록하기만 할뿐 대기하지는 않는데, sigsuspend는 블록과 대기를 동시에 할 수 있는 것이죠. 성공시 0, 실패시 -1을 반환합니다.
SIGQUIT, SIGINT, SIGTSTP를 sigprocmask의 SIG_SETMASK로 블록시키려고 하는군요. 5초 후에 set을 빈 집합으로 설정합니다. 만일 SIGQUIT, SIGINT, SIGTSTP가 5초 이내에 발생했다면 프로그램은 5초후 바로 종료하게 되고, 발생시키지 않았다면 위 3개의 시그널이 발생할때까지 대기하게 되는 것입니다.
여러개의 신호를 간편하게 다루기 위해서는 신호를 집합으로 표시하는 자료 형식이 필요하게 됩니다. 단순히 생각해보면 int 형식을 한비트마다 하나의 신호로 대응시켜 집합으로 표시할 수도 있지만, int의 비트보다 더 많은 신호가 존재할 수 있기 때문에 신호만의 새로운 자료 형식이 필요하게 되었습니다. int의 비트 32비트이고 신호는 32개가 넘게되니까요. 이러한 자료 형식이 sigset_t라는 자료 형식입니다. sigset_t는 신호의 집합임을 기억합시다.
이런 신호 집합을 왜 쓰게 될까요? 앞에서 얘기했다시피 많은 신호를 간편하게 다루기 위함입니다. 모든 신호를 막는다거나(BLOCK), 막은 신호를 다시 푼다던가(UNBLOCK), 신호가 발생했지만 Block되어서 대기(PENDING) 중인 신호가 무엇이 있는가, 이러한 작업을 쉽게 할 수 있습니다. 프로세스는 신호 집합을 가지고 있고 관리합니다. 이와 연관된 함수가 추가로 필요하게 되는데, 그것이 오늘 소개할 함수들입니다.
시그널 중에서 SIGSTOP와 SIGKILL은 절대 제어할 수 없으므로 알아두시기 바랍니다.
o sigfillset, sigemptyset
int sigfillset(sigset_t *set);
int sigemptyset(sigset_t *set);
이 두 함수는 setset_t라는 집합에서 모든 시그널을 추가하거나 모든 시그널을 제거합니다. 성공시 0, 실패시 -1을 반환하구요. 아래는 sigfillset과 sigemptyset의 동작과정을 말해줍니다.
sigfillset을 사용하면 모든 시그널을 집합에 추가하는데요. 반대로 sigemptyset은 set이라는 집합에서 시그널을 전부 깨끗이 지워줍니다.
o sigaddset, sigdelset
int sigaddset(sigset_t *set, int signum);
int sigdelset(sigset_t *set, int signum);
이 함수들은 이름에서 알 수 있듯 signal을 추가하거나 삭제합니다. 역시 성공시 0, 실패시 -1을 반환합니다.
기존의 SIGSEGV와 SIGHUP이 있는 set에서 SIGINT를 추가하면 set은 {SIGINT, SIGSEGV, SIGHUP}가 있게 됩니다. 거기서 SIGHUP을 sigdelset으로 제거하면 결국 set에는 {SIGSEGV, SIGINT}가 존재하게 되는 것입니다.
o sigprocmask
int sigprocmask(int how, const sigset_t *set, sigset_t oldset);
sigprocmask는 시그널을 블록시킬지 말지를 결정합니다.
how : 시그널을 어떻게 제어할지를 말해줍니다. how에는 세가지 동작이 있는데요.
1. SIG_BLOCK : 기존에 블록된 시그널이 있다면 두 번째 인자는 set의 시 그널을 추가하라는 의미입니다.
2. SIG_UNBLOCK : 기존의 블록된 시그널에서 set의 시그널을 제거합니 다.
3. SIG_SETMASK : 기존의 블록된 시그널을 전부 제거시키고 새로운 set 의 시그널들을 블록시킵니다.
set : how가 동작하는 방식에 따라 기존의 block된 시그널에 대해 set을 추가시킬지, 제거시킬지, 아니면 전부 set으로 설정할지를 의미합니다. 그러니 set은 이번에 설정할 시그널이라고 기억해두세요.
oldset : 이 전에 블록된 시그널들을 저장합니다.
예제 코드 1)
sigprocmask는 우선 이해하기가 조금 까다로운데요. 주석을 통해서 설명을 하긴 했지만 그림이 조금 필요하겠네요. 아래는 sigprocmask를 통해서 시그널을 제어하는 코드입니다.
#include <stdio.h>
#include <signal.h>
#include <unistd.h>
int main(){
sigset_t set, oldset;
sigemptyset(&set);
sigemptyset(&oldset);
sigaddset(&set,SIGINT);
sigaddset(&set,SIGQUIT);
sigprocmask(SIG_BLOCK,&set,NULL);
printf("SIGINT와 SIGQUIT는 블록되었습니다.\n");
printf("Ctrl+C와 Ctrl+\\ 눌러도 반응이 없습니다.\n");
//만약 Ctrl + \(SIGQUIT)을 눌렀다면 5초후 Coredump가 생기고 종료
//SIGQUIT의 기본동작은 Coredump + 종료
sleep(5);
//현재 set에서 SIGINT를 뺌. set에는 SIGQUIT만 있는 상태
//중요한것은 프로세스에 적용하지 않은 상태
sigdelset(&set,SIGINT);
//프로세스에 Unblock을 set에 적용. SIGQUIT은 이제 Block되지 않음
sigprocmask(SIG_UNBLOCK,&set,&oldset);
printf("만약 Ctrl+\\을 눌렀다면 종료합니다.\n");
printf("현재 남은 시그널은 SIGINT입니다.\n");
printf("Ctrl+C를 눌러도 반응이 없습니다.\n");
sleep(5);
set=oldset;
sigprocmask(SIG_SETMASK,&set,NULL);
printf("다시 SIGINT와 SIGQUIT이 블록됩니다.\n");
printf("Ctrl+C와 Ctrl+\\ 눌러도 반응이 없습니다.\n");
sleep(5);
sigprocmask(SIG_UNBLOCK,&set,NULL);
//아무 시그널(Cntl +C 혹은 Cntl+\)을 주지 않았다면 아래의 메시지가 출력되고 종료
printf("모든 시그널이 해제되었습니다.\n");
}
이제 하나하나씩 까보도록 합시다.
1.
초기에 현재 프로그램의 블록된 시그널은 없습니다. set과 oldset도 역시 깨끗이 비워줍니다.
5초가 지나면 set에서 SIGINT를 제거하는 군요. 그렇다면 set에는 SIGQUIT만 남게 되죠. sigprocmask로 set에 있는 집합을 blocked signal에서 제거합니다.
하지만 oldset이 설정되어있었네요. 그러니까 oldset은 기존에 블록된 시그널이 잡히게 됩니다. 기존에 블록된 시그널은 위의 그림에서 SIGINT와 SIGQUIT이었군요. 그 후 blocked signal에서 set에 있는 시그널을 제거하게 되면 SIGINT만 남겠네요.
아래 그림에서 보여주듯 blocked signal에는 결국 SIGINT만 남게됩니다. 따라서 5초이내에 SIGQUIT을 보냈다면 프로그램이 코어덤프와 함께 종료됩니다. SIGQUIT의 블록 상태가 풀리게 되니까요.
5.
이후 set은 oldset의 값을 복사하네요.
set=oldset;
6.
sigprocmask(SIG_SETMASK,&set,NULL);
이제 SIG_SETMASK로 set에 있는 시그널들을 blocked signal에 설정합니다. 설정하는 것입니다. 추가하는 것이 아니에요.
그러니 blocked signal에는 SIGINT와 SIGQUIT이 다시 설정되는 것을 알 수 있죠.
그래서 다시 SIGINT와 SIGQUIT을 보내도 5초간 아무 응답이 없게 되지요.
7.
sigprocmask(SIG_UNBLOCK,&set,NULL);
5초가 지난 후 set에 있는 시그널들을 blocked signal에서 제거하게 되는데요. 만약 5초 전에 SIGINT나 SIGQUIT 신호를 주었다면 바로 종료하게 되는 겁니다.
왜냐면 5초가 지나면 아래의 그림처럼 blocked signal에서 SIGINT와 SIGQUIT이 존재하지 않으니 블록된 시그널은 풀리게 되면서 프로그램이 종료가 됩니다.
만약 SIGINT 또는 SIGQUIT를 보내지 않았다면 프로그램은 "모든 시그널이 해제되었습니다" 라는 메세지와 함께 종료될겁니다.
process의 signal 정보는 어디에?
그렇다면 프로그램 실행시, 이 process의 block된 시그널의 정보는 어디에 저장이 되고 관리가 될까요? 즉, 위의 그림에서 blocked signal은 누가 관리해주냐는 것입니다. 이에 대한 정보들은 kernel의 task_struct 구조체로 인해 관리가 됩니다. task_struct는 process나 thread가 실행될때마다 하나씩 생성이 되는데, 여기에 정말 많은 정보들이 들어있습니다. 다음은 signal 관련 field들입니다.
// linux/sched.h
struct task_struct {
#ifdef CONFIG_THREAD_INFO_IN_TASK
...
/* Signal handlers: */
struct signal_struct *signal;
struct sighand_struct *sighand;
sigset_t blocked;
sigset_t real_blocked;
/* Restored if set_restore_sigmask() was used: */
sigset_t saved_sigmask;
struct sigpending pending;
unsigned long sas_ss_sp;
size_t sas_ss_size;
unsigned int sas_ss_flags;
};
task_struct의 멤버를 보게되면 blocked, real_blocked라는 이름이 보이시죠? sigset_t 어디서 많이 보았죠? 이처럼 kernel에서 task_struct를 통해서 관리하여진다는 것입니다.
이상으로 signal 집합을 제어하는 함수들을 소개하고 알아보았습니다. 다음 포스팅은 sigpending과 관련된 함수에 대해서 알아보도록 하겠습니다.
