Array

색인(Index)을 이용한 자료 저장&접근법 이다.

쉽게 이야기하면 선형으로 길게 이어지는 자료들의 집합이다. 아래는 배열의 예시이다.

JavaScript에서의 배열 선언

const menu = ['pizza', 'pasta', 'hamburger', 'icecream', 'chocolate'];

메모리 관점에서의 배열

휘발성(Volatile) vs 비휘발성(Non-Volatile)

메모리는 2가지가 있다. 휘발성(Volatile) vs 비휘발성(Non-Volatile)

• 휘발성 메모리: 컴퓨터를 재시작하면 데이터가 사라진다. → RAM
• 비휘발성 메모리: 컴퓨터를 재시작해도 데이터가 사라지지 않는다. → HD

프로그램에서 모든 자료들은 RAM에 저장된다. RAM은 말그대로 **Random Access Memory* 이기 때문에 읽고 쓰기가 하드 드라이브(HD)보다 빠르기 때문이다.

메모리의 랜덤 접속

예를 들어, 아래와 같은 박스 그룹을 메모리라고 한다면 각각의 박스에 자료를 저장할 수 있다.

각각의 박스들에는 이름이 있는데 이를 Memory Address 라고 한다.

• Memory Address 01 번에 자료 1 을 저장한다면

  1(저장됨)			5
  			6
  		hi
  				me
  hello

• Memory Address 04 번에 자료를 가져온다면 바로 가져올 수 있다.(1~4번 순서대로 찾지 않고)

  1			5(가져옴)
  			6
  		hi
  				me
  hello

메모리에서 배열을 다루는 원리

컴퓨터는 배열의 길이를 알려줘야 예약&할당을 한다.

• 배열의 길이는 4이고 메모리에 할당하려 한다.(아래와 같이)

  | pizza | pasta | hamburger | icecream | | — | — | — | — |

• 컴퓨터는 배열의 길이(4)를 기억하고 메모리에 예약&할당을 한다. (아래와 같이 16~19번에 배열의 값이 할당되었다.)

  1			5
  			6
  		hi
  pizza	pasta	hamburger	icecream	me
  hello

참조(Reference) 하다.

주소보다 조금 더 포괄적인 표현으로 자료에 접근 할 수 있게 해주는 값이다.

예를 들어, a=1 이라고 할 때

1. 메모리에 할당된다.
2. a를 불러온다.
3. 메모리는 a 가 가리키는 메모리 주소(Memory Address)로 접근 한다.
4. 결과적으로 a는 1이 저장된 메모리 주소를 이야기한다.

a는 1이 저장된 메모리 주소의 참조이다.

때문에 정확한 표현은 아래와 같다.

• a는 1이다 → X
• a는 1을 가리킨다 → O

배열의 색인(index)을 참조하다.

배열이 저장된 메모리 주소는 색인을 참조한다. 참조된 색인을 이용하여 배열의 자료를 불러올 수 있다.

특정 요소의 메모리 주소를 구하는 방법은 아래와 같다.

**<메모리 주소> = <시작 메모리 주소> + <요소의 크기> * <색인>**

C언어를 예로 들어, 아래와 같은 menu 라는 배열이 있다.

*C언어의 경우 배열 각각의 요소는 4Byte에 크기를 갖는다.

메모리에 값을 저장하는데 1000번의 주소로 시작한다면

메모리 주소의 참조 값은 아래와 같다.

배열 다루기

1. 읽기(Reading)

배열의 요소를 읽는다.

아래 배열의 pizza를 읽으려면 0번 색인을 읽으면 된다.

컴퓨터는 배열이 어디서부터 시작하는지 알기때문에 연산시간은 O(1)이다. (색인은 메모리 주소의 참조이다.)

2. 검색(Searching)

찾고자 하는 자료가 배열에 어디에 있는지 그리고 존재하는지 모르기 때문에 각각의 요소를 확인해야 한다. 때문에 시간복잡도는 O(N)이다.

예를 들어, 메모리 또한 주소가 있어 접근할 수 있지만, 그 박스를 열어야 알 수 있다.

Random Access가 있어 빠르고 쉽게 접근할 수 있지만, 그 값은 알 수 없다.

즉, 값을 찾기 위해 선형 검색(Linear Search)을 해야한다.

상황별 예시

• 값이 첫번째 색인에 있다.
• 보통의 경우 찾으려는 값은 중간에 있다.
• 운이 나쁠경우 값이 마지막에 있다.
• 최악의 경우는 찾으려는 값이 존재하지 않다.

3. 쓰기(Insert)

예를 들어, 5개 길이를 가진 배열을 메모리에 예약 후 할당했다. 하지만 이 배열에 아래와 같이 4개의 자료만 들어있다.

| pizza | pasta | hamburger | icecream | | | — | — | — | — | — |

이 배열에 potato라는 자료를 추가한다면 3가지 상황이 있다.

• 좋은 상황은 배열 마지막 요소에 자료를 추가한다.(절차를 한 번만 수행하면 된다)

  색인	0	1	2	3	4(마지막 요소)
  자료	pizza	pasta	hamburger	icecream	potato(추가됨)

• 보통의 상황은 중간에 추가하는 것이다. 새로운 요소를 추가하기 위해 이전 요소들을 움직여 주어야 한다.

  색인	0	1	2	3	4
  자료	pizza	pasta	potato(추가됨)	hamburger	icecream

• 최악의 상황은 배열 첫번째에 추가하는 것이다.

  색인	0	1	2	3	4
  자료	potato(추가됨)	pizza	pasta	hamburger	icecream

핵심은 요소를 어디에 추가할 것인지이다.

더 최악의 상황은 배열이 꽉 차있지만 새로운 자료를 추가해야 하는 상황이다. 이럴 경우 추가된 길이를 가진 새로운 배열을 예약&할당하고 이전 배열 요소들을 복사해야 한다.

삭제(Delete)

삭제 또한 추가와 마찬가지로 배열의 요소를 움직여주어야 한다.

• 좋은 상황은 마지막 요소를 삭제하는 것이다. 마지막 요소만 삭제하는 것이기 때문에 절차를 한 번 수해하면 된다.

  색인	0	1	2	3	4
  자료	pizza	pasta	hamburger	icecream	potato(삭제됨)

• 보통의 상황은 중간에 있는 자료를 삭제하는 것이다. 이 경우 빈 자리를 매꾸기위해 앞에 있었던 요소들을 움직여 주어야 한다.

  색인	0	1	2	3	4
  자료	pizza	pasta	hamburger(삭제됨)	icecream(2번 색인으로 이동)	potato(3번 색인으로 이동)

• 최악의 상황은 첫 번째 요소를 삭제하는 것이다. 나머지 요소들을 하나씩 움직여주어야 한다.

  색인	0	1	2	3	4
  자료	pizza(삭제됨)	pasta(이동)	hamburger(이동)	icecream(이동)	potato(이동)

요약하면 다음과 같다.

• 배열을 읽는 것은 랜덤 접속이 가능하기 때문에 매우 빠르다. 시간복잡도는 O(1)이다.
• 배열 찾는 것은 느리다. 선형 또는 이진 검색을 해야하기 때문에 시간복잡도는 O(N)이다.(이진 검색의 경우 O(Log N))
• 배열을 추가하거나 삭제하는 것은 느리다. 보통의 경우 추가 혹은 삭제 후 배열을 움직여 주어야한다. 때문에 배열의 마지막 요소에 작업하는 것이 좋다.