알고리즘 문제를 제출했을 때 string 변수 하나를 생성하면 런타임 오류가 발생합니다.

Question

#include #include #include #include #include using namespace std; string strList[16]; int n,cache[16][1<<15]; int restore(int front, int taken) { int& ret = cache[front][taken]; if (taken == (1 << n) - 1) return strList[front].size(); if (ret != -1) return ret; ret = 987654321; for (int i = 0; i < n; i++) { if ((taken & (1 << i)) > 0) { continue; } int nextTaken = taken | 1 << i; int dupl=0; for (int j = 0; j < (int)min(strList[front].size(), strList[i].size()) ; j++) { for (int p = 0; p < j + 1; p++) { if (strList[front][strList[front].size() - 1 - j + p] != strList[i][p]) break; if (p == j) dupl = j + 1; } } ret = min(ret,(int)(strList[front].size() - dupl + restore(i,nextTaken))); } return ret; } void recon(int front, int taken, string& retstr) { if (taken == (1 << n) - 1) return; int minval = 987654321; int minindex=0; for (int i = 0; i < n; i++) { int nextTaken = taken | 1 << i; int retdef = restore(i, nextTaken); if (retdef < minval) { minval = retdef; minindex = i; } } int dupl = 0; for (int j = 0; j < (int)min(strList[front].size(), strList[minindex].size()); j++) { for (int p = 0; p < j + 1; p++) { if (strList[front][strList[front].size() - 1 - j + p] != strList[minindex][p]) break; if (p == j) dupl = j + 1; } } string k; // 이 부분을 주석 처리하면 런타임 오류가 뜨지 않습니다. recon(minindex, taken | 1 << minindex, retstr); } int main() { int testcase; cin >> testcase; vector ret; while (testcase--) { cin >> n; memset(cache, -1, sizeof(cache)); for (int i = 0; i < n; i++) { cin>>strList[i]; } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (strList[i].size() > strList[j].size()) { if (!(string::npos == strList[i].find(strList[j]))) { n--; for (int p = j; p < n ; p++) // 배열 한칸씩 당기기 { strList[p] = strList[p + 1]; } j--; } } else { if (!(string::npos == strList[j].find(strList[i]))) { n--; for (int p = i; p < n; p++) // 배열 한칸씩 당기기 { strList[p] = strList[p + 1]; } j--; } } } } int minval = 987654321; int minindex; for (int i = 0; i < n; i++) { int mainTaken = 1 << i; int retdef = restore(i, mainTaken); if (retdef < minval) { minval = retdef; minindex = i; } } //cout << "답" << minval << endl; string rets = strList[minindex]; recon(minindex, 1 << minindex, rets); ret.push_back(rets); } for (string s : ret) cout << s << endl; return 0; } https://www.algospot.com/judge/problem/read/RESTORE알고리즘 문제는 이 문제입니다.recon 함수에서 string k; 이 부분을 주석 처리 하지 않으면 런타임 오류가 발생합니다.컴파일러에서는 오류가 발생하지 않지만 알고스팟 사이트에서 제출했을 때만 오류가 발생합니다.오류 메시지는 RTE (SIGSEGV: segmentation fault, probably incorrect memory access or stack overflow) 입니다.다른 int나 char 배열 등등 다 만들어봐도 오류는 뜨지 않고 string 변수만 오류가 발생합니다.이 부분이 오류인지 몰라서 찾는다고 2시간이 걸렸네요 ㅠㅠ저 부분에 string 변수를 사용하지 않고 코드를 수정해서 정답 코드를 작성하긴 했는데 저 부분이 왜 오류인지는 전혀 모르겠어서 질문드립니다.

mirheeoj · Accepted Answer

저런 건 대부분 코드 자체에 메모리 침범 문제가 있으나 전혀 상관없는 곳에서 희생자가 발견되는 경우입니다. 저 부분을 주석처리한 건 문제를 해결한 것이 아니라, 있는 문제를 터지지 않는 상태로 만든 것 뿐인 셈이죠. 네이티브 언어가 어려운게 이런 부분입니다.

알고리즘 문제를 제출했을 때 string 변수 하나를 생성하면 런타임 오류가 발생합니다.

1개의 답변

기술 목록