이것 저것 &

문제링크:https://www.acmicpc.net/problem/2140

전형적인 구현문제입니다. 

모서리의 숫자들이 주어질 때 해당 지뢰의 최대갯수를 찾는 문제였습니다.

생각해보면 최대개수이기때문에 지뢰가 있을 수 없는 장소들만 찾아주면 됩니다.

저는 #위치를 탐색하면서  주변(8방향)에 0이 포함되어있으면 해당 #은 지뢰가 없다고 표시해주는 방법으로 해결하였습니다. 

그리고 0이 없다면 해당 위치는 지뢰가 있는것이고 주변(8방향)값들은 값을 1씩 낮춰줌으로써 구현하였습니다.

#include <iostream>
#include <string>
using namespace std;
int n = 0, result = 0;
string arr[101];
int y_ar[8] = {-1,-1,0,1,1,1,0,-1};
int x_ar[8] = {0,1,1,1,0,-1,-1,-1};


// 규칙을 보다보면 8방향에 0이 있는 경우에만 폭탄이 없고 나머지는 폭탄이 있다고 가정
int main() {
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for (int i = 1; i < n - 1; i++)
		for (int j = 1; j < n - 1; j++) {
			bool jud = true;
			for (int u = 0; u < 8; u++) {
				int y = i + y_ar[u];
				int x = j + x_ar[u];
				
				if (arr[y][x] == '0') {
					arr[i][j] = ' ';
					jud = false;
				}
			}
			if (jud == true) {
				for (int u = 0; u < 8; u++) {
					int y = i + y_ar[u];
					int x = j + x_ar[u];

					if ('0' < arr[y][x] &&  arr[y][x] <= '3') {
						arr[y][x] -= 1;
					}
				}
			}

		}
			
	for (int i = 1; i < n - 1; i++)
		for (int j = 1; j < n - 1; j++)
			if (arr[i][j] == '#') result++;
	
	cout << result << endl;

	return 0;
}

문제링크:https://www.acmicpc.net/problem/5582

공통 부분 문자열을 찾는 문제입니다. n의 범위가 4000까지입니다.

일반적인 구현방법을 생각해볼때 O(n^3)이 됩니다. 이때 최악의 경우 64,000,000,000 번 반복되기에 당연히 시간초과입니다.

n^2 번의 계산법을 찾아야합니다. 

저는 표를 만들어 보며 규칙을 찾았습니다. 

보이시나요? 이전 배열값에서 1을 더한 값이 자신의 최대연속배열값입니다.

점화식은 dp[i][j] = dp[i - 1][j - 1] + 1 입니다. 

정답코드입니다.

#include <iostream>
#include <string>
using namespace std;
string arr;
string arr2;
int dp[4001][4001] = { 0 };
int result = 0;
int main() {
	cin >> arr;
	cin >> arr2;

	for (int j = 0; j < arr2.size(); j++) {
		if (arr[0] == arr2[j]) {
			dp[0][j] = 1;
			if (result < dp[0][j]) result = dp[0][j];
		}
	}

	for (int j = 0; j < arr2.size(); j++) {
		if (arr[j] == arr2[0]) {
			dp[j][0] = 1;
			if (result < dp[j][0]) result = dp[j][0];
		}	
	}


	for (int i = 1; i < arr.size(); i++) {
		for (int j = 1; j < arr2.size(); j++) {
			if (arr[i] == arr2[j]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				if (result < dp[i][j]) result = dp[i][j];
			}
		}
	}
	cout << result << endl;

}

문제링크: https://www.acmicpc.net/problem/1493

정렬을 하고 최선의 선택을 함으로써 결과를 도출하는 그리디 문제입니다.

처음에는 부피로 접근하여 문제를 해결하려고 했지만, 부피가 크다고 해당 범위를 채울 수 없는 것을 깨닭았습니다.

왜냐하면 한번 채운 상태인 부피의 모양이 사각형모양이 아닐 수 있기 때문입니다. 

문제해결하기위해서는 

