[CS/Computer Science][자료구조/Data Structure] 배열

지난 포스팅에서는 프로그래밍을 하면서 판단할 수 있는 알고리즘 성능의 척도인 시간복잡도 및 공간복잡도에 대하여 알아보았습니다.

이번 포스팅에서는 7가지 핵심 자료구조 중 하나인 배열에 대해 알아보겠습니다.

1. 배열

1.1 배열이란

일정한 메모리 구조를 차지하는 여러 요소들이 순차적으로 나열된 자료구조

• 각 요소는 0부터 시작하는 고유한 순서 번호인 인덱스(index)가 매겨짐
• 인덱스를 활용한 연산
  • 인덱스를 통해, 요소에 접근하는 시간 - 요소의 갯수와 무관하게 일정 (Time Complexity: $O(1)$)
  • 인덱스를 통해, 요소를 수정하는 시간 - 동일하게 일정($O(1)$)
  • 인덱스를 통해, 요소를 찾는 시간 - 앞에서 부터 차례로 탐색(순차적 검색) (Time Complexity: $O(n)$)
  • 인덱스를 통해, 요소를 추가 혹은 삭제하는 시간 - 추가 / 삭제 이후 요소의 재정렬이 필요함 (Time Complexity: $O(n)$) ⇒ 배열은 가장 기본적인 자료 구조인 만큼 그 활용도가 매우 높음
• 데이터 관리 및 다른 자료구조 & 알고리즘 구현
  
  

1.2 배열의 차원

1차원 배열: 한 쪽 방향으로 요소가 나열되는 배열

• 행 (dim=0) 2차원 배열: 2개의 인덱스로 요소 식별
• 행 + 열 (dim=0, 1) 3차원 배열: 3개의 인덱스로 요소 식별
• 행 + 열 + 깊이 (dim=0, 1, 2)
  
  

1.3 정적 배열 및 동적 배열

1. 정적 배열(static array)
   • 프로그램 실행 전, 배열의 크기가 고정되어 있는 배열
   • 실행 도중 배열의 크기를 바꿀 수 없음
2. 동적 배열(dynamic array, 벡터)
   • 실행 과정에서 크기가 변할 수 있는 배열
   • 프로그램 실행 전 배열의 크기를 알 수 없는 경우 사용
     
     

이어서 다음 포스트에서는 연결 리스트에 대해 알아보도록 하겠습니다.