차차

문제 출처 : https://www.acmicpc.net/problem/2458

알고리즘

- 그래프 이론

- 그래프 탐색

- 플로이드-워셜

키 순서를 알기 위해서는 자기보다 큰 사람이 누구인지, 작은 사람이 누구인지 모두 알고 있어야 한다.

자기 자신과는 키 비교를 안해도 순서를 알 수 있기 때문에 1로 체크해준다.

키를 비교한 결과 a < b 를 입력받고 arr[a][b] = 1로 체크해준다.

플로이드-워셜 알고리즘을 돌려주면 자기보다 큰 사람이 체크 된다.

배열을 돌며 반대의 경우도 체크하여 자기보다 작은 사람을 체크해준다.

배열을 돌며 0이 하나라도 있다면 비교 불가이므로 넘어간다.

모두 1이라면 비교 가능이므로 cnt를 1 올려준다.

플로이드-워셜 알고리즘 이후 작은 사람을 체크 하는 이유

체크 후에 돌리게 된다면 예제와 같은 경우 3 -> 4 -> 5로 3과 5가 이어지게 되어 오답이 나온다.

플로이드-워셜 이후 체크를 한다면 3 -> 4, 4 -> 3, 5 -> 4, 4 -> 5로만 이어지고 3과 5는 이어지지 않아 정답이 제대로 나온다. 

문제 출처 : https://www.acmicpc.net/problem/5972

알고리즘

- 그래프 이론

- 데이크스트라

최대 헛간의 개수 만큼 비용배열을 선언하고 무한(10억)값을 넣어준다.
두 개의 헛간과 소 마릿수를 입력 받아 v[헛간1]에 pair(헛간2, 소 마릿수)을 넣어준다.

헛간2에서 헛간1로도 이동 가능하므로 v[헛간2]에 pair(헛간1, 소 마릿수)도 같이 넣어준다.

dijk(헛간1) 함수를 돌려준다.

dis[헛간N]을 출력한다.

dijk 함수
오름차순 우선순위큐(pair)를 선언한다. (마릿수 오름차순으로 정렬)
start에서 start까지의 마릿수는 0이므로 (0, start)를 넣는다.
dis[start]도 0으로 업데이트 한다.

큐가 빌 때까지 반복문을 돈다.

distance에는 큐 top의 첫번째 값을, now에는 큐 top의 두번째 값을 넣고 pop 한다.

dis[now] < distance 라면 이미 체크한 노드이므로 다음 노드를 확인한다.

now와 연결된 노드를 모두 확인한다.
start에서 해당 노드에 가는 비용은 now까지의 비용과 now에서 해당 노드로 가는 비용의 합이다.
만약 방금 구한 값이 비용배열에 있는 값보다 작다면 최소비용이므로 업데이트 하고 큐에 넣어준다.

문제 출처 : https://www.acmicpc.net/problem/17216

문제 출처 : https://www.acmicpc.net/problem/1965

알고리즘

- 다이나믹 프로그래밍

n으로 상자의 개수를 받고, 크기가 n인 벡터에 상자 크기를 담는다.

cnt는 최대 상자의 개수가 넣을 것인데, 하나도 못 넣는다면 자기 자신 1개이므로 1로 선언한다.

dp[i]는 v[i]를 포함한 최대 상자 개수이다.

이도 역시 자기 자신 1개가 최소값이므로 1로 선언한다.

이후 반복문을 돌며 자기보다 이전 인덱스를 확인한다.

자기보다 작은 값을 발견했다면 해당 상자를 포함한 최대 상자의 개수 (dp[j])에 자신을 포함한 값 (dp[j] + 1)과 현재 들고있는 최대 상자의 개수 (dp[i])를 비교하여 큰값으로 업데이트 한다.

cnt와 dp[i]를 비교하여 정답값도 업데이트 한다.

반복문이 끝나면 답을 출력한다.

문제 출처 : https://www.acmicpc.net/problem/11055

알고리즘

- 다이나믹 프로그래밍

수열 A의 크기를 n에 담고, arr[] 배열에 수열 A를 담았다.

dp[i]에는 arr[i]를 포함한 가장 큰 증가 부분 수열의 합이 들어간다.

dp[0]은 arr[0]을 포함한 가장 큰 증가 부분 수열의 합이므로 arr[0]을 그대로 넣어준다.

