jh20s   2년 전

D1: 1, D2:2000 일때 최대 관중석의 개수는 1216588입니다.

pair<int,int> 로 구성된 map에 최대 1216588개를 삽입하는데

64MB에서 메모리 초과가 뜹니다.

이게 왜 메모리 초과인지 모르겠습니다 ㅠㅠ

map에 대한 이해도가 적어서 그런데,  

map에 들어가는 노드 하나당 메모리가 몇인가요?


chogahui05   2년 전

그건 정확히 잘 모르겠는데요.

일단 map 자체가 레드 블랙 트리로 구성되어 있으니까.. 자손 2개 정보까지 들어가야 하지 않을까 싶습니다.

트리 특성상 이 2개는 들어가고요. 거기에 추가적인 정보까지 (얼만큼 노드가 깊어졌나.. 등등) 들어가면.. 사실 무시 못합니다.


관심 있으시면 레드 블랙 트리 한 번 검색해 보세요.

진짜 진짜 재수가 없는 경우에는 메모리 초과 날 만하죠.


이 문제는 2차원 배열로 충분히 커버 가능합니다.

jh20s   2년 전

문제는 비슷한 방법으로 해결했지만,

map의 한 개의 노드에 몇 개의 변수가 들어가는지  찾아보려고 하는데, c++reference에서도 딱히 정보가 없어서 못 찾고 있어요 ㅠㅠ... 

적어도 하나의 노드당 포인터나 변수가 5개 이상인것 같아 말해주신것 처럼 메모리 초과가 나는 것 같네요.

정확히 찾아보고 싶은데 좀 더 검색을 해봐야겠네요 ㅠ

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