딩코딩 : Computer Science 블로그

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

1. 문제설명

모눈 종이에 직사각형이 그려져 있을 때

직사각형이 색칠되어 있지 않은 남은 부분들의 갯수와 부분들의 넓이를 구해서

오름차순으로 정렬해 출력하면 된다.

사각형의 갯수가 곧 넓이가 된다.

2. 접근방법[알고리즘]

색칠된 부분을 저장하기 위해 M*N 배열을 만들어야한다.

좌표를 설정하는 걸 조심해야한다.

N, M은 7,5지만 이건 꼭짓점이고 실제로

해당 칸 마다 좌표를 부여하면 (0,0) ~ (6,4)까지만 사용 한다.

입력

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

arr[i][j]의 값에 색칠되었다면 -1을 저장하고 색칠되지 않았다면 0을 저장해준다.

색칠해줄 때도 (0,2)에서 (4,4)까지 칠해주는게 아니라 (0,2)에서 (3,3)까지 칠해주어야한다.

이유는 위와 동일하게 (4,4)는 사각형의 해당 좌표가아니라 꼭짓점이기 때문이다.

	//직사각형 -1로 칠하기
	for (int i = 0; i < k; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int j = y1; j < y2; j++) { // y1 ~ <y2 까지 돌아야 한다
			for (int k = x1; k < x2; k++) { // x1 ~ <x2 까지 돌아야 한다
				arr[j][k] = -1;
			}
		}
	}

그리고 arr배열 값이 -1인 좌표는 BFS를 돌지 않고

arr배열이 0인 값만 탐색한다.

이제 arr배열을 돌면서 값이 0인 좌표를 발견하면

BFS를 실행하면서 arr 값에 사각형의 개수를 저장해준다.

BFS 실행 코드

arr값이 0인 좌표를 발견할 때 arr 값을 1로 저장해준다. 

cnt 변수는 arr값이 0인 좌표를 발견했을 때 +1 해주어 전체 하얀 부분의 개수를 구할 수 있다.

this_area 변수는 BFS를 돌면서 0인좌표를 발견할 때마다 +1 해주어 해당 부분의 넓이를 저장해준다

그리고 Q가 empty가 되어 BFS가 끝나면 해당 하얀 부분을 다 탐색했다는 뜻이므로

this_area 변수의 값을 ans에 저장해준다.

이렇게 모든 좌표에대해 탐색하면 하얀 부분의 넓이를 모두 구할 수 있다.

	queue<pair<int, int> > Q;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 0) {
				cnt++;
				arr[i][j] = 1;
				int this_area = 1;
				Q.push(make_pair(i, j));

				while (!Q.empty()) {
					int cur_x = Q.front().first;
					int cur_y = Q.front().second;
					Q.pop();

					for (int k = 0; k < 4; k++) {
						int nx = cur_x + dx[k];
						int ny = cur_y + dy[k];
						if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
						if (arr[nx][ny] == 0) {
							arr[nx][ny] = ++this_area;
							Q.push({ nx,ny });
						}
					}
				}
				ans.push_back(this_area);
			}
		}
	}

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int n,m,k, cnt, arr[101][101];
vector<int> ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	//색칠영역 -1로 두고
	//-1이 아닌 곳 BFS 돌면서 넓이 구해주면 된다
	cin >> m >> n >> k;

	//직사각형 -1로 칠하기
	for (int i = 0; i < k; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int j = y1; j < y2; j++) {
			for (int k = x1; k < x2; k++) {
				arr[j][k] = -1;
			}
		}
	}

	//직사각형 확인
	//cout << "------------------------\n";
	//for (int i = 0; i < m; i++) {
	//	for (int j = 0; j < n; j++) {
	//		cout << arr[i][j] << ' ';
	//	}
	//	cout << '\n';
	//}
	//cout << "-------------------\n";

	queue<pair<int, int> > Q;

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (arr[i][j] == 0) {
				cnt++;
				arr[i][j] = 1;
				int this_area = 1;
				Q.push(make_pair(i, j));

				while (!Q.empty()) {
					int cur_x = Q.front().first;
					int cur_y = Q.front().second;
					Q.pop();

					for (int k = 0; k < 4; k++) {
						int nx = cur_x + dx[k];
						int ny = cur_y + dy[k];
						if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
						if (arr[nx][ny] == 0) {
							arr[nx][ny] = ++this_area;
							Q.push({ nx,ny });
						}
					}
				}
				ans.push_back(this_area);
			}
		}
	}


	//결과 확인
	//for (int i = 0; i < m; i++) {
	//	for (int j = 0; j < n; j++) {
	//		cout << arr[i][j] << ' ';
	//	}
	//	cout << '\n';
	//}
	//cout << "-------------------\n";


	//정답 출력
	cout << cnt << '\n';
	sort(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << ' ';
	}

}

