글 읽기 - 포켓몬 마스터 이다솜 질문입니다.

cubalys 6년 전 0

계속해서 런타임 에러가 나는데 원인을 못찾겠습니다.

trie를 사용해서 풀었습니다

trie크기를 2000001 로 잡았는데

각 문자마다 trie의 size가 최대 1 만큼 커지기 때문에

20 * 100000인 200만을 넘어갈 수 없다고 생각했는데

이 이상 갈 수가 있나요?

trie 배열 크기를 500만으로 잡아도 런타임 에러가 나네요

다른 부분에서 오류가 생겼을까요?? ㅜㅜ

#include <iostream>
using namespace std;
int trie[2000001][26], size;
int idx[2000001];
char monster[100001][22];
void insert(char *key, int index){
	int node = 0;
	for (char *p = key; *p != '\0'; p++){
		char tmp = *p - 'A';
		if (*p >= 'a') 
			tmp = *p - 'a';
		if (trie[node][tmp] == -1)
			trie[node][tmp] = size++;
		node = trie[node][tmp];
	}
	idx[node] = index;
}

int atoi(char *key){
	int res = 0;
	for (char *p = key; *p != '\0'; p++)
		res += *p - '0', res *= 10;
	return res / 10;
}

int find(int x, char *key){
	if (*key == '\0') return idx[x];
	char cur = *key - 'A';
	if (*key >= 'a') cur = *key - 'a';
	if (trie[x][cur] != -1)
		return find(trie[x][cur], key + 1);
}

int main(){
	freopen("input.txt", "r", stdin);
	for (int i = 0; i < sizeof(trie) / 4; i++)
		*(trie[0] + i) = -1;
	int N, M;
	
	cin >> N >> M;
	size = 1;
	for (int i = 1; i <= N; i++)
		cin >> monster[i], insert(monster[i], i);
	for (int i = 0; i < M; i++){
		char K[22];
		cin >> K;
		if (K[0] <= '9') cout << monster[atoi(K)] << "\n";
		else cout << find(0, K) << "\n";
	}
}

moonhi123 6년 전 1

35번 freopen을 주석처리하면 컴파일 에러는 해결될것 같습니다

cubalys 6년 전 0

제출할 때에는 지우고 냈습니다.

컴파일에러는 안나는데 런타임 에러가 나네요 ㅜㅜ

moonhi123 6년 전 1

아 런타임에러이셨군요....ㅜㅜ 제가 컴파일에러로 잘못봤네요

죄송합니다

chogahui05 6년 전 1

int trie[2000001][26]

런타임 에러가 날 만 하네요..

moonhi123 6년 전 1

아님 변수 size가 함수 size()와 이름이 겹쳐서 일수도있겠네요.

chogahui05 6년 전 1

트라이는

(1) 벡터를 써서 go_pointer를 관리합니다.

(2) Trie에 문자 단위로 대롱 대롱 문자들이 '트리' 형태로 저장되어 있다고 가정하고

"abcabcd"를 추가한다고 가정하면..

들어갈 수 있는 데까지 들어갑니다.

만약에 Trie에서 abca라는 패턴을 찾을 수 있다면 abca는 사실상 추가할 필요가 없고요.

abcab라는 패턴이 없다면

abca 밑에 bcd 패턴을 차례대로 추가하면 됩니다.

보통 트라이를 구축하는 방법과는 완전히 다르게 구현하셨는데요.

http://kks227.blog.me/220938122295

요 링크 따라가셔서 공부해 보시고 구현해 보세요.

chogahui05 6년 전 1

그리고 하나 더..

트라이 같은 경우에는 메모리를 많이 먹기 때문에

정말 제한적인 조건에서 구현하는 자료구조인데요.

https://www.acmicpc.net/proble...

링크 건 문제 같은 경우.. n이 3만, m이 30이고요.

이 문제는 n이 10만, m이 20이네요. 참고로 링크 건 문제를 트라이로 구현해 보니

64M 정도 나왔습니다. 이건 데이터에 따라서 트라이로 구현하면 메모리 초과 날 지도 모르겠네요.

cubalys 6년 전 0

아 계산을 해보니까 2000000 * 26 의 배열이 메모리 제한인 128MB를 넘어가네요
결과에 '메모리 초과' 가 아닌 '런타임 에러' 라고 나와서 인덱스 쪽에 실수가 있었나 그것만 보고 있었습니다.

구조체로 Trie를 구성하는 방법은 많이 해봤는데 최근에 배열로 구성하는 방법을 접하게 되어 연습삼아 풀어봤는데

메모리를 생각을 안하고 있었네요 답변 감사합니다.

cubalys 6년 전 0

동적할당이 아닌 처음부터 배열로 메모리 사이즈를 정해도 메모리 초과 상황에 런타임 에러가 나기도 하는군요 처음 알았습니다.

댓글을 작성하려면 로그인해야 합니다.