언제나 처음처럼

#include <iostream>
using namespace std;

// 원소 교환
void swap(int arr[], int idx1, int idx2) {
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}

// 선택정렬 
// time complexity : O(n^2)
void selectionSort(int arr[], int len) {
	for (int i = 0; i < len; i++) {
		int idx = i;
		for (int j = i + 1; j < len; j++) {
			if (arr[idx] >= arr[j])
				idx = j;
		}

		swap(arr, i, idx);
	}
}

// 삽입정렬 
// 정렬 되어있는 경우 time complexity : O(n)
// 정렬 되어있지 않는 경우 time complexity : O(n^2);
void insertionSort(int arr[], int len) {
	for (int i = 1; i < len; i++) {
		int val = arr[i];
		for (int j = i - 1; j >= 0; j--) {
			if (val < arr[j]) {
				arr[j + 1] = arr[j];
				arr[j] = val;
			}
			else {
				break;
			}
		}
	}
}

// 버블정렬
// time complexity : O(n^2)
void bubbleSort(int arr[], int len) {
	for (int i = 0; i < len - 1; i++) {
		for (int j = 0; j < len - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(arr, j, j + 1);
			}
		}
	}
}

// 퀵정렬
// 평균, 최고 time complexity : O(n log n)
// 최악 time complexity : O(n^2) <--- 최적화 전
// 퀵정렬 최적화 -> left, mid, right 값 중에서 중간값을 pivot으로 선택하도록 구현
// 선택한 pivot과 left 값을 서로 바꾼다
int getMidIndex(int arr[], int left, int right) {
	int mid = (left + right) / 2;
	int idx[3] = { left, mid, right };

	if (arr[idx[0]] > arr[idx[1]]) {
		swap(idx, 0, 1);
	}

	if (arr[idx[1]] > arr[idx[2]]) {
		swap(idx, 1, 2);
	}

	if (arr[idx[0]] > arr[idx[1]]) {
		swap(idx, 0, 1);
	}

	return idx[1];
}

void quickSort(int arr[], int left, int right) {
	if (left >= right) return;

	int pIdx = getMidIndex(arr, left, right);
	swap(arr, left, pIdx);

	int pivot = left;
	int low = left + 1;
	int high = right;

	while (1) {
		while (low <= right && arr[low] <= arr[pivot])
			low++;
		while (high > left && arr[high] >= arr[pivot])
			high--;

		if (low > high) // low, high 가 서로 교차했다면
			break;

		int temp = arr[low];
		arr[low] = arr[high];
		arr[high] = temp;
	}

	int temp = arr[pivot];
	arr[pivot] = arr[high];
	arr[high] = temp;

	quickSort(arr, left, high - 1);
	quickSort(arr, high + 1, right);
}

// 병합정렬
// time complexity : O(n log n)
// 정렬한 배열을 임시로 저장할 임시 메모리가 필요한 단점이 있다
// 정렬의 대상이 배열이 아닌 리스트일 경우 임시 메모리 필요 없어서 좋은 성능 발휘
void merge(int arr[], int left, int mid, int right) {
	int idx1 = left;
	int idx2 = mid + 1;

	int* temp = new int[right + 1];
	int idx = left;

	while (idx1 <= mid && idx2 <= right) {
		if (arr[idx1] < arr[idx2]) // idx1이 가리키는 값이 idx2가 가리키는 값보다 작다면
			temp[idx++] = arr[idx1++];
		else
			temp[idx++] = arr[idx2++];
	}

	if (idx1 > mid)
		while (idx2 <= right)
			temp[idx++] = arr[idx2++];
	else
		while (idx1 <= mid)
			temp[idx++] = arr[idx1++];

	for (int i = left; i <= right; i++)
		arr[i] = temp[i];

	delete[] temp;
}

void mergeSort(int arr[], int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;

		mergeSort(arr, left, mid);
		mergeSort(arr, mid + 1, right);

		merge(arr, left, mid, right);
	}
}


int main(void) {
	int arr[10] = { 3,4,5,6,1,10,2,7,8,9 };

	//	selectionSort(arr, 10);
	//	insertionSort(arr, 10);
	//	bubbleSort(arr, 10);
	//	quickSort(arr, 0, 9);
	mergeSort(arr, 0, 9);

	for (auto x : arr)
		cout << x << ' ';
}

[문제 링크]

너비 우선 탐색으로 풀 수 있는 문제였다.

