뚝딱뚝딱

https://www.acmicpc.net/problem/1541

💡 잃어버린 괄호

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

[입력]
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

[출력]
첫째 줄에 정답을 출력한다.

✅ 문제 풀이

• 주어지는 수식에서 부호는 + 또는 - 밖에 주어지지 않는다.
• 따라서 -부호 뒤에 오는 수식은 다음 - 부호가 오기 전까지는 괄호로 묶어 전체를 -값으로 계산할 수 있다.
  이때의 값이 이 수식의 최소값이 될 것이다.
• 그럼 주어지는 수식에서 첫번째로 주어지는 -부호 이후에 오는 숫자들은 모두 -가 붙어서 계산된다고 생각할 수 있다.
• 따라서 첫번째 -부호가 부호들 중에서 몇번째로 등장하는지 카운트 해 줄것이다.
• 그리고 부호가 아닌 문자열은 숫자로 판단하여, temp라는 저장소에 계속해서 업데이트 하며 값을 계산할 것이고, 부호가 등장했을 때는 숫자값을 넣어두는 벡터에 temp값을 넣고, temp는 다시 0으로 초기화 해줄것이다.
• 이렇게 되면 마지막 숫자에 대해서는 부호로 끝나지 않기때문에, temp에 저장된 숫자 값이 벡터에 들어가지 않고 끝나기 때문에, 마지막에는 벡터에 temp값을 한번 더 추가해준다.
• 위의 과정은 입력으로 받는 문자열을 하나씩 탐색해가면서 판단하는 것이다.
• 문자열을 모두 순회한 뒤에는, 숫자가 담긴 벡터 arr와, 첫번째 -부호의 위치를 갖는 cnt가 결정되게 된다.
• 따라서 arr의 크기만큼 순회하면서, 현재 arr의 인덱스가 cnt이하이면 각각을 sum에 더하고, cnt를 초과하면서부터는 sum에서 빼는 방식으로 계산해주면 된다.
• 그럼 최종 최소값이 sum에 저장되고, 출력하면 된다.

#include<iostream>
#include<vector>
#include<string>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string str;
	cin >> str;

	int temp = 0;
	int res = 0;
	//한번 마이너스가 발생하고 나면 그 뒤로는 +에 대해서는 다 -로 묶을수 있으니까 마이너스 발생 후에는 모두 -로 계산

	vector<int> arr;
	int cnt = 0;
	int cntbreak = false;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] != '+'&&str[i] != '-') {//숫자이면
			temp *= 10;
			temp += str[i] - '0';
		}
		else {
			arr.push_back(temp);
			temp = 0;

			if (!cntbreak&&str[i] == '+') cnt++;
			else if (str[i] == '-') cntbreak = true;
		}
	}

	arr.push_back(temp);

	for (int i = 0; i < arr.size(); i++) {
		if (i <= cnt) {
			res += arr[i];
		}
		else {
			res -= arr[i];
		}
	}

	cout << res;

	return 0;
}

💡 printf문에서 소수점 이하 n째자리수 까지 출력하는 방법

float grade, sum;
//grade, sum 초기화

printf("%.6lf", grade / sum);
//grade/sum을 소수점 이하 6자리까지 출력한다
//이때 lf로 쓴다

• 여기서 %lf는 double 형식의 변수를 출력하라는 의미이다.

https://www.acmicpc.net/problem/1388

💡 바닥 장식

형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다.이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다.기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.

[입력]
첫째 줄에 방 바닥의 세로 크기N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 문자가 주어진다. 이것은 바닥 장식 모양이고, '-‘와 ’|‘로만 이루어져 있다. N과 M은 50 이하인 자연수이다.

[출력]
첫째 줄에 문제의 정답을 출력한다.

✅ 문제 풀이

• 문제에서 주어진 조건을 고려하기만 하면 쉽게 풀리는 문제이다.
• 같은 행에서 -가 반복된다면 같은 판자인것이고, 같은 열에서 |가 반복된다면 같은 판자인 것이다.
• 먼저 크기가 N*M인 배열에 -와 |를 입력 받고, N*M만큼 순회한다.
• i는 행의 번호, j는 열의 번호인데, 행을 순회할 때마다 첫번째 값을 일단 row라는 변수에 저장해 두고, 이 값을 비교하면서 몇개의 나무 판자가 필요한지 카운트 할 것이다. 이때 각 행의 첫번째 요소는 비교 기준이 되므로 일단 count를 하나 올리고 시작한다.
• 일단 현재의 row가 -인지 |인지 상관없이, 동일한 행안의 요소들을 비교하면서 현재 row와 현재 순회한 값 arr[i][j]가 다르다면 count해준다.
• 그런다음, 두번째 줄 행부터 앞에 행의 동일한 열에 있는 값과 현재 값을 비교해서, 동일하면서 |이면 count를 하나 빼준다.
• 그러면 -로는 연속한 것끼리 하나의 판자로, |로 연속한 것끼리 하나의 판자로 계산되어 최종 필요한 판자의 개수를 구할 수 있게 된다. 

