굳건하게

안녕하세요, 여행벌입니다.

오늘은 자료구조 서로소 집합(Disjoint set)과 유니온-파인드(Union-find) 기법에 대해서 다뤄보겠습니다.

Disjoint Set( 서로소 집합 )

 고등학교 때, 수학 시간에 배운 집합에서 서로 공통 원소가 없는 집합을 Disjoint Set 이라 합니다. 집합을 구현하는 데는 벡터, 배열, 연결리스트를 이용할 수 있으나 보통 그중 가장 효율적인 트리 구조를 이용하여 구현합니다.

● 어떤 집합 S에 대해서 공통 원소가 없는 부분 집합들로 나눠진 원소들에 대한 자료구조

 U = { 1, 2, 3, 4, 5, 6 } 일 때, A = { 1, 2 }, B = { 3, 4 } , C = { 5, 6 } 과 같은 경우를 Disjoint Set 이라고 표현한다. 쉽게 말하면 원소 N개를 서로 겹치지 않게 나눠가져 간다고 생각하면 됩니다. 

Union-Find (유니온-파인드)

 Disjoint Set 을 표현할 때 사용하는 알고리즘이 Union-Find 알고리즘입니다. 

● Union(x, y)

 - x가 속한 집합과 y가 속한 집합을 합친다. 즉, x 와 y가 속한 두 집합을 합집합하는 연산

● Find(x)

 - x가 속한 집합의 대푯값을 반환한다. 즉, x가 어떤 집합에 속해 있는지 찾아주는 연산

 - 트리를 이용해서 구현하므로 대푯값은 루트 노드 번호를 의미한다.

Union-Find 코드 구현

 Disjoint set 은 트리 구조를 이용해서 표현한다고 위에서 언급했습니다. 따라서, parent[x] := x 노드의 부모 노드의 번호를 저장하는 배열을 먼저 선언해야 합니다. x 노드가 루트 노드인 경우에는 자기 자신의 번호를 저장합니다.

 Find(x) := x가 속한 집합의 루트 노드를 반환합니다. 이때, 루트 노드는 자기 자신의 번호를 저장하고 있으므로, 재귀적으로 Find 함수를 호출하며 parent[x] 와 x가 같을 때 값을 return 해주면 됩니다

 Union(x, y) := x가 속한 집합과 y가 속한 집합을 합집합 해줍니다. 따라서 먼저 x와 y 노드의 루트 노드를 find 하고 그 둘이 다르다면(다른 집합이라면) 하나의 루트 노드를 다른 루트 노드로 새롭게 갱신해주면 됩니다.

int find(int node) {
	if (node == parent[node])
		return node;
	return find(parent[node]);
}

void merge(int node1, int node2) { // union 키워드는 이미 존재해서 보통 merge로 함수명을 선언합니다.
	int parentNode1 = find(node1);
	int parentNode2 = find(node2);
	if (parentNode1 == parentNode2)
		return;
	parent[parentNode1] = parentNode2;
	return;
}

 위의 예시를 parent 배열까지 함께 나타내며 다시 보겠습니다.

Find 최적화

 트리의 높이가 작아지면 작아질수록 루트 노드를 탐색하는 게 빨라집니다. 

 예를 들어 위와 같이 같은 Set을 나타내는 트리가 있다고 해봅시다. 이때 find(6) 을 수행하려면 왼쪽 트리는 루트 노드(1)을 찾기 위해 탐색을 여러 번 수행해야 하고, 오른쪽 트리는 단 한 번에 탐색을 끝낼 수 있습니다. 지금이야 원소가 6개뿐인 집합이라 탐색 횟수가 많이 차이 나지는 않지만, 트리가 커지면 커질수록 이 차이는 점점 커지게 됩니다. 따라서 우리는 트리의 노드들을 최대한 루트 노드와 직접 연결시켜야 합니다.

