신장트리(Spanning tree)?

신장트리는 그래프에서 모든 정점이 연결되어있고, 그래프에 싸이클이 존재하지 않는(tree의 조건) 그래프를 말합니다.

 - 싸이클 : 그래프의 특정 정점에서 출발하여 다시 처음 출발했던 곳으로 되돌아 갈 수 있으면 사이클이 있다고 합니다.

위와같은 그래프에서 싸이클이 존재하지 않고 모든 정점을 연결하는 경우는 아래와 같을 수 있습니다.

최소신장트리?

위와같은 신장트리에서 간선의 가중치의 합이 최소가되는 신장트리를 최소신장트리(Minimum Spanning Tree)라고 합니다

크루스칼 알고리즘?

크루스칼 알고리즘은 위의 최소신장트리를 구하는 알고리즘입니다.

먼저 최소 비용으로 모두 연결만 시키면 되기 때문에 가중치의 값을 기준으로 오름차순 정렬합니다.

과정은 이렇습니다

1.정렬된 가중치 순서에 맞게 간선을 그래프에 포함시킵니다.

2.포함시키기 전에 싸이클이 형성되는지 확인합니다.

3.싸이클이 형성되는 경우 간선을 포함시키지 않습니다.

그럼 세부 과정을 그림으로 확인해 보겠습니다.

1) A - D 의 간선을 추가할 경우 싸이클이 존재하지 않으니 그래프에 포함시킵니다. 

2) C - E 의 간선을 추가할 경우 싸이클이 존재하지 않으니 그래프에 포함시킵니다. 

3) D - F 의 간선을 추가할 경우 싸이클이 존재하지 않으니 그래프에 포함시킵니다. 

4) A - B 의 간선을 추가할 경우 싸이클이 존재하지 않으니 그래프에 포함시킵니다.

5) D - E 의 간선을 추가할 경우 싸이클이 존재하지 않으니 그래프에 포함시킵니다.

6) B - G 의 간선을 추가할 경우 싸이클이 존재하지 않으니 그래프에 포함시킵니다.

7) B - C의 간선을 추가할 경우 싸이클이 존재하게되니 그래프에 포함시키지 않습니다.

8) D - B의 간선을 추가할 경우 싸이클이 존재하게되니 그래프에 포함시키지 않습니다.

9) E - G의 간선을 추가할 경우 싸이클이 존재하게되니 그래프에 포함시키지 않습니다.

10) F - G의 간선을 추가할 경우 싸이클이 존재하게되니 그래프에 포함시키지 않습니다.

그림으로 확인해보니 더 간단하게 느껴지네요!

하지만 이 알고리즘을 코드로 구현하는 경우는 조금 까다로울 수 있습니다.

구현 과정에서 서로소 집합(Disjoint Set), Union-Find라는 개념이 쓰이는데요 이부분은 다음 포스팅에서 알아보도록 하겠습니다.

감사합니다.

스티커 성공

한국어   

시간 제한메모리 제한제출정답맞은 사람정답 비율

문제

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 

출력

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

간단한 DP 문제 입니다.

알고리즘은 다음과 같습니다.

 - 자신의 전 대각선, 전전 대각선 중 큰 값을 자기 자신과 더해 자신의 위치에 더해갑니다.

 - 즉 , 윗 칸의 경우는 max(ary[1][i-1],ary[1][i-2]) 아랫 칸의 경우는 max(ary[0][i-1],ary[0][i-2]) 이렇게 됩니다.

실행 코드

#include<iostream>
#include<algorithm>
using namespace std;
int T;
int ary[2][100001];
int main() {
	cin >> T;
	int n;
	for (int tc = 0; tc < T; tc++) {
		cin >> n;
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < n; j++) {
				cin >> ary[i][j];
			}
		}
		ary[0][1] += ary[1][0];
		ary[1][1] += ary[0][0];
		for (int i = 2; i < n; i++) {
			ary[0][i] += max(ary[1][i - 2], ary[1][i - 1]);
			ary[1][i] += max(ary[0][i - 2], ary[0][i - 1]);
		}
		cout << max(ary[0][n - 1], ary[1][n - 1]) << endl;
	}
}

문제

항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.

파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.

항승이는 길이가 L인 테이프를 무한개 가지고 있다.

항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.

물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.

입력

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.

<출처> https://www.acmicpc.net/

상당히 쉬운 문제라고 생각이 든다.

알고리즘의 순서입니다.