✏ 코드 전문

#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	vector<vector<char>> arr(N);

	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;

		for (int j = 0; j < str.length(); j++) {
			arr[i].push_back(str[j]);
		}
	}

	int count = 0;

	for (int i = 0; i < N; i++) {
		char row = arr[i][0];
		count++;

		if (i > 0 && row == '|'&&row == arr[i - 1][0]) count--;

		for (int j = 1; j < M; j++) {
			if (row != arr[i][j]||(row==arr[i][j] && row=='|')) {
				count++;
				row = arr[i][j];
			}
			if (i > 0 && arr[i][j] == '|'&&arr[i][j] == arr[i - 1][j]) count--;
		}
	}

	cout << count;

	return 0;
}

https://www.acmicpc.net/problem/1759

💡 암호 만들기

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

[입력]
첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

[출력]
각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

✅ 문제 풀이

• vector에 C개의 문자를 입력 받은 후, 알파벳 순으로 정렬해준다.
• des함수는 C개의 각 문자를 포함하는 경우와 포함하지 않는 경우로 재귀 호출된다.
• 처음에는 빈 문자열로 시작했다가, C개의 문자를 차례로 방문하면서 붙이거나, 붙이지 않도록 한다.
• 그래서 붙인 문자열이 L개가 되면 res 벡터에 문자열을 넣어두고, des함수를 멈춘다.
• 그렇지 않다면 des함수를 호출해 붙일 문자를 붙여 넘긴 것과, 붙이지 않고 넘긴 것으로 두번 호출한다. 그리고 현재 가리키는 문자를 cnt로 정의하여 +1해준 값을 넘겨준다.
• 그리고 des함수가 종료되고 나면, res에 있는 크기가 L인 문자열들을 걸러내야 한다. 문제에서 주어진 빨간 색 조건에 맞도록 한다.
• 즉 모음이 1개 이상이고, 자음이 2개 이상인지 확인 한다.
• res 벡터를 순회하면서 각 문자열에 모음과 자음을 count한다. 모음이 1개 이상이고 자음이 2개 이상이면 화면에 출력하도록 하고, 그렇지 않으면 출력하지 않는다.