일반적인 BFS탐색 문제와 비슷하다.

다만 좌표설정하는 부분을 잘 유의해야할 필요가 있다.

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

1. 문제설명

입력으로 N개의 노드가 주어지고 노드간의 연결관계가 주어진다.

그리고 마지막 입력으로 DFS 방문 순서가 주어진다.

노드간의 연결관계를 바탕으로 깊이우선탐색을 할 때

주어진 방문 순서처럼 방문할 수 있는지 여부를 묻는 문제이다.

2.접근방법[알고리즘]

접근 방법은 문제 이름부터 DFS이기 때문에 쉽게 알 수 있다.

하지만 이 문제를 푸는 게 생각보다 많이 어려웠다.

그동안 DFS를 이용해 최단 거리나 백트래킹 위주 문제를 많이 풀다보니

처음 이 문제를 봤을 때

"주어진 정점과 간선을 통해 DFS로 탐색할 수 있는 모든 방문순서를 구해야하나?" 생각했다

그렇게 할 수도 있겠지만 그러면 시간초과할 것 같았다.

이 문제는 DFS의 방문 순서에대해 생각해보아야 해결 할 수 있다.

예제 입력을 갖고 생각해보자.

4
1 2
1 3
2 4
1 2 3 4

이렇게 주어졌을 때 그래프는 다음과 같다

DFS로 탐색 할 때 1번 노드에서 출발하면

2번, 3번 중 방문 순서를 택해야 한다.

2번을 먼저 방문하기로 택하면 

1 2 4 3 이렇게 탐색 하고

3번을 먼저 택하면 1 3 2 4 순서로 탐색하게 된다.

2번 노드와 3번 노드중 어떤 걸 먼저 탐색하게 해야 할까?

보통 일반적인 DFS나 BFS 문제에서는 어떤 노드를 먼저 탐색하게끔 문제를 만들지 않는다.

결과적으로 다 탐색한 뒤 어떤 결괏값을 갖는지를 많이 물어본다.

하지만 이 문제에서는 어떤 노드를 먼저 탐색할지 정해주는 과정이 필수적이다.

문제 입력 마지막 줄에 예상 DFS 탐색 순서를 준다.

만약 위처럼 1 2 3 4 이렇게 주어졌다면

우리는 깊이 우선 탐색을 할 때 2번 노드를 3번노드 보다 먼저 택해야한다.

만약 주어진 예상 DFS 탐색 순서가 1 3 2 4 라면

우리는 깊이 우선 탐색을 할 때 3번 노드를 2번노드 보다 먼저 택해야한다.

즉 마지막 예상 DFS 탐색 순서를 바탕으로해서

어떤 노드를 먼저 탐색해야할지 정해주고,

정해진 노드 탐색 순서를 바탕으로 DFS를 수행했을 때

예상 DFS 탐색 순서와 일치하는지 확인하는 문제이다.

노드간의 연결 관계를 인접리스트로 만들고,

인접리스트의 노드 순서를 정해진 노드 탐색 순서로 정렬한 뒤

깊이우선탐색을 실행해야 한다.

이해를 돕기 위해 다른 입력으로 생각해보자

(마지막 줄, DFS예상 탐색 순서만 다르다)

4
1 2
1 3
2 4
1 3 2 4

order

1,2,3,4 노드가 있을 때

항상 탐색 순서는

1번 노드가 첫번째

3번 노드가 두번째

2번 노드가 세번째

4번 노드가 네번째로 돌아야한다.

이를 위해 order 배열에 순서에 해당하는 노드를 저장해준다

order[2] = 3이면 우선 순위 두번째 노드가 3이라는 뜻이다.

