[컴퓨터 구조 & 알고리즘] 컴퓨터의 기억장치와 공간복잡도

* 이 글은 이것 저것 공부하면서 줍줍한 내용들을 종합 정리하기 위한 글이다.

기억장치(Memory)

간단한 컴퓨터 구조

: 컴퓨터는 기억장치에 원하는 데이터를 저장하여 읽기/쓰기를 할 수 있다. 데이터는 많이 저장해둘 수록 유용하겠지만 공강 자원은 유한하고, 읽기/쓰기에도 시간이 소요된다. 크게는 RAM과 ROM으로 구분한다.

RAM과 ROM

알고리즘에서 공간복잡도를 따지는데 메모리는 유한하기 때문에 시간복잡도와 마찬가지로 프로그래밍을 할 시 신경써야 하는 부분이다.

그렇기 때문에 필요한 데이터만 효율적으로 저장/관리하는 것도 컴퓨터 공학의 중요한 내용이다.

1. 주기억장치(Main Memory, RAM)

: 알고리즘과 자료구조에서 공간복잡도를 따질 때, 프로그램이 수행되는 동안 연산에 직접적으로 사용되는 주기억장치 영역인 Ram(Random Access Memory)이다.

Ram에는 프로그램 내부에서 선언된 변수와 실행과 연산에 필요한 정보들이 저장되게 되며 계산을 위해 읽는 파일의 내용 또한 주 기억장치에 저장된다. 또한 프로그램 실행과 함께 메모리에 정보들이 적재되지만, 프로그램을 종료하면 적재된 데이터가 사라지는 휘발성 메모리이다.

Cache Memory와 CPU Register 또한 프로그램 수행에 직접적으로 관련된 공간이지만 원칙적으론 직접 내용을 조작할 수 없기 때문에 공간복잡도에 크게 영향을 끼치지 않는다.

---

2. 공간복잡도(Space Complexity) : 데이터 저장과 연산을 위해 할당한 크기가 클 수록 많은 메모리를 사용하게 되는데, 시간 복잡도와 마찬가지로 알고리즘이 할당하고 소모하는 공간의 크기를 나타내는 방식을 공간 복잡도라 한다.

즉, 처리하는 데이터 크기에 대해서 프로그램의 순간 혹은 최대의 메모리 사용량을 나타내는 지표이다.

불필요한 메모리는 선언을 하지 않거나, 할당된 메모리를 해제함으로써 메모리의 순간 사용량을 낮출 수 있다.

JAVA인 경우 JVM이 이 메모리를 자동으로 조절해주지만, C나 C++은 개발자가 직접 메모리를 동적 메모리 할당 혹은 메모리 해제 등을 통해 관리할 수 있다.(그래서 숙련된 개발자들은 C나 C++이 더 하이퀄리티 언어라고 한다.)

장시간 수행되는 프로그램에서 고려해야할 점은,

• 얼마 동안 사용되지 않을 예정인지
• 할당 해제해두면 얼마나 여유 메모리를 확보할 수 있는지
• 할당 해제한 데이터를 다시 복구하는 데에 얼마나 큰 비용이 드는지
• 메모리 누수가 발생하지 않는지

등등을 고려해야 한다.

짧은 시간 수행되는 알고리즘 문제와 같은 프로그램에서 고려해야할 점은, 현재 계산에 필요한 정보들을 얼마나, 어떤 형태로 저장해 두어야 효과적인지 고려해야한다.

• 저장하기에 공간이 충분한지
• 저장함으로써 얻은 성능상의 이득이 큰지
• 저장한 데이터를 원하는 방식으로 가공 혹은 검색하기 용이한지
• 현재 시점에 사용할 수 있는 최대의 메모리 크기를 초과하지 않는지

등등을 고려해야 한다.

---

알고리즘 문제를 풀 때 수행 시간과 함께 메모리 크기의 한계를 설정하는 경우를 많이 보았을 것이다.

Time Over나지도 않았고, 논리적으로 오류 혹은 런타임, 컴파일 오류가 생기지도 않았는데 에러로 알고리즘이 통과되지 않은 경우가 몇 있었을 것이다.

그것은 공간복잡도가 복잡해서 생겨나는 해프닝이다.

그럴 때 내가 사용한 자료구조가 적절한지, 적절하지 않았다면 해당 문제에 따라 고려해야할 점은 무엇인지(검색이 빨라야 하는제 삽입 삭제를 고려해야하는지 등등) 등을 생각하고 그에 맞게 자료구조를 활용해야 할 것 이다.

그러기 때문에 컴퓨터 프로그래밍을 공부할 때 알고리즘만 생각해서 될 것이 아니라 자료구조, 컴퓨터 구조 등등을 비롯한 전산학 개념을 모두 가지고 있어야 한다.