[Algorithm] divide and conquer, quick sort - 분할정복, 퀵정렬

오늘은 분할정복과 퀵정렬에 대해 이야기를 해볼까 한다. 지난번 알고리즘에서 재귀함수를 설명했는데, 재귀함수야 말로 분할정복의 가장 대표적인 예이다. 문제를 base case와 recursive case로 나누어서 생각하고, 가장 최소 단위가 해결이 될 때 전체가 해결되도록 하기 때문이다. [ Hello Coding, 그림으로 개념을 이해하는 알고리즘 ]의 챕터 4에 나오는 내용으로 설명을 시작해본다

 

Divide and conquer ( 분할 정복 )

한자로 번역이 되니까 어려워보인다. 조금 말을 쉽게하자면, "쪼개고 쪼개서 하나씩 해결하자" 이다.

 

아래의 그림은 책의 예제이다.

여러분이 농부이고, 위의 그림과 같은 농장을 가지고 있다고 가정한다. 이 농장을 똑같이 생긴 정사각형 토지로 나누고 싶습니다. 정사각형 토지의 크기는 최대한 컸으면 좋겠어요. 그러니까 아래 중 마지막처럼 전부 정사각형이 되도록 나누어야 해요. 물론 정사각형이 충분히 크다면요!

직사각형의 가로가 1680m 이고, 세로가 640m 이므로, 이 직사각형을 가득메우는 한 변의 길이를 최대로 한 정사각형은 한 변의 길이가 몇일까. 이 문제를 해결하기 위해서는 두가지 단계를 거친다.

1. 기본 단계를 해결한다. 가능한 가장 간단한 문제를 해결해야 한다.
2. 문제가 기본단계가 될 때까지 나누거나 작게 쪼갭니다.

만약 직사각형의 한 변의 길이가 50m 이고, 다른 변이 25m 라면, 우리는 두 개의 정 사각형을 찾을 수 있다.

마찬가지로 긴 변의 길이가 짧은 변의 2배 이상이라면, 우리는 2개의 큰 정사각형과 나머지를 구할 수 있다.

 

이 나머지 공간을 위와 같은 방식 ( 긴 변의 길이가 짧은 변의 2배 이상이라면, 2개의 큰 정사각형과 나머지를 구하는 방식 ) 에 적용하여 결과적으로 긴 변이 짧은 변의 2배가 될때의 짧은 변의 길이를 확인하면 된다.

 

아래의 코드를 실행하면,

const x = 1680,
	y = 640;

const maxSquare = function (x, y) {
	let short, long;
	if (x > y) {
		long = x;
		short = y;
	} else {
		short = x;
		long = y;
	}
	console.log(`x: ${x}, y: ${y}, long: ${long}, short: ${short}`);
	if (short * 2 === long) {
		console.log(`The answer is ${short}m`);
		return short;
	}
	return maxSquare(long - short, short);
};

let a = maxSquare(x, y);
console.log(a);

아래와 같은 결과가 나온다.

 

이처럼 분할정복은 큰 문제를 해결가능한 가장 작은 문제로 쪼개는 것이 포인트이며, 이것은 앞서 소개한 recursion의 base case에 해당한다.

 

그럼 바로 활용해보자.

 

Quick Sort ( 퀵 정렬 )

퀵소트는 정렬시리즈 중에서 가장 무난하고 빠른 정렬 중 하나이다. bubble sort, insertion sort, selection sort, merge sort 등이 있지만, 다른 친구들이 O(N^2)의 시간복잡도를 가지는 데 비해, 퀵소트는 평균적으로 O(NlogN)의 시간복잡도를 가진다. ( 단, 퀵소트에서 worst case는 O(N^2)의 시간복잡도를 가진다. )

 

빠른 속도를 자랑하는 퀵소트는 d&c 의 대표적인 예 중 하나이다.

먼저, 정렬하고싶은 배열이 있다고 가정하자.

const arr = [2, 1, 4, 3, 6, 5, 0];

이 배열을 정렬하기 위해 가장 작은 단위는 뭘까?

배열의 요소가 하나만 남는 게 가장 이상적인 단위일 것이다.

 

하나의 요소와 그 외의 나머지 하나를 비교해서 앞 뒤를 정렬하면 되는 게 퀵소트의 base case 이다.

• base case: 배열의 길이가 2보다 작아 하나의 요소만 남으면 배열을 리턴한다
• recursive case: 1. 피봇 ( pivot, 배열의 요소 중 임의의 값 ( 원하는 걸 고르면 됨 / 여기서는 0번째 요소 ) ) 을 정한다
• recursive case: 2. 피봇보다 작으면 왼쪽 배열에, 크면 오른쪽 배열에 담은 뒤 quickSort를 다시 호출한다.
• recursive case: 3. 모든 결과를 합친다.

const quickSort = function (...arr) {
	if (arr.length < 2) {
		return arr;
	}
	let pivot = arr[0];
	let previousArr = [],
		afterArr = [];
	for (let i = 1; i < arr.length; i++) {
		if (arr[i] <= pivot) {
			previousArr.push(arr[i]);
		} else {
			afterArr.push(arr[i]);
		}
	}
	return quickSort(...previousArr)
		.concat(pivot)
		.concat(quickSort(...afterArr));
};

 

아주 간단하고 명료하게 퀵정렬을 마무리할 수 있다.

 

앞으로의 알고리즘은 점점 어려워지고 따라가기 벅찰 수 있다. 그러므로 문제를 잘게 쪼개서 부분적으로 이해하는 연습을 하자.