배열(Array)

배열 (Array) 

◾ 같은 타입의 데이터를 하나의 묶음으로 나열한 선형 자료구조
◾ 연속된 메모리 공간에 순차적으로 저장함

◾ 배열의 크기가 고정되어 있고, 선언 시 배열의 크기를 정하고 이를 변경할 수 없음

 

 장점

1. 인덱스를 이용해 접근하기 때문에, 검색 성능이 좋음
2. 데이터의 크기가 확정적일 때 배열을 사용하는 것이 메모리나 처리속도 면에서 좋음

 

 단점

1. 자료의 삽입, 삭제에 비효율적
(삽입, 삭제가 이루어질 때마다 배열의 크기를 다시 지정하고 삽입, 삭제 수행해야 함)

2. 배열의 크기를 바꿀 수 없음
배열을 크게 잡을 경우 메모리 낭비

배열은 데이터가 정해져 있을 때, 데이터 삽입 삭제가 적은 경우, 검색 등 이러한 상황에서 쓰는 게 좋다.

 

시간복잡도

1. 삽입/삭제
배열의 맨 앞에 삽입/삭제하는 경우: O(n)
배열의 맨 뒤에 삽입/삭제하는 경우 : O(1)
배열의 중간에 삽입/삭제하는 경우: O(n)

2. 탐색 : O(1)

 

 백준 배열 # 10818 문제 풀이

# 10818 - 최소, 최대