언제나 처음처럼

[문제 링크]

스택과 재귀를 이용하는 구현 문제였다.

문자열을 탐색하면서 숫자를 만날 경우 스택에 쌓아두고 '(' 를 만날 경우 그 다음 인덱스부터 재귀호출 하여 반환된 값에 스택의 가장 위에 있는 숫자를 곱해주는 방식으로 구현하였다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int decompress(string& str, int& here) {
	stack<char> stk;

	int ret = 0;

	while (str.size() > here) {
		if (str[here] == '(') {
			ret += (stk.top() - '0') * decompress(str, ++here);
			stk.pop();
		}
		else if (str[here] == ')') {
			here++;
			break;
		}
		else 
			stk.push(str[here++]);
	}
	ret += stk.size();

	return ret;
}

int main(void) {

	string str;
	cin >> str;

	int start = 0;
	cout << decompress(str, start) << endl;

	return 0;
}

[문제 링크]

은근히 까다로운 구현 문제였다.

2차원 세계 바깥쪽은 블록이 없기 때문에 빗물이 고이지 않는다. 따라서 첫번째와 마지막 블록의 높이가 중요하다고 볼 수 있다. 

필자는 주어진 배열에서 블록의 높이가 가장 높은 인덱스를 찾은 다음, 양 끝을 시작점으로 하여 두개의 포인터가 높이가 가장 높은 인덱스를 향해 가도록 구현하였다.

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

int H, W;
int block[501];

int getHighestIndex() {
	int highest = block[0];
	int idx = 0;

	for(int i=1; i<W; i++)
		if (highest <= block[i]) {
			highest = block[i];
			idx = i;
		}

	return idx;
}

int getRainWater() {
	queue<int> qFront, qBack;
	int highIdx = getHighestIndex();
	int frontHigh = 0, backHigh = 0;
	int ret = 0;

	for (int i = 0; i < W; i++) {
		int front = i;
		int back = W - 1 - i;

		if (front <= highIdx) {
			if (frontHigh > block[front]) {
				qFront.push(block[front]);
			}
			else {
				while (!qFront.empty()) {
					ret += frontHigh - qFront.front();
					qFront.pop();
				}
				frontHigh = block[front];
			}
		}

		if (back >= highIdx) {
			if (backHigh > block[back]) {
				qBack.push(block[back]);
			}
			else {
				while (!qBack.empty()) {
					ret += backHigh - qBack.front();
					qBack.pop();
				}
				backHigh = block[back];
			}
		}
	}

	return ret;
}

int main(void) {
	cin >> H >> W;

	for (int i = 0; i < W; i++)
		cin >> block[i];

	cout << getRainWater() << endl;

	return 0;
}

[문제 링크]

완전탐색 문제였다.

리모컨 버튼이 0~9 번까지 있기 때문에 버튼만 가지고 만들 수 있는 채널의 범위는 0~999999 이라는 것을 알 수 있다.

i = 0 부터 999999까지 숫자에 대해 고장나지 않은 버튼으로 만들 수 있는 숫자인지 확인하고 만들 수 있는 숫자라면 해당 채널로 이동할 경우 버튼 누르는 횟수를 계산해서 최솟값을 구하면 된다.

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

bool number[10];

bool isMakeNumber(int num) {
	string numStr = to_string(num);

	while (!numStr.empty()) {
		if (number[numStr.back() - '0'])
			numStr.pop_back();
		else
			return false;
	}

	return true;
}

int getMinimumClick(int N) {
	int start = 100;
	int ret = abs(N - start);

	for (int i = 0; i <= 999999; i++) {
		if (i == 100) continue;
		if (isMakeNumber(i)) {
			int click = to_string(i).size() + abs(N - i);
			ret = min(ret, click);
		}
	}

	return ret;
}

