기록을

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

n이 10000 이하이고, 시간 제한이 0.5초이기 때문에, n^2 풀이로 풀게 되면 시간 초과가 날 것이다.

따라서 O(n)에 해결할 수 있도록 투포인터를 사용하도록 한다.

초기에 st와 en을 모두 시작점으로 정해두고, en이 범위 밖으로 벗어날 때까지 진행해준다.

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

총감독관은 무조건 1명은 존재해야 하기 때문에 기본적으로 답은 n부터 시작한다.

시험장마다의 인원보다 b가 크다면, 총감독관 혼자 커버할 수 있기 때문에 시험장 인원을 0으로 갱신해준다.

그렇지 않다면 시험장 인원에서 총감독관이 감시하고 있는 인원의 수인 b를 감소시켜준다.

다음으로 필요한 부감독관의 수를 계산한다. 1명이라도 부감독관이 감시할 수 있는 사람보다 수가 많으면 부감독관 한 명이 더 필요하기 때문에, 갱신한 시험장 인원을 c로 나눈 나머지가 0인지 아닌지에 따라서 부감독관의 인원을 정한다.

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

이차원 배열로 주어지는 격자에서, 모든 테트로미노 모양을 다 넣어보면 된다.

주어지는 다섯개의 테트로미노를 회전 또는 대칭해서 얻을 수 있는 모양들까지 포함해서 계산해주면 된다.

가능한 모양은 총 19개이다.

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

로봇의 위치와 방향을 관리하며 bfs를 돌려주면 된다. 모든 순간에 로봇은 하나이기 때문에 큐에는 최대 하나의 좌표(로봇의 좌표)만 들어갈 수 있다.

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

문자열을 무작위 재배열해서 반환하는 함수에 대한 문제이다.

두 문자열의 알파벳 성분이 일치하면 되기 때문에, 각 문자열을 이루는 알파벳의 개수를 파악해주면되겠다.

입력은 소문자로만 들어온다는 것을 확인하고, 각 문자열의 알파벳 개수를 파악해주자.

#include<string>
#include<iostream>
using namespace std;
int alpSrc[26], alpDes[26];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tc;
	cin >> tc;
	string src, des;
	bool res = true;
	while (tc--) {
		
		cin >> src >> des;
		for (int i = 0; i < src.length(); i++) {
			alpSrc[src[i] - 'a']++;
			alpDes[des[i] - 'a']++;
		}
		res = true;
		for (int i = 0; i < 26; i++) {
			if (alpSrc[i] != alpDes[i]) {
				res = false;
				break;
			}
		}
		if (res)
			cout << "Possible" << '\n';
		else
			cout << "Impossible" << '\n';

		for (int i = 0; i < 26; i++) {
			alpSrc[i] = 0;
			alpDes[i] = 0;
		}
	}
	return 0;

문제 링크이다.

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

풀면서 정답률이 이렇게 높게 나올 문제인가 하면서 자책했는데,

가장 긴 증가하는 부분 수열이라는 문제가 있어서 정답률이 상대적으로 높았던 것 같다.

(문제 풀이)

먼저 배열을 입력받고, 데이터들을 앞에 있는 모든 성분들과 비교해야 한다.

10 30 10 20 20 

위와 같이 배열이 주어졌다고 하면.

3번째 수인 10을 10과 30 모두와 비교하고, 20은 다시 처음부터 10, 30, 10 이런식으로 

이전에 나온 수들과 비교해야 한다.

즉 앞에서 해결한 문제가 뒤의 문제를 해결할 때 사용되기 때문에 dp라는 감을 잡고 접근하면 되겠다.

d[i]를 index i까지의 수를 활용해서 만들 수 있는 감소수열의 최대 길이라고 정한다.

확인하는 숫자가 이전 숫자보다 크다면 이전까지 나온 감소 수열의 길이에 영향을 미치지 않기 때문에 넘어가 주고, 

이전 숫자보다 작다면 처리를 해주면 된다.

길이의 최댓값을 찾고 있기 때문에, d[i]의 갱신도 최대 길이일때만 해주면 된다.

즉 위의 예시에서, 4번째 수인 20에 대한 처리를 한다고 해보자.

먼저 20은 10보다 크기 때문에 넘어간다.

