dreamian   3년 전

안녕하세요, 가입 한 지 얼마 안 된 뉴비입니다.

그동안 몇 개의 문제를 풀어보며 궁금한 점이 있어서요.

이곳에서 제공하는 많은 문제의 경우 메모리 제한이나 시간 제한이 있는데,

시간 제한의 경우는 알고리즘의 복잡도를 어느정도 예상할 수 있는데, 메모리 제한의 경우는 어떻게 대처해야 할 지 모르겠어서

질문 올리게 되었습니다.

혹시 다른 분들께서는 코딩을 할 때, 배열 선언이나 메모리가 가용될 때에 그것을 어느 정도 예상하고 코딩을 하시는지, 아니면

코딩을 하면서 그것을 정확하게 알 수 있게 해주는 방식이 있는지 궁금합니다.


또한, 디버깅에 대해 저는 의심이 되는 문에 printf문을 선언하여 돌아가는지 확인하는 편인데,

이러한 방식이 맞는건지 궁금합니다.

감사합니다!

kjp4155   3년 전

제 경우에는 int 백만개 = 4MB 기준으로 생각합니다. 

int arr[1000][1000] 을 잡으면 4MB정도 쓸 것이고 long long으로 선언한다면 그 두배인 8MB, char이라면 1/4인 1MB를 사용하게 되겠죠.

예를 들어, long long arr[4000][4000] -> int arr[1000][1000] 의 4* 4 * 2 = 32 배 -> 128 MB  처럼 계산을 합니다.

동적으로 메모리를 사용하는 vector, set, map 등의 STL 자료구조들은 조금 복잡해질 수 있는데, 최악의 경우 자료구조에 몇개정도의 데이터가 들어가는지 계산해보면 됩니다. 다만 set, map등 복잡한 자료구조의 경우에는 단순히 데이터 외에도 여러 변수들이 같이 저장되므로 여유를 좀 많이 잡아줘야 됩니다. 


디버깅을 할 때 무작정 코드만 보고있는것 보다는 printf를 써서 확인하는건 좋은 습관이라고 생각합니다. 다만 규모가 큰 개발을 할 때는 사용할 수 없는 방법이라 알고리즘 문제를 풀때만 유효한 방법이긴 한 것 같네요. 

djm03178   3년 전

컴퓨터의 공간 단위에 대해 익혀두면 쉽게 계산할 수 있습니다. 1바이트부터 시작해서 대략 1000배 단위로 1000바이트는 1킬로바이트, 1000킬로바이트는 1메가바이트 정도로 생각하면 char형 백만 개가 1메가이고 1억 개면 100메가인 등 대략적인 계산이 가능합니다.

chogahui05   3년 전

vector 같은 동적 배열은 grow_rate에 따라 다를 수도 있긴 하지만

저 같은 경우 보통 배열처럼 잡거나, 최악의 경우 원소 갯수가 size * 2이겠거니.. 정도로 잡는 편이고요.


set과 map은.. 하나당 8*(5에서 7) byte정도로 잡습니다.

unordered_map은 다를 수도 있긴 한데요.. java의 hashmap이나..

이 경우는 상당히 넉넉하게 잡아놓습니다. 대충 set과 map의 2배 정도..

이건 어디까지나 제가 여기 문제들을 풀면서 잡아놓는 메모리이니.. 다른 분들과 다를 수 있어요.

dreamian   3년 전

정말 많은 도움이 되었습니다 !

감사합니다 !!

nhouyng   2년 전

으휴

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