[코딩테스트 ALL IN ONE] 자료구조와 메모리구조 이해하기

자료구조 : 데이터를 저장하고 관리하는 방식

그렇다면, 데이터를 저장하는 곳은? → 메모리

 

메모리는 크게 하드디스크와 RAM 메모리가 있다.

우리가 코딩을 하고 저장하면 코드들이 하드디스크에 저장된다. 저장된 코드들을 실행하면 RAM 메모리에 데이터가 올라가게 된다.

 

우리의 관심사는 RAM 메모리에 있다.

만약 비효율적인 자료구조를 사용하면 RAM 메모리 낭비를 초래하고 프로그램 성능 저하의 원인이 된다.

그래서 용도와 상황에 맞는 자료구조를 잘 선택해야한다.

 

나중에 배울 자료구조 중, LIST를 잠깐 보자.

LIST: 숫자나 문자와 같은 데이터를 순차적으로 나열해 놓은 집합

L,I,S,T를 각각 하나의 문자형 데이터라고 생각하자.

 

 

L,I,S,T를 Array로 구현한다면 데이터가 메모리상에 연속되게 저장이 된다.

 

 

Linked List로 구현 : 메모리상에 불연속적으로 저장되지만, 다음 데이터의 위치를 가리킴으로써 연속성을 유지할 수 있다.

 

 

이런 메모리적 차이로 인해 장단점이 뚜렷하다.

Array : 데이터 접근이 쉽다.

Linked List : 데이터 추가, 삭제가 쉽다.

이처럼 메모리에 대한 이해가 있으면, 자료구조를 더 쉽게 배울 수 있다.

 

 

# RAM

전기신호를 저장할 수 있는 트렌지스터라고 하는 작은 반도체 소재로 이루어져있다. 트렌지스터에 전기가 on되면 1, off되면 0을 나타낸다. 이를 이용해서 binary Digit, 즉 2진수를 나타낼 수 있다. 이를 bit라고 한다.

1bit는 두 가지의 숫자를 나타낼 수 있다. : 0, 1

2bit : 4(2의 2승)가지의 숫자를 표현할 수 있다. 00, 01, 10, 11

 

8bit = 1byte라고도 한다.

1byte(8bit)는 2의 8승 가지의 상태를 나타낼 수 있다.

 

이처럼 컴퓨터는 2진법을 사용하기 때문에 제대로 알고 넘어가야 한다.

 

 

2진법과 16진법이 있다.

2진법 : 앞에 '0b'를 붙여준다. 16진법 : 앞에 '0x'를 붙여주어 구별을 한다.

8자리 2진수는 0부터 255숫자까지 표현할 수 있다. 000000(0) ~ 11111111(255)

ex: 217은 2진수로 표현하면 11011001로 표현할 수 있다.

만약 숫자가 엄청 크면, 2진법으로 표현하기 힘들어진다. 그래서 16진법도 종종 사용한다.

16은 2의 4승. 즉, 2진수 4개를 16진수 하나로 표현할 수 있다.

1101 → 13 / 1001 → 9

오른쪽 변환표기법을 사용하여 16진수로 표현해보면, 13은 D, 9는 9로 변환 가능.

 

217이 10진법, 2진법, 16진법 이렇게 다양하게 표시된다.

 

 

데이터의 기본단위인 bit와 byte를 알게되었으니, 본격적으로 실제 우리 컴퓨터의 RAM이 얼마만큼의 bit를 저장할 수 있는지 한번 보자.

노트북 RAM 메모리는 1MB라고 가정해보자.

1byte가 1024(2의 10승)개 모이면 1KB가 된다.

1024byte === 1KB

 

1KB가 1024개 모이면 1MB가 된다.

1024KB === 1MB

즉, 1MB는 2의 20승 byte와 동일하다.

1MB === 1024(2의 10승)KB === 1024*1024(2의 20승)byte

 

 

 

이 넓은 메모리공간 속에서 컴퓨터가 데이터를 찾으려면 어떤 지표가 있어야한다. 그래서 하나하나 byte마다 주소값을 달아놨다. (10진법으로 표현하기에는 너무 길어지기 때문에 16진법으로 표시를 할 예정.)

 

# 메모리 할당

c언어에서는 정수를 저장하는 int 데이터타입이 있다.

int는 메모리에서 4byte를 차지하게 된다. (옆 주소는 임의로 달아놓았다.)

price라는 int형 변수를 선언하고, 여기에 290,000,000을 저장해보겠다.

int price = 290,000,000;

 

290000000을 binary(2진법)로 변환하면 이렇게 된다.

그리고 이 2진수가 메모리상에 4byte에 걸쳐서 할당된다.

 

 

 

그럼 문자는 어떻게 표현할까?

컴퓨터는 숫자밖에 저장을 할 수 없다. 그래서 문자를 숫자로 표현하기로 국제적으로 규약을 맺었다. 이를 ASCII code(아스키 코드)라고 하고, 128개의 문자를 숫자와 1:1 매칭을 하였다.

문자를 표현하는 char 데이터타입 === 1byte

만약 변수에 문자 'A'를 저장한다면, 메모리에는 숫자 65가 저장된다.

Q. 그러면 65를 저장할때도 int 데이터타입과 같이 4byte? → char는 1byte. 그래서 ASCII코드를 찾아보면 255까지만 있다.

 

 

# LIST는 과연 어떻게 메모리 할당을 할까?

List를 구현하는 방법은 Array와 Linked List가 있다.

 

Array

Array는 메모리상에서 연속적으로 할당된다.

만약 1,2,3,4 int형 변수 4개를 묶어서 저장하고 싶다면, 이렇게 배열을 선언할 수 있다.

하나하나가 int형 변수이기 때문에 각각 4byte씩, 총 16byte의 메모리를 차지한다.

 

 

메모리에서 연속적으로 할당하기 위해, 16byte 메모리에 1,2,3,4를 2진법으로 저장한다.

 

 

각 데이터는 가장 작은 address를 대표 address로 설정한다.

 

Linked List

Array와는 다르게, 메모리 상에 불연속적으로 저장된다. 값만 저장한다면 1 다음 값이 무엇인지 알 수 없다. 그래서 다음으로 나올 값의 address도 같이 저장한다. 이렇게 서로 연결하면 연속성을 보장할 수 있다.

이렇게 값과 address를 묶어서 저장한 구조체를 Node라고 부른다.

address의 메모리는 항상 4byte를 저장한다고 가정해보면, 하나의 node당 메모리는 8byte가 된다.

8byte each(value + address)

 

메모리상에 불규칙하게 할당되어 있지만, 다음 주소값이 적혀있기 때문에, 연결된 채로 연속성을 유지할 수 있다.

 

메모리구조를 잘 이해하면 추후에 자료구조를 공부할 때 큰 도움이 된다.

 

 

**모든 내용은 메모리구조 | 자료구조 2강이 출처입니다.

https://www.youtube.com/watch?v=JHxY08iENxs