[Python 자료구조] 배열 (Array)

배열이란?

CodeIt 자료구조 수업을 정리한 내용입니다.

배열

• 파이썬은 C를 기반으로 만들어졌고 C의 배열을 이용해서 만들어진게 파이썬 리스트
• C 배열은 크기 고정, 같은 데이터 타입만 가능
  • C 배열의 경우 데이터가 메모리에 연속적으로 저장
• 파이썬은 데이터가 연속적일수도 있고 아닌 아예 다른 곳에 저장될 수도 있음
  • 파이썬의 경우 메모리에 데이터의 주소값을 저장
  • 아무리 큰 값이어도 가리키기만 하는 역할이므로 C배열과 다르게 다양한 값 저장 가능
    • item_list = [10, "데이터", True, -4]

배열 인덱스 접근

찾고자 하는 위치의 주소(index)를 알고 있기에 시간복잡도는 O(1) 입니다.

배열 탐색

배열의 탐색은 특정 조건을 만족하는 값을 찾는 것을 말합니다.

예를 들어 하나의 배열에 특정 값이 존재하는지 아닌지 확인하는 것을 의미합니다.

결국 모든 길이의 값을 다 확인해야해서 접근보다 비효율적이며 모든 길이의 값이 N이라

할 때 N번을 확인해야함으로 시간복잡도는 O(n) 입니다.

정적 배열과 동적 배열

정적 배열

• 크기 고정 (데이터 갯수 제한)
• 추가하려고 할때 추가 공간이 사용해도 되는지에 대한 여부가 불확실
• 반대로 미리 많이 길이를 선언한다면 메모리 공간이 낭비가 됌

동적 배열

• 크기 변함 (데이터 갯수 추가 가능)
• 정적배열로 만들어진 자료구조
• 정적배열의 크기를 상황에 맞게 늘린 후 데이터를 추가, 이후 데이터가 다 차면 다시 크기 증가
• 파이썬의 리스트는 동적 배열

파이썬의 리스트

파이썬의 리스트는 내부적으로 길이가 어느정도 사용되고 있는지 모릅니다.

저장된 데이터는 5개라 해도 배열의 크기는 10일지 7일지 알 수가 없습니다.

따라서 len() 함수를 사용하더라도 데이터를 가리키는 메모리 공간이 있는 길이만 알려줄 뿐입니다.

배열의 추가 연산

Case 1 (최선)

• 정적 배열에 남는 공간이 있을 때
  • O(1)
• 자주 일어나는 케이스

Case 2 (최악)

• 정적 배열이 꽉 찼을 때
  • 현재 사용중인 배열의 크기보다 더 큰 메모리 공간을 예약
  • 기존 배열의 값 복사 (n번 -> O(n))
  • 새 값을 빈칸에 추가
• 가끔 일어나는 케이스

분할 상환 분석

연산을 n번 했을때 총 소요되는 시간 X를 n으로 나누는 개념입니다.

최악의 경우 시간복잡도를 이야기할 때 비합리적인 경우에 사용합니다.

최악의 경우 분석 vs 분할 상환 분석 어떤 것을 사용할까?

분할상황을 한다고 무조건 시간복잡도가 줄어드는 것은 아닙니다.

만약 최악의 경우보다 분할 상환 분석의 시간복잡도가 더 적다면, 분할 상황 분석을 사용합니다.

이 때문에 동적 배열의 끝에 데이터를 추가시 O(1) 이 걸린다 라고 표현되기도 합니다.

배열의 삽입 연산

아무 위치에 데이터를 더해줄 때를 말합니다.

추가와 다른점은 추가는 메모리의 가장 끝에 더해주지만 삽입의 경우는 위치와 무관하게 더해줄 수 있습니다.

삽입 연산의 시간복잡도는 O(n)입니다.

Case 1. 정적 배열에 남는 공간이 있을 때

• n번의 인덱스에 데이터를 추가시
  • 기존 배열의 위치를 뒤로 한칸씩 이동시킨 후 해당 공간에 추가
    • 0번의 인덱스에 더할때 최악 시간복잡도 O(n)

Case 2. 정적 배열이 꽉 찼을 때

• 현재 사용중인 배열의 크기보다 더 큰 메모리 공간을 예약
• 생성된 배열에 기존 데이터를 복사해서 저장 O(n)
  • 기존 배열의 위치를 뒤로 한칸씩 이동시킨 후 해당 공간에 추가
    • 0번의 인덱스에 더할때 최악 시간복잡도 O(n)

배열의 삭제 연산

삭제하고자 하는 인덱스의 데이터 값을 삭제합니다. 이후 중간에 있는 값을 삭제했다면

해당 삭제한 인덱스보다 큰 인덱스를 가진 값들을 한칸씩 앞칸으로 이동시켜 저장합니다.

Case 1. 맨 앞 데이터 삭제

• 최악의 경우는 맨 앞의 인덱스 값을 지우는 경우
  • 0번 인덱스 값을 지운 후 뒤에 모든 길이의 데이터 이동 필요 O(n)

Case 2. 맨 뒤 데이터 삭제

• 최선의 경우는 맨 뒤 인덱스 값을 지우는 경우
• 맨 뒤 삭제시 삭제 후 그대로 저장만 하면 종료 O(1)

동적 배열 크기 줄이기

동적배열은 내부적으로 정해진 크기의 정적 배열을 사용합니다.

이는 상황에 따라 늘리고 줄이고 할 수 있는 것을 말합니다.

줄이는 경우는 배열의 크기가 커서 자원의 공간을 낭비할 때 발생합니다.

배열의 크기를 늘리는 시점은 데이터가 꽉 찼을때 인데 반대로 줄이는 시점은 언제일까요?

크기를 줄이는 경우는 내부 배열의 데이터 공간 사용 비율이 특정 기준 이하일때 발생합니다.

개발된 환경에 따라 비율의 차이가 있고 줄일때에는 새로운 크기의 내부 배열을 만들고

기존의 값들을 복사하여 저장합니다.

분할 상황 분석

동적 배열에서 맨 끝 데이터를 삭제하는 연산은 최악의 경우 O(n)이 걸리지만,

분할 상환 분석을 적용하면 O(1)이라고 할 수 있습니다.

동적 배열 삭제

예를 들어 arr = [2,3,5,7] 이 있다고 했을때 동적 배열 인덱스 1을 삭제하고 싶습니다.

이때 인덱스 1에 5를 저장하고 인덱스 2에 7을 저장해 [2,5,7,7]로 값을 저장합니다.

이후 인덱스 3에 있는 7을 지우는게 아니라 인덱스 접근 범위를 0~2로 제한시켜버립니다.

접근할 수 없으니 실질적으로 삭제되었다라고 생각할 수 있는 것입니다.