백준 11728 : 배열 합치기 (분할정복 알고리즘)

https://www.acmicpc.net/problem/11728

1. 접근

• 처음에는 단순하게 벡터를 하나만 정의해서 저장한 후 정렬을 해주었다. 이 경우에는 1차원 배열이기 때문에 가능했지만, 2차원 배열이 되거나, 배열의 크기가 기하급수적으로 커진다면 효율성이 굉장히 낮아진다.
• 두 정렬되어있는 배열을 정렬해서 합치는 경우, 결국에는 각 배열의 값을 비교하여 작은 값을 먼저 빈 배열에 넣으면 된다. 이 과정을 반복하게 된다 => 분할 정복 !
  cf. 분할 정복 : 큰 문제를 작게 나누어서 푸는 방식 / DP : 작은 문제들을 통해 큰 문제를 해결하는 방식. 큰 문제에서는 무조건 작은 문제들의 결과를 사용한다.

2. 나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	int* n_arr;
	int* m_arr;
	int* answer;

	cin >> n >> m;
	n_arr = new int[n];
	m_arr = new int[m];
	answer = new int[n + m];

	for (int i = 0; i < n; i++) {
		cin >> n_arr[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> m_arr[i];
	}

	int n_index=0, m_index=0;
	int index=0;
	while (n_index < n && m_index < m) {
		if (n_arr[n_index] < m_arr[m_index]) {
			answer[index++] = n_arr[n_index++];
		}
		else answer[index++] = m_arr[m_index++];
	}

	while(n_index<n) answer[index++] = n_arr[n_index++];
	while(m_index<m) answer[index++] = m_arr[m_index++];

	for (int i = 0; i < n + m; i++) cout << answer[i] << " ";
	cout << "\n";

	return 0;
}

3. 참고

https://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Dynamic-Programming-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95?category=646973

분할정복 외의 다른 알고리즘도 설명되어 있는 블로그