furthermares   3년 전

배열의 차원 선언 순서를 한 번 확인해보세요.

visited[1000][1000][11]의 메모리 사용량이 visited[11][1000][1000]의 메모리 사용량의 약 2배 정도입니다.

로직은 맞는데 TLE나 MLE가 나시는 분들은 한번 참고해보세요. 가장 큰 길이의 차원을 가장 오른쪽에 놓는 것이 메모리가 가장 절약됩니다.

이에 대한 이유는 공간지역성과 (Java에서는) 헤더의 수 차이 때문이라고 하네요.

두 방식 모두 AC를 받게 해보면 차이가 이렇게 납니다.

visited[1000][1000][11]: 478536 KB / 6984 ms

visited[11][1000][1000]: 338688 KB / 3812 ms

ironhee8005   3년 전

궁금한 것이 있습니다.

올리신 글을 읽어보았는데요. 

말씀하신 공간 지역성이란게, 컴퓨터의 참조의 지역성을 이용해 캐시메모리를 쓰는 것과 같은 원리인가요??

제가 잘 이해한지 모르겠습니다.

visited[1000][1000][11]의 경우 11 * 1000 의 배열 1000개가 서로 떨어진 공간에 생기고,

visited[11][1000][1000]는 1000 * 1000의 배열이 11개가 서로 떨어진 공간에 생기니, 

전자에 경우 계속해서 miss가 나고 매핑을 1000번(극단적으로 볼 경우) 하는 반면,

후자는 11번의 매핑만을 하면되니 속도가 차이 난다. 제가 이해한 것이 맞을까요??

furthermares   3년 전

바로 그렇습니다.

하나는 바로 다음에 확인할 원소가 바로 옆에 있는 반면에, 다른 하나는 아예 다른 배열로 찾아가야 합니다.

101호 → 102호 → 103호 → 201호 → …가 101호 → 201호 → 301호 → 102호 → …보다 더 빠른 것처럼요.

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