int main(void) {
	memset(number, true, sizeof(number));

	int N;
	cin >> N;

	int M;
	cin >> M;

	for (int i = 0; i < M; i++) {
		int num;
		cin >> num;
		number[num] = false;
	}

	cout << getMinimumClick(N) << endl;

	return 0;
}

[문제 링크]

LIS를 구하는 문제였다. 다만 수열의 길이가 1,000,000 으로 매우 길기 때문에 이중 for문을 돌려서 답을 얻는 일반적인 방법으로 구현할 경우 시간복잡도가 매우 커지게 된다.

따라서 다른 방법으로 구현해야 하는데... 예를 들어 다음과 같은 수열이 있다고 하자.

1  2  3  3  1  4  6  5

방법은 다음과 같다.

우선 첫 번째 인덱스에 있는 원소는 바로 추가한다.

1

그 다음 인덱스를 확인하여 LIS의 마지막 원소와 비교한다.

다음 인덱스의 원소는 2, LIS의 마지막 원소는 1 이다.

다음 인덱스의 원소가 더 클 경우 LIS의 맨 끝에 원소를 추가한다.

1  2

그 다음 인덱스를 확인하여 LIS의 마지막 원소와 비교한다.

다음 인덱스의 원소가 3이므로 2보다 크기 때문에 LIS의 맨 끝에 원소를 추가한다.

1  2  3

그 다음 인덱스를 확인하여 LIS의 마지막 원소와 비교한다.

다음 인덱스의 원소는 3, LIS의 마지막 원소 또한 3으로 같다.

다음 인덱스의 원소가 같거나 더 작을 경우 LIS 배열에서 정렬이 깨지지 않는 위치에 값을 덮어씌운다.

이때 LIS 배열은 오름차순으로 정렬되어 있는 상태이므로 이분 탐색을 통해 값을 바꿀 위치를 O(logN) 시간만에 찾을 수 있다.

1  2  3

이런 방식으로 배열의 모든 원소를 탐색하면 된다.

다음 인덱스의 원소는 1, LIS의 마지막 원소는 3 이다. 따라서 LIS 배열에서 값을 바꿀 위치를 찾는다.

1  2  3

다음 인덱스의 원소는 4, 마지막 원소는 3 이다. 따라서 LIS 배열 맨 끝에 4를 추가한다.

1  2  3  4

다음 인덱스의 원소는 6, 마지막 원소는 4 이다.

1  2  3  4  6

다음 인덱스의 원소는 5, 마지막 원소는 6이다.

1  2  3  5  6

LIS 배열의 원소는 총 5개. 따라서 LIS 의 길이는 5임을 알 수 있다.

이 방식으로 구현하게 되면 LIS가 어떻게 이루어져 있는지는 알 수 없지만, LIS 길이를 구하는데 있어서는

크기가 N인 배열의 모든 원소에 대하여 이분탐색을 수행하는 최악의 경우에도 O(NlogN)의 시간복잡도를 보장해준다.

#include <iostream>
using namespace std;

int N;
int arr[1000001];
int LIS[1000001];

int binary_search(int start, int end, int num) {
	int ret;

	while (start <= end) {
		int mid = (start + end) / 2;
		if (LIS[mid] >= num) {
			ret = mid;
			end = mid - 1;
		}
		else
			start = mid + 1;
	}

	return ret;
}

int getLIS() {
	int length = 1;
	
	LIS[0] = arr[0];
	for (int i = 1; i < N; i++) {
		if (LIS[length - 1] < arr[i]) {
			LIS[length] = arr[i];
			length++;
		}
		else {
			int idx = binary_search(0, length - 1, arr[i]);
			LIS[idx] = arr[i];
		}
	}

	return length;
}

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

	cout << getLIS() << endl;

	return 0;
}

[문제 링크]

그래프 탐색과 이분 탐색을 활용하는 문제였다.

공장이 있는 두 섬 A, B가 있다고 할 때, 중량을 견딜 수 있는 다리만 이용하여 A와 B를 왕래할 수 있는지 체크하기 위해 bfs를 이용하였다.

