Array 배열 기초개념

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

실제 시간을 측정하는 것이 아니라 1초 1분단위가 아니라 얼마나 많은 "단계(steps)"가 있는가로 측정

어떤 오퍼레이션이 5개 단계만 요구된다면 20개 단계보다 훌륭한 알고리즘

단계(steps)에 관한 것. 초/분이 아님.

2가지 메모리
volatile(휘발성 메모리) vs non-nolatile(비휘발성 메모리)

비휘발성메모리는 하드디스크 같은 것 컴퓨터 꺼도 안사라짐
휘발성메모리는 RAM 끄면 초기화
프로그램이 돌아가고 변수 생성할때 RAM에 저장 
Random Access Memory

RAM에서 읽는 게 하드에서 읽는 것보다 빨라
왜냐면 이름에 적혀있는 것처럼 데이터 접속을 랜덤으로 할수있다.
RAM을 박스 그룹이라고 상상
박스들은 데이터를 저장. 박스의 이름은 Memory Address
프로그램이 RAM 메모리에게 메모리주소 2로 가주세요
하면 RAM이 바로 빠르게 접속할 수 있다.
랜덤하게 접속이 가능하니까
5번으로 가주세요 했을 때
1번, 2번, 3번 순차적으로 가는 게 아니라 즉각 5번으로 접속 가능

메모리 관점에서 Array(배열)은 어떤 모습일까?
배열을 만들 때 이게 얼마나 긴 지를 설명해야해
내 배열은 4개 박스만큼 길어
그 공간을 미리 예약/할당해줘
메모리 안에서 박스들이 나란히 위치할 수 있게 말이지
컴퓨터는 이 배열이 얼마나 긴 지를 기억하고
최대 길이가 어느정도인지 알고 어디서 시작하는지 알고 있어
JS, Python 기반이라면 몰랐을 것. 배열 길이 주고 뭐 할 필요 없어
JS, Python이 우리 대신 핸들링해주기 때문
그 때문에 너의 프로그램이 느려질 수도 있다.
직접 핸들링해야하는 c와 비교해서
자세히 배열의 길이를 알려줘야 함.

1.Reading
배열은 0부터 인덱싱
즉 위치만 알면 배열의 데이터에 접속할 수 있다.
4개의 요소(element)가 있는 배열이 있다고 하자.
컴퓨터는 0부터 숫자를 셈
배열 1번,첫번째 요소를 얻고 싶으면 인덱스 0번을 달라고 하면 됨.
배열에서 읽어내는 건 겁나 빠름.
컴퓨터는 배열이 어디서 시작하는지를 알고있으니까
많은 자료를 읽어야한다면 배열이 짱
Random Access덕분
배열이 얼마나 긴지 중요하지 않음
인덱스에서 요소를 읽어내는 속도는 동일

2.Searching
시간이 좀 걸려. 왜냐면 검색은 읽는 거랑 쫌 달라
데이터를 읽을 때는 그냥 값(피자)을 얻으면 됨.
검색을 할 때는 해당 값(피자)이 배열에 있는지 없는지 몰라
어디에 있는지도 모름
그래서 검색을 해야하는 것
불행하게도 하나하나 다 뒤져야 함
메모리는 마치 데이터를 넣은 박스 같은 것 
하지만 박스들이 열려있지 않아. 
주소가 있어서 접근 할 수 있지만
그 박스를 열어야 값을 볼 수 있어 
랜덤 엑세스가 있어서 박스를 쉽게 접근할 수 있는데
박스 안의 값은 모르는 상황
배열에서 값을 찾으려면 열어보고 맞는지 체크하는 과정을 하나씩 거쳐야해
인덱스 첫번째에 있다면 금방 찾을 것 그러나 보통은 중간에 있을 거고 처음부터 차근차근 열어야한다 내가 찾는 아이템이 인덱스 맨 마지막에 있는 경우
처음부터 끝까지 몽땅 열어봐야하니까 
그보다 안좋은 경우 없으면 첨부터 끝까지 다 찾아봐야함
이런 걸 Linear Search(선형검색)
순서대로 0부터 끝까지 차근차근 찾는 것
배열 검색을 빠르게 하는 다른 방법도 있다.
배열안에서 검색은 그닥 빠르지 않다

3.Insert(Add) Insert 배열에 쓰기
세가지 경우
배열을 만들 때에는 메모리 공간을 미리 확보해야 함.

어디에 토마토를 추가할지가 시나리오들
마지막에 추가할거라면 쉬워
근데 중간에 넣는다면 하나씩 뒤로 옮겨야
배열 제일 앞에 넣는 게 최악 전부 옮겨야 함 큰 배열이면 더 안좋아

또다른 안좋은 경우는 추가할 자리가 없는 경우
새배열 만들고 이전 배열을 복사하고 새로 추가해야함.
요소 복사하고 시간 오래 걸려

4. Delete삭제
삭제는 배열에 뭔가를 추가하는 것과 비슷
배열을 이리저리 움직여야함
제일 끝에 껄 삭제하면 쉽지
컴퓨터는 배열이 어디서 시작하고 얼마나 긴지 기억하니까
배열 마지막으로 이동해서 삭제하는 건 넘나 쉽다.
보통의 시나리오는 배열 중간 요소를 삭제할 때
삭제하면 가운데 공백 생겨
배열엔 공백이 있으면 안되서 뒤에꺼 옮겨
첫번째 요소 삭제하면 모든 값들이 한칸씩 움직여야해서
올라ㅏㄱ가락 움직이는 건 몇천개있는 상태에선 정말 조심해야함

배열은 읽을때 정말 빠르고 랜덤으로 접근 가능하니까
검색 추가 삭제할 때 느림
배열에서 추가하고 삭제하고 싶은 상황이라면 
배열의 맨 끝에서 작업하는 걸 강력 추천
가장 빠르니까
중간 혹은 맨 처음 값을 움직이게 되면 그 때 좀 느리게 됨
어느위치에서 검색, 추가, 삭제해도 속도가 빠른 데이터 구조가 있어 

 

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