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

안녕하세요 진욱님 ㅎㅎ

시간 초과가 발생했습니다. 어떻게 시간복잡도를 최적화 할지 감이 잘 안와서 질문 드립니다!

-> 최적화 부분은 강의내에 설명드리고 있습니다.

여기서 근데 시간복잡도 산정을 하고 -> 시간초과가 발생할만한 코드인지를 확인하는게 중요한데요 ㅎㅎ

문제 지문을 잠시 볼까요?

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

자 그러면 N * K는 10만 곱하기 10만이 되는 것을 볼 수 있습니다.

10만 곱하기 10만은 100억이 되는 숫자입니다. 제가 100억은 잘 통과하는 시간복잡도라고 했죠? 그렇기 때문에 -> 더 효율적인 방법을 찾아야 겠다 라는 생각을 해야 하는 것입니다.

	for (int i = 0; i < num1 - num2; i++) {
		sum = 0;
		for (int j = i; j < i + num2; j++) {
			sum += vec[j];
		}
		
		ret.push_back(sum);
	}

앞의 코드는 N * K 코드에요

알고리즘 1주차 교안내용을 잠시 볼까요?

가능한 시간복잡도의 기준 

문제마다 다르지만 100억이상 -> 절대 안됨 / 10억이상 -> 거의 안됨 / 1억 -> 어느정도는 됨 이렇게 생각하고 들어가는게 좋습니다.

+ 문제풀 때는 최고차항의 계수도 고려해야 합니다. 문제 범위기준 -> 시간복잡도 판단하는데요. 예를 들어 15000 * 15000 / 2 -> 시간복잡도 -> 어 ? 1억이네 될 수도 있겠네..? 이렇게 판단해야 합니다.

이 부분은 문제를 풀 때 매우 매우 중요합니다. 항상 문제를 보고 문제로 부터 어떻게 풀어야 하는지 로직을 생각한 후 그 로직의 시간복잡도를 얼추 계산하고 그리고 나서 시간초과가 뜰 것 같은면 다른 낮은 시간복잡도를 가진 로직을 빠르게 생각하는 것이 문제를 푸는데 있어 기본입니다.

그리고 실버 3까지는 풀 수 있는 문제가 많은데 실버 2로 올라가는 순간 도식화까지는 가능한데 이 도식화 한 것을 어떻게 코드로 표현해 풀 수 있는지 감이 안 잡히는 문제들이 많습니다. 이런 문제를 만나면 보통 정답 코드를 보는 편인데 큰돌님 강의 외에는 해설이 없다보니 어떻게 공부해야할지 잘 모르겠습니다ㅠㅠ 이 부분도 어떻게 공부하면 좋을까요??

-> 감히 안잡히는 문제는 지금 실력이 낮아서 그렇습니다. 하다보면 됩니다. 꾸준하게 하루에 3시간정도만 하면 됩니다. 그렇다면 문제가 고민인데요. 일단은 사람들이 많이 푼문제를 중심으로 학습하시면 답안이 많아서 좋기 때문에 그걸 기반으로 하시고 + 일단은 제 문제 위주로 풀어주세요

그러면 어떻게 그런 문제를 찾아야하냐? 여기 17:40 쯤에 문제 찾는 방법 나옵니다. ㅎㅎ 이 영상 참고해주세요

https://www.youtube.com/watch?v=DBXEWJx2mIw&ab_channel=%ED%81%B0%EB%8F%8C%EC%9D%98%ED%84%B0%EC%A0%84

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

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

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다.

최진욱님께서 직면하신 문제는 시간 초과와 관련된 것으로 보입니다. 현재 작성하신 코드의 시간 초과 원인은 아마도 O(n*k)의 복잡도를 가지는 연속 부분합 계산 방법에 있을 것입니다. 이 문제를 해결하기 위해서는 좀 더 효율적인 알고리즘 패턴을 적용해야 합니다. 여기서는 누적합(Prefix Sum)과 같은 개념을 사용해 시간 복잡도를 줄일 수 있습니다.

문제 접근 방법

• 누적합(Prefix Sum)을 활용하면 매 구간의 합을 반복문을 통해 계산하지 않고도 빠르게 구할 수 있습니다. 이는 O(n)의 시간 복잡도를 가집니다.
  
• 누적합을 계산하면 특정 구간의 합을 O(1)의 시간에 계산이 가능하여 시간 초과 문제를 방지할 수 있습니다.
  

이를 좀 더 이해하고 적용하기 위해 지식공유자님의 기존 답변과 유사한 문제 상황에 대한 답변을 참고하는 것을 추천드립니다. 이러한 답변은 누적합을 통한 효율적인 계산 방법과 시간 초과 방지 전략을 설명합니다.

답변을 더 구체적으로 다룬 유사한 사례로는 아래 링크를 참고하세요:

• 1-H 시간초과 관련해서 질문드립니다: 이 답변에서는 이중 루프로 인해 발생하는 시간 복잡도 문제를 어떻게 최적화할 수 있을지에 대한 방향을 제시하고 있습니다.
  

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.