목표
- 배열의 특징을 안다
- 배열을 조작하는 방법을 안다.
배열(Array)
정의
배열(Array)이란 하나의 변수에 여러 값을 저장하기 위해 연속된 메모리 공간을 차지하는 정적(Static)인 자료구조이다.
개요
배열은 여러 값을 저장하기 위해 메모리의 연속적인 공간을 차지하고 있다. 연속적인 공간 다음의 공간이 비어있을지는 알 수가 없으므로, 안정성을 위해 배열(Array)의 크기는 생성할 때 정해지며 배열의 크기를 늘리거나 줄일 수 없다. 우리는 이를 정적(Static)이라고 부른다.
예를 들어 아래의 코드를 실행할 시, 메모리에 그림1과 같이 올라간다.
val stringArray: Array<String> = arrayOf("a", "b", "c")
val intArray: Array<Int> = arrayOf(1, 2, 3, 4)
*Kotlin에서는 Primitive Type에 대한 생성도 지원하지만, 여기서는 설명을 위해 모두 arrayOf로 array를 생성한다.
*Kotlin에서는 식에 대해 컴파일 시 타입 추론이 가능하므로 타입 생략이 가능하지만, 이해를 위해 같이 쓴다.
특징
접근
Array는 연속적인 공간을 차지하므로, 특정한 특정한 위치의 변수에 대한 Random access가 가능해 접근에 대한 속도가 빠르다. 찾고자 하는 원소의 위치만 안다면 O(1)의 시간 복잡도로 접근이 가능하다.
val stringArray: Array<String> = arrayOf("a", "b", "c")
stringArray[1] // "b"특정 원소 접근에 대한 시간 복잡도 : O(1)
검색
크기 N의 배열에서 검색을 하기 위해서는 O(N)의 시간 복잡도가 필요하다. 처음부터 하나하나 확인을 하며 찾아가야 하기 때문이다.
val stringArray: Array<String> = arrayOf("a", "b", "c")
for (string in stringArray) {
if(string == "c")
println("c is in the array")
}
코틀린에서는 검색을 위한 다양한 함수를 제공해준다. 하나하나 확인하면서 즐거움을 느끼도록 하자.
stringArray.forEach {
if(it == "c")
println("c is in the array")
}검색에 대한 시간 복잡도 : O(N)
추가
배열(Array)는 기존 공간을 사용하면서 크기를 늘리는 것이 불가능하다. 연속적인 공간을 차지하기 때문에 다음 공간이 비어있을지 알 수 없기 때문이다.
기존 공간을 사용하지 않고 복사를 통해 크기를 늘리는 것은 가능하다. 기존 Array의 크기만큼에 추가할 값 만큼의 크기를 잡은 후, 기존 Array를 복사한 후 추가할 값을 추가하면 되기 때문이다.
val stringArray1: Array<String> = arrayOf("a", "b", "b", "c")
val stringArray2: Array<String> = arrayOf("e", "f")
val addedArray = stringArray1 + stringArray2
크기가 N인 Array와 M인 Array를 합치기
시간 복잡도 : O(N+M)
공간 복잡도 : O(N+M)
크기가 N인 Array에 1개 요소를 더하기
시간 복잡도 : O(N)
공간 복잡도 : O(N)
삭제
배열(Array)는 기존 공간을 사용하면서 크기를 줄이는 것 또한 불가능하다. 중간에 값이 비게되면 연속성이 파괴되기 때문이다.
따라서 Array를 줄이기 위해서는 기존에 사용하던 메모리 공간을 사용하지 않고 새로운 메모리 공간을 사용해 크기를 줄여야 한다. 즉 Array를 새로 만들어야 한다.
따라서 크기가 N인 Array에서 하나의 값을 빼기 위해서는 O(N) 의 시간 복잡도와 공간 복잡도가 필요하다.
크기가 N인 Array에서 하나의 값을 빼기
시간 복잡도 : O(N)
공간 복잡도 : O(N)
