2021년 8월 2일 - 배열 Array

● 본 공부와 기록은 유튜버 '노마드 코더 Nomad Coders' 님의 "Array 배열 기초개념? 10분안에 정리해줌!"을 기본으로 하였다.

→ https://www.youtube.com/watch?v=NFETSCJON2M&list=PL7jH19IHhOLMdHvl3KBfFI70r9P0lkJwL&index=3 

 

☆ 시간복잡도 Time Complexity란?

→ 시간복잡도는 데이터 구조의 오퍼레이션 혹은 알고리즘이 얼마나 빠르고 느린지 측정하는 방법이다.

→ 실제 '초/분' 시간을 측정하는 것이 아니라 얼마나 많은 '단계Steps'가 있는지로 측정한다.

ex) 같은 작업에 A 오퍼레이션이 5단계 요구되는 알고리즘이 B 오퍼레이션이 20단계를 요구하는 알고리즘보다 훌륭한 알고리즘이다.

• O(1) : 상수복잡도. 처리해야하는 변수의 갯수와 상관없이 처리 시간이 동일
• O(n) : 선형복잡도. 처리해야하는 변수의 갯수가 늘어나는만큼 처리 시간이 비례해 증가

 

---

 

☆ 메모리 관점에서 배열이 어떻게 보이는지 생각해보자

 

→ 메모리에는 2가지 종류가 있다.

• 휘발성volatile 메모리
• 비휘발성non-volatile 메모리

→ 비휘발성 메모리란 '하드 드라이브'와 같다.

→ 컴퓨터를 껐다 켜도 하드 드라이브의 데이터는 그대로이다.

 

→ 휘발성 메모리란 'RAM 메모리'와 같다.

→ 컴퓨터를 껐다 키면 모든 데이터가 사라지며, 처음부터 다시 시작하게 된다.

→ 프로그램이 돌아가고 변수를 생성할 때, 이것들은 모두 'RAM(Ramdon Access Memory)'에 저장된다.

→ 따라서 데이터 접속을 랜덤으로 하기에 RAM에서 데이터를 읽는 것이 하드 드라이브에서 읽는 것보다 빠르다.

→ 이걸 이해하기 위해서는 RAM을 데이터를 보관할 수 있는 박스 그룹이라고 생각해보자.

 

 

→ 박스에는 고유의 이름이 존재하는데, 이걸 Memory Address라고 한다.

→ 프로그램이 RAM 메모리에 2번으로 가달라고 부탁할 경우, 랜덤하게 접속이 가능하기에 RAM이 빠르게 접속이 가능하다.

ex) Memory Address 005번으로 가고 싶다고 할 경우, 바로 이동할 수 있다.

→ 1, 2, 3번을 순차적으로 가는 것이 아닌, 즉각 5번으로 접속이 가능하다.

 

---

 

☆ 배열 Array이란?

→ 가장 기본이 되는 데이터 구조이다.

→ Array의 배열은 다음과 같은 오퍼레이션이 존재한다.

• Read
• Search
• Add
• Delete

→ 메모리 관점에서 배열을 만들 때, 컴퓨터에게 메모리의 길이가 얼마나 긴지 설명해야 한다.

 

→ 배열의 길이가 특정 크기만큼 길다고 할때, 그 공간을 미리 예약/할당해준다.

→ 메모리 안에서 박스들이 나란히 위치할 수록 있도록 말이다.

→ 컴퓨터는 이 배열이 얼마나 긴지를 기억하고, 최대 길이가 어느 정도인지 알고 어디서 시작하는지 알 수 있다.

→ JS나 Python은 배열 길이를 주는 등의 작업을 우리 대신 핸들링해주기에, 이 배열이 얼마나 긴지 생각할 필요가 없다.

→ 허나, 이에 대한 대가로, 직접 사용자가 전부 핸들링(자세히 배열을 알려주어야 함)해야하는 C와 비교해 컴퓨터가 느려질 수 있는 것이다.

 

---

 

☆ Operation : Reading

→ "어떻게 배열을 읽는가?"의 문제이다.

→ 배열은 0에서부터 인덱싱을 한다.

→ 즉, 위치만 알면 배열의 데이터에 바로 접속할 수 있다는 것이다.

 

ex) 배열에서 pizza를 얻고 싶다면, 컴퓨터에게 index 2번의 값으로 가달라고 하면 된다.

→ 따라서 배열에서 Reading Operation이 매우 빠른 것이다.

→ 컴퓨터는 어디서부터 배열이 시작하는지 알고 있기에, 많은 자료를 읽어야 한다면 배열이 최선의 선택이다.

→ 이것은 Random Access 덕분이다.

→ 배열이 얼마나 긴지 상관없이, 인덱스에서 요소를 읽어내는데 걸리는 시간복잡도는 O(1)로 동일하다.

→ 따라서 배열의 요소가 5개든 100개든 스텝은 동일하다.

 

 

---

 

☆ Operation : Searching

→ 배열에서 Searching Operation은 시간이 제법 소요된다.

→ 데이터를 Reading 할때는 단순히 값을 얻으면 된다.

→ Searching 할때는 해당 값이 배열에 있는지 없는지, 어디에 있는지도 알지 못하는 상태이다.

→ 그렇기에 메모리의 상자 하나하나를 전부 다 뒤져야한다.

→ 이 박스들은 열려있지 않고 주소가 있어 접근할 수는 있으나, 그 박스를 열어야 값을 볼 수 있다.

→ 랜덤 엑세스가 있기에 박스에 쉽게 접근할 수 있는데, 박스의 값은 무엇인지 모르는 상황이다.

