기록을

문제 풀이 소요 시간을 획기적으로 감소시켜야 할 때 생각해 볼만한 것들

1. 정렬

2. modular 연산

3. 이분탐색

priority queue가 터져서 최근에 메모리 초과를 몇번 받았다.

C++ 기준

1. 배열의 크기를 벗어나서 index에 접근하는 경우

2. 전역 변수들의 메모리 크기 총합이 메모리 제한을 초과하는 경우

3. 지역 변수들을 메모리 크기 총합이 스택 메모리 제한을 초과하는 경우

4. 재귀 호출이 너무 깊어지는 경우

5. 0으로 나누는 경우

6. main 함수가 0이 아닌 다른 값을 반환하는 경우

#include<iostream>
#include<vector>
using namespace std;
int mem[100001];
int solution(vector<int> prices)
{
	int min = 1000001;
	for (int i = 0; i < prices.size(); i++) {
		if (prices[i] < min) {
			min = prices[i];
		}
		mem[i] = min;
	}
	int max = 0;
	for (int i = 0; i < prices.size(); i++) {
		if (prices[i] - mem[i] > max) {
			max = prices[i] - mem[i];
		}
	}
	return max;
}

prices 배열의 어떤 index까지의 최솟값을 mem 배열에 저장한다.

가령 prices = {1,5,2,6,2,4,0} 이런 상황이라면 mem = {1,1,1,1,1,1,0} 이렇게 되는 것이다.

최소의 가격일 때 구매해서 최대의 가격에 되팔아서 이윤의 최대치를 구하는 문제에 이용할 수 있다.

index가 시간을 의미한다고 볼 수 있다. 같은 index에서 prices와 mem의 차이가 가장 큰 지점이 정답이 된다.

최대 마진을 내야 하는 경우로 기억

가령 상황을 하나 혹은 두 개의 배열로 나타낼 수 있다고 하자.

배열이 하나라면, index 0부터 최댓값을 담는 배열을 만들고,

가장 끝 index부터 최댓값을 담는 배열을 만들고, 상황에 맞게 사용하는 것이다.

꼭 최댓값이 아니더라도, 한쪽에서는 최대, 다른 한쪽에서는 최소를 잡을 수도 있겠다.

이런 유사한 방식을 세번 이상 사용한 것 같다. 아마 다른 사람이 보면 이게 무슨 말인가 싶겠지만,

일단 내가 기억하고자 하는 목적으로 정리를 해두겠다.

#define ll long long
#include<iostream>
#include<vector>
using namespace std;

ll lmax[300001], rmin[300001];
int solution(vector<int> &T) {
	ll Max = T[0];
	for (int i = 0; i < T.size(); i++) {
		if (T[i] > Max)
			Max = T[i];
		lmax[i] = Max;
	}

	ll Min = T.at(T.size() - 1);
	for (int i = T.size() - 1; i >= 0; i--) {
		if (T[i] < Min)
			Min = T[i];
		rmin[i] = Min;
	}

	for (int i = 0; i < T.size() - 1; i++) {
		if (lmax[i] < rmin[i + 1]) {
			//len = i + 1;
			return i + 1;
		}
	}
}
int main(void) {
	vector<int> vec{ -5, -5, -5, -42, 6, 12 };
	solution(vec);
	return 0;
}

주어진 배열에서, 조건에 따라 부분 배열을 찾는 문제이다. vec 벡터를 두 개의 벡터로 나눌 것인데, 하나의 벡터의 모든 성분이 또 다른 벡터의 어떤 성분보다도 작도록 벡터를 양분하려고 할 때, 위와 같은 방법을 사용할 수 있다.