[1-H]시간 초과 관련해서 질문드립니다

http://boj.kr/ab659fec129e45c7b35407ed7e322f06

안녕하세요 선생님

문제 제출 결과가 시간초과로 나왔는데 ,

vector의 사용이 문제인지 이중 for문이 문제인지 아니면 다른 어떤 게 문제인지 궁금합니다
그리고 결과가 시간 초과라고 나왔을 경우 어떻게 대처하면 좋을까요? 예를 들어서 다른 자료형을 사용한다던지 아니면 로직을 바꾼다던지.. 제가 왕초보라 어떻게 대처해야 할지 모르겠습니다. ㅜㅜ

저는 위 코드를 다음과 같이 짰습니다.

입력받은 온도 값을 벡터에 저장.
총 n-k+1번 동안 반복해서 연속된 온도k개의 합을 구해 다른 벡터에 저장.
가장 큰 값 출력.

항상 감사합니다!!

안녕하세요 0201님 ㅎㅎ

코드를 잠깐 볼게요. ㅎㅎ

	for (int i = 0; i < n - k + 1 ;i++)
	{
		sum = 0;	//연속 합을 초기화
		for (int j = i; j < k+i; j++)		
		{
			//인덱스 i부터 k+i까지, 총 k개를 연속으로온도값을 sum에 더함
			sum += v[j];

이 코드의 시간복잡도는 얼마가 될까요? n * k가 됩니다.

문제의 범위를 볼게요.

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다.

즉, 최대치로 계산하면 N은 10만, K는 10만이 되기 때문에 0201님의 코드는 10만 * 10만이 되기 때문에 시간초과가 발생한 것 같습니다.

그렇기 때문에

이부분은 prefix sum을 사용하셔야 합니다. 1주차 개념강의를 참고해주세요.

그리고 결과가 시간 초과라고 나왔을 경우 어떻게 대처하면 좋을까요? 예를 들어서 다른 자료형을 사용한다던지 아니면 로직을 바꾼다던지.. 제가 왕초보라 어떻게 대처해야 할지 모르겠습니다. ㅜㅜ

>> 보통은 문제의 최대범위를 기반으로 시간복잡도를 측정했을때 1000만이거나 1억이면 아 좀 많은데? 하고 들어가셔야 합니다. 본인이 짠 A라는 알고리즘이 1억인데 아무리 생각해도 그정도의 알고리즘밖에 생각이 안난다? 그러면 들어가셔야 합니다. 그러나 B라는 알고리즘이 더 효율적인거 같은데 라고 생각난다면 그런 알고리즘을 써야 하구요. 이부분은 8주차까지 완강하시면 아 이런 문제는 ~ 한 알고리즘이 더 효율적이겠구나 하는 생각이 드실겁니다. 꾸준히 해주세요. ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

인프런 커뮤니티 질문&답변