기록을

https://programmers.co.kr/learn/courses/30/lessons/17680

현재 캐시의 크기와, 사용 빈도에 관련된 정보를 배열을 활용해서 계속 검사해주며 miss와 hit 여부를 판단해주면 된다.

주의할 것은, 대소문자에 상관없이 비교를 하기 때문에 (Seoul과 seoul이 둘 다 입력으로 들어올 수 있는데, 같다고 판단해야 함) 이 부분을 잘 확인하면 된다.

어떤 문자열을 소문자로 변환하는 경우, algorithm 헤더에 있는 transform 함수를 이용한다.

파라미터는 transform(변환할 문자열의 시작주소, 변환할 문자열의 끝주소, 변환 결과를 저장할 문자열의 시작주소, ::변환방식)이다.

transform(ct[i].begin(), ct[i].end(), ct[i].begin(), ::tolower);

이런식으로 사용해준다.

1. std::transform을 쓰는 방법

#include <algorithm>
#include <string>

std::string str = "Hello World";
std::transform(str.begin(), str.end(),str.begin(), ::toupper);

범위에 있는 모든 원소에 대해 function을 수행한 결과를 다른 범위에 저장

toupper 혹은 tolower 앞에 :: 꼭 붙어야한다.

원형은

template< class InputIt, class OutputIt, class UnaryOperation >
OutputIt transform( InputIt first1, InputIt last1, OutputIt d_first,
                    UnaryOperation unary_op );

//또는

template< class InputIt1, class InputIt2, class OutputIt, class BinaryOperation >
OutputIt transform( InputIt1 first1, InputIt1 last1, InputIt2 first2, 
                    OutputIt d_first, BinaryOperation binary_op );

파라미터

• first1, last1 : transform 할 첫 번째 원소
• first2 : transform 할 2번째 범위의 첫 번째 원소
• d_first : transform 결과를 저장할 범위의 첫 번째 위치
• unary_op : 객체를 바꾸는 unary 함수
• bianry_op : 객체를 바꾸는 binary함수

https://programmers.co.kr/learn/courses/30/lessons/17682

문자열에서 숫자를 골라내야 하는데, 이 때 10이 포함된 경우를 잘 확인해주면 된다.

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;
}