자료구조(파이썬) - 배열 (Arrays)

교육 정보

• 교육 명: 경기미래기술학교 AI 교육
• 교육 기간: 2023.05.08 ~ 2023.10.31
• 오늘의 커리큘럼:
  파이썬 자료구조
  (7/31 ~ 8/18)
• 강사: 이현주, 이애리 강사님
• 강의 계획:
  1. 자료구조

자료구조

배열

• 배열

  • 가장 기본적인 자료 구조
  • 처음 선언할때 배열의 크기가 정해져있고 같은 타입의 자료형만 담을수 있음
  • 메모리(램)에 배열이 사용할 연속적인 공간을 할당
    • 모든 자료형이 같으므로 한 배열의 모든 인덱스에 대한 값이 가지는 메모리의 크기가 같음
      : i번 인덱스의 주소 = 배열의 시작 주소 + (자료형의 메모리 크기 * i)
      램은 임의 접근 메모리이므로 주소를 알면 어떤 값이든 O(1)에 접근 가능

• 동적 배열

  • 한번 선언하면 크기를 변경할 수 없는 배열의 단점을 극복하기 위해 내부적으로 배열을 사용하여 사용자 입장에서는 동적으로 크기가 변하는 것으로 보이는 배열
    • 동적 배열의 메커니즘
    1. 배열에 할당된 모든 메모리 사용 & 새로운 값 추가 시도 → 메모리의 다른 공간에 더 큰 공간 확보
    2. 확보한 공간에 원래 데이터 복사
    3. 새로운 데이터 추가
       → 파이썬의 리스트가 동적 배열
  • 동적 배열 맨 뒤에 값을 추가하는 연산의 복잡도
    • 공간이 있을 경우: O(1) (이미 알고있는 위치에 값 하나만 추가하면 되므로)
    • 공간이 없을 경우: O(n) (기존 값n개를 모두 복사해야 하므로)
      → 보통 복잡도는 보수적으로 표현하기 위해 최악의 경우로 표현하지만 위와같이 발생 빈도가 확연히 다른 경우는 이를 반영해주기도 함 (분할 생환 분석): 동적배열의 추가 연산을 분할 상환 분석을 하면 O(1)임
  • 동적 배열 중간에 앖을 추가하는 연산의 복잡도: O(n) (값을 삽입하는 자리 뒤의 모든 값을 한칸씩 이동해야 하므로)