분할정복 개념에 대해서 아셔야합니다.

저는 가장큰 박스로 채우고 나머지 부분을 재귀호출을 통해서 결과를 얻게끔 하였습니다. 

코드를 이해하시고 꼭 직접 작성해보세요.

정답코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
struct var{
	int a;
	int b;
};
bool cmp(var t1, var t2) {
	if (t1.a > t2.a) return true;
	return false;
}
int l, w, h, n;
int result = 0;
var arr[20];
bool jud = true;
void solved(int ll, int ww, int hh) {
	if (jud == false) return;
	if (ll == 0 || ww == 0 || hh == 0) return;

	for (int i = 0; i < n; i++) {
		if (ll >= arr[i].a && ww >= arr[i].a && hh >= arr[i].a && arr[i].b > 0) {
			arr[i].b--;
			result++;
			solved(ll, ww, hh - arr[i].a);
			solved(arr[i].a, ww - arr[i].a, arr[i].a);
			solved(ll - arr[i].a, ww , arr[i].a);
			return;
		}
	}

	jud = false;
}


int main() {
	cin >> l >> w >> h;
	cin >> n;
	int temp1, temp2;
	for (int i = 0; i < n; i++) {
		cin >> temp1 >> arr[i].b;
		arr[i].a = pow(2,temp1);
	}
	sort(arr, arr + n, cmp); // 내림차순 정렬

	solved(l, w, h);

	if (jud == false)
		cout << -1 << endl;
	else
		cout << result << endl;
}

문제링크:https://www.acmicpc.net/problem/6416

1. 들어오는 간선이 하나도 없는 단 하나의 노드가 존재한다. 이를 루트(root) 노드라고 부른다.
2. 루트 노드를 제외한 모든 노드는 반드시 단 하나의 들어오는 간선이 존재한다.
3. 루트에서 다른 노드로 가는 경로는 반드시 가능하며, 유일하다. 이는 루트를 제외한 모든 노드에 성립해야 한다.

3가지조건을 만족해야합니다.

그리고 수의 범위가 주어지지 않았기 때문에 배열의 크기를 정해놓는 것은 안됩니다.

위의 조건들에 대해서 곰곰히 생각하다 보면 집합에 대해서 생각하실 수 있습니다. 

위 조건들을 만족시키위해서 노드 집합의 개수 s + 1 과  입력받은 횟수가 같아야 한다는 것을 알 수있습니다. 

정답코드입니다.

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

int a, b;
int u = 0;
set <int> arr;

int main() {
	
	while (1) {
		u++;
		arr.clear();
		int sum = 0;
		bool jud2 = true;
		for (int k = 0;; k++) {
			
			cin >> a >> b;
			if (k == 0) {
				if (a == -1 && b == -1)
					return 0;
				else if (a == 0 && b == 0) {
					cout << "Case " << u << " is a tree." << '\n';
					jud2 = false;
					break;
				}
			}
			if (a == 0 && b == 0)
				break;
			arr.insert(a);
			arr.insert(b);
			sum++;

		}
		if (jud2 == true) {
			if (sum + 1 == arr.size())
				cout << "Case " << u << " is a tree." << '\n';
			else
				cout << "Case " << u << " is not a tree." << '\n';
		}
	}

	return 0;
}

문제링크:https://www.acmicpc.net/problem/5557

dp문제입니다.

수의 범위가 0~20까지 밖에 되지않고 값이 2^63-1 이라고 명시해주었기 때문에 dp로 풀 수 있는 문제였습니다. 

• 초기값으로 배열에 처음 값을 넣어줍니다.
• 이전배열에서 이전배열값들에서 현재값을 더하거나 빼서 얻을 수 있는 값들을 현재배열에 저장합니다.
• 이 과정을 반복한후 마지막값의 인덱스의 현재배열값을 출력합니다. 

정답코드입니다.

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

int n = 0, val = 0;
int arr[100] = { 0 };
long long before[21] = { 0 };
long long current[21] = { 0 };

