🎯 Goal
arr타입의 메모리 저장 방식을 이해할 수 있다.- 공간지역성에 대해 이해할 수 있다.
⛳ Process
알고리즘 문제를 푸는 도중 시간초과/메모리초과로 인해 해결이 안되는 문제가 있었다. BFS 알고리즘을 사용해야했으며 문제 특성상 3차원 배열을 생성해 탐색해야만 했다. 풀이과정에서 로직에는 문제가 없다고 생각했으나 지속적으로 시간초과/메모리초과 발생으로 인해 질문글을 통해 나의 문제를 해결해보려했다. 여러 글을 확인하던 중 어떤 한 글에서 흥미로운 점을 발견할 수 있었다.
글의 내용은 배열의 차원 순서가 성능에 영향을 미친다는 내용이였다. 가장 큰 길이의 차원을 가장 오른쪽에 놓는 것이 시간 및 메모리를 절약할 수 있다고 한다. 예를 들어 visited[1000][1000][11]같이 선언한 배열보다 visited[11][1000][1000] 같이 선언한 배열이 더 시간 및 메모리를 절약할 수 있다는 것인데 곰곰히 생각해보니 당연하다는 생각이 들었다.
전자의 경우 길이가 11인 배열이 1000 * 1000 = 1000000개가 생기는 것이고, 후자의 경우 길이가 1000인 배열이 11 * 1000 = 11000개가 생기는 것이다. 또한, 파이썬에서 arr 타입의 경우 원소를 저장할때마다 바로 옆 주소에 저장을 하게 된다. 하지만 배열끼리는 그렇지 않기 때문에 탐색할 배열의 개수가 많아질수록 옆 주소에서 찾을 수 있는 내부 원소를 탐색하는 시간보다 먼 주소에 저장되어있는 배열을 탐색하는 시간이 클 수밖에 없다.
이를 이용해 두 개의 코드를 제출한 결과 밑의 코드(가장 큰 길이의 차원을 가장 오른쪽에 놓는 코드)가 위의 코드보다 시간 및 메모리 성능이 좋은 것을 확인할 수 있었다.
메모리 저장 방식에 대해서는 CS를 공부하면서 본 적이 있었지만, 문제를 풀면서 이를 연관지어 생각할 생각은 못했다. 결과적으로 문제의 원인은 같은 곳을 다시 탐색하지 않도록 예외 처리를 해야하는데 이를 적절하게 하지 못해서 생긴 문제였지만, 이 문제를 통해 CS의 중요성을 다시 깨닫는 계기가 되어 좋았다.
📖 Learning Point
- 코드를 짜면서 성능 개선을 할 수 있는 방법이 있는지 꾸준히 고민하는 것이 중요하다는 생각이 들었다.
- CS 공부를 단순히 암기방식으로 하는 것이 아닌 어떻게 적용할 수 있는지를 생각하며 공부함으로써 평소에 이를 적용할 수 있도록 해야겠다.
- 코드 예외 처리에 신경을 더 써 실수를 줄여야겠다.