이어서, 20은 30보다 작다 -> 30인 지점에서 감소 수열의 길이는 1이다. (엄밀히 말하면 0이라고 생각하지만 풀이의 간편성을 위해 1이라고 했다). 그렇다면 30까지의 수열과, 20이 연결되어서 수열의 길이는 1이 증가하게 되고, 수식으로 표현하면 d[20의 인덱스] = d[30의 인덱스] + 1 이다.

이것도 확정이 아니라, 만약 같은 방식으로 20보다 큰 30과 같은 수가 20의 이전에 여러개 나올 수 있는데,

d[20의 인덱스] = d[20보다 크고, 20보다 앞에 나온 수의 인덱스] + 1 이것들을 비교해서 최댓값을 d[20의 인덱스]로 결정해주면 된다.

#include<iostream>
using namespace std;
int d[1002];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	int arr[1002];
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	for (int i = 1; i <= n; i++) {
		int Max = 0;
		for (int j = 0; j < i; j++) {
			if (arr[i] < arr[j]) {
				//작은 인덱스의 값보다 더 작은 값이 들어오면
				if (d[j] > Max) {
					Max = d[j];
				}
			}
		}
		d[i] = Max + 1;
	}
	
	int Max = 0;
	for (int i = 1; i <= n; i++) {
		if (Max < d[i]) {
			Max = d[i];
		}
	}
	cout << Max << '\n';
	
	return 0;
}

문제 링크는 다음과 같다.

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

위와 같은 예시를 보면, 쉽게 이차원 배열을 사용해야겠다는 생각을 떠올릴 수 있다.

특정 학년의 특정 성별을 가지는 학생의 수를 그대로 배열에 저장해준다.

k보다 인원이 작으면 방은 1개만 있으면 되고, 그 이상일 경우 k로 나눈 몫 + 1개만큼 방이 필요하다.

#include<iostream>
using namespace std;

int arr[2][7];

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

	int n, k;
	cin >> n >> k;

	int s, y;
	while (n--) { //n명의 정보를 2차원 배열에 저장
		cin >> s >> y;
		arr[s][y]++;
	}

	int room = 0;

	for (int i = 0; i < 2; i++) {
		for (int j = 1; j <= 6; j++) {
			if (!arr[i][j]) //특정 학년과 성별의 학생수가 0이면 continue
				continue;
			
			if (arr[i][j] < k) // k보다 작으므로 방은 하나만 있으면 됨
				room++;
			else { //k보다 크거나 같을 때
				if (arr[i][j] % k == 0) {
					//k로 나눠 떨어질 때
					room = room + arr[i][j] / k;
				}
				else {
					room = room + arr[i][j] / k + 1;
				}
			}
		}
	}

	cout << room << '\n';

	return 0;
}

문제링크

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

순서를 섞었을 때 문자열이 같아질 수 있느냐를 물어보는 문제였다.

단순히 문자열에서, 각 알파벳의 개수를 파악해주고 비교해주면 된다.

#include<iostream>
#include<string>
#include<math.h>
using namespace std;

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

	string org, cpr;
	int orga[26] = { 0, }, cpra[26] = { 0, };

	cin >> org >> cpr;

	for (int i = 0; i < org.length(); i++) {
		orga[org[i] - 'a']++;
	}
	for (int i = 0; i < cpr.length(); i++) {
		cpra[cpr[i] - 'a']++;
	}

	int cnt = 0;
	
	for (int i = 0; i < 26; i++) {
		cnt = cnt + abs(orga[i] - cpra[i]);
	}
	cout << cnt << '\n';

	return 0;
}
/*
strfry와 같은 원리. 단어에 쓰인 알파벳별 개수를 파악해서 비교.
입력 문자열의 길이가 다른 경우도 생각해줘야함
*/

문제링크

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

설명은 코드의 주석으로 대체하겠다.

#include<iostream>
#include<string>
using namespace std;
int A, B, C, arr[10];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> A >> B >> C;
	long long res = A * B*C;	
	string str = to_string(res);
	for (int i = 0; i < str.length(); i++) {
		arr[str[i] - '0']++;
	}
	for (int i = 0; i < 10; i++) {
		cout << arr[i] << '\n';
	}
	return 0;
}
/*
각 자리수의 숫자를 확인하기 위해 계산 결과를 long long에서 string 으로 변환
string으로 변환된 값의 각 자리수인 char에서 int로 변환을 -'0'을 활용
*/