int main() {
	cin >> n;
	for (int i = 0; i < n-1; i++) {
		cin >> arr[i];
	}
	cin >> val;

	before[arr[0]] = 1; //초기값 지정
	for (int i = 1; i < n - 1; i++) {
		memset(current, 0, sizeof(current));
		for (int j = 0; j <= 20; j++) {
			if (before[j] != 0){
				if ((j + arr[i]) <= 20)
					current[(j + arr[i])] += before[j];
				if((j - arr[i]) >= 0)
					current[(j - arr[i])] += before[j];
			}
		}
		for (int j = 0; j <= 20; j++)
			before[j] = current[j];

	}

	cout << current[val] << '\n';
}

문제링크:https://www.acmicpc.net/source/10245386

스택을 이용한 구현문제였습니다. 

예외처리때문에 애먹은 문제입니다.

우선 올바른 괄호열인지 구분하기 위해서 스택을 사용합니다.

스택을 사용하여 올바른 괄호열인지 구분하는 것은 쉽게 하실거라고 생각합니다. 

문제는 괄호의 점수계산입니다.

이러한 조건을 가지고 있습니다.

각각의 괄호안에 들어갈 때 값이 커집니다. 

2(2+(3x3)) +2(3) 입니다. 즉 2X2 + 2X3X3 + 2X3 =28 입니다.

• 문자열을 검사하며 '(' 라면 스택에 넣습니다. TEMP 값에 2를 곱합니다. 
• 문자열을 검사하며 '[' 라면 스택에 넣습니다. TEMP 값에 3을 곱합니다. 
• 문자열을 검사하며 ')' 라면 스택을 확인해 값을 연산이 되는 확인합니다.
• 연산이 된다면 값을 RESULT에 추가하고 스택을 POP하며 TEMP값도 나누기 2 합니다. 
• ']' 도 마찬가지의 방식입니다.

만약 스택에 값이 남아있다면 올바르게 괄호 검사 상태가 아니기 때문에 0을 출력합니다. 

정답코드입니다. 다양한 예외사항이 있었습니다. 

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

string input;
deque <char> arr;
int temp = 1;
int result = 0;
int main() {

	cin >> input;

	for (int i = 0; i < input.size(); i++) {
		if (input[i] == '(') {
			arr.push_back('(');
			temp *= 2;
		}
		else if (input[i] == '[') {
			arr.push_back('[');
			temp *= 3;
		}
		else if (input[i] == ')' && i>0) {
			if (input[i - 1] == '(') {
				arr.pop_back();
				result += temp;
				temp /= 2;			
			}
			
			else if (arr.empty() != 1){
				if (arr.back() == '(') {
					arr.pop_back();
					temp /= 2;
				}
			}
			else{
				cout << 0 << '\n';
				return 0;
			}

		}
		else if (input[i] == ']' && i > 0 ) {
			if (input[i - 1] == '[') {
				arr.pop_back();
				result += temp;
				temp /= 3;
			}
			else if (arr.empty() != 1) {
				if (arr.back() == '[') {
				arr.pop_back();
				temp /= 3;
				}
			}
			else {
				cout << 0 << '\n';
				return 0;
			}
		}

		
		
	}

	if(arr.empty()!= 1)
		cout << 0 << '\n';
	else
		cout << result << endl;
	return 0;
}

문제링크:https://www.acmicpc.net/problem/2194

bfs를 사용하는 문제였습니다.

하지만 기존 탐색과는 다르게 탐색하는 유닛의 크기가 1X1이 아닌 값이기 때문에 

이동하면서 숫자 넘어가는 숫자들의 범위나 이동할 수 있는지 여부를 반복문을 통해서 판별해야하기 때문에 구현문제로 분류하였습니다.

• 값 입력
• 상하좌우로 움직기
• 이동할때 모든 값이 배열을 벗어나는지 장애물이 있는지 확인하기
• 이동가능할 경우 visited에 표시하기
• 값 출력

정답코드입니다.