✏ 코드 전문

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int L, C;
vector<string> res;
void des(vector<string> alp, string sum, int cnt) {
	if (sum.length() == L) {
		res.push_back(sum);
		return;
	}
	if (cnt < C) {
		des(alp, sum + alp[cnt], cnt + 1);
		des(alp, sum, cnt + 1);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> L >> C;

	vector<string> alp;
	for (int i = 0; i < C; i++) {
		string ch;
		cin >> ch;
		alp.push_back(ch);
	}

	sort(alp.begin(), alp.end());

	des(alp, "", 0);
	
	
	for (int i = 0; i < res.size(); i++) {
		int moem=0;
		int jaem = 0;
		for (int j = 0; j < res[i].length(); j++) {
			if (res[i][j] == 'a' || res[i][j] == 'e' || res[i][j] == 'i' || res[i][j] == 'o' || res[i][j] == 'u') moem++;
			else jaem++;

			if (moem >= 1 && jaem >= 2) {
				cout << res[i] << "\n";
				break;
			}
		}
	}

	return 0;
}

https://www.acmicpc.net/problem/1260

💡 DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

[입력]
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

[출력]
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

✅ 문제 풀이

• DFS와 BFS의 로직을 나누어서 두번의 결과를 따로 구하고 출력하도록 하였다.
• 일단 입력으로 받은 간선의 정보를 2차원 벡터에 저장하였다.
  이때 양방향 간선이라는 점을 고려하여, A->B로 B->A로의 간선 정보를 저장해준다.
• S노드에서 시작하므로, S번의 visited를 true로 설정하고 시작한다.
• 간선 정보를 담은 arr배열을, 각 노드에 대해서 오름차순 정렬해준다. 노드 번호가 낮은 것부터 방문해야 하기 때문이다.
• dfs함수는, arr배열의 s번 vector를 탐색하는데, 먼저 방문하는 노드를 시작으로 또 dfs를 재귀호출하며 방문하도록 한다. 
• bfs함수는, arr배열의 s번 vector를 탐색하는데, 각 노드를 탐색할 때마다 queue에 담아주고, 해당 벡터를 다 탐색하고 나서는 queue의 front부터 탐색하며 bfs를 재귀호출하도록 한다.
• 각각의 결과는 dfs_result, bfs_result에 담은 후 출력한다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

void dfs(int s, vector<vector<int>> arr, vector<bool> &visited, vector<int> &dfs_result) {
	for (int i = 0; i < arr[s].size(); i++) {
		if (!visited[arr[s][i]]) {
			visited[arr[s][i]] = true;//방문
			dfs_result.push_back(arr[s][i]);
			dfs(arr[s][i], arr, visited, dfs_result);
		}
	}
}
void bfs(int S, vector<vector<int>> arr, vector<bool> &visited, vector<int> &bfs_result, queue<int> &q) {
	for (int i = 0; i < arr[S].size(); i++) {
		if (!visited[arr[S][i]]) {
			visited[arr[S][i]] = true;//방문
			q.push(arr[S][i]);
			bfs_result.push_back(arr[S][i]);
		}
	}
	while (!q.empty()) {
		int next = q.front();
		q.pop();
		bfs(next, arr, visited, bfs_result, q);
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, S;
	cin >> N >> M >> S;

	vector<vector<int>> arr(N+1);
	vector<bool> visited1(N + 1, false);//dfs에서사용
	vector<bool> visited2(N + 1, false);//bfs에서사용
	queue<int> q;//bfs에서 사용
	vector<int> dfs_result;
	vector<int> bfs_result;
	for (int i = 0; i < M; i++) {//간선 정보 입력받기
		int n1, n2;
		cin >> n1 >> n2;

		arr[n1].push_back(n2);
		arr[n2].push_back(n1);
	}

	for (int i = 1; i < N + 1; i++) {//노드별로 간선 정보를 오름차순 정렬
		sort(arr[i].begin(), arr[i].end());
	}


	visited1[S] = true;
	visited2[S] = true;
	dfs_result.push_back(S);
	bfs_result.push_back(S);

	dfs(S, arr, visited1, dfs_result);
	bfs(S, arr, visited2, bfs_result, q);

	for (int i = 0; i < dfs_result.size(); i++) {
		cout << dfs_result[i]<<" ";
	}
	cout << "\n";
	for (int i = 0; i < bfs_result.size(); i++) {
		cout << bfs_result[i] << " ";
	}
	
	return 0;
}

https://www.acmicpc.net/problem/1026

💡 보물

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.
길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.
S = A[0] × B[0] + ... + A[N-1] × B[N-1]
S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.
S의 최솟값을 출력하는 프로그램을 작성하시오.

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

첫째 줄에 S의 최솟값을 출력한다.

✅ 문제 풀이

크기가 각각 N인 A와 B배열을 입력받은 뒤, B는 그대로 두고, A만 재정렬 하여 A와 B의 원소를 각각 곱해서 최소의 값이 되도록 하는것이다.

여기서 구하고자 하는 것은 그때의 최소값이다.

따라서 A와 B가 어떻게 정렬이 되어 있던 간에, 결국 최소 값을 구하기 위해서는 한쪽은 가장 큰 값, 다른 한쪽은 가장 작은 값을 곱한 것이 최소가 된다.

따라서 A를 오름차순 정렬하고, B를 내림차순 정렬한 후에 각각의 원소끼리 차례로 곱한 값들을 더해주면 최소값이 나오게 된다.

B는 그대로 두되, A를 "재정렬" 하라는 말에 너무 초점을 맞추게 되면, 생각이 많아질 수 있으나, 목적인 최소값을 생각하면 쉽게 해결하는 문제이다.

☑ 코드 전문

#include<iostream>
#include<algorithm>

using namespace std;

bool compare(int a, int b) {
	return a > b;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	int *A = new int[N];
	int *B = new int[N];
	
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}

	sort(A, A + N);//오름차순
	sort(B, B + N, compare);//내림차순

	int answer = 0;
	for (int i = 0; i < N; i++) {
		answer += A[i] * B[i];
	}
	
	cout << answer;

	return 0;

}