[Algorithm] 22. 온도의 최대값

인트로

수열이 주어졌을 연속된 값의 합을 계산하고 최댓값만 출력하는 문제이다.

 

결론부터 말하면 O(N)으로 해결 가능한 문제를 O(N^2)으로 해결하려 했다.

개인적으로 어렵다고 느껴져서 기록을 남긴다. 

 

온도의 최댓값

문제

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.
예를 들어, 다음과 같이 10일간의 온도가 주어졌을 때, 3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이틀간의 온도의 합은 다음과 같다.

이때, 온도의 합이 가장 큰 값은 21이다. 매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

※ 입력설명
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다.

첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다.

두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다.

둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.

※ 출력설명
첫째 줄에는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

입력

10 2
3 -2 -4 -9 0 3 7 13 8 -3

출력

21

코드 : O(N^2)

코드 설명

문제를 읽고 나서 가장 먼저 든 생각은, 어쩌면 가장 쉽게 생각할 수 있는 방법일 텐데, 이중 for문으로 한 묶음씩 계산하는 방식을 택했다.

 

코드 효율은 그리 좋지 못하다.

이중 for문이라는 점과 n이 무수히 크고 k가 1에 가까울수록 시간 복잡도는 O(N^2)이나 다름없기 때문이다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, k, sum, max = -2000000;

	cin >> n >> k;

	vector<int> vec(n);

	for (int i = 0; i < n; i++)
		cin >> vec[i];

	for (int i = 0; i + k <= n; i++)
	{
		sum = 0;
		for (int j = i; j < i + k; j++)
		{
			sum += vec[j];
		}
		if (sum > max) max = sum;
	}

	cout << max;
}

코드 : O(N)

단일 for문으로도 문제를 해결할 수 있다.

0 ~ K까지 더한 값을 max와 sum으로 저장하고 vector를 하나씩 옮겨가며 범위에서 벗어난 값은 빼주고 새로 범위에 들어온 값은 더해주는 방식으로 동작하게 된다.

 

k == 2

k == 3

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, k, sum = 0, max;

	cin >> n >> k;

	vector<int> vec(n);

	for (int i = 0; i < n; i++)
		cin >> vec[i];

	for(int i = 0; i < k; i++)
		max = sum += vec[i];

	for (int i = k; i < n; i++)
	{
		sum += vec[i] - vec[i - k];
		if (sum > max) max = sum;
	}

	cout << max;
}