Data Structure - Array
Array
배열은 가장 대표적인 자료구조 중 하나이므로 잘 알아두자!!!
Python에서 Array 역할을 하는 것은 List이다.
정밀히 말하면 Array와 List는 같지 않다. 만약 python에서 Array를 사용하고자 한다면 Array 모듈을 import 해주어야 한다.
Array는 논리적 저장순서와 물리적 저장순서가 같다.
그렇기 때문에 Index를 이용해서 요소에 접근할 수 있다.
인덱스를 이용한 슬라이싱도 가능하다.
모든 요소가 Index를 가지기 때문에 시간 복잡도는 O(1)이 된다. 그러므로 요소에 대한 접근이 빠르다.
하지만 요소에 대한 추가, 또는 삭제가 발생할 경우는 이야기가 달라진다.
만약 중간에 위치의 요소를 삭제하거나, 추가하는 경우라면 배열은 논리적 위치와 물리적 위치가 같다는 특성 때문에 위치를 변화 시켜 주어야 한다.
그러므로 한칸씩 앞을로 당기거나 뒤로 밀려 나야하는 추가적인 작업(expensive operation)이 필요하다.
그러므로 원하는 인덱스에 찾아가는 것은 O(1)이나 추가적인 작업의 시간 복잡도는 O(n)이 된다.
또한 Array의 경우 초기 선언시, 순차적으로 저장되는 구조이기 때문에, 어느정도의 크기를 자동으로 설정한다. 이를, pre-allocation이라고 한다. 그렇기 때문에 설정한 크기 이상의 데이터가 들어갈 경우 다시 크기를 늘려 주어야 한다. 많은 프로그램언어에서 이러한 Resizing을 자동적으로 지원하고 있으나, 데이터의 사이즈가 급격히 늘어나는 상황에서는 Array를 사용하는 것은 효율적이지 않다.
언제 사용하는가?
-
데이터를 순차적으로 저장하는 경우
-
인덱스를 이용한 접근이 필요한 경우
-
데이터에 대한 추가 및 삭제가요없는 경우
-
다차원 데이터를 다루는 경우
배열과 리스트
데이터를 나열하고, 각 데이터에 인덱스번호가 있느 자료 구조이다.
파이썬의 경우 리스트, list(), [ ] 가 배열 자료구조를 제공한다.
같은 종류의 데이터를 순차적으고 효율적으로 관리하기 위해서 배열을 사용한다.
배열은 인덱스 번호가 있으므로 인덱스 번호를 이용해서 배열의 각 요소에 접근할 수 있다.
배열은 인덱스를 이용해 각 요소에 접근이 빠르다는 장점이 있지만
추가, 삭제가 어렵다는 단점도 있다.
파이썬의 리스트의 경우 리스트안의 요소는 데이터타입에 상관없이 담을 수 있다.
# 리스트를 이용한 배열
lst = [1,2,3,4,5]
arr =[1,"hi",True,3.14]
# 인덱스를 이용한 접근
lst[0] => 1
lst[3] => 4
arr[2] =>True
# 중첩리스트
arr = [[1,2,3][4,5,6]]
arr[0][2] => 3
arr[0][1] => 2
arr[0][0] => 1
arr[1][0] => 4
arr[1][1] => 5
arr[1][2] => 6단어배열이 주어졌을떄 배열안에서 a의 개수를 구하는 알고리즘을 구현해보자.
words = [
"apple",
"append",
"cat",
"banana"
]
word_a_count = 0
for word in words:
for index in range(len(word)):
if word[index] == 'a':
word_a_count +=1
print(word_a_count)
count =0
for i in range(len(words)):
if "a" in words[i]:
count = count + words[i].count("a")
print(count)
참고
https://www.fun-coding.org/Chapter04-array-live.html
배열은 가장 대표적인 자료구조 중 하나이므로 잘 알아두자!!!
