Static Array(정적 배열)정의

  • 정적 배열은 고정된 크기의 연속적인 메모리 공간을 뜻한다
  • 한 번 크기를 정하면, 중간에 늘리거나 줄일 수 없다

Dynamic Array(동적 배열 = Python의 리스트)

  • python에서 사용하는 리스트는 동적배열이다
    • 크기를 미리 정의하지 않고, 마음껏 늘릴 수 있는 배열이란 뜻

동작방식

  • 내부적으로는 정적 배열을 사용
  • 공간이 부족하면 더 큰 정적 배열을 만들고 복사
  • 보통 2배 크기로 확장해서 복사 비용 줄임(이걸 amortized O(1)이라고 한다)

시간 복잡도

작업 예시 시간복잡도
끝에 추가 a.append(x) 평균 O(1), 가끔(용량 초과 시) O(n)
끝에서 제거 a.pop() O(1)
중간 삽입 a.insert(2, x) O(n)
중간 삭제 del a[2] O(n)
값 접근/변경 a[i], a[i] = x O(1)
값 검색 x in a O(n)
길이 확인 len(a) O(1)


Strings(문자열)

  • python의 문자열은 immutable(불변) 객체다
    • 한 번 만들어진 문자열은 수정이 불가하다는 뜻
s = "hello"
s[0] = "H"  # 에러!

# 문자열 조작 > 새로운 문자열을 만들어야 함
s = "hello"
s = s + "!"  # hello!

시간 복잡도

작업 설명 시간복잡도
인덱스 접근 s[i] O(1)
값 변경 불가능 불가
값 추가 새 문자열 만들어야 함 O(n)
포함 확인 "e" in s O(n)
길이 확인 len(s) O(1)

CODE

# 리스트 생성
a = [1, 2, 3]

# 끝에 추가
a.append(4)

# 끝에서 제거
a.pop()

# 중간 삽입
a.insert(1, 99)

# 값 변경
a[0] = 42

# 값 접근
print(a[2])  # 인덱스 2의 값

# 포함 여부
print(99 in a)  # True or False

# 길이
print(len(a))  # O(1)

정리

구조 크기 조절 수정 가능? 삽입/삭제 접근 속도 대표 언어
Static Array 불가능 가능 느림 (O(n)) 빠름 (O(1)) C, Java 등
Dynamic Array 가능 가능 위치 따라 O(1)~O(n) O(1) Python (리스트)
String (Python) 불가능 불가능 모두 O(n) O(1) Python