먼저 크기가 10000인 prime 배열을 선언하고, 에라토스테네스의 체 알고리즘을 통해 소수가 아닌 숫자들을 true로 바꿔주었다.

그다음 문제 조건에 따라 너비 우선 탐색을 통해 A의 숫자를 한개씩 바꾸면서 숫자 B와 일치할 때까지 바꾼 최소 횟수를 구해주면 된다.

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

bool prime[10000];
bool visited[10000];

void getPrime() {
	prime[1] = true;

	for (int i = 2; i < 10000 / 2; i++) {
		if (prime[i]) continue;

		for (int j = i * 2; j < 10000; j += i)
			if (!prime[j]) 
				prime[j] = true;
	}
}

int bfs(int a, int b) {
	queue<pair<int, int>> q;
	q.push({ a, 0 });
	visited[a] = true;

	while (!q.empty()) {
		int here = q.front().first;
		int move = q.front().second;
		q.pop();

		if (here == b) return move;

		for (int i = 1; i <= 4; i++) {
			int there;
			switch (i) {
			case 1: // 1000의 자리
				for (int j = 1; j <= 9; j++) {
					there = (j * 1000) + (here % 1000);
					if (!visited[there] && !prime[there]) {
						visited[there] = true;
						q.push({ there, move + 1 });
					}
				}
				break;

			case 2: // 100의 자리
				for (int j = 0; j <= 9; j++) {
					there = (here / 1000 * 1000) + (j * 100) + (here % 100);
					if (!visited[there] && !prime[there]) {
						visited[there] = true;
						q.push({ there, move + 1 });
					}
				}
				break;

			case 3: // 10의 자리
				for (int j = 0; j <= 9; j++) {
					there = (here / 100 * 100) + (j * 10) + (here % 10);
					if (!visited[there] && !prime[there]) {
						visited[there] = true;
						q.push({ there, move + 1 });
					}
				}
				break;

			case 4: // 1의 자리
				for (int j = 0; j <= 9; j++) {
					there = (here / 10 * 10) + j;
					if (!visited[there] && !prime[there]) {
						visited[there] = true;
						q.push({ there, move + 1 });
					}
				}
			}
		}
	}

	return -1;
}

int main(void) {
	int tc;
	cin >> tc;

	getPrime();

	while (tc--) {
		memset(visited, false, sizeof(visited));
		int a, b;
		cin >> a >> b;

		int result = bfs(a, b);

		if (result == -1)
			cout << "Impossible" << endl;
		else
			cout << result << endl;
	}
}

알고리즘 200일 프로젝트 - 168 day

[문제 링크]

문제를 보고 생각난 알고리즘은 플로이드-와샬 알고리즘이었다. 하지만 N이 최대 800이므로 O(N^3)이면 약 5억이 넘게 되어 시간초과가 날 것이라 생각하고 다익스트라 알고리즘으로 구현하였다.

정점 v1과 v2를 반드시 지나야 하기 때문에 1부터 N까지 갈 수 있는 방법은 아래 두가지 경로만 가능하다.

경로 1) dist[1][v1] -> dist[v1][v2] -> dist[v2][N] 

경로 2) dist[1][v2] -> dist[v2][v1] -> dist[v1][N]

dist[v1][v2] 와 dist[v2][v1] 의 최단경로는 서로 같으므로, 3개의 정점 1, v1, N 을 출발점으로 하는 다익스트라 알고리즘을 수행하여 최단경로를 계산해주면 된다.

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

// INF를 987654321로 할 경우
// 62~63 라인에서 int의 최대 범위 넘어갈 수 있다.
const int INF = 700000000;
int N, E;
vector<vector<pair<int, int>>> adj(801);
vector<vector<int>> allDist(801, vector<int>(801, INF));

void dijkstra(int start) {
	vector<int> dist(N + 1, INF);
	dist[start] = 0;

	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });

	while (!pq.empty()) {
		int here = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();

		if (dist[here] < cost) continue;

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextCost = adj[here][i].second + cost;

			if (dist[there] > nextCost) {
				dist[there] = nextCost;
				pq.push({ -nextCost, there });
			}
		}
	}

	allDist[start] = dist;
}

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

	cin >> N >> E;

	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({ b, c });
		adj[b].push_back({ a, c });
	}

	int v1, v2;
	cin >> v1 >> v2;

	dijkstra(1);
	dijkstra(v1);
	dijkstra(N);

	int path1 = allDist[1][v1] + allDist[v1][v2] + allDist[v2][N];
	int path2 = allDist[1][v2] + allDist[v1][v2] + allDist[v1][N];

	int result = min(path1, path2);

	if (result >= INF)
		cout << -1 << endl;
	else
		cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 168 day

