22. 온도의 최댓값 (1차원 배열 구간합 : 제한시간 1초)

이 문제의 저작권은 인프런 강의 "it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비" 에 있습니다.

 

 

 

 

문제 22

 

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

 

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

 

 

 

입력예제

 

>> 10 2

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

 

 

출력예제

 

>> 21

 

 

 

 

---

* 새로 학습한 내용 - 벡터

 

vector 컨테이너는 자동으로 메모리가 할당되는 배열이다.

이 아이는 자료구조 스택이랑 비슷한 느낌! (맨 뒤쪽에서 삽입 push_back(), 삭제 pop_back()이 가능하다)

vector를 사용하기 위해서 헤더에 include<vector>를 추가해줘야 한다.

 

vector의 선언 : vector<[data type]> [변수이름] 이다.
ex) vector<int> v;

 

<vector의 생성자와 연산자>

• vector<int> v;
  - 비어있는 vector v를 생성합니다.
  
  
• vector<int> v(5);
  - 기본값(0)으로 초기화 된 5개의 원소를 가지는 vector v를 생성합니다.
  
  
• vector<int> v(5, 2);
  - 2로 초기화된 5개의 원소를 가지는 vector v를 생성합니다.
  
  
• vector<int> v1(5, 2);
  vector<int> v2(v1);
  - v2는 v1 vector를 복사해서 생성됩니다.

• vector<int> v1; , vector<int> v2;  가 있고, 내부에 인자들이 있다고 했을때.
  
  연산자 : "==", "!=", "<", ">", "<=", ">=" 로 대소비교 가 가능합니다.

출처: https://blockdmask.tistory.com/70 [개발자 지망생]

---

+ )

이 문제에서는 바깥에서 char a[100001]을 선언하는 것이 아닌 벡터를 사용해주는데, 그 이유는 바깥에서 배열을 선언하면 2자릿수인 배열도 길이가 100000인 배열 크기 안에서 생성되기 때문에 메모리 낭비가 발생한다. 

따라서 동적으로 배열 크기를 할당할 수 있는 벡터를 선언해주면 메모리 낭비가 발생하지 않는다.

 

 

 

 

코드 짜보기 (시간 초과)

 

#include<stdio.h>
#include<vector>
using namespace std;

int main(){
	int n, k, i, j, sum=0, max=-2147000000;
    
    scanf("%d %d", &n, &k);
    vector<int> a(n);
    
    for(i=0; i<n; i++){
    	scanf("%d", &a[i]);
    }
    
    for(i=0; i<n-k; i++){       //이중 for문.. i의 시작점과 끝점을 먼저 지정
    	sum=0;
        for(j=i; j<i+k; j++){    //i의 시작점을 기준으로 i+K까지 더해주기
        	sum=sum+a[j];
        }
        if(sum>max) max=sum;
     }
     printf("%d\n", max);
     return 0;
     
     }

 

예를 들어, n이 100000, k가 30000이라고 해보자.

그럼 a[0] + a[1] + a[2] + .... + a[29999] , a[1] + a[2] + a[3] + ... + a[30000] , ........ , a[70000] + a[70001] + a[70003] + ... + a[99999] 이런 식으로 합들이 구해진다. 이는 이중 for문으로 코드를 짤 경우, 약 70000 * 30000번의 횟수로 돌아간다. Time Limited.. 

시간 초과로 실패한 코드이지만 한 번 학습해보면 좋을 것 같다.

 

 

 

 

 

코드 짜보기 (이중 for문을 사용하지 않고!)

아이디어 : sum + a[i] + a[i-k]

#include <stdio.h>
#include <vector>
using namespace std;

int main(){
	//freopen("input.txt", "rt", stdin);
	int n, k, i, sum=0, max;
	
    scanf("%d %d", &n, &k);
	vector<int> a(n);  //동적으로 배열 크기 할당
	
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
	}	
    
	for(i=0; i<k; i++){  //첫번째 배열 합 구해주기
		sum+=a[i];
	}
	max = sum;           //max에 할당
	for(i=k; i<n; i++){     //k부터 sum에 더해주기
		sum = sum+(a[i]-a[i-k]);   //단 i-k번째는 빼주기
		if(sum>max) max=sum;     //크기 비교
	}
	printf("%d\n", max);
	return 0;
}

 

이중 for문으로 배열의 합들을 매번 더해서 비교하는 것보다 첫번째 배열의 합을 구해준 후 k자리부터 하나 더해주기, 맨 앞에 있는 것은 빼주기 방법이 오히려 효율적으로 작동하는 것을 알 수 있다.