→ 이 말인 즉슨 배열에서 내가 원하는 값을 찾으려면 배열의 아이템을 하나하나 열어보고 맞는지 체크하는 과정을 반복해야한다.

 

ex) 내가 pizza의 값을 원할 경우 0번을 열어보고, 1번을 열어보고, 2번을 열어보고 드디어 pizza를 찾을 수 있다.

→ 따라서 Reading보다 Searching이 시간이 많이 소요되는 편이다.

 

 

➀ Best Scenario

→ 만약 내가 찾는 아이템이 인덱스 첫번째에 있다면 순식간에 찾고 끝난다.

 

 

➁ Normal Scenario

→ 내가 찾는 아이템이 배열 중간에 있는 경우이다.

→ 처음부터 차근차근 열어서, 중간에 찾는 경우가 된다.

 

 

➂ Bad Scenario

→ 내가 찾는 아이템이 인덱스 맨 마지막에 있는 경우이다.

→ 처음부터 끝까지 몽땅 열어봐야한다.

 

 

➃ Worst Scenario

→ 최악의 경우는 내가 찾는 아이템이 인덱스에 없는 경우이다.

→ 처음부터 끝까지 찾아야 하고, 시간이 오래 걸릴 것이다.

→ 이를 'Linear Search 선형검색'이라고 한다.

→ 순서대로 0부터 끝까지 차근차근 찾는 것으로, 시간복잡도는 O(n)이다.

→ 결과적으로 배열안에서 검색은 그다지 빠르지 않다.

 

---

 

☆ Operation : Insert [Add]

→ 배열을 만들때는 메모리 공간을 미리 확보해놓아야 한다.

 

→ 위의 경우엔, 아이템이 5개라고 얘기를 해주어야 한다.

→ 이런 배열이 존재할 때, 꽉 차이지는 않았고 대략 4개의 아이템만 있는 상황이다.

 

→ 이 배열에 '토마토'를 추가하고 싶다면, 미리 공간을 확보해 놓았으니 공간 걱정은 하지 않아도 된다.

→ 시나리오는 결국, "어디에 토마토를 추가할 것인가"이다.

 

 

➀ Best Scenario

 

→ '토마토'를 배열 맨 끝에 추가하는 경우이다.

→ 컴퓨터는 배열이 어디서 시작하고, 얼마나 긴지 기억하므로 그냥 배열의 맨 끝으로 이동해서 토마토를 추가하면 된다.

→ 이 경우, 매우 빠른게 작업이 완료된다.

 

 

➁ Normal Scenario

 

→ 토마토를 배열의 중간에 추가하는 경우이다.

→ 내가 토마토를 아이스크림 옆에 추가하고 싶을 경우, "potato"를 일단 오른쪽으로 옮기고, "pizza"도 오른쪽으로 이동해야해야 토마토를 추가할 공간이 생기게 된다.

 

 

➂ Worst Scenario (1)

 

→ 토마토를 배열 맨 앞으로 추가하는 경우이다.

→ 배열에 있는 모든 아이템들을 움직여야만 한다.

→ 배열의 크기가 크다면, 그 모든 것을 전부 움직이는데 엄청난 시간이 소요된다.

 

➃ Worst Scenario (2)

 

→ 이미 공간이 꽉 찬 배열에 새 값을 추가하는 경우다.

→ 배열은 정해진 길이가 존재하고, 만들때 해당 공간을 미리 할당하게 되어있다.

 

→ 만약 5개의 정해진 공간에 그 이상의 아이템을 입력할 경우, 더 큰 배열을 만들어 이전 배열을 복사하고 그 다음에 새로 추가해야한다.

→ 이 경우, 요소를 복사하는데 시간이 소요된다.

 

---

 

☆ Operation : Delete

→ 삭제는 배열에 뭔가 추가하는 것과 비슷하다.

→ 배열을 이리저리 움직여야하기 때문이다.

 

 

➀ Best Scenario

→ 배열의 마지막 요소를 삭제하고 할 때이다.

 

→ 그냥 삭제하면 된다.

→ 컴퓨터는 배열이 어디서 시작하고, 얼마나 긴지 기억하기 때문이다.

→ 따라서 마지막 배열로 이동해서 삭제하는 건 너무나도 간단한 일이다.

 

 

➁ Normal Scenario

→ 배열의 중간 요소를 삭제해야 할 때이다.

 

→ 이 경우, 중간에 공백이 생기게 된다.

→ 배열에 공백이 있으면 안되니까 그 공백을 채우기 위해서 모든 배열의 값들이 움직여야 한다.

 

 

➂ Worst Scenario

→ 배열의 첫번째 요소를 삭제할 경우이다.

 

→ 첫 번째 배열의 공백을 메우기 위해서 모든 값들이 한칸씩 움직여야한다.

→ 이 경우, 시간이 소요된다.

→ 이렇게 배열에서 오락가락 움직이는 것은 아이템 수가 적으면 큰 문제가 되지 않는다.

→ 허나, 몇 천개의 아이템이 존재하는 상황이라면 그땐 문제가 된다.

 

---

 

☆ 정리

→ 배열은 데이터를 읽을 때Reading는 랜덤으로 접속이 가능해서 매우 빠르다.

→ 그러나 검색Searching, 추가Inserting[Adding], 삭제Deleting 할 때는 상황에 따라 제법 시간이 소요된다.

→ 만약 배열에서 추가, 삭제하고 싶은 상황이라면, 배열의 맨 끝에서 작업하는 걸 가장 추천하는 바이다.

→ 중간 혹은 맨 처음 값을 움직이게 되면, 이때는 시간이 걸리게 된다.