배열의 가장 기초를 먼저 알아봅니다.
데이터가 많아지고 그룹관리의 필요에 따라 사용한다.
0부터 시작하는 index를 사용하여 순차적으로 번호를 지정할 수 있다.
배열의 크기가 정해져있어 어디서 시작되는지와 최대 길이를 알 수 있다.
번호를 지정해주는 index와 value(각각의 값)를 합쳐서 element(요소)라고 한다.
- read
- search
- add
- delete
이해를 위해 체크하고 넘어가봅시다!
시간복잡도란?
데이터 구조의 오퍼레이션(연산) 혹은 알고리즘이 얼마나 빠르고 느린지를 측정하는 방법이다.
실제 시간 측정이 아닌, 얼마나 많은 단계가 있는지를 측정하는 것!
같은 작업 시 적은 단계일수록 좋다는 것!
- Big O란?
시간복잡도를 간단하게 표현한 것이다.
빠르고 느리다는 것은 시간에 따른 것이 아닌, 완료까지 걸리는 절차의 수를 뜻한다.
선형검색(0부터 끝까지 찾는 검색법) 알고리즘은 n 스텝이 요구된다. = O(N) 으로 표기
BigO에 대해서는 제일 마지막에 좀 더 추가해봐야겠다.
메모리 - 데이터를 넣은 박스같은 것
- 휘발성 메모리(volatile) : RAM 같음 -> 컴퓨터 재부팅 시 사라지고 처음부터 다시 시작
- 비휘발성 메모리(non-volatile) : 하드 드라이브 같음 -> 컴퓨터 재부팅 시 메모리가 그대로
RAM (휘발성 메모리)
Random Access Memory
하드 드라이브보다 읽는게 빠르다.
데이터 접속이 랜덤으로 가능하다.
이 표를 보며 자세히 알아봅시다!
| 서울 | 인천 | 김포 | |
|---|---|---|---|
| memory address | 001 | 002 | 003 |
| index | 0 | 1 | 2 |
1. Read (장점)
배열은 index를 사용하여 0부터 읽힌다.
즉, 위치만 알면 배열의 데이터에 접속 가능하다.
배열의 읽는 속도는 빠르다. (컴퓨터는 배열의 시작점을 알고 있기 때문)
많은 자료를 읽을 때 좋다. (Random Access 덕분)
배열의 길이는 속도와 관계가 없다.
왜??? 인덱스에서 요소(element)를 읽어내는 속도는 동일하기 때문이고 이는 단계가 동일한 것이라!!!
ex)
--> 인덱스 1번은 인천!
2. Searching (단점)
해당 value의 존재 유무와 위치를 모른다.
결국 하나하나 찾아내야 되기에 시간이 오래걸린다.
Random Access와 memory address를 이용한 접근은 가능하지만 그 value는 모르는 것이다.
선형 검색(Linear Search) - 순서대로 0부터 끝까지 찾는 방법.
!!!!!!!배열의 단점 중 하나인 검색 시간을 단축시키기 위한 검색법이 있다고?!!!!!!
- 이진 검색(Binary Search) 알고리즘
많은 검색이 필요할 때 사용하면 적절!
정렬된 배열(value가 순서대로 정렬한 상태)에서만 사용 가능하다.
정렬된 배열에서 검색할 때는 일반 배열에서 검색 시 보다 비교도 못 할 만큼 빠르다.
--> 반으로 나눈다고 생각하면 쉽다. 배열의 길이를 알고 있기 때문에 배열의 절반!부터 검색을 시작한다.
반, 반의반, 반의반의반 식으로 반복하며 진행된다.
정렬된 배열에 value 추가 시에는 일반 배열보다 시간이 더 걸린다. 작은 수에서 큰 수로 정렬해뒀는데 7이 끼려고 하는데 3이 뒤에 있어서는 정렬된 배열이 깨지기 때문!!
3. Insert (Add) (단점)
배열을 만들 떄에는 미리 메모리 공간 확보가 중요하다.
배열의 길이를 알려줘야한다.
새로운 value를 배열 중간에 추가 시 그 뒤 value는 뒤로 밀리게 된다.
ex)
--> 인천과 김포 사이에 제주라는 value를 넣을 경우에는, 김포가 뒤으로 한 칸 밀리게 된다.
--> 제주라는 value를 맨 앞에 넣을 경우, 모든 value가 뒤로 한 칸 밀리게 된다.
하지만!!! 위 표처럼 꽉 찬 경우에 추가가 된다면,
이전 배열을 복사 후 더 긴 새로운 배열에 추가해줘야한다.
4. Delete (단점)
배열에 value 추가와 비슷하다.
배열의 중간에는 공백이 있으면 안된다.
배열의 중간 value를 삭제하면 그 뒤에 있는 value들이 다 앞으로 한 칸 당겨져야한다.
좀 더 구체적으로 Big O란?
항상 선호되는 알고리즘 먼저 예시와 함께 보자.
1. O(1)
def print_first(arr):
print(arr[0])arr = array, 배열
arr[0] = array 중 index 0 즉 첫번쨰 element를 print하라는 함수다.
--> 배열 길이가 n까지 있어도 스텝은 동일한(이 함수에서는 단 1번) 것이다. 이것은 상수 시간(constant time)이라고 할 수 있다.
이 함수를 그래프(x축이 input, y축이 time)로 보자면 ㅡ 형태가 될텐데, 이는 O(1)이다.
그럼 함수를 조금 다르게 고친 뒤 시간복잡도는??
def print_first(arr):
print(arr[0])
print(arr[0])이 함수는 index 0를 2번 프린트하게 되는 것, 끝내기 위해서는 2개의 스텝이 필요하다.
그래도 O(1)이다.
--> 왜???? Big O는 함수의 디테일에는 관심이 없고 상수(constant)도 신경을 안 쓴다. 항상 200개의 스텝이 필요한 함수라고 쳐도 인풋 사이즈와 관계없이 200개 스텝이 필요하다고 해도 O(1)이 되는 것이다. 인풋 사이즈가 증가한다고 해도 시간은 균일하기 때문에, 여전히 상수 시간(constant time)이니까!
2. O(N)
그럼 이번에는 다른 시간복잡도를 알아보자
def print_all(arr):
for n in arr:
print(n)위는 각 아이템을 다 프린트하는 함수이다.
배열 사이즈가 10이면 10, 100이면 100번의 스텝으로 작동하는 함수이다.-->선형검색과 비슷
이 함수를 그래프(x축이 input, y축이 time)로 보자면 / 형태가 된다.
이런 함수는 배열이 커지면 필요한 스텝도 같이 커진다. = O(N)
이런 함수들도 상수는 관련이 없다.
인풋 사이즈가 커짐과 같이 시간도 늘어난다는 그 사실만이 중요한 것이다.
즉
def print_all(arr):
for n in arr:
print(n)
for n in arr:
print(n)이게 O(2N)이 아니라 O(N)이라는 것!!
3. 2차 시간(Quadratic Time)
이는 중첩 반복이 있을 때 나타난다.
def print_twice(arr):
for n in arr:
for x in arr:
print(x,n)위 함수는 배열의 각 아이템에 대해 루프를 반복 실행한다는 뜻을 담고있다.
루프 안의 루프에서 실행된다는 결과를 갖는다.
따라서 시간복잡도는 인풋의 n^2이다.
선형 시간복잡도가 더 효율적인 것이다.(인풋에 비해 시간, 스텝이 많음)
4. 로그 시간(Logarithmic Time)
이는 이진 검색 설명 시 사용한다.
로그는 제곱의 반대이다.
로그는 해당 수를 해당 수로 몇 번을 나눠야 하는지에 대한 것이다.
시간복잡도는 O(log n)
간단하게 정리
배열은 읽을 때는 랜덤으로 접속이 가능하기에 무지하게 빠르다.
검색, 추가, 삭제 시에는 시간이 오래걸린다.
배열 상에서 추가나 삭제 시에는 배열의 맨 마지막에 하는 것을 가장 추천한다.
왜냐?! 그게 가장 빠르기 떄문이다.
검색을 할 떄는 이진 검색을 사용하는 방법도 좋겠다!!
배열에 대해 알아봤는데 읽는 것만이 장점이라 빠르게 읽어야 할 때 위주로 사용하게 될 것 같다. 추가나 삭제가 자주 필요한 상황에는 적절한 선택이 아닐듯한.. 다음 시간에는 배열의 단점이 장점인! 추가나 삭제 시 유용한 연결리스트(Linked list)에 대하여 공부하겠습니다!!
