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

안녕하세요 김준님 ㅎㅎ

		int vSize = v.size();
		for (int i = 0; i < vSize; i++)
		{
			if (!v[i].alive)
				continue;

			if (v[i].age % 5 == 0)
			{
				for (int j = 0; j < 8; j++)
				{
					int ny = v[i].y + dy[j];
					int nx = v[i].x + dx[j];
					//cout << "Y: "<< v[i].y << ", X: " << v[i].x << ", dy[i]: "<<dy[i]<<", dx[i]"<<dx[i] << ", (" << ny << ", " << nx << ")" << '\n';
					if (ny >= n || nx >= n || ny < 0 || nx < 0)
						continue;

					int age = 1;
					int y = ny;
					int x = nx;
					bool alive = true;
					bool check = false;

					namu naa;
					naa.age = age;
					naa.x = x;
					naa.y = y;
					naa.alive = alive;
					naa.check = check;
					v.push_back(naa);

이 코드 보시면 v에다가 push_back을 계속 하고 있는데요.

제가 이해하기로는 v는 이전 상태값 그리고 여기서 naa는 새로운 값 아닌가요? 이러한 걸 기반으로 새로운 v를 만들어야 하지 않을까요? 물론 age를 기반으로 오름차순 하고 있고

			if (!v[i].alive)
				continue;

해당 부분을 continue하지만 계속해서 불필요한 v를 순회하다 보니 시간초과가 나는 것 같습니다.

이부분을 개선해보시겠어요?

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

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

감사합니다.

강사 큰돌 올림.

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

이번 질문에 대해 분석해보았을 때, 시간초과 문제는 주로 알고리즘의 비효율성이나 불필요한 연산 때문에 발생하는 경우가 많습니다. 따라서 우선 코드 내의 불필요한 중복 연산, 비효율적인 데이터 구조 사용 여부 등을 점검해보시는 것이 좋습니다.

시간초과 관련 문제는 몇 가지 자주 발생하는 원인이 있습니다:

1. 복잡도 감소: 해결하고자 하는 문제의 입력이 매우 큰 경우 O(N^2) 이상의 복잡도를 가진 알고리즘은 시간초과를 발생시킬 수 있습니다. 주어진 문제에 대한 최적화된 알고리즘이 있는지 확인해 보세요.

2. 입출력 최적화: C++에서는 입출력 성능이 떨어질 수 있기 때문에 ios_base::sync_with_stdio(false);와 cin.tie(NULL);를 사용하여 최적화하는 것이 좋습니다.

3. 중복된 계산 방지: 같은 값을 반복적으로 계산하지 않도록 메모이제이션을 사용해 보세요.

관련된 기존 질문을 참고하시면 도움이 될 수 있을 것 같습니다. 아래는 유사한 사례를 다룬 질문들입니다:

1. 이다솜 문제 시간초과.. ㄷㄷ

   • 이 질문에서는 C++ 입출력 최적화가 시간초과 문제 해결에 영향을 준 사례를 설명하고 있습니다.
     

2. 7-V 질문 있습니다

   • 여기서는 메모이제이션 오류로 인해 시간 초과가 발생했던 사례를 다루고 있습니다.
     

위의 자료들을 확인하신 후에도 문제 해결이 어렵다면, 해당 문제의 조건과 입출력 예시를 좀 더 상세하게 공략해보는 것을 추천드립니다.

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