[TIL] 자료구조 : 배열 (Array)

1. 배열 (Array) 이란?

---

• 메모리 상에 같은 타입의 데이터(원소)를 연속하게 배치한 자료구조
• 배열의 위치를 가리키는 인덱스(Index)와 구성하는 데이터 값인 원소(Element)로 구성
• 파이썬에서는 리스트 타입으로 배열을 쉽게 구현 가능.
• 같은 종류의 데이터를 순차적으로 저장하며, 효율적으로 관리하기 위해 사용
  
  

2. 배열의 특징

---

• 선형 자료구조 (같은 타입의 데이터를 여러개 나열함)

• 메모리 주소가 연속되어야 함 -> 따라서 배열의 크기를 늘릴 수 없다.

• 늘리고자 할 때엔 크기가 큰 새 배열을 만들고 기존 내용을 복사해야함.

• 추가적으로 소모되는 메모리(Overhead)가 거의 없다.

• 캐시 메모리 적중률 (Cache hit rate)가 높다.

• 장점

  • 인덱스를 통한 빠른 접근이 가능하다.
  • 연속적이므로 메모리 관리가 편하다.

• 단점

  • 한 데이터를 삭제해도 배열은 연속해야 하므로 공간이 남아 메모리가 낭비된다.
  • 미리 최대 길이를 지정 해야 함.(선언 시 크기를 정하면 고정됨)
  • 추가, 삭제가 어렵다.

3. 배열의 시간복잡도 (Big O)

---

1. 주어진 위치의 원소를 확인 또는 변경 하는 연산 : O(1)

2. 배열의 맨 끝에 원소를 추가/삭제하는 연산 : O(1)

3. 주어진 위치에 있는 배열의 데이터를 추가/삭제 하는 연산 : O(n)

   • 중간에 데이터를 삭제하거나 추가 시 기존에 있는 데이터를 한 칸씩 당기거나 밀어 주어야 하기 때문

4. 배열을 사용하면 좋은 경우

---

• 데이터 개수가 확실하게 정해져 있을 때
• 삽입/삭제 작업이 적을 때
• 배열에 저장된 데이터를 검색하는 작업이 많을 때

5. 예제

---

빈도 수 구하기

# 특정 문자 배열에서 알파벳 'e'의 등장 빈도 수 구하기

language = ['go','elixir','haskell','erlang','java','javascript','kotlin',
'lua','objectivec','perl','php','python','ruby','r','typescript','Visual Basic']

lang_count = 0
for data in language:
    for index in range(len(data)):
        if data[index] == 'e':
            lang_count += 1

print(lang_count) #7개

가장 긴 단어 구하기

la_vita = "Ma che cosa pretendiamo cosa ci aspettiamo Dalla vita."
arr = la_vita.split(" ")
maxLen = 0
result = []

# 가장 긴 단어의 길이 출력
for data in arr:
    if(len(data) > maxLen):
        maxLen = len(data)
print(maxLen) # 11

# 가장 긴 단어 출력
for index in range(len(arr)):
    if(len(arr[index]) == maxLen):
        result.append(arr[index])
print(result) # ['pretendiamo'] 

참고 자료 (Reference)

---

https://velog.io/@2seunghye/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EA%B3%BC-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EB%B0%B0%EC%97%B4
https://choheeis.github.io/newblog//articles/2020-12/data-structure-array
https://velog.io/@hanif/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%B0%B0%EC%97%B4
https://changun516.tistory.com/9
https://velog.io/@2seunghye/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EA%B3%BC-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EB%B0%B0%EC%97%B4