최대 중량을 구하기 위해 여러번의 bfs 탐색을 수행해야 하는데, 중량 C의 최대값이 10억으로 매우 크기 때문에 1~10억까지 전부 시도해보는 것이 아닌 이분 탐색을 활용하여 탐색 횟수를 최소화하였다.

추가로 섬의 개수 N이 최대 10000이므로, 그래프를 인접 행렬로 구현하게 되면 공간복잡도가 매우 커질 것이기에 인접리스트로 구현하여 공간복잡도를 줄였다.

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

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

bool dfs(int start, int end, int weight) {
	if (start == end) return true;
	visited[start] = true;

	for (auto x : adj[start]) {
		int next = x.first;
		int bridge = x.second;

		if (bridge >= weight && !visited[next]) {
			if (dfs(next, end, weight))
				return true;
		}
	}

	return false;
}

bool bfs(int start, int end, int weight) {
	queue<int> q;
	q.push(start);
	visited[start] = true;

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

		if (here == end)
			return true;

		for (auto x : adj[here]) {
			int next = x.first;
			int bridge = x.second;

			if (bridge >= weight && !visited[next]) {
				q.push(next);
				visited[next] = true;
			}
		}
	}

	return false;
}

int getMaximumWeight(int factory1, int factory2) {
	int start = 1;
	int end = 1000000000;

	int ret = 0;

	while (start <= end) {
		memset(visited, false, sizeof(visited));

		int mid = (start + end) / 2;

		if (bfs(factory1, factory2, mid)) {
			start = mid + 1;
			ret = mid;
		}
		else
			end = mid - 1;
	}

	return ret;
}

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

	cin >> N >> M;

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

	int factory1, factory2;
	cin >> factory1 >> factory2;

	cout << getMaximumWeight(factory1, factory2) << endl;

	return 0;
}

[문제 링크]

간단한 그래프탐색 문제였다.

자신의 키가 정확히 몇번째인지 알기 위해선 다른 모든 학생들과 그래프가 연결되어 있어야 한다.

우선, 연결되어 있는 학생들을 체크하는 함수는 dfs로 구현하였다.

학생 a보다 학생 b의 키가 더 큰지 여부를 확인하기 위해선 adj[a][b] == true 인지 확인하면 되고,

학생 a보다 학생 b의 키가 더 작은지 여부를 확인하기 위해선 그 반대인 adj[b][a] == true 인지 확인하면 된다.

따라서 키가 더 큰 학생들을 체크하는 dfs, 키가 더 작은 학생들을 체크하는 dfs를 수행하여 모든 학생들과 연결되어 있는지 알 수 있도록 구현하였다.

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

int N, M;
bool adj[501][501];
bool visited[501];
const int DOWN = 1;
const int UP = 2;

int dfs(int here, int type) {
	int ret = 1;
	visited[here] = true;

	for (int i = 1; i <= N; i++) {
		if (type == DOWN) {
			if (adj[here][i] && !visited[i])
				ret += dfs(i, type);
		}
		else if (type == UP) {
			if (adj[i][here] && !visited[i])
				ret += dfs(i, type);
		}
	}

	return ret;
}

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

	cin >> N >> M;

	while (M--) {
		int a, b;
		cin >> a >> b;
		adj[a][b] = 1;
	}

	int result = 0;
	for (int i = 1; i <= N; i++) {
		memset(visited, false, sizeof(visited));
		int visitCnt = dfs(i, DOWN) + dfs(i, UP) - 1;
		if (visitCnt == N)
			result++;
	}

	cout << result << endl;

	return 0;
}

[문제 링크]

dp의 메모이제이션 기법을 이용하는 전형적인 피보나치 수열 문제였다.

다만, n의 최대가 10000인데, 피보나치 수열은 갈수록 값이 어마어마하게 커지기 때문에 n의 값이 클경우 unsigned long long 자료형에도 담을 수 없을 정도로 커지게 된다.

