전말 🌥
여느 때와 다름없이 열심히 벽을 부시던 중… https://www.acmicpc.net/problem/14442
분명히 로직도 맞고 답도 잘 나오는 것 같은데, 시간초과를 피할 수가 없었다 😥
답답한 마음에 게시판 글을 찾아보니, 가장 긴 차원의 배열을 맨 오른쪽에 두는 것이 가장 메모리를 적게 사용한다는 말을 보게 되었다!
말을 듣고 기존에는 최대 visited[1000][1000][11] 로 해두었던 것을, visited[11][1000][1000] 으로 바꾸어서 제출하니 정답을 맞출 수 있었다 😮
파이썬에서는 다음과 같이 작성할 수 있다.
# visited[k][x][y] = k만큼 기회가 있는 상태
visited = [[[0] * M for _ in range(N)] for _ in range(K+1)]정답은 맞추었지만, 왜 이렇게 되는 것인지 궁금증이 생겨났다.
이를 설명하기 위해서는 캐시 메모리와 공간지역성에 대한 이야기가 필요할 것 같다!
캐시 메모리와 공간 지역성 🧭
컴퓨터에 있는 중앙처리장치인 CPU (central processing unit)는 속도가 빠르다. 그러나 주기억장치이자 메인 메모리인 RAM (Random Access Memory)는 속도가 이에 비해 많이 느리다.
그렇기에 이 둘의 속도 차이가 병목 현상을 만들어내고, 속도 저하를 일으키는 원인이 되곤 한다.
이를 최대한 방지하기 위해, 그 사이에서 열심히 일을 하는 부품이 바로 캐시 메모리(Cache Memory) 이다.
캐시 메모리 ❔
CPU에서 요청한 데이터를 모두 RAM에서 찾아 가져오려면 시간이 한참 걸린다.
그렇기에 자주 사용하는 데이터는 캐시 메모리에 담아두어 필요시에 꺼내어 사용하며 시간을 절약한다. 마치 우리가 자주 쓰는 물건들을 가깝고 잘 알고 있는 곳에 두는 것처럼 말이다.
요청한 데이터가 만약 캐시 메모리 안에 있다면 캐시 히트 (Cache Hit), 없다면 캐시 미스 (Cache Miss)라 부른다.
이름만 봐도 알겠듯이, 캐시 히트를 자주 일어나도록 하는 것이 효율적이다.
그럼 캐시 메모리는 어떻게 효율성을 증대하려고 노력하고 있을까?
시간지역성과 공간지역성
캐시 메모리는 효율적으로 동작하기 위해서, 참조 지역성의 원리 (principle of locality)를 이용한다.
이를 간단히 설명하면, 시간 혹은 공간적으로 자주 반복되는 데이터를 파악하여 저장해두는 것이다.
시간 지역성
시간 지역성은 최근 사용된 메모리에 집중적으로 액세스하는 것을 말한다.
- 어떤
A라는 학생이 상습적으로 절도 행위를 일삼은 학생이라고 가정해보자. 어느날 다시 한 번 학급에서 절도 행위가 일어난다면, 선생님은 모범생인C학생을 의심하겠는가, 아니면A학생을 의심하겠는가?
우선 A학생을 의심하는 것이 합리적일 것이다.
이처럼, 이미 참조했던 경험이 있는 메모리가 더 자주 쓰일 것이라 예상하는 것을 시간 지역성이라 부른다.
공간 지역성
공간 지역성은 특정 메모리의 근처를 집중적으로 탐색하는 것으로, 참조된 메모리의 근처를 우선적으로 참조하는 것이다.
위의 예시를 이어서 설명해보겠다.
- 어떤
B라는 학생은 평소에도A학생과 자주 어울리며 노는 절친 사이라고 가정해보자. 절도 사건에서A가 범인이 아니라고 밝혀졌다면, 선생님은 절친인B학생을 의심하겠는가, 모범생인C학생을 의심하겠는가?
B학생이 억울할 수도 있겠지만, 먼저 의심하는 것이 합리적일 것이다.
이와 같이, 참조된 메모리 근처에 있는 메모리도 사용될 것이라고 예상하는 것을 공간 지역성이라 부른다.
여기서 중요하게 보아야 할 부분은
공간 지역성이다.
컴퓨터는 참조한 메모리 근처에 있는 메모리를 우선 탐색하려는 경향을 가지고 있고, 그러한 예측이 맞았을 때 더욱 효율적이다.라는 것을 기억해두자!
그래서 왜 ❓
지금까지 열심히 설명을 했지만, 근본적으로 공간지역성과 이 문제 간 연관성이 무엇인지에 대해서는 다루지 않았다.
이해를 위해서 예시를 들어 설명해보도록 하겠다.
벽 부수고 이동하기 2 🔨
본 문제에서는, visited 배열을 매 반복마다 만들어준다면 메모리 초과가 발생하고 만다.
그렇기에 visited를 길이 11의 배열로 만들어주어, 남아 있는 기회만큼을 index 삼아 따로 저장해주는 것이 포인트인 문제이다.
평범한 생각으로 다음과 같이
[1000][1000][11]의 배열을 만들어 보았다.
visited = [[[0]*(k+1) for _ in range(M)] for _ in range(N)]이는 곧 11*1000의 배열이 1000개 존재하는 것이라 할 수 있다.
그렇기에 최악의 경우에는 1000번의 매핑이 이루어져야한다.
이번에는
길이 11의 배열이 마지막에 감싸고 있는 형식으로 만들어 보자.
visited = [[[0] * M for _ in range(N)] for _ in range(K+1)]이는 곧 1000*1000의 배열이 11개 존재하는 것이라 할 수 있다.
그렇기에 위의 경우보다 훨씬 적은 최대 11번의 매핑만이 필요하다.
그래도 이해가 안된다면…🤔
여기까지 와도 이해가 안될 수 있다! 본인 또한 처음에는 이해가 잘 되지 않았기 때문이다…
그렇다면 D라는 학생이 어느 아파트에서 E학생의 집을 찾고 있다고 가정해보자. 친구의 집은 1동 1층 2호이며, 여기서 동 = k, 층 = x, 호 = y로 둔다.
즉, k = 1, x = 1, y = 2인 경우로 생각해보자.
visited[x][y][k]의 형식
-
가장 먼저
1동 1층 1호을 보게 된다. -
그다음에는
2동 1층 1호를 보게 된다. -
반복하여
3동 1층 1호,4동 1층 1호,5동 1층 1호까지 보고 나서야,1동 1층 2호로 넘어가게 된다.
👉 k에서의 반복이 우선 끝나야, y에서의 반복도 진행할 수 있기 때문이다.
- 이러한 방식으로 찾게 된다면, 바로 옆집임에도 불구하고 총
6 번의 탐색이 필요하다.
visited[k][x][y]의 형식
-
처음에는 동일하게
1동 1층 1호을 보게 된다. -
그다음에는 바로
1동 1층 2호를 보며 친구의 집을 찾아낼 수 있다.
최종 정리
-
길이(차원)이 가장 긴 배열을 맨 오른쪽에 두는 이유는,
공간 지역성의 원리를 활용하기 위해서이다! -
근처에 있는 메모리를 먼저 탐색하려는 특성상,
배열의 길이가 길수록 안쪽에 두고, 길이가 짧을수록 바깥쪽에 두어 감싸는 것이 효율적이다!
(참고한 게시글: https://www.acmicpc.net/board/view/111938)