result에는 답을 넣어줄 것인데 현재 가장 큰 증가 부분 수열의 합은 dp[0] (arr[0])이므로 그대로 넣어준다.

이후 반복문을 돌며 나머지 배열을 확인한다.

자신보다 값이 작은 배열값을 찾는다.

현재 저장되어 있는 자신을 포함한 가장 큰 증가 부분 수열의 합 (dp[i])보다 해당 값을 포함한 가장 큰 증가 부분 수열의 합 (dp[j])에 자신 (arr[i])을 포함한 값이 더 크다면 이를 업데이트 해준다.

result도 더 큰 값으로 업데이트 해준다.

arr[0]까지 다 확인했음에도 dp[i]가 0값을 가진다면 자신보다 작은 값을 가지는 배열값이 없다는 의미이므로 자신을 포함한 가장 큰 증가 부분 수열의 합은 자기 자신이 된다. dp[i]에는 arr[i]값을 넣어준다.

모든 배열값을 확인했다면 result값을 출력한다.

문제 출처 : https://www.acmicpc.net/problem/1916

알고리즘

- 그래프 이론

- 데이크스트라

최대 도시의 개수 만큼 거리배열을 선언하고 무한(10억)값을 넣어준다.
출발 도시 번호, 도착 도시 번호, 버스 비용을 입력 받아 v[출발 도시 번호]에 pair(도착 도시 번호, 버스 비용)을 넣어준다.

구하고자 하는 출발 도시 번호와 도착 도시 번호를 입력 받아 dijk(출발 도시 번호) 함수를 돌려준다.
이후 거리배열[도착 도시 번호]를 출력한다.

dijk 함수
오름차순 우선순위큐(pair)를 선언한다. (거리 오름차순으로 정렬)
start에서 start까지의 거리는 0이므로 (0, start)를 넣는다.
dis[start]도 0으로 업데이트 한다.

큐가 빌 때까지 반복문을 돈다.

distance에는 큐 top의 첫번째 값을, now에는 큐 top의 두번째 값을 넣고 pop 한다.

dis[now] < distance 라면 이미 체크한 노드이므로 다음 노드를 확인한다.

now와 연결된 노드를 모두 확인한다.
start에서 해당 노드에 가는 비용은 now까지의 비용과 now에서 해당 노드로 가는 비용의 합이다.
만약 방금 구한 값이 거리배열에 있는 값보다 작다면 최소비용이므로 업데이트 하고 큐에 넣어준다.

문제 출처 : https://www.acmicpc.net/problem/1238

알고리즘

- 그래프 이론

- 데이크스트라

모여야 하는 마을 s를 입력받는다.

도로의 시작점, 끝점, 시간을 입력 받고 v[시작점]에 pair(끝점, 시간)을 넣어준다.

모든 마을에 대해서 왕복 시간을 구해준다.

시간배열을 무한값(10억)으로 초기화 한 후 모여야 하는 마을 s로 dijk함수를 돌려준다.

s에서 i까지의 시간을 temp에 저장해 둔 후 시간배열을 초기화 한다.

i에 대해 dijk함수를 돌린 후 i에서 s까지의 시간을 구해준다.

s에서 i까지의 시간과 i에서 s까지의 시간의 합과 현재 들고있는 maxtime(답)을 비교하여 큰 값을 저장한다.

maxtime을 출력한다.

dijk 함수
오름차순 우선순위큐(pair)를 선언한다. (시간 오름차순으로 정렬)
start에서 start까지의 시간은 0이므로 (0, start)를 넣는다.
dis[start]도 0으로 업데이트 한다.

큐가 빌 때까지 반복문을 돈다.

distance에는 큐 top의 첫번째 값을, now에는 큐 top의 두번째 값을 넣고 pop 한다.

dis[now] < distance 라면 이미 체크한 노드이므로 다음 노드를 확인한다.

now와 연결된 노드를 모두 확인한다.
start에서 해당 노드에 가는 시간은 now까지의 시간과 now에서 해당 노드로 가는 시간의 합이다.
만약 방금 구한 값이 시간배열에 있는 값보다 작다면 최단시간이므로 업데이트 하고 큐에 넣어준다.

문제 출처 : https://www.acmicpc.net/problem/1753

알고리즘

- 그래프 이론

- 데이크스트라

문제 출처 : https://www.acmicpc.net/problem/11438

트리를 만들고 깊이를 체크해준다.

