[Algorithm & Data Structure] Array

// "Normad Coder의 알고리즘과 데이터 구조 강의" 듣는 중//

​

time complexity, 시간복잡도

• 데이터 구조의 오퍼레이션 또는 알고리즘이 얼마나 빠르고 느린지 측정하는 방법.
• 초나 분같은 실제 시간 단위의 측정이 아님.
• 얼마나 많은 단계step이 있는 지로 측정하는 것. so, 단계가 적을수록 빠름!

만약 어떤 오퍼레이션이 5단계만 요구되면, 20단계가 요구되는 알고리즘보다 훌륭한 것. ​

 

meomory 메모리 관점에서 데이터를 보자.

• 2종류.
• volatile(휘발성) vs. non-volatile(비휘발성) 메모리

1. non-volatile(비휘발성) 메모리: 하드 드라이브 같은 것. 껐다가 켜도 데이터가 계속 있음.
2. volatile(휘발성) 메모리: 램(RAM, random access memory). 껐다가 키면 다 사라지는 것. 프로그램이 돌아가고 변수가 생성될 때 모두 램에 저장됨. 램에서 데이터를 읽는 것이 하드 드라이브에서 읽는 것보다 빠름. 데이터를 순서대로 읽는 것이 아닌 "랜덤"하게 원하는 것부터 임의로 읽을 수 있기 때문.

​

• 메모리 관점에서 배열 --> 배열을 만들 때 얼마나 긴지(length)를 설명해줘야 함. 그래서 그 공간을 예약/할당 할 수 있도록.
• so, 컴퓨터가 배열의 최대 길이를 알고 어디서 시작하는 지 알고 있음.
• 그러니까, 연결된 메모리 공간을 사용하므로 빈칸이 없도록 데이터를 유지해야 함.

--> js. python 몰랐을 것... 둘이 알아서 해 주거든... 근데 그러면 C같이 직접 다뤄줘야 하는 것에 비해서 느려짐.

• 메모리를 데이터를 넣는 박스들이 쭉 나열된 것으로 생각하면 됨. (table처럼)

 

---

operation1. reading

• 어떻게 배열을 읽는 가?
• 0부터 인덱싱을 하기 때문에 위치만 알면 배열 데이터에 접속 가능
• 만약 4개 요소가 있다면, "pizza"는 인덱스 2 호출하면 됌.

element	"pasta"	"ice cream"	"pizza"	"rice"
memory address	001	002	003	004
index	0	1	2	3

• 많은 데이터를 읽어야 되면, array가 최고임. 젤 빠름.
• 컴퓨터가 배열이 어디서 시작하는 지 아니깐. 배열이 얼마나 긴지 상관없이 스텝은 같기에 요소를 읽는 속도가 동일함.

​

operation2. searching

• 하나하나 값이 맞는지 체크해야 해서 시간이 조금 더 걸림.
• 읽는 것은 그냥 값(피자)을 얻으면 됌.
• 검색은 값이 있는 지 없는지, 어딨는지 모름. 그래서 하나하나 다 살펴야 하지만, 메모리 주소는 있는 데 상자가 안 열려 있어서 하나하나 열어서 확인해야함.
• 랜덤 엑세스로 쉽게 메모리에 접근은 할 수 있지만, 값(value)을 모르는 상황.
• 선형 검색 linear search: 순서대로 0부터 끝까지 찾는 것. 최고는 제일 처음 확인하는 것. 중간도 괜춘 but, 만약 인덱스 마지막에 찾는 게 있거나, 없으면 엄청 오래 걸림
• 다른 종류도 있음.

​

operation3. insert (add)

• 3개 시나리오.
• 배열을 만들때는 메모리 공간을 미리 확보해서, "이건 5개 아이템 길이다" 같이 말해줘야 함.
• 예, 4개 요소만 있어서 1개 더 추가 해도 갠춘. 근데 어디에 추가 할 거냐.

element	"pasta"	"ice cream"	"pizza"	"rice"	​
memory address	001	002	003	004	​
index	0	1	2	3	​

• 예를 들어 위의 배열에 토마토를 어디에 넣을 건지.

1. 맨 마지막에 넣는 것이 가장 최고.
2. 보통은 중간에 추가하는 것. 아이스 크림 옆에 넣으려면 피자와 밥을 옆으로 옮겨야 중간에 넣을 수 있음.
3. 최악은 토마토를 맨 앞에 추가하는 것.. 그러면 다 뒤로 하나씩 빼야 함. 배열의 크기가 정말 크다면.. 최악임. 또, 공간이 꽉 찼는데 넣어야 하는 경우가 생길 수도. 미리 공간을 5개만 생성해놨는데 하나나 더 넣어야 하면,, 큰 공간을 따로 만들고 배열을 복사하고 등등 시간이 오래 걸림

​​

operation4. delete

• 배열 추가랑 비슷해서 배열을 이리저리 움직여야 함.
• 3개 시나리오.

1. 맨 마지막을 삭제하는 것이 가장 최고. 젤 빠름. (컴퓨터는 어디서 시작하고 얼마나 긴 지 알고 있으니까)
2. 보통은 중간을 삭제하는 것. 아이스 크림을 지우면 피자와 밥을 앞으로 옮겨서 공백 채워야 함.
3. 최악은 맨 앞을 삭제하는 것.. 그러면 다 앞으로 하나씩 땡겨야 함. 배열의 크기가 정말 크다면.. 최악임.

​​

• 즉 배열은 읽을 때는 엄청 빠름 랜덤 접속이 가능하기 때문에. but, 검색, 추가, 삭제 시 조금 느려짐.
• 그러니깐, 배열은 그냥 맨끝에서 3개 작업할 것. 그러나, 어느 지점에서 추가, 삭제 해도 빠른 데이터 구조가 있고, 또 검색 속도가 빠른 알고리즘도 있음.