그리고 이런 우선순위를 바탕으로 인접리스트의 노드들을 정렬해준다.

각 노드의 탐색 우선순위를 지정해주기 위한 코드다.

bool comp(int a, int b){
	return order[a] < order[b];
}
    
for(int i=1; i<=n; i++){
	int node;
	cin >> node; 
	given_path[i] = node;
	order[node] = i;
}
	
for(int i=1; i<=n; i++){
	sort(ad[i].begin(), ad[i].end(), comp);
}

sort를 시행하기 전

1번 노드는 2번 노드를 먼저 탐색한다.

sort 한 후 3번이 2번보다 우선순위가 높기 때문에 2 앞으로 온다.

이제 DFS를 돌면 2보다 먼저 탐색된다.

다시 설명하자면,

이렇게 해주는 이유는

문제 입력에서 1,3,2,4 순으로 탐색을 할 수 있는지 물어보았기 때문에 3은 무조건 2보다 먼저 탐색되야한다.

문제입력에 주어진 조건을 바탕으로 

각 노드마다 우선순위를 적용해준 뒤 탐색한 후 1,3,2,4 순으로 탐색이 되는지 확인하기 위함이다.

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

vector<int> ad[100001]; 
int order[100001], given_path[100001], DFS_path[100001], L=1;
bool ch[100001];

bool comp(int a, int b){
	return order[a] < order[b];
}

void DFS(int x){
	ch[x] = 1;
	DFS_path[L++] = x;
	
	for(int i=0; i<ad[x].size();i++){
		int nx = ad[x][i];
		if(ch[nx]==0) DFS(nx);
	}
}


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	
	for(int i=1; i<n; i++){
		int node1, node2;
		cin >> node1 >> node2;
		ad[node1].push_back(node2);
		ad[node2].push_back(node1);
	}
	
	// 각 노드마다 순서를 정해준다  
	for(int i=1; i<=n; i++){
		int node;
		cin >> node; 
		given_path[i] = node;
		order[node] = i;
	}
	
	for(int i=1; i<=n; i++){
		sort(ad[i].begin(), ad[i].end(), comp);
	}
	
	//1번부터 돌기 떄문  
	DFS(1);
	for(int i=1; i<=n; i++){
		if(given_path[i]!=DFS_path[i]){
			cout << 0;
			return 0;
		}
	}
	cout << 1;
	
	
}

배열 대신 벡터로 동적으로 배열을 이용하면

메모리를 절약할 수 있겠지만 귀찮은 관계로 대부분 배열을 이용했다.

아마 인접리스트를 이용하지 않고 인접행렬[nxn]그래프를 이용하면 메모리 초과가 될 것이다.

인접리스트 알아보기

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

1. 문제설명

첫째 줄에는 이번 시험의 단원 개수 N(1 ≤ N ≤ 100)과

시험까지 공부 할 수 있는 총 시간 T(1 ≤ T ≤ 10000)가 공백을 사이에 두고 주어진다.

둘째 줄부터 N 줄에 걸쳐서 각 단원 별 예상 공부 시간 K(1 ≤ K ≤ 1000)와

그 단원 문제의 배점 S(1 ≤ S ≤ 1000)가 공백을 사이에 두고 주어진다.

각 문제는 한번 씩만 풀 수 있고 최대 점수를 구해야 한다.

2. 접근 방법[알고리즘]

각 문제는 한 번만 풀 수 있으므로

다이나믹 테이블 dy에 for문을 뒤부터 돌면서

최댓값을 누적해주면 된다.

for문을 뒤부터 도는 이유는

이 문제는 각 단원 문제를 단 한 번씩 풀 수 있는데

앞에서부터 돌면 계속해서 중복된 값을 더해서 누적하기 때문이다.

중복된 값을 누적하는 걸 피하기 위해 뒤부터 돈다.

만약 각 단원 문제를 여러번 풀 수 있다면

for문을 앞에서 부터 돌아 계속 중복해서 누적해주면 된다.

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, t, dy[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> t;
	for (int i = 0; i < n; i++) {
		int k, s;
		cin >> k >> s;
		for (int j = t; j >= k; j--) {
			dy[j] = max(dy[j], dy[j - k] + s);
		}
	}
	cout << dy[t];

}

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

1.문제설명

투자금액 N과 기업의 개수 M이 주어진다.

