분할 정복

🙇‍♀️분할 정복

분할 정복은 후위 순회를 이용한 방식이다.

왼쪽 서브트리, 오른쪽 서브트리를 다 지나고 자신의 동작을 수행한다.

void divide(int lt, int rt)
{
	int mid;
	int p1, p2, p3;
	if (lt < rt)
	{
		mid = (lt + rt) / 2;
		divide(lt, mid);
		divide(mid + 1, rt);

		p1 = lt;
		p2 = mid + 1;
		p3 = lt;
		while (p1 <= mid && p2 <= rt)
		{
			if (arr[p1] < arr[p2]) 
				temp[p3++] = arr[p1++];
			else 
				temp[p3++] = arr[p2++];
		}
		while (p1 <= mid)
		{
			temp[p3++] = arr[p1++];
		}
		while (p2 <= rt)
		{
			temp[p3++] = arr[p2++];
		}

		for (int i = lt; i <= rt; ++i)
		{
			arr[i] = temp[i];
		}

	}
}

이전의 39번 두 배열합치기 문제와 비슷하다.

시간 복잡도는 O(nlogn)이라고 한다.

분할 정복 생각안날 때 마다 와야겠다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
int arr[100], temp[100];

void divide(int lt, int rt)
{
	int mid;
	int p1, p2, p3;
	if (lt < rt)
	{
		mid = (lt + rt) / 2;
		divide(lt, mid);
		divide(mid + 1, rt);

		p1 = lt;
		p2 = mid + 1;
		p3 = lt;
		while (p1 <= mid && p2 <= rt)
		{
			if (arr[p1] < arr[p2]) 
				temp[p3++] = arr[p1++];
			else 
				temp[p3++] = arr[p2++];
		}
		while (p1 <= mid)
		{
			temp[p3++] = arr[p1++];
		}
		while (p2 <= rt)
		{
			temp[p3++] = arr[p2++];
		}

		for (int i = lt; i <= rt; ++i)
		{
			arr[i] = temp[i];
		}

	}
}

void solve()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> arr[i];

	divide(1, n);

	for (int i = 1; i <= n; ++i)
		cout << arr[i] << " ";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}