[문제 링크]

그래프의 오일러 서킷과 관련된 문제였다. 순환을 이루는 정점들은 서로 팀을 이루고 있다고 볼 수 있고, 순환하지 않는 정점들의 개수를 찾아주면 된다.

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

int n;
int adj[100001];
bool visited[100001];

int dfs(int here, vector<int>& circuit) {

	visited[here] = true;
	circuit.push_back(here);

	int there = adj[here];
	if (!visited[there]) {
		return dfs(there, circuit);
	}
	return there;
}

int bfs(int start, vector<int>& circuit) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

	while (!q.empty()) {
		int here = q.front();
		q.pop();
		circuit.push_back(here);

		int there = adj[here];

		if (!visited[there]) {
			visited[there] = true;
			q.push(there);
		}
		else
			return there;
	}
}

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

	int tc;
	cin >> tc;

	while (tc--) {
		memset(visited, false, sizeof(visited));
		cin >> n;

		for (int i = 1; i <= n; i++)
			cin >> adj[i];

		int result = 0;
		for (int i = 1; i <= n; i++) {
			if (!visited[i]) {
				vector<int> circuit;
				int idx = bfs(i, circuit);
				int len = circuit.size();

				for (int i = 0; i < len; i++) {
					if (idx == circuit[i]) break;
					result++;
				}
			}
		}
		cout << result << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 168 day

[문제 링크]

간단한 문제였다. 모든 정점을 시작점으로 bfs나 dfs를 수행하여 그중 최댓값을 찾으면 정답을 받을 수 있다.

하지만 이 문제를 더 빠르게 풀 수 있는 방법이 존재한다고 한다. 

뿌리노드인 1번 노드에서 가장 멀리 떨어진 정점을 찾고, 그 정점을 시작점으로 하여 가장 멀리 떨어진 정점까지의 거리가 곧 트리의 지름이 된다. 따라서 탐색을 2번 수행하므로 O(n) 시간에 문제를 해결할 수 있다.

자세한 증명은 구사과님의 블로그에 설명되어 있다.

https://koosaga.com/14

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N;
vector<vector<pair<int, int>>> adj(10001);
bool visited[10001];

pair<int, int> bfs(int start) {
	queue<pair<int, int>> q;
	q.push({ start, 0 });
	visited[start] = true;

	pair<int, int> ret = { 0,0 };
	while (!q.empty()) {
		int here = q.front().first;
		int cost = q.front().second;
		q.pop();

		if (ret.second < cost)
			ret = { here, cost };

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextCost = cost + adj[here][i].second;

			if (!visited[there]) {
				visited[there] = true;
				q.push({ there, nextCost });
			}
		}
	}

	return ret;
}


int main(void) {
	cin >> N;
	
	for (int i = 0; i < N - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c;

		adj[a].push_back({ b, c });
		adj[b].push_back({ a, c });
	}

	// find maximum node
	int maxNode = bfs(1).first;

	memset(visited, false, sizeof(visited));

	// get diameter
	int diameter = bfs(maxNode).second;

	cout << diameter << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 168 day

[문제 링크]

간단한 문제처럼 보였는데 고려해줘야 할 점이 많은 문제였다.

다른 bfs 문제들을 풀듯이 D,S,L,R 4가지 경우에 대해 탐색하면서 string에 추가해주는 방식으로 구현했는데 메모리초과에 시간초과에 난리가 났다.

원인을 찾아보니 string 컨테이너의 경우 문자를 추가하는 연산이나 복사본을 큐에 집어넣는 연산에 있어 많은 시간이 필요하다고 한다.

따라서 bfs 탐색을 하면서 방문체크 대신 방문한 숫자 인덱스에 만들기 전 숫자와 어떤 버튼으로 만들었는지 정보를 원소로 담았다.

그다음 목표 숫자 B에서부터 역으로 추적하면서 어떤 버튼을 눌렀는지 vector에 담은 다음 역순으로 출력하도록 구현하였다.

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

vector<pair<int, char>> visited(10000);

int calculate(int num, char type) {
	switch (type) {
	case 'D':
		num = (num * 2) % 10000;
		break;

	case 'S':
		if (num == 0) num = 9999;
		else num -= 1;
		break;

	case 'L':
		num = (num % 1000) * 10 + (num / 1000);
		break;

	case 'R':
		num = (num % 10) * 1000 + (num / 10);
		break;
	}

	return num;
}

void Queue_push(queue<int>& q, int num, char type) {
	int nextNum = calculate(num, type);
	if (visited[nextNum].first == -1) {
		visited[nextNum].first = num;
		visited[nextNum].second = type;
		q.push(nextNum);
	}
}

void bfs(int A, int B) {
	visited = vector<pair<int, char>>(10000, { -1,-1 });
	queue<int> q;
	q.push(A);
	visited[A] = { -1, -1 };

	while (!q.empty()) {
		int hereNum = q.front();
		q.pop();

		if (hereNum == B) return;

		Queue_push(q, hereNum, 'D');
		Queue_push(q, hereNum, 'S');
		Queue_push(q, hereNum, 'L');
		Queue_push(q, hereNum, 'R');
		
	}
}

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

	int tc;
	cin >> tc;

	while (tc--) {
		int A, B;
		cin >> A >> B;
		bfs(A, B);

		vector<char> result;
		int idx = B;
		while (idx != A) {
			result.push_back(visited[idx].second);
			idx = visited[idx].first;
		}
		
		int len = result.size();
		for (int i = len; i >= 0; i--)
			cout << result[i];
		cout << '\n';
	}

	return 0;
}

