[중급 알고리즘] 분할 정복(연습)
2022. 5. 18. 18:20ㆍTIL💡/Algorithms
💚 1780 종이의 개수
solve(x, y, n)
(x, y)부터 가로로 n개, 세로로 n개의 종이 개수를 확인하는 함수
m = n / 3이라고 했을 때 부분 문제로 나눠보면
0: solve(x, y, m)
1: solve(x, y + m, m)
2: solve(x, y + 2 * m, m)
3: sovle(x + m, y, m)
...
cnt[x] = x - 1의 개수
x는 -1, 0, 1이 가능하기 때문
#include <iostream>
using namespace std;
int a[3000][3000];
int cnt[3] = {0, };
// n * n 종이 내의 색이 모두 동일한지 확인
bool same(int x, int y, int n) {
for(int i = x;i < x + n;i++) {
for(int j = y;j < y + n;j++) {
if(a[x][y] != a[i][j]) {
return false;
}
}
}
return true;
}
// (x, y)부터 가로로 n개, 세로로 n개의 종이 개수를 확인하는 함수
void solve(int x,int y, int n) {
if(same(x, y, n)) {
cnt[a[x][y] + 1] += 1;
return;
}
int m = n / 3;
for(int i = 0;i < 3;i++) {
for(int j = 0;j < 3;j++) {
solve(x + i * m, y + j * m, m);
}
}
}
int main() {
int n;
cin >> n;
for(int i = 0;i < n;i++) {
for(int j = 0;j < n;j++) {
cin >> a[i][j];
}
}
solve(0, 0, n);
for(int i = 0;i < 3;i++) {
cout << cnt[i] << '\n';
}
return 0;
}
💚 2263 트리의 순회
- N개의 정점을 갖는 이진 트리의 정점에 1부터 N까지 번호가 중복없이 매겨져 있다.
- 이 이진 트리의 인오더와 포스트 오더가 주어졌을 때 프리오더를 구하는 문제
포스트 오더의 마지막 수를 통해 루트를 알 수 있다.
인오더 정보를 통해 가장 왼쪽 수를 알 수 있다.
#include <iostream>
using namespace std;
int inorder[100000];
int postorder[100000];
// position[i]: i번 정점이 인오더에서 몇 번째에 있는지 저장, 이건 정점의 숫자로 인덱싱하기 때문에 100001의 크기가 필요
int position[100001];
void solve(int in_start, int in_end, int post_start, int post_end) {
if(in_start > in_end || post_start > post_end) return;
int root = postorder[post_end];
cout << root << ' ';
// p = 루트의 인오더 배열에서의 위치
int p = position[root];
// inorder: in_start p in_end
// postorder: post_start post_end
// left: p - in_start = 왼쪽 자식의 수
// right: in_end - p = 오른쪽 자식의 수
int left = p - in_start;
solve(in_start, p - 1, post_start, post_start + left - 1);
solve(p + 1, in_end, post_start + left, post_end - 1);
}
int main() {
int n;
cin >> n;
for(int i = 0;i < n;i++) {
cin >> inorder[i];
}
for(int i = 0;i < n;i++) {
cin >> postorder[i];
}
for(int i = 0;i < n;i++) {
position[inorder[i]] = i;
}
solve(0, n - 1, 0, n -1);
return 0;
}
💚 1571 버블 소트
N개로 이루어진 수열 A가 있을 때
Swap이 총 몇 번 발생하는지
실제로 Swap을 하지 않아도 카운트 가능하다. 머지 소트를 이용한다.
왼쪽에 있으면서(i < j) 더 큰 값(A[i] > A[j]) 찾기
오른쪽 절반이 이동할 때 왼쪽 절반에서 아직 이동하지 않은 것의 개수가 inversion의 개수다.
#include <iostream>
using namespace std;
int a[500000];
int b[500000];
long long solve(int start, int end) {
if(start == end) {
return 0;
}
int mid = (start + end) / 2;
// 재귀 호출
long long ans = solve(start, mid) + solve(mid + 1, end);
int i = start;
int j = mid + 1;
int k = 0;
// 왼쪽, 오른쪽 모두 탐색 끝나야 while문 종료
while(i <= mid || j <= end) {
if(i <= mid && (j > end || a[i] <= a[j])) {
b[k++] = a[i++];
}
else {
ans += (long long)(mid - i + 1);
b[k++] = a[j++];
}
}
for(int i = start;i <= end;i++) {
a[i] = b[i - start];
}
return ans;
}
int main() {
int n;
cin >> n;
for(int i = 0; i < n;i++) {
cin >> a[i];
}
long long ans = solve(0, n - 1);
cout << ans << '\n';
return 0;
}
'TIL💡 > Algorithms' 카테고리의 다른 글
[중급 알고리즘] 이분 탐색 (0) | 2022.05.23 |
---|---|
[중급 알고리즘] 분할 정복(도전) (0) | 2022.05.23 |
[중급 알고리즘] 그리디(도전) (0) | 2022.05.17 |
[중급 알고리즘] 그리디 (연습) (0) | 2022.05.16 |
[프로그래머스] 섬 연결하기 (0) | 2022.05.14 |