개발일지

문제설명 입출력 예제 개념 먼저 예제 1에 대해 스택 수열이 어떻게 형성되는지 그림으로 확인해 보자. 그림에서 알 수 있듯이, 입력받은 수 n이 기존의 max보다 크다면 max + 1부터 n까지 스택에 수를 푸시한다. 그렇지 않다면, 입력받은 수가 스택에서 뽑을 때까지 pop을 해주면 된다. 반대로 스택 수열을 형성할 수 없는 경우인 예제 2를 보자. 3을 입력받는 순간 3을 뽑기 위해서 4를 뽑아야 하는데, 4를 빼면 주어진 수열을 만들 수 없으므로 에러가 뜬다. 즉, 입력받은 수가 num보다 작거나 같은데, 그 수가 스택의 top과 다르다면 주어진 수열을 만들 수 없다. 풀이 #include #include #include using namespace std; int main() { ios::sync..

문제설명 입출력 예제 개념 특정 구간까지의 수열의 합을 구하는 문제다. 단순히 반복문을 중첩시켜 결괏값을 얻으려 하면 십중팔구 시간초과에 걸린다. 이러한 문제처럼 연속된 값을 더하는 문제를 풀 땐 구간합 개념을 이용하면 쉽게 해결할 수 있다. 구간합(Prefix Sum) - 수열에서 특정 구간의 합 풀이 #include using namespace std; int N, K, temp, sum[100001], ret = -2147483647; int main() { cin >> N >> K; 온도를 측정한 전체 날짜의 수 N, 합을 구하기 위한 연속적인 날짜의 수 K, 구간합을 구할 배열 sum, 구간합 배열의 최솟값 변수 ret을 초기화한다. 이때 ret의 값은 int의 최솟값이다. for (int i ..