3-D 시간초과와 range based for
325
작성한 질문수 6
안녕하세요 큰돌님 몸은 괜찮으신지요. 문제를 풀다가 index out of bound도 아닌 segmentation fault가 떠서 헤매고 있습니다.
코드 한 번 봐 주시면 감사하겠습니다.
http://boj.kr/28b2fc7b2381489fb1ba98f2299c5906
range based for문에서 데이터를 추가해 이상한 값이 들어가 오류가 나는 거 였습니다.
cpp에서 range based for문이 어떻게 실행되길래 이런 현상이 발생하나요? range based for에서는 수정도 되지 않던데 말이지요. reference를 읽어도 모르겠어서 여쭈어 봅니다.
또한 제 코드가 왜 시간 초과가 나는지 모르겠습니다. dfs두개에 여러 로직들로 O(k(n)^2) 아닌가요? 72 ~ 77라인은 결국 ny, nx가 조건을 만족 할때 하는거라 n^3이 되지않는다고 보입니다. 이 라인들을 64번 for문 밖으로 빼면 72~ 77 라인의 시간 복잡도는 n^2이라고 생각는데 말이지요.
http://boj.kr/6eca2b27e3f84a14af220a09ef488606
답변 1
0
안녕하세요 태완님 ㅎㅎ
걱정해주셔서 감사합니다. ㅎㅎ 통원치료중이에요. ㅎㅎ
cpp에서 range based for문이 어떻게 실행되길래 이런 현상이 발생하나요? range based for에서는 수정도 되지 않던데 말이지요. reference를 읽어도 모르겠어서 여쭈어 봅니다.
>> 음.. 이해가 잘안가는데 어떤 부분인지 다시 질문해주실 수 있나요?
2. 시간초과
>> 제 생각에는 이부분이 불필요해서 시간초과가 나는 것 같습니다.
혹시 고쳐보시겠어요?
로직은 문제 없는 것같아요.
//왜 굳이? escape는 불필요한 자료구조
if(i == 0 || i == n - 1 || j == 0 || j == m - 1){
escape.push_back({i, j});
}
}
else{
ls[i][j] = 0;
h_cor.push({i, j});
//또다시? 이부분을 만약 할거면 아 if문 바끙로 뺴서 i와 j를 체크하는게 좋다.
if(i == 0 || i == n - 1 || j == 0 || j == m - 1){
escape.push_back({i, j});
}
}
}
}
for(auto pa : escape){
if(pa.first == h_cor.front().first && pa.second == h_cor.front().second){
cout << 1;
exit(0);
}
}
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
4 - A
0
26
2
코딩살구클럽 입장이 안됩니다
0
65
2
4-F 경우의 수 질문입니다.
0
33
2
코딩살구클럽 가입이 안됩니다.
0
76
2
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
57
1
교안 158페이지 문의드립니다
0
45
2
코딩살구클럽 관련 건의사항
0
116
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
44
1
진행 방법 질문드립니다!
0
81
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
63
2
2주차 개념#12 트리 순회
0
32
2
백준사이트가 종료된다고 합니다.
0
316
2
백준 서비스 종료
9
952
1
sk 하이닉스 코테 대비
0
386
2
3-G 최댓값 질문
0
54
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
84
2
3-I 코드 질문드립니다.
0
65
2
3-N 질문 있습니다.
0
68
2
학습방법
0
105
2
4-H 질문 있습니다 (코드 리뷰)
0
69
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
183
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
72
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
65
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
53
2