따라서 숫자를 문자열로 표현한 다음, 두 문자열의 합을 구해주는 sum 함수를 구현하여 이와 같은 문제를 해결하였다.

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

string memo[10001];

string sum(string a, string b) {
	string result;
	int up = 0;

	// 자리수가 다를 경우 뒤에 있는 수가 반드시 자리수가 큼
	while (!b.empty()) {
		if (!a.empty()) {
			int num1 = a.back() - '0';
			int num2 = b.back() - '0';
			a.pop_back();
			b.pop_back();

			int sum = num1 + num2 + up;
			up = 0;

			if (sum >= 10) {
				up = 1;
				sum -= 10;
			}
			result.push_back(sum + '0');
		}
		else {
			int num = b.back() - '0';
			b.pop_back();

			int sum = num + up;
			up = 0;

			if (sum >= 10) {
				up = 1;
				sum -= 10;
			}
			result.push_back(sum + '0');
		}
	}
	if (up == 1)
		result.push_back('1');

	reverse(result.begin(), result.end());

	return result;
}

string bottomUp(int n)
{
	memo[0] = '0', memo[1] = '1';
	
	for (int i = 2; i <= n; i++) {
		memo[i] = sum(memo[i - 2], memo[i - 1]);
	}
	
	return memo[n];
}

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

	cout << bottomUp(n) << endl;
	
	return 0;
}

10000번째 피보나치 수열은 정말 어마어마한 숫자이다.....

[문제 링크]

간단한 bfs 문제였다.

문제에 주어진 3가지 방법을 각각 구현하여 이를 수행한 3가지 결과를 큐에 담아주도록 구현하였다.

방문 체크는 이모티콘의 개수 뿐만이 아니라 클립보드에 저장된 이모티콘의 개수에 따라서도 결과가 바뀔 수 있기 때문에 2차원 visited 배열을 선언하였다.

visited 배열 대신 memo 배열을 통해 메모이제이션 기법을 활용하여 풀이한 코드도 추가하였다.

// bfs

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

bool visited[2001][2001];

struct info {
	int cnt;
	int clipBoard;
	int time;
};

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

	while (!q.empty()) {
		int cnt = q.front().cnt;
		int clipBoard = q.front().clipBoard;
		int time = q.front().time;
		q.pop();

		if (cnt == S)
			return time;

		// case 1
		if (!visited[cnt][cnt]) {
			q.push({ cnt, cnt, time + 1 });
			visited[cnt][cnt] = true;
		}

		// case 2
		if (cnt+clipBoard < 2000 && !visited[cnt + clipBoard][clipBoard]) {
			q.push({ cnt + clipBoard, clipBoard, time + 1 });
			visited[cnt + clipBoard][clipBoard] = true;
		}

		// case 3
		if (cnt - 1 > 0 && !visited[cnt - 1][clipBoard]) {
			q.push({ cnt - 1, clipBoard, time + 1 });
			visited[cnt - 1][clipBoard] = true;
		}
	}

	return -1;
}
int main(void) {
	int S;
	cin >> S;

	cout << bfs(S) << endl;

	return 0;
}

// dp

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

int memo[2001][2001];
const int INF = 987654321;

int dp(int here, int clipBoard, int S) {
	if (here < 0 || here > S*2 || clipBoard > S*2) return INF;
	if (here == S) return 0;

	int& ret = memo[here][clipBoard];
	if (ret != 0) return ret;
	ret = INF;

	int case1 = dp(here, here, S) + 1;
	int case2 = dp(here - 1, clipBoard, S) + 1;
	int case3 = dp(here + clipBoard, clipBoard, S) + 1;

	ret = min(ret, min(case1, min(case2, case3)));
	return ret;
}

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

	cout << dp(1, 0, S) << endl;

	return 0;
}