[자료구조] Data structure

자료구조(Data Structure)는 컴퓨터 과학 분야에서 사용되는 도구들 중 하나로, 우리가 다양한 종류의 데이터를 효율적으로 저장하고 다룰 수 있도록 도와주는 개념입니다. 데이터를 컴퓨터에 저장하는 것은 일상적인 과제 중 하나입니다. 그러나 어떻게 데이터를 구성하느냐에 따라 프로그램의 성능, 효율성, 그리고 메모리 사용 등이 크게 영향을 받습니다. 이때 자료구조는 마치 데이터를 정리정돈하는 도구 같은 역할을 합니다.

 

간단한 비유로 설명하자면, 자료구조는 데이터를 담는 상자나 정리된 체계로 생각할 수 있습니다. 예를 들어, 책을 정리하는 방법에 따라 책장에 배열할 수도 있고, 스택처럼 쌓아둘 수도 있습니다. 

이런 정리 방식에 따라 책을 찾거나 추가하는 데 걸리는 시간이나 효율성이 달라집니다. 즉, 책을 어떻게 정리할 것인가에 대한 것은 자료구조라 말할 수 있고 책을 효율적으로 신속하게 찾는 '방법'에 관한 것이 바로 알고리즘입니다. 이렇게 자료구조와 알고리즘은 긴밀한 관계를 이루고 있습니다. 

 

---

 

 

 

자료구조와 메모리 구조는 서로 깊게 연관되어 있습니다. 프로그램이 실행될 때, 데이터를 효율적으로 저장하고 접근하기 위해 메모리를 어떻게 구성하느냐가 프로그램의 성능에 영향을 미치기 때문입니다. 프로그래머가 작성하는 코드는 컴퓨터의 하드디스크에 저장이 됩니다. 그리고 CPU가 프로그램을 실행할 때, 하드디스크에서 램으로 데이터가 올라가게 됩니다. 우리의 관심사는 '램에서 어떻게 데이터를 효율적으로 적재 및 관리할 것인가'에 있습니다. 만약 비효율적인 자료구조로 데이터가 저장이 되면 컴퓨터의 성능이 급격하게 저하되기 때문입니다.

 

RAM(랜덤 액세스 메모리)에서는 전기 신호를 사용하여 데이터를 저장합니다. 이러한 메모리 셀은 트랜지스터와 커패시터로 구성되어 있습니다.

 

• 트랜지스터 (Transistor): 트랜지스터는 전기 신호를 사용하여 데이터를 읽거나 쓸 수 있는 반도체 디바이스입니다. 하나의 트랜지스터는 오직 0과 1만 인식할 수 있습니다. 그래서 트랜지스터 하나를 '1 bit'라고 부릅니다. 
• 커패시터 (Capacitor): 커패시터는 전하를 저장하는 디바이스로, 트랜지스터와 함께 사용됩니다. 트랜지스터가 데이터를 나타내는 비트를 유지하거나 변경하기 위해 커패시터는 전하를 축적하거나 방출합니다.

전원이 꺼지면 데이터가 손실되기 때문에 RAM은 일시적인 데이터 저장에 주로 사용되며, 컴퓨터가 꺼지거나 다시 시작되면 RAM에 저장된 내용은 초기화됩니다.

 

 

메모리 주소

넓은 메모리 공간에서 사용자가 원하는 데이터를 찾기 위해서는 주소가 필요합니다. 메모리 주소는 컴퓨터의 주기억장치(메모리)에서 각각의 데이터가 위치한 물리적인 주소를 나타냅니다. 이 주소를 통해 프로세서는 데이터에 접근하고 조작할 수 있습니다. 메모리 주소는 보통 16진수로 표현되며 논리 주소와 물리 주소로 구분됩니다.

 

 

1) 논리 주소(Logical Address): 프로세스가 실제로 사용하는 주소. 프로세스는 이 주소를 사용하여 데이터에 접근하지만, 실제 메모리에 있는 물리 주소와는 다를 수 있습니다.

2) 물리 주소(Physical Address): 실제 메모리 모듈이나 칩에서 해당 데이터의 물리적인 위치를 나타내는 주소. 메모리 관리 장치(Memory Management Unit, MMU)는 논리 주소를 물리 주소로 변환하여 실제 데이터에 접근합니다.

일반적으로 32비트 또는 64비트 아키텍처의 컴퓨터에서는 32비트 또는 64비트 길이의 메모리 주소를 사용합니다. 32비트 아키텍처에서는 2^32 (약 4GB) 개의 주소를 나타낼 수 있고, 64비트 아키텍처에서는 2^64 개의 주소를 나타낼 수 있습니다.

 

 

메모리 할당

메모리 할당은 컴퓨터 시스템에서 프로세스나 프로그램이 실행될 때, 그에 필요한 메모리 공간을 할당하는 과정을 의미합니다. 메모리 할당은 운영체제에 의해 관리되며, 효율적인 메모리 사용을 위해 여러 전략과 알고리즘이 적용됩니다.

 

 

일반적으로 메모리 할당의 세 가지 방식

1. 정적 할당(Static Allocation): 컴파일 타임에 프로그램의 크기와 데이터 구조가 결정되고, 이에 따라 고정된 메모리 공간이 할당
2. 동적 할당(Dynamic Allocation): 프로그램이 실행 중에 동적으로 메모리를 할당하고 해제합니다.
3. 가상 메모리 할당(Virtual Memory Allocation): 프로세스는 자신만의 가상 주소 공간을 가지며, 실제 물리 메모리와는 분리된 가상 메모리를 사용합니다. 이를 통해 각 프로세스는 더 큰 메모리 공간을 사용하는 것처럼 보일 수 있습니다.

운영체제는 가상 메모리를 물리 메모리에 매핑하며, 필요에 따라 페이지 교체 등을 통해 효율적인 메모리 관리를 수행합니다.

메모리 할당은 다양한 알고리즘과 전략을 사용하여 최적화됩니다. 예를 들면, First Fit, Best Fit, Worst Fit과 같은 할당 알고리즘이 있으며, 가상 메모리에서는 페이지 교체 알고리즘 등이 사용됩니다. 이러한 알고리즘과 전략은 메모리의 효율성, 공간 활용, 응답 시간 등을 최적화하기 위해 사용됩니다.

 
자바에서는 Collections Framework라는 자료 구조와 알고리즘을 제공하는 라이브러리를 제공합니다. 이는 데이터를 저장하고 처리하는데 사용되는 표준화된 클래스와 인터페이스들로 이루어져 있습니다.

 

 

 

---

[출처] Youtube, 개발남노씨, 메모리구조 | 자료구조 2강, https://youtu.be/JHxY08iENxs?si=xEFHTZuF8eaYjiqc