신비로운 C++의 세계 (feat. vector와 I64d)

요약

• long long을 size_t에 넣지 말자
• long long을 받을때 %I64d안되면 %lld를 써보자
• resize를 하던가 생성자에 갯수를 넘기던가 하나만 하자.

오늘은 PS(알고리즘 문제풀이)를 하면서 만난 신비한 현상을 공유한다

현상

• https://www.acmicpc.net/problem/1916
  다음 문제를 제출했는데, 무려 메모리 초과가 나왔다.
  단순한 다익스트라 구현에 메모리 터질 일이 없는데? 그렇게 한시간동안 헤맸다.

  이렇게 해맨건, 로컬에서는 발생안하고(VS2019) 오로지 백준에서만 메모리 초과가 발생했기 때문이다.

  조사 결과, 문제를 일으킨 건 다익스트라 부분이 아니라 이 부분이였다.

    vector<vector<pair<int, int>>> mat(n);
   mat.resize(n);
  
   for (int i = 0; i < m; i++) {
       int f, t, c;
       scanf("%d%d%d", &f, &t, &c);
       f--; t--;
       mat[f].push_back({c, t});
   }

  n개로 초기화 후, resize도 n개로 하는 실수를 범한 것이다.
  근데, resize를 한것만으로 메모리 초과가 발생한 것도 이상하고, push_back을 해야 메모리 에러가 일어나는것도 이상했다.

찾은 첫번째 문제는 n이 long long 이였다는 것이다.

ll n, m, from, to;
scanf("%I64d", &n);
scanf("%I64d", &m);

int로 바꾸니 잘 되었다.

그래서 long long을 size_t에 강제로 넣어서 생긴것같다...라 생각했는데 또 그것도 아니다.

이렇게 resize를 지우니 정상 작동했다.

    vector<vector<pair<int, int>>> mat(n);

더 웃긴건, 이래도 정상 작동한다. 단지 다른 변수를 하나 만들었을 뿐이다.

     vector<vector<pair<int, int>>> mat_another(n);
    mat_another.resize(n);

     vector<vector<pair<int, int>>> mat(n);
    mat.resize(n);

이것도 된다.

     vector<vector<pair<int, int>>> mat(n);
    mat.resize(n);
    mat.resize(n);

이게 왜 되지???????????를 끊임없이 생각하며 그냥 포기했다...

삽질한 코드들

• 문제의 코드
  • https://www.acmicpc.net/source/23434463
• long long 말고 int로 바꾸니 된다
  • https://www.acmicpc.net/source/23434472
  • 넘길때 int 캐스팅 https://www.acmicpc.net/source/23434500
• lld 쓰니까 long long을 넘겨도 된다
  • https://www.acmicpc.net/source/23434508
• resize 지우니까 된다
  • https://www.acmicpc.net/source/23434394
• 다른 vector 초기화 후 진행하니 성공
  • https://www.acmicpc.net/source/23434457

분석한 원인들

원인을 완벽히 분석하지 못했다. 테스트케이스를 알기도 불가능하고 백준 시스템에서만 오작동하고... 코드를 계속 바꿔가며 어디서 문제가 생기는지 파악하는 법도 있긴 한데 그건 좀 너무 가는것같아서 알아낸것만 정리하고 마치려 한다.

• I64d 말고 lld로 받으면 제대로 되는 경우가 있다
  • 그러니 lld로 받자
• size_t 넘기는 곳은 되도록 int를 넘겨주도록 하자
  • 문제가 생길 수 있다
• vector를 만들 때, 생성자에서 n개로 만들고 resize(n)을 하면 문제가 생길 수 있....다?
  • 이건 솔직히 이상한 값이 resize로 넘어가서 생기는 문제 같다. 아직 모르겠다.

C++은 신비롭다

C++에 너무 오래 떨어져있다보니 이런 신비함을 간만에 느껴봐서 삽질을 정리해봤다.
C++에 한해서는 이게 되면 이것도 되겠지?라는 걸 알아볼 때 너무 깊게 들어가야되고 결국 모르는 경우도 있는 것 같다. 컴파일러에 따라 동작이 바뀌기도 하니까...