1. 물이 새는 파이프를 입력 받으면서 bool 배열[파이프 번호]의 값을 true로 설정.
   1. 입력받은 파이프 번호 중 가장 큰 값을 변수에 저장해 놓는다.
2.  1부터 저장해 놓은 가장 큰 파이프 번호까지 for 문을 돌린다.
   1. bool 배열의 값이 true 이면 문제가 있는 파이프 이므로 int 변수에 테이프의 길이(L) -1 을 저장해 놓는다.
   2. 이후 테이프의 길이를 감소 시키면서 for 문을 진행한다
   3. 테이프의 길이가 1보다 작으면 테이프를 한번 붙인 것이므로, 다시 문제 있는 파이프를 찾는다.

<실행 코드>

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

int N, L, res;
bool ary[1001];
int main() {
	cin >> N >> L;
	int maxidx = 0;
	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		ary[a] = true;
		if (a > maxidx) {
			maxidx = a;
		}
	}
	bool check = false;
	int tem = 0;
	for (int i = 1; i <= maxidx; i++) {
		if (tem  <1) {
			check = false;
		}
		if (!check&&ary[i]) {
			tem = L-1;
			res++;
			check = true;
			continue;
		}
		tem--;
	}
	cout << res << endl;
}

후기

다른 분들의 풀이를 보면 파이프를 int 배열에 입력을 받고 오름차순 정렬 후 테이프의 길이 만큼 bool 배열을 true로 만들며 고쳤다고 표시하는 방식을 사용하였다.

내가 한건 뭔가 가독성이 좋지 않아보인다..

문제

반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.

예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오

입력

첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

출력

첫째 줄에 최대 연결 개수를 출력한다.

<출처> https://www.acmicpc.net/

이 문제를 풀다풀다 계속 오답이 나오길래 구글링을 통해 다른 분들의 해법을 보았다.

그런데 도무지 이해가 되지 않는 점이 ... 1가지 있었다..

먼저 LIS의 개념을 모르시는 분들을 위해

참고 사이트 : http://dyngina.tistory.com/16

다른 분들의 풀이를 보면 LIS를 이용해 풀었다. 나 또한 LIS의 개념은 일부 맞지만 이 문제의 핵심인 "선이 교차하지 않는것" 이 부분을 어긴다? 라고 생각이 들었는데 정답 처리가 되어 더 혼란속으로 빠져들었다...

이런식으로 주어졌을 때 (2와2),(4와3),(6과5) 이렇게 이어졌을 때 겹치지 않으면서 최대로 연결할 수 있다.

다른 분들의 풀이를 보면 LIS를 토대로 (2와2)(4와3)까지 이어졌을 때 오른쪽에 있는 1이 들어갈 최적의 위치를 계산해서 (2와2)를 제거하고 대신 들어가게 된다.

그러면 겹치는 선이 아닌가?? 여기서 의문이 들었다.... 지금도 모르겠다...

나는 선이 겹치는 문제 때문에 아래와 같은 방식으로 했었다.

check[1] = weight[1];
	int idx = 1;
	for (int i = 2; i <= N; i++) {
		if (check[idx] < weight[i]) {
			check[++idx] = weight[i];
			continue;
		}
		if (idx == 1) {
			check[idx] = weight[i];
		}
		else if (check[idx - 1] < weight[i]) {
			for(int k=)
			check[idx] = weight[i];
		}
	}

<마지막에 들어간 수보다 작고, 마지막 보다 한칸 전에 들어간 수보다 크다면 마지막을 대신해 넣고 작다면 아무것도 하지 않는다. 작다면 겹치는 문제가 발생하기 때문!> 이라고 생각했다. 

지금도 왜 안되는지 모르겠다.. 혹시 아시는분이 계시면 댓글로 알려주시면 감사하겠습니다!!!

결론적으로, 이 부분만 참고했고 고쳐서 통과했다.

#include<iostream>
#include<algorithm>

using namespace std;
int N;
int weight[40001];
int check[40001];
int main() {

	cin >> N;

	for (int i = 1; i <=N; i++) {
		cin >> weight[i];
	}
	check[1] = weight[1];
	int idx = 1;
	for (int i = 2; i <= N; i++) {
		if (check[idx] < weight[i]) {
			check[++idx] = weight[i];
			continue;
		}
		int iter = lower_bound(check + 1, check + 1 + idx, weight[i]) - check;
		check[iter] = weight[i];
	}
	cout << idx << endl;
}