알고리즘 200일 프로젝트 - 167 day

[문제 링크]

방향그래프를 만든 다음 최단 경로 알고리즘을 통해 간단히 풀 수 있는 문제였다.

처음 풀었을 땐 플로이드-와샬 알고리즘으로 구현해서 정답을 받았는데, 생각해보니 N이 최대 1000이기 때문에 시간복잡도가 O(N^3)인 플로이드-와샬 알고리즘을 사용하면 최악의 경우 10억만큼의 시간이 걸리게 된다. 입력데이터가 부실했기 때문에 운좋게 통과했다고 생각한다.

따라서 다익스트라 알고리즘을 사용해서 다시 구현하였다.

//추가 : 질문게시판에서 시간복잡도를 더 줄이는 방법에 대한 힌트를 발견하였다.

도착지점이 X로 정해져 있기 때문에 모든 정점의 최단 경로를 다 구할 필요 없이 정점으로 들어오는 간선들의 집합과 정점에서 나가는 간선들의 집합을 분리한 다음, 정점 X에서 들어오는 간선과 나가는 간선을 대상으로 두번의 다익스트라를 수행하면 문제를 해결할 수 있다.

// 플로이드-와샬 알고리즘 사용

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

const int INF = 987654321;
vector<vector<int>> adj(1001, vector<int>(1001, INF));

void floyd(int N) {
	for (int i = 1; i <= N; i++) {
		adj[i][i] = 0;
	}

	for (int k = 1; k <= N; k++)
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}

int main(void) {
	int N, M, X;
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int A, B, W;
		cin >> A >> B >> W;
		adj[A][B] = W;
	}

	floyd(N);

	int result = 0;
	for (int i = 1; i <= N; i++) {
		result = max(result, adj[i][X] + adj[X][i]);
	}

	cout << result << endl;

	return 0;
}

// 다익스트라 알고리즘 사용

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

const int INF = 987654321;
int N, M, X;
vector<pair<int, int>> adj[1001];
vector<vector<int>> allTownDist(1001);

void dijkstra(int start) {
	vector<int> dist(N+1, INF);
	dist[start] = 0;
	
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });

	while (!pq.empty()) {
		int here = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();

		if (dist[here] < cost) continue;
		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextCost = adj[here][i].second + cost;

			if (dist[there] > nextCost) {
				dist[there] = nextCost;
				pq.push({ -nextCost, there });
			}
		}
	}

	allTownDist[start] = dist;
}

int main(void) {
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int A, B, W;
		cin >> A >> B >> W;
		adj[A].push_back({ B, W });
	}

	for (int i = 1; i <= N; i++)
		dijkstra(i);

	int result = 0;
	for (int i = 1; i <= N; i++) 
		result = max(result, allTownDist[i][X] + allTownDist[X][i]);

	cout << result << endl;

	return 0;
}

// 다익스트라 2번으로 문제를 해결하는 코드

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

const int INF = 987654321;
int N, M, X;
vector<pair<int, int>> adjIn[1001];
vector<pair<int, int>> adjOut[1001];

vector<int> inDist(1001);
vector<int> outDist(1001);

