[자료구조] 배열

선형적인 자료구조 배열에 대해 정리

배열

• 메모리 공간 기반의 연속적인 방식의 가장 기본이 되는 자료형

• 파이썬의 동적 배열 자료형 : 리스트

  • Cpython의 내부 구현을 보면, 배열의 정해진 공간보다 추가적으로 원소가 들어오면 조금씩 용량을 늘린다.
  • 정적 배열과 달리 크기를 지정할 필요가 없다.
  • 크기가 꽉 차면 새로운 메모리 공간에 더 큰 크기의 배열을 할당하고 기존 데이터를 복사하는 작업이 필요해서 O(n)의 비용이 발생한다.

Python code 예시

• Link
• 두 수의 합
• 빗물 트래핑
• 투 포인터로 합 계산
• 짝수합
• 자신을 제외한 배열의 곱
• 주식을 사고팔기 가장 좋은 시점

Reference

• 파이썬 알고리즘 인터뷰 (박상길 지음)