백준 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. 참고
분할정복 외의 다른 알고리즘도 설명되어 있는 블로그
Author And Source
이 문제에 관하여(백준 11728 : 배열 합치기 (분할정복 알고리즘)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jeongopo/백준-11728-배열-합치기-분할정복-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)