void dijkstra(int start, int type) {
	vector<int> dist(N + 1, INF);
	dist[start] = 0;

	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });
	
	if (type == 1) {
		while (!pq.empty()) {
			int here = pq.top().second;
			int cost = -pq.top().first;
			pq.pop();

			if (dist[here] < cost) continue;
			for (int i = 0; i < adjIn[here].size(); i++) {
				int there = adjIn[here][i].first;
				int nextCost = adjIn[here][i].second + cost;

				if (dist[there] > nextCost) {
					dist[there] = nextCost;
					pq.push({ -nextCost, there });
				}
			}
		}
		inDist = dist;
	}

	else {
		while (!pq.empty()) {
			int here = pq.top().second;
			int cost = -pq.top().first;
			pq.pop();

			if (dist[here] < cost) continue;
			for (int i = 0; i < adjOut[here].size(); i++) {
				int there = adjOut[here][i].first;
				int nextCost = adjOut[here][i].second + cost;

				if (dist[there] > nextCost) {
					dist[there] = nextCost;
					pq.push({ -nextCost, there });
				}
			}
		}
		outDist = dist;
	}
}

int main(void) {
	cin >> N >> M >> X;

	for (int i = 0; i < M; i++) {
		int A, B, W;
		cin >> A >> B >> W;
		adjIn[A].push_back({ B, W });
		adjOut[B].push_back({ A, W });
	}

	dijkstra(X, 1); // 정점으로 들어오는 간선들의 최단경로
	dijkstra(X, 2); // 정점에서 나가는 간선들의 최단경로

	int result = 0;
	for (int i = 1; i <= N; i++) 
		result = max(result, inDist[i] + outDist[i]);

	cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 167 day

[문제 링크]

너비 우선 탐색을 활용하는 문제였다.

알고리즘은 다음과 같다.

1) 입력받은 배열에서 하나로 연결된 섬들을 1이 아닌 다른 숫자로 바꿔준다.

2) 배열의 모든 원소를 탐색하면서 0이 아닌 좌표를 발견하면 이 좌표를 시작점으로 하는 너비 우선 탐색을 수행한다.

3) 현재 좌표의 동서남북 방향에서 값이 0인 좌표와 (현재까지 놓은 다리 길이 + 1)을 큐에 담는다.

만약 현재 좌표에서 인접한 곳에 다른 섬이 존재한다면 두 섬이 연결된 것이므로 현재까지 놓은 다리 길이를 반환한다.

4) 0이 아닌 모든 좌표에 대해 너비 우선 탐색을 수행하면서 반환된 다리 길이 중 가장 작은 값을 결과로 출력한다.

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct Pos {
	int y;
	int x;
};

const int INF = 987654321;
int N;
int board[100][100];
bool visited[100][100];
int dy[4] = { 0, 0, 1, -1 };
int dx[4] = { 1, -1, 0, 0 };

int bfs(Pos start, int type) {
	queue<pair<Pos, int>> q;
	q.push({ start, 0 });
	visited[start.y][start.x] = true;

	while (!q.empty()) {
		Pos here = q.front().first;
		int isLen = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			Pos there = { here.y + dy[i], here.x + dx[i] };

			if (there.y >= 0 && there.y < N && there.x >= 0 && there.x < N) {
				int nextType = board[there.y][there.x];

				if (!visited[there.y][there.x] && nextType == 0) {
					visited[there.y][there.x] = true;
					q.push({ there, isLen + 1 });
				}
				else if (nextType != 0 && nextType != type)
					return isLen;
			}
		}
	}

	return INF;
}

void divide_Island(Pos start, int type) {
	queue<Pos> q;
	q.push(start);
	board[start.y][start.x] = type;

	while (!q.empty()) {
		Pos here = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			Pos there = { here.y + dy[i], here.x + dx[i] };
			
			if(there.y >= 0 && there.y < N && there.x >= 0 && there.x < N)
				if (board[there.y][there.x] == 1) {
					board[there.y][there.x] = type;
					q.push(there);
				}
		}
	}
}

int main(void) {
	cin >> N;
	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> board[i][j];

	int type = 2;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (board[i][j] == 1) {
				divide_Island({ i,j }, type);
				type++;
			}

	int result = INF;
	for(int i=0; i<N; i++)
		for (int j = 0; j < N; j++) {
			if (board[i][j] != 0) {
				memset(visited, false, sizeof(visited));
				result = min(result, bfs({ i,j }, board[i][j]));
			}
		}

	cout << result << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 166 day