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

안녕하세요 수현님 ㅎㅎ

이부분은 배열의 크기를 잘못선언해서 -> UB가 뜨는 것 같습니다.

둘의 코드 위치는 결과적으로 상관없지만 배열의 크기 때문에 : 100을 참조할 수 있기 때문에 101이상으로 선언해야 함 -> UB -> 시간초과가 발생하는 것 같습니다.

이렇게 선언해보시겠어요?

구조체 위치를 다르게 해도 맞는 코드:

#include <bits/stdc++.h>
#define max_n 104
using namespace std;

const int dx[] = {0, 0, 1, -1 };
const int dy[] = {-1, 1, 0, 0 };
int shark[max_n][max_n], R, C, M, ret, temp[max_n][max_n];

struct Shark {
    int y, x, s, dir, z, death;
}a[max_n*max_n];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    cin >> R >> C >> M;
    for (int i = 1; i <= M; i++) 
    {
        cin >> a[i].y >> a[i].x >> a[i].s >> a[i].dir >> a[i].z;
        a[i].y--; a[i].x--; a[i].dir--;
		
		if(a[i].dir <= 1) a[i].s %= (2 * (R - 1));
		else a[i].s %= (2 * (C - 1));

        shark[a[i].y][a[i].x] = i;
    }
    for (int t = 0; t < C; t++) 
    {
        for (int y = 0; y < R; y++) 
        {
            if (shark[y][t]) 
            {
                a[shark[y][t]].death = 1;
                ret += a[shark[y][t]].z;
                shark[y][t] = 0;
                break;
            }
        }
        memset(temp, 0, sizeof(temp));
        for (int i = 1; i <= M; i++) 
        {
            if (a[i].death) continue; 

			int y = a[i].y;
            int x = a[i].x;
            int s = a[i].s;
            int d = a[i].dir; 
			int ny, nx; 

			while (1) 
            {  
				ny = y + s * dy[d];
				nx = x + s * dx[d]; 
                if (nx < C && ny < R && ny >= 0 && nx >= 0)break;
				if(d <= 1){
					if(ny < 0){
						s -= y;
						y = 0;
					}else{
						s -= R - 1 - y;
						y = R - 1;
					} 
				}else{ 
					if(nx < 0){
						s -= x;
						x = 0;
					}else {
						s -= C - 1 - x;
						x = C - 1;
					} 
				}
				d ^= 1;  
            }
            
			if (temp[ny][nx]) 
            {
                if (a[temp[ny][nx]].z < a[i].z) 
                { 
					a[temp[ny][nx]].death = 1; 
					temp[ny][nx] = i; 
				}
                else a[i].death = 1;
            }else temp[ny][nx] = i;
            
			a[i].y = ny; 
			a[i].x = nx; 
			a[i].dir = d;
        }
		memcpy(shark, temp, sizeof(temp)); 
    }
    cout << ret << "\n";
    return 0;
}

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

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

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. 전수현님.

구조체 선언 위치에 따른 시간초과 문제와 관련된 질문에 대해 적절한 정보를 제공할 내용을 찾았습니다. 아래에 관련된 질문을 참고해 주세요.

1. 3-K 시간초과 관련 질문있습니다!

   • 시간초과 문제가 발생하는 원인과 이를 해결하는 방법에 대해 설명되어 있습니다. 특히, 코드의 특정 부분이 시간초과를 일으킬 수 있는 이유와 효율적인 방법을 논의하고 있습니다.
     

2. 3-K 시간초과 & 학습 방법 고민있어요

   • 백조 문제에서의 시간초과 문제와 이를 어떻게 해결할 수 있는지 구체적으로 설명되어 있으며, 효율적인 메모리 사용 법에 대해 안내하고 있습니다.
     

3. 3-D 문제 시간초과

   • DFS와 BFS의 차이를 설명하고, DFS가 왜 시간초과가 날 수 있는지, BFS로 변환하는 방법을 제시하고 있습니다. 또, 불필요한 계산을 줄이는 방법을 설명합니다.
     

구조체 선언의 위치가 알고리즘의 시간 복잡도에 영향을 미치지는 않지만, 메모리 관리와 관련된 부분에서 시간이 늦춰질 수 있습니다. 예를 들어, 반복문 안에 구조체 변수를 선언하는 경우, 루프마다 메모리를 할당하고 해제하는 작업이 반복되기 때문에 시간 초과 문제가 발생할 수 있습니다. 따라서, 메모리 할당을 최소화하고 효율적으로 사용하는 것이 중요합니다.

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