M개의 기업에 주어진 투자액수를 활용해 최대 이익을 얻어야 한다.

각각 기업은 최대 한번 투자할 수 있고, 투자하지 않아도 된다.

A에 4를 투자하고 B에 0을 투자하는 건 가능 하지만

A에 1을 투자하고 또 3을 투자하는 건 불가능 하다.

답으로 각 기업에 투자한 금액과, 얻을 수 있는 이익의 최댓값을 산출해야한다.

2. 접근방법[알고리즘]

다이나믹 프로그래밍이자 냅색 문제이다.

표를 만들어 각 투자액수에 대하여 얻을 수 있는 최대 이익을 갱신하면 된다.

단 이 문제가 까다로운 건 단순히 최대 이익을 구하는 게 아니라

각 기업에 투자한 금액을 저장해야 한다.

이를 위해 dy테이블을 2차원 배열로 만들어 최대 이익을 갱신할 때마다

각 기업에 투자한 금액 또한 누적했다.

[ 최대 이익, A에 투자한 금액, B에 투자한 금액]

점화식

dy 테이블에서 index가 0인 column에 이익 최댓값을 저장하고,

index 1 ~ m 까지 1부터 m번 기업까지에 투자한 액수를 저장한다.

최댓값은 다른 냅색, 배낭 문제처럼

단순히 dy[j][0] = dy[j-k][0] + arr[k][i]; 구할 수 있다.

if (dy[j][0] < dy[j - k][0] + arr[k][i]) {
    dy[j][0] = dy[j - k][0] + arr[k][i];

    for (int t = 1; t <= m; t++) {
        if (t == i) dy[j][i] = k;
        else dy[j][t] = dy[j - k][t];
    }
}

3. 문제풀이 코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[301][21], dy[301][21];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		int tmp;
		cin >> tmp;
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}

	for (int i = 1; i <= m; i++) {
		for (int j = n; j >= 0; j--) {
			for (int k = 0; k <= j; k++) {
				//k는 가격
				if (dy[j][0] < dy[j - k][0] + arr[k][i]) {
					dy[j][0] = dy[j - k][0] + arr[k][i];

					for (int t = 1; t <= m; t++) {
						if (t == i) dy[j][i] = k;
						else dy[j][t] = dy[j - k][t];
					}
				}

			}
		}
	}
	cout << dy[n][0] << '\n';

	for (int i = 1; i <= m; i++) {
		cout << dy[n][i] << ' ';
	}

}

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

1.문제 설명, 접근 방법[알고리즘]

다이나믹프로그래밍 문제이자 배낭 문제이다.

"현재 활성화 되어 있는 앱 A1, ..., AN 중에서 몇 개를 비활성화 하여

M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다."

M바이트의 메모리를 확보하는 게 아니라

M바이트 이상의 메모리를 추가로 확보해야 한다.

나는 처음에 이전에 배낭문제를 풀었던 걸 기억해서

무지성으로 메모리를 기준점을 잡고 비용의 최솟값을 갱신해나가려 했는데

그러면 메모리의 범위가 1 ≤ M ≤ 10,000,000 이어서 배열의 최대 사이즈를 넘어 사용할 수가 없다.

그런데 알고보니 메모리를 기준점으로 하는 게 아니라

비용을 기준점으로 하면 비용의 최댓값이 100이고 n의 최댓값이 100이어서

배열을 dy[10001]로 잡아주면 충분하다.

dy[i] 는 cost가 i 일 때 최대 확보한 메모리이다.

점화식

dy[j] = max(dy[j], dy[j - cost[i]] + mem[i]);

문제처럼 입력이 다음과 같을 때

5 60
30 10 20 35 40
3 0 3 5 4

dy 테이블은

각 문제를 적용했을 때 확보된 메모리가 60이상인 최소의 비용은

6이다.

문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, mem[101], cost[101], dy[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> mem[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> cost[i];
	}


	for (int i = 0; i < n; i++) {
		for (int j = 10000; j >= cost[i]; j--) {
			dy[j] = max(dy[j], dy[j - cost[i]] + mem[i]);
		}
	}

	for (int i = 0; i <= 10000; i++) {
		if (dy[i] >= m) {
			cout << i;
			break;
		}
	}


}