이후 깊이에 맞게 부모를 설정해준다.

같은 깊이까지 끌어올리고 두 수가 같은지 비교후 같다면 출력, 다르다면 한단계 올라가기가 생각 한 풀이방법이다.

#define MAX_NODE 100001
#define MAX_DEPTH 17 // 2^17 > 100000
int parent[MAX_NODE][MAX_DEPTH];
int depth[MAX_NODE];
bool check[MAX_NODE];
vector<int> tree[MAX_NODE];

MAX_NODE는 문제에서 주어진 정점의 최대 개수를, MAX_DEPTH는 log2(100001) 약 16.6이므로 17을 설정해 주었다.

부모를 담을 배열과 깊이를 담을 배열, dfs에서 체크를 해줄 배열, 트리틑 만들 tree벡터를 선언해주었다.

int n, m;
cin >> n;
for (int i = 1; i < n; i++) {
	int u, v;
	cin >> u >> v;
	tree[u].push_back(v);
	tree[v].push_back(u);
}
DFS(1, 0);

두 수를 입력 받고 tree에 저장한 후 DFS를 돌려준다.

루트는 1번 노드이며 루트의 깊이는 0이다.

void DFS(int node, int d) {
	check[node] = true;
	depth[node] = d;
	for (int i = 0; i < tree[node].size(); i++) {
		int next = tree[node][i];
		if (check[next]) continue;
		parent[next][0] = node;
		DFS(next, d + 1);
	}
}

방문한 노드인지 check배열에 체크 후, depth배열에 깊이를 저장해준다.

parent의[][0]에 한칸 위의 부모를 저장해준다.

void setParent() {
	for (int j = 1; j < MAX_DEPTH; j++) {
		for (int i = 1; i < MAX_NODE; i++) {
			parent[i][j] = parent[parent[i][j - 1]][j - 1];
		}
	}
}

parent[i][j] = parent[parent[i][j-1]][j-1]

node   :      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
parent[.][0]: 0 1 1 2 2 2 3 3 4 4  5  5  7  7  11
parent[.][1]: 0 0 0 1 1 1 1 1 2 2  2  2  3  3  5
parent[.][2]: 0 0 0 0 0 0 0 0 1 1  1  1  1  1  2
...

setParent를 돌리면 위와 같은 형태로 되어있을 것이다.

0에는 부모, 1에는 조부모.. 형태로 들어가 있다.

int LCA(int x, int y) {
	if (depth[x] > depth[y]) swap(x, y);
	for (int i = MAX_DEPTH - 1; i >= 0; i--) {
		if (depth[y] - depth[x] >= (1 << i)) {
			y = parent[y][i];
		}
	}
	if (x == y) return x;
	for (int i = MAX_DEPTH - 1; i >= 0; i--) {
		if (parent[x][i] != parent[y][i]) {
			x = parent[x][i];
			y = parent[y][i];
		}
	}
	return parent[x][0];
}

이후 LCA를 돌려준다.

우선 2번째 매개변수 y쪽이 더 높은 depth를 가지도록 순서를 변경해준다.

y가 x와 같은 깊이를 가질 때까지 끌어올려주고 y를 해당 깊이의 조상으로 값을 변경해준다.

x와 y가 같다면 이가 최소 공통 조상이므로 return 해준다.

같지 않다면 더 위로 올라가 최소 공통 조상을 찾아야 한다.

한칸씩 위로 올라가며 둘이 같지 않다면 각각 부모의 값으로 변경해준다.

둘이 같다면 최소 공통 조상이므로 이를 return 해준다.

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

#define MAX_NODE 100001
#define MAX_DEPTH 17 // 2^17 > 100000
int parent[MAX_NODE][MAX_DEPTH];
int depth[MAX_NODE];
bool check[MAX_NODE];
vector<int> tree[MAX_NODE];

void DFS(int node, int d) {
	check[node] = true;
	depth[node] = d;
	for (int i = 0; i < tree[node].size(); i++) {
		int next = tree[node][i];
		if (check[next]) continue;
		parent[next][0] = node;
		DFS(next, d + 1);
	}
}

void setParent() {
	for (int j = 1; j < MAX_DEPTH; j++) {
		for (int i = 1; i < MAX_NODE; i++) {
			parent[i][j] = parent[parent[i][j - 1]][j - 1];
		}
	}
}