int find(int node) {
	if (node == parent[node])
		return node;
	return parent[node] = find(parent[node]);
}

 find 함수를 정말 조금만 수정하면 위와 같은 문제를 해결할 수 있습니다!

 parent[node] 에 find(parent[node]) 를 저장하면 됩니다! 정말 간단하죠?

 예를 들어 위의 왼쪽 그림에서 find(6) 을 수행하면, parent[6] = parent[5] = parent[3] = 1; 이 됩니다. 즉, 왼쪽 그림이 오른쪽 그림으로 바로 바뀌게 되는 것을 볼 수 있습니다.

Union 최적화

 Union 함수 최적화에 대해서도 생각을 해봐야 합니다. Find 함수와 마찬가지로 우리는 노드들의 높이가 낮으면 낮을수록 연산을 수행하기 좋습니다.

 위와 같은 상황에서 2개의 집합을 Union 할 때, 왼쪽 트리를 오른쪽 트리에 합치는 경우와 오른쪽 트리를 왼쪽 트리에 합치는 경우 2가지가 존재합니다.

 노드의 수가 더 많은 트리에 더 작은 트리를 합친 오른쪽의 경우가 전체 노드의 Level을 합했을 때 더 작은 값이 나오는 걸 알 수 있습니다. 즉, Union 을 더 큰 트리에 작은 트리를 합쳐가며 진행을 한다면 최적화를 할 수 있습니다.

 그렇다면 트리의 Size 를 따로 저장해야되는데 어떻게 하면 트리의 Size 를 저장할 수 있을까요?

 제일 간단한 방법은 Size를 저장하는 배열을 하나 더 선언하는 방법입니다.

void merge(int node1, int node2) {
	int parentNode1 = find(node1);
	int parentNode2 = find(node2);
	if (parentNode1 == parentNode2)
		return;
	if (size[parentNode1] > size[paretNode2]) {
		parent[parentNode2] = parentNode1;
		size[parentNode1] += size[parentNode2];
	}
	else {
		parent[parentNode1] = parentNode2;
		size[parentNode2] += size[parentNode1];
	}
	return;
}

Weighted-Union-Find

  위의 방법은 parent 배열과 size 배열을 2개 선언해야 해서 메모리 낭비가 심합니다. parent 배열 하나로 트리의 크기 정보까지 저장하는 방법인 Weighted-Union-Find 방법을 소개해드리겠습니다. Weighted-Union-Find 는 parent 배열에 루트 노드라면 -(집합의크기), 루트 노드가 아니라면 부모 노드를 저장합니다. 따라서, parent 배열을 -1 로 초기화합니다. 즉, 자기가 루트 노드인 경우에는 parent 값이 음수이고 아니라면 부모 노드를 가리킵니다. 따라서, find 함수는 parent 값이 음수가 나올 때까지 진행하면 됩니다. 그리고 Union 함수는 서로 다른 집합일 경우 root 노드의 parent 값이 더 작은 경우(음수이므로 절댓값은 더 큰 경우)가 더 덩치가 큰 트리이므로 작은 트리를 큰 트리에 합쳐줍니다.

int find(int num) {
	if (p[num] < 0)
		return num;
	return p[num] = find(p[num]);
}

void merge(int num1, int num2) {
	int pNum1 = find(num1), pNum2 = find(num2);
	if (pNum1 == pNum2)
		return;

	if (p[pNum1] <= p[pNum2]) {
		p[pNum1] = p[pNum1] + p[pNum2];
		p[pNum2] = pNum1;
	}
	else{
		p[pNum2] = p[pNum1] + p[pNum2];
		p[pNum1] = pNum2;
	}
	return;
}

이상으로 Disjoint Set(서로소 집합) & Union-Find(유니온 파인드) 포스팅을 마무리하도록 하겠습니다.

굉장히 자주 쓰이는 개념과 알고리즘으로 최적화까지 완벽하게 익혀두시면 좋을 것 같습니다!

안녕하세요, 여행벌입니다.

오늘은 합병정렬(Merge sort)에 대해서 포스팅해보겠습니다.

