It really really depends on the kind of map. If you want a map that is a 2-D grid of boolean values, then it depends on how sparse the map is expected to be.
If you want to keep all boolean values, you would need at least
N * M * S bits (assuming the map is
M and each location has
S sensor readings), which for your numbers translate to ~2MB of data. If your microcontroller doesn't have this much space, then that's a bad approach.
However, all is not lost! Usually the environment has some feature you can take advantage of. For example, if the environment is not full of obstacles, you don't need to memorize all the empty spaces, right? Or if there is an area closed by obstacles, you don't to keep track of what's inside it, since you can't get there anyway.
That said, perhaps the approach with the least amount of memory would be to model your environment by a set of closed polygons. As you explore the world, you refine the polygons, but not with extreme details, to reduce the memory footprint. All algorithms would then work with polygons (e.g. collision detection) rather than bitmaps which is possibly also less costly, so it could be a win for everyone!
This Wikipedia article may help, where topological frameworks are hinted at, and the thereby linked Map Database Management which could also provide some insight.