int LCA(int x, int y) {
	if (depth[x] > depth[y]) swap(x, y);
	for (int i = MAX_DEPTH - 1; i >= 0; i--) {
		if (depth[y] - depth[x] >= (1 << i)) {
			y = parent[y][i];
		}
	}
	if (x == y) return x;
	for (int i = MAX_DEPTH - 1; i >= 0; i--) {
		if (parent[x][i] != parent[y][i]) {
			x = parent[x][i];
			y = parent[y][i];
		}
	}
	return parent[x][0];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	DFS(1, 0);
	setParent();
	cin >> m;
	for (int i = 1; i < m; i++) {
		int u, v;
		cin >> u >> v;
		cout << LCA(u, v) << "\n";
	}
	return 0;
}

전체 코드

알고리즘

- 자료 구조

- 트리

- 최소 공통 조상

- 희소 배열

문제 출처 : https://www.acmicpc.net/problem/2293

다이나믹 프로그래밍으로 풀었다.

int n, k;
cin >> n >> k;
vector<int> coin(n + 1, 0);
vector<int> dp(k + 1, 0);
dp[0] = 1;

n과 k를 입력 받고 사이즈에 맞게 vector를 선언해준다.

coin은 n개의 동전 값을 받아 저장하고, dp는 금액을 만들 수 있는 방법의 수를 저장할 것이다.

dp[0]이 1인 이유는 0원을 만드는 방법은 아무것도 사용하지 않는 한가지 방법만 있기 때문이다.

for (int i = 0; i < n; i++) {
	cin >> coin[i];
}
for (int i = 0; i < n; i++) {
	for (int j = coin[i]; j <= k; j++) {
		dp[j] += dp[j - coin[i]];
	}
}
cout << dp[k];

동전의 가치를 입력 받고 2중 for문을 통해 각각의 동전마다 다이나믹 프로그래밍을 수행한다.

dp[j] += dp[j - coin[i]]는 j원을 만들 수 있는 방법의 수 dp[j]를 계산하는 것이다.

coin[i]는 현재 다이나믹 프로그래밍을 수행하는 동전의 가치이다.

j - coin[i]는 현재 만드려하는 j원에서 코인의 가치를 뺀 것으로 j - coin[i]를 만드는 방법의 수 dp[j - coin[i]에 coin[i]를 추가하면 j를 만드는 방법의 수가 되는 것이다.

예시와 같이 3 10 1 2 5를 입력했다고 했을 때

dp: 1 0 0 0 0 0 0 0 0 0 0 (index는 목표하는 금액을 의미합니다.)

초기에는 위와 같은 상태이다.

dp: 1 1 1 1 1 1 1 1 1 1 1

1원 동전에 대해 다이나믹 프로그래밍을 수행한 결과이다.

dp: 1 1 2 2 3 3 4 4 5 5 6

2원 동전에 대해 다이나믹 프로그래밍을 수행한 결과이다.

예를 들어 2원을 만드는 방법에는 1원 2개를 쓰는 방법과 2원 1개를 쓰는 방법, 총 2가지가 있을 것이다.

3원을 만드는 방법에는 1원 3개를 쓰는 방법과 2원 1개, 1원 1개를 쓰는 방법, 총 2가지가 있을 것이다.

4원을 만드는 방법은 2원을 만드는 방법인 1원2개, 2원 1개에서 2원을 추가하여 (1, 1, 2), (2, 2)와 1원만을 사용한 (1, 1, 1, 1) 총 3가지 방법이 있을 것이다.

위와 같이 j원을 만드는 방법은 현재 저장되어 있는 j원을 만드는 방법의 수에서 j - coin[i]을 만드는 방법의 수를 더해 나가면 구할 수 있다.

dp: 1 1 2 2 3 4 5 6 7 8 10

5원 동전에 대해 다이나믹 프로그래밍을 수행한 결과이다.

모든 동전에 대해 다이나믹 프로그래밍을 수행했다면 k원을 만드는 방법의 가지 수인 dp[k]를 출력해준다.

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	vector<int> coin(n + 1, 0);
	vector<int> dp(k + 1, 0);
	dp[0] = 1;
	for (int i = 0; i < n; i++) {
		cin >> coin[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = coin[i]; j <= k; j++) {
			dp[j] += dp[j - coin[i]];
		}
	}
	cout << dp[k];
	return 0;
}

전체코드

알고리즘

- 다이나믹 프로그래밍