#include <iostream>
#include <queue>
using namespace std;
int arr[501][501] = { 0 };
int visited[501][501] = { 0 };
int n = 0, m = 0, a = 0, b = 0, k = 0;
int start_y, start_x, destination_y, destination_x;

int x_ar[4] = { 0,0,1,-1 };
int y_ar[4] = { 1,-1,0,0 };

void bfs() {
	queue<int> que[2];
	que[0].push(start_y);
	que[1].push(start_x);
	visited[start_y][start_x] = 1;
	while (!que[0].empty()) {
		int yy = que[0].front();
		int xx = que[1].front();
		que[0].pop(), que[1].pop();

		
		for (int k = 0; k < 4; k++) {
			bool jud = true;
			for (int i = 0; i < a; i++) {
				for (int j = 0; j < b; j++) {
					int y = i + yy + y_ar[k];
					int x = j + xx + x_ar[k];
					if (y >= 1 && y <= n&&x >= 1 && x <= m) {
						if (arr[y][x] == 1) {
							jud = false;
							break;
						}
					}
					else { //해당공간에서 벗어나니까 
						jud = false;
						break;
					}
				}
				if (jud == false)
					break;
			}
			if (jud == true && visited [yy+y_ar[k]][xx+x_ar[k]] == 0) {
				visited[yy + y_ar[k]][xx + x_ar[k]] = visited[yy][xx] + 1;
				que[0].push(yy + y_ar[k]);
				que[1].push(xx + x_ar[k]);
			}
		}
		
	}
}

int main() {
	cin >> n >> m >> a >> b >> k;
	int num_a = 0, num_b = 0;
	for (int i = 0; i < k; i++) {
		cin >> num_a >> num_b;
		arr[num_a][num_b] = 1;
	}
	cin >> start_y >> start_x >> destination_y >> destination_x;

	bfs();

	cout << visited[destination_y][destination_x] - 1 << '\n';
}

문제링크:https://www.acmicpc.net/problem/1756

구현문제로 분류되지만 그리디 알고리즘이라고도 생각할 수 있는 문제였습니다.

흔하게 생각하는 방법으로 구현하게 되면 

O(n*d) 의 시간복잡도가 걸리는 이준 포문을 구현할 수 있습니다.

하지만 해당 방법은 시간초과입니다. 

n,d 둘다 300000까지이기 때문입니다. 

그렇기 때문에 nlgn, n, d 만큼 걸리는 방법을 고안해야합니다.

n입장에서볼때 d배열에서 자신보다 작은위치 아래로는 들어갈 수 없습니다. 

즉, n => 3 2 5일 때 3은 d의 제일 아래인 3으로 갈 수 없습니다. 

그렇다면  5 6 4 3 6 2 3를 5 5 4 3 3 2 2 로 나타낼 수 있습니다. 어차피 작은 위치아래로는 내려갈 수 없기 때문이죠.

이렇게 배열을 바꾼 후에는 d 배열의 끝부터 n을 삽입할 수 있는지 순서대로 확인해주시면 됩니다. 

구현자체는 쉽고, 구현방법을 생각하는게 어려운 문제였습니다. 

정답코드입니다. 꼭 직접 작성해보세요! 화이팅 : ) 

#include <iostream>
using namespace std;
int d = 0, n = 0, result = 0;
int arr_d[300000] = { 0 };
int arr_n[300000] = { 0 };
int visited[300000] = { 0 };
int main() {
	cin >> d >> n;

	for (int i = 0; i < d; i++) {
		cin >> arr_d[i];
		if (i > 0 && arr_d[i - 1] < arr_d[i]) arr_d[i] = arr_d[i - 1];
	}
	for (int i = 0; i < n; i++)
		cin >> arr_n[i];



	int cnt = 0;
	for (int i = d - 1; i >= 0; i--) {
		if (arr_n[cnt] <= arr_d[i]) {
			visited[cnt] = 1 + i;
			cnt++;
		}
		if (cnt == n)
			break;
	}

	if (cnt == n)
		cout << visited[cnt - 1] << endl;
	else
		cout << 0 << endl;

	return 0;
}