합병 정렬의 원리

 합병 정렬은 존 폰 노이만이 개발한 정렬 알고리즘입니다.

 합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법으로 분할 정복에 바탕을 두고 있습니다. 즉, 주어진 리스트를 크기가 1이 될 때까지 분할한 후 각각의 부분 리스트들을 정렬하면서 합병해나가 최종적으로 정렬된 리스트를 얻는 방법입니다.

 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병하는 단계입니다. 이때, 새로운 리스트를 추가로 필요로 합니다. 합병 알고리즘은 2개의 리스트의 요소들을 처음부터 하나씩 비교하여 두 개의 리스트의 요소 중에서 더 작은 요소를 새로운 리스트로 옮깁니다. 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이하고 만약 둘 중에서 하나의 리스트 순회가 먼저 끝나게 되면 나머지 리스트의 요소들을 전부 새로운 리스트로 복사해 정렬된 합병 리스트를 얻습니다.

 합병 정렬은 분할 → 정렬 → 합병 의 과정을 반복하며 배열을 정렬해나가는 알고리즘입니다.

합병 정렬 예시

[ 5 3 8 4 1 6 2 7 ] 리스트를 합병 정렬을 통해 정렬해보겠습니다.

 먼저, 주어진 리스트를 크기를 동일하게 균등 분열하는 과정을 반복해 크기가 1인 부분 배열들을 얻어냅니다.

 그 후, 이 부분 배열들을 정렬하며 합병해 최종적으로 정렬된 배열을 얻습니다.

 (2) 배열 A와 배열 B를 정렬하며 합병하면 [ 3 5 ] 로 이루어진 배열 AB를 얻을 수 있고, 같은 방법으로 배열 CD, EF, GH 를 얻을 수 있습니다.

 (3) 배열 AB와 배열 CD를 정렬하며 합병하면 [ 3 4 5 8 ] 로 이루어진 배열 ABCD를 얻을 수 있고, 같은 방법으로 배열 EFGH를 얻을 수 있습니다.

 (4) 마지막으로 배열 ABCD와 배열 EFGH를 정렬하며 합병하면 정렬된 전체 배열을 얻을 수 있습니다.

 2개의 부분 배열이 어떻게 정렬되고 합병되는지 자세히 다뤄보도록 하겠습니다.

 배열 A [ 3 4 5 8 ] 과 배열 B [ 1 2 6 7 ] 을 합병 정렬 알고리즘을 이용해 합병해보겠습니다.

 합병 정렬은 새로운 리스트가 필요하므로 새로운 리스트를 배열 C라고 하겠습니다. 배열 A와 배열 B의 요소들을 순회하며 더 작은 값인 '1' 을 배열 C에 저장합니다.

  배열 A와 배열 B의 요소들을 순회하며 더 작은 값인 '2' 를 배열 C에 저장합니다.

 배열 A와 배열 B의 요소들을 순회하며 더 작은 값인 '3' 을 배열 C에 저장합니다.

 같은 과정을 반복하면 다음과 같이 정렬된 합병 배열 C를 얻을 수 있습니다.

합병 정렬 코드

int sorted[MAX_SIZE]; // 새로운 배열 C

void merge(int list[], int left, int mid, int right) {
	int i, j, k, l;
	i = left; j = mid + 1; k = left;

	while (i <= mid && j <= right) {
		if (list[i] <= list[j])
			sorted[k++] = list[i++];
		else
			sorted[k++] = list[j++];
	}
	if (i > mid)
		for (l = j; l <= right; l++)
			sorted[k++] = list[l];
	else
		for (l = i; l <= mid; l++)
			sorted[k++] = list[l];
	// 새로운 배열 C를 다시 원래 배열로 옮긴다.
	for (l = left; l <= right; l++)
		list[l] = sorted[l];
	return;
}

