inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-C

3-D 시간초과와 range based for

325

권태완

작성한 질문수 6

0

안녕하세요 큰돌님 몸은 괜찮으신지요. 문제를 풀다가 index out of bound도 아닌 segmentation fault가 떠서 헤매고 있습니다.

코드 한 번 봐 주시면 감사하겠습니다.

http://boj.kr/28b2fc7b2381489fb1ba98f2299c5906

 


range based for문에서 데이터를 추가해 이상한 값이 들어가 오류가 나는 거 였습니다.

  1. cpp에서 range based for문이 어떻게 실행되길래 이런 현상이 발생하나요? range based for에서는 수정도 되지 않던데 말이지요. reference를 읽어도 모르겠어서 여쭈어 봅니다.

  2. 또한 제 코드가 왜 시간 초과가 나는지 모르겠습니다. dfs두개에 여러 로직들로 O(k(n)^2) 아닌가요? 72 ~ 77라인은 결국 ny, nx가 조건을 만족 할때 하는거라 n^3이 되지않는다고 보입니다. 이 라인들을 64번 for문 밖으로 빼면 72~ 77 라인의 시간 복잡도는 n^2이라고 생각는데 말이지요.

http://boj.kr/6eca2b27e3f84a14af220a09ef488606

c++ 코딩-테스트

답변 1

0

큰돌

안녕하세요 태완님 ㅎㅎ

걱정해주셔서 감사합니다. ㅎㅎ 통원치료중이에요. ㅎㅎ

  1. 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