[it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비] 코드구현력 기르기 - 온도의 최대값

문제

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.
매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

💡 입력설명
첫째 줄에는 두 개의 정수 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

 

---

코드

첫 번째 풀이

#include <stdio.h>

int main() {
	int n, k, i, j, max = -2147000000, sum;
	scanf("%d %d", &n, &k);
	int arr[n] = {0, };
	for(i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	
	for(i = 0; i <= n - k; i++) {
		sum = 0;
		for(j = i; j < i + k; j++) {
			sum += arr[j];
		}
		if(sum > max) {
			max = sum;
		}
	}
	printf("%d", max);
	return 0;
}

최종 풀이

#include <stdio.h>
#include <vector>

int main() {
	int n, k, i, j, max = -2147000000, sum = 0;
	scanf("%d %d", &n, &k);
	std::vector<int> arr(n);
	for(i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	
	for(i = 0; i < k; i++) {
		sum += arr[i];
	}
	
	for(i = k; i <= n - 1; i++) {
		sum = sum + arr[i] - arr[i - k];
		if(sum > max) {
			max = sum;
		}
	}
	printf("%d", max);
	return 0;
}

 

---

설명

사용자로부터 n(날짜), k(연속적인 날짜)를 입력받고 n만큼의 vector arr을 선언한다.

n번 반복하는 for문을 작성하여 해당 arr에 온도를 입력받는다.

k번 반복하는 for문을 작성하여 sum값에 미리 할당받는다.

이후 k부터 n-1만큼 반복하는 for문을 작성하여 sum에 다음 날짜의 온도를 더하고 k이전의 온도를 빼나간다.

해당 sum값이 max보다 클 경우 max에 sum을 할당해 나간다.

해당 for문에서 빠져나오면 max를 출력하여 마무리한다.

 

---

배운 점

1. 동적메모리 할당: vector

#include <vector>

int main () {
	int n;
    scanf("%d", &n);
    // n크기의 메모리 할당
	std::vector<int> a(n);
}​

 

• 배열을 사용할 경우 int *arr=new int[n]  로 new 연산자를 써서 동적으로 할당받아야한다.
• 동적할당 해제는 delete[] arr; 하면 할당이 해제된다.
• 요즘은 배열을 쓰지 않고 벡터를 쓰는 경향이 있다.

2. 2중 for문을 사용하여 풀다보니 시간복잡도 O(n^2)으로 인한 time_limit가 발생하였다.
해당 문제를 Slicing Window 기법을 활용하면 시간복잡도를 O(n)으로 줄일 수 있다는 것을 알게되었다.

 

---

 

해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.