void merge_sort(int list[], int left, int right) {
	int mid = (left + right) / 2;
	if (left < right) {
		merge_sort(list, left, mid);
		merge_sort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
	return;
}

merge_sort로 배열을 계속 반으로 분할해주고 분할이 완료되면 merge 함수를 호출해 정렬과 합병을 진행합니다.

합병 정렬의 복잡도 분석

 합병 정렬은 퀵 정렬과 마찬가지로 레코드의 개수가 n 이라고 한다면 절반씩 나눠지며 분할하므로 log(n) 번의 분할 연산이 진행됩니다. 그 후 merge 함수에서 비교 연산과 이동 연산이 수행되는데 비교 연산은 최대 n 번 발생하고, 이동 연산은 2n번 발생하는 것을 알 수 있습니다. 즉, O( nlogn ) 시간 복잡도를 가지게 됩니다.

 단점으로는 임시 배열이 필요하므로 추가적인 메모리가 요구됩니다. 또,  이동 횟수가 많으므로 레코드들의 크기가 큰 경우에는 매우 큰 시간 장비를 초래하게 됩니다. 하지만 연결리스트를 활용해 구현한다면 레코드의 크기가 큰 경우도 문제가 되지 않는다. 퀵 정렬과 다르게 항상 균등하게 분할되므로 최악의 경우에 퀵 정렬보다 더 잘 작동합니다.

합병 정렬의 안정성

 합병 정렬은 같은 값이 있는 경우에도 같은 값들의 정렬 순서가 변하지 않는 안정 정렬에 해당합니다.

이상으로 합병 정렬 포스팅을 마치겠습니다.

안녕하세요, 여행벌입니다.

C언어로 쉽게 풀어쓴 자료구조 10장 - 그래프1 연습문제 풀이입니다.

4번과 15번은 문제에 오류가 있는 것 같고,

12번은 그래프와 무관하여 다루지 않았습니다.

틀린 부분이나 궁금하신 부분은 편하게 댓글에 남겨주세요!

[ 14번 ]

단절선을 찾는 문제로 따로 코드는 첨부하지 않았습니다.

아래 링크 포스팅을 참고하시면 될 것 같습니다.

https://jason9319.tistory.com/119

안녕하세요, 여행벌입니다.

오늘은 퀵정렬(Quick sort)에 대해서 포스팅해보겠습니다.

퀵 정렬의 원리

 퀵 정렬은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘입니다.

 퀵 정렬은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방식으로 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵 정렬하는 분할 정복 방법을 사용합니다.

 먼저 리스트 안에 있는 한 요소를 피벗(Pivot)으로 선택합니다. 우리는 리스트의 첫 번째 요소를 피벗으로 선택하고 퀵 정렬을 진행하겠습니다. 물론, 다른 요소를 피벗으로 선택해도 무관합니다. 그 후, 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮기고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮깁니다. 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 요소들로 구성된 부분 리스트, 오른쪽은 피벗보다 큰 요소들로 구성된 부분 리스트가 생깁니다. 그 후 각각 부분 리스트에 대해서 같은 과정을 반복합니다.

퀵 정렬 예시

( 5 3 8 4 9 1 6 2 7 ) 리스트를 퀵 정렬을 이용해 정렬해보겠습니다.

 처음에는 전체 리스트에 대해서 퀵 정렬을 진행합니다.

 첫 번째 요소를 피벗으로 선택하므로 피벗은 5가 되고 left 는 전체 리스트의 가장 왼쪽, right 는 전체 리스트의 가장 오른쪽을 지칭합니다.

 low 는 피벗을 제외한 리스트의 왼쪽부터 피벗보다 큰 값을 찾아나가고, high 는 리스트의 오른쪽부터 피벗보다 작은 값을 찾아나갑니다.

(2) low 는 피벗 5보다 큰 8에서 멈추고 high 는 피벗 5보다 작은 2에서 멈춥니다. 그 후 둘을 SWAP 합니다.

(3) low 는 피벗 5보다 큰 9에서 멈추고 high 는 피벗 5보다 작은 1에서 멈춥니다. 그 후 둘을 SWAP 합니다.

(4) low 는 피벗 5보다 큰 9에서 멈추고 high 는 피벗 5보다 작은 1에서 멈춥니다. 하지만, low 와 high 가 뒤바뀐 것을 확인할 수 있습니다. 따라서, 더 이상 퀵 정렬을 진행하지 않고 high 와 pivot 을 SWAP 합니다.

(5) 피벗을 기준으로 왼쪽 리스트에는 피벗보다 작은 값, 오른쪽 리스트에는 피벗보다 큰 값들이 모여있는 것을 확인할 수 있습니다.

이제 두 개의 부분 리스트 [ 1 3 2 4 ] 와 [ 9 6 8 7 ] 에 대해서 각각 퀵 정렬을 진행합니다.

왼쪽 리스트의 피벗은 1로 오른쪽 리스트의 피벗은 9로 지정합니다.

같은 작업을 진행해 최종적으로 [ 1 3 2 4 ] 리스트는 [ 1 ] / [ 3 2 4 ] 2개의 부분 리스트로 나눠지고,

[ 9 6 8 7 ] 리스트는 [ 7 6 8 ] / [ 9 ] 2개의 부분 리스트로 나눠집니다.

크기가 1인 리스트는 이미 정렬이 되어있으므로 [ 3 2 4 ] / [ 7 6 8 ] 리스트에 대해서 퀵 정렬을 진행합니다.

왼쪽 리스트의 피벗은 3으로 오른쪽 리스트의 피벗은 7로 지정합니다.

같은 작업을 진행해 최종적으로 [ 2 ] / [ 3 ] / [ 4 ] 와 [ 6 ] / [ 7 ] / [ 8 ]  6개의 부분 리스트로 나눠집니다.

모든 리스트의 크기가 1이므로 정렬이 완료됩니다.

퀵 정렬은 전형적인 분할 정복 기법을 활용한 정렬 방식입니다.

요약하면 퀵 정렬은 아래 그림과 같이 움직인다고 볼 수 있습니다.

퀵 정렬 코드

int partition(int list[], int left, int right) {
	int pivot, temp, low, high;
	low = left;
	high = right + 1;
	pivot = list[left];
	do {
		do {
			low++;
		} while (low <= right && list[low] < pivot);
		do {
			high--;
		} while (high >= left && list[high] > pivot);
		if (low < high) { //SWAP진행.
			temp = list[low];
			list[low] = list[high];
			list[high] = temp;
		}
	} while (low < high);

	temp = list[left];
	list[left] = list[high];
	list[high] = temp;
	return high;
}

void quick_sort(int list[], int left, int right) {
	if (left < right) {
		int q = partition(list, left, right);
		quick_sort(list, left, q - 1);
		quick_sort(list, q + 1, right);
	}
}

퀵 정렬 복잡도

퀵 정렬의 복잡도는 리스트 상태에 따라 크게 바뀝니다.

만약 퀵 정렬에서의 리스트 분할이 항상 그림과 같이 리스트의 가운데에서 이루어진다고 가정하면 n 개의 레코드를 가지는 리스트가 n / 2, n / 4 와 같이 반으로 계속 분할될 것이고, 따라서 log(n) 번 분할이 발생합니다. 또 각 분할마다 평균 n번 정도의 비교가 이루어지므로 퀵 정렬의 복잡도는 nlog(n) 이 됩니다.

 하지만 리스트가 계속 불균형하게 나누어지는 경우에는 최대 n 번의 분할이 발생하고, 각 분할마다 평균 n번 정도의 비교가 이루어지므로 퀵 정렬의 복잡도는 n^2 가 됩니다.

 그럼에도 불구하고 퀵 정렬은 평균적인 경우의 시간 복잡도가 O( nlogn ) 으로 나타나고 같은 O( nlogn ) 복잡도를 가지는 정렬 중에서도 가장 빠릅니다.

퀵 정렬 안정성

퀵 정렬은 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있는 불안정 정렬에 속합니다.

 [ 5-1 5-2 3 2 1 ] 를 퀵 정렬로 정렬해보겠습니다.

[ 5-1 5-2 3 2 1] → [ 1 2 3 5-2 5-1 ]

 위와 같이 퀵 정렬은 같은 값이 있는 경우에 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있습니다.

이상으로 퀵 정렬 포스팅을 마치겠습니다.