[Swift] Array에서 활용되는 함수들과 시간 복잡도

 

 

이미지를 클릭하시면 원본 페이지로 이동합니다!

 

 

Q. Swift의 Array에서 활용되는 함수 전체에 대하여 함수 이름, 시간 복잡도, 사용 예시로 나눠서 설명해 줘

 

A. Swift의 Array에서 활용되는 함수들은 크게 배열에 요소를 추가/제거하는 함수, 배열을 조작/검색하는 함수, 배열의 요소를 정렬하는 함수, 배열의 메모리를 관리하는 함수로 구분할 수 있습니다. 이번에는 이러한 카테고리로 나누어서 각 함수의 이름, 시간 복잡도, 사용 예시를 설명해드리겠습니다.

 

 

배열에 요소를 추가/제거하는 함수

 

1. append(_:)

- 배열의 맨 뒤에 요소를 추가합니다.

- 시간 복잡도: O(1)

var arr = [1, 2, 3]
arr.append(4)
// arr: [1, 2, 3, 4]

 

 

2. removeLast()

- 배열의 맨 뒤에 있는 요소를 제거합니다.

- 시간 복잡도: O(1)

var arr = [1, 2, 3]
arr.removeLast()
// arr: [1, 2]

 

 

3. popLast()

- 배열의 맨 뒤에 있는 요소를 제거하고 반환합니다.

- 시간 복잡도: O(1)

var arr = [1, 2, 3]
let last = arr.popLast()
// arr: [1, 2]
// last: 3

 

 

4. Insert(_: at:)

- 배열의 지정된 인덱스에 요소를 삽입합니다.

- 시간 복잡도: O(n)

var arr = [1, 2, 3]
arr.insert(4, at: 1)
// arr: [1, 4, 2, 3]

 

 

5. remove(at:)

- 배열의 지정된 인덱스에 있는 요소를 제거합니다.

- 시간 복잡도: O(n)

var arr = [1, 2, 3]
arr.remove(at: 1)
// arr: [1, 3]

 

 

6. removeAll()

- 배열의 모든 요소를 제거합니다.

- 시간 복잡도: O(n)

var arr = [1, 2, 3]
arr.removeAll()
// arr: []

 

 

 

 

배열을 조작/검색하는 함수

 

7. contains(_:)

- 배열에 지정된 요소가 포함되어 있는지 여부를 반환합니다.

- 시간 복잡도: O(n)

let arr = [1, 2, 3]
let hasTwo = arr.contains(2)
// hasTwo: true

 

 

8. dropLast(while:)

- 배열에서 지정된 조건을 충족하는 마지막 요소를 제외한 요소를 포함하는 시퀀스를 반환합니다.

- 시간 복잡도: O(n)

let arr = [1, 2, 3, 4, 5, 4, 3, 2, 1]
let result = arr.dropLast(while: { $0 >= 4 })
// result: [1, 2, 3, 4, 5, 4]

 

 

9. prefix(upTo:)

- 배열의 앞부터 지정된 인덱스 미만까지의 요소를 포함하는 새로운 배열을 반환합니다.

- 시간 복잡도: O(k)

let arr = [1, 2, 3, 4, 5]
let result = arr.prefix(upTo: 3)
// result: [1, 2, 3]

 

 

10. suffix(from:)

- 배열의 지정된 인덱스부터 끝까지의 요소를 포함하는 새로운 배열을 반환합니다.

- 시간 복잡도: O(k)

let arr = [1, 2, 3, 4, 5]
let result = arr.suffix(from: 3)
// result: [4, 5]

 

 

11. firstIndex(where:)

- 배열에서 지정된 조건을 충족하는 첫 번째 요소의 인덱스를 반환합니다.

- 시간 복잡도: O(n)

let arr = [1, 2, 3, 4, 5]
let index = arr.firstIndex(where: { $0 % 2 == 0 })
// index: 1

 

 

12. lastIndex(where:)

- 배열에서 지정된 조건을 충족하는 마지막 요소의 인덱스를 반환합니다.

- 시간 복잡도: O(n)

let arr = [1, 2, 3, 4, 5]
let index = arr.lastIndex(where: { $0 % 2 ==0 })
// index: 3

 

 

13. contains(where:)

- 배열에서 지정된 조건을 충족하는 요소가 있는지 여부를 반환합니다.

- 시간 복잡도: O(n)

let arr = [1, 2, 3, 4, 5]
let hasEven = arr.contains(where: { $0 % 2 == 0 })
// hasEven: true

 

 

14. allSatisfy(_:)

- 배열의 모든 요소가 지정된 조건을 충족하는지 여부를 반환합니다.

- 시간 복잡도: O(n)

let arr = [2, 4, 6, 8, 10]
let allEven = arr.allSatisfy({ $0 % 2 == 0 })
// allEven: true

 

 

15. reduce(into: _:)

- 배열의 요소를 지정된 초기 값으로 축소하고, 각 요소와 지정된 클로저를 사용하여 새로운 값을 생성합니다.

- 시간 복잡도: O(n)

let arr = [1, 2, 3, 4, 5]
let sum = arr.reduce(into: 0, { $0 += $1 })
// sum: 15

 

 

16. shuffled()

- 배열의 요소를 무작위로 섞은 새로운 배열을 반환합니다.

- 시간 복잡도: O(n)

let arr = [1, 2, 3, 4, 5]
let result = arr.shuffled()
// result: [4, 3, 2, 5, 1] (랜덤)

 

 

 

배열의 요소를 정렬하는 함수

 

17. sorted(by:)

- 배열의 요소를 지정된 비교 함수를 사용하여 정렬합니다.

- 시간 복잡도: O(n log n)

let arr = [5, 2, 4, 1, 3]
let result = arr.sorted(by: <)
// result: [1, 2, 3, 4, 5]

 

 

18. sorted()

- 배열의 요소를 기본 비교 함수를 사용하여 정렬합니다.

- 시간 복잡도: O(n log n)

let arr = [5, 2, 4, 1, 3]
let result = arr.sorted()
// result: [1, 2, 3, 4, 5]

 

 

19. partition(by:)

- 배열을 지정된 비교 함수를 사용하여 분할합니다.

- 시간 복잡도: O(n)

var arr = [5, 2, 4, 1, 3]
let pivot = arr.partition(by: { $0 > 3 })
// arr: [5, 4, 5, 1, 3] (순서는 상관 없음)
// pivot: 2

 

 

배열의 메모리를 관리하는 함수

 

20. withUnsafeBufferPointer(_:)

- 배열의 포인터를 반환하여, 해당 포인터로 배열에 접근할 수 있도록 합니다.

- 시간 복잡도: O(1)

let arr = [1, 2, 3]
let count = arr.withUnsafeBufferPointer { $0.count }
// count: 3

 

 

21. index(of:)

- 배열에서 지정된 요소의 인덱스를 반환합니다.

- 시간 복잡도: O(n)

let arr = [1, 2, 3, 2, 1]
let index = arr.index(of: 2)
// index: 1

 

 

22. reversed()

- 배열의 요소를 뒤집은 새로운 배열을 반환합니다.

- 시간 복잡도: O(1)

let arr = [1, 2, 3]
let reversed = arr.reversed()
// reversed: [3, 2, 1]

 

 

23. enumerated()

- 배열의 요소와 해당 인덱스를 포함하는 시퀀스를 반환합니다.

- 시간 복잡도: O(n)

let arr = [1, 2, 3]
let enumerated = arr.enumerated()
// enumerated: [(0, 1), (1, 2), (2, 3)]

 

 

24. index(after:)

- 배열의 지정된 인덱스의 다음 인덱스를 반환합니다.

- 시간 복잡도: O(1)

let arr = [1, 2, 3]
let index = arr.index(after: 1)
// index: 2

 

 

25. reserveCapacity(_:)

- 배열의 저장 용량을 지정된 값으로 변경합니다.

- 시간 복잡도: O(n)

var arr = [1, 2, 3]
arr.reserveCapacity(10) 
// arr: [1, 2, 3]

 

 

26. reverse()

- 배열의 요소를 뒤집습니다.

- 시간 복잡도: O(n)

var arr = [1, 2, 3]
arr.reverse()
// arr: [3, 2, 1]

 

 

27. removeSubrange(_:)

- 배열에서 지정된 범위의 요소를 제거합니다.

- 시간 복잡도: O(n)

var arr = [1, 2, 3, 4, 5]
arr.removeSubrange(1...3)
// arr: [1, 5]

 

 

28. insert(_: at:)

- 배열의 지정된 인덱스에 요소를 삽입합니다.

- 시간 복잡도: O(n)

var arr = [1, 2, 3]
arr.insert(4, at: 1)
// arr: [1, 4, 2, 3]

 

 

29. removeFirst()

- 배열의 첫 번째 요소를 제거합니다.

- 시간 복잡도: O(n)

var arr = [1, 2, 3]
arr.removeFirst()
// arr: [2, 3]

 

 

30. removeAll(keepingCapacity:)

- 배열의 모든 요소를 제거합니다. 이 함수는 배열의 저장 용량을 유지합니다.

- 시간 복잡도: O(n)

var arr = [1, 2, 3]
arr.removeAll(keepingCapacity: true)
// arr: [] (저장 용량은 유지됨)

 

이상으로 Swift의 Array에서 활용되는 함수들의 이름, 시간 복잡도, 사용 예시에 대해 설명해드렸습니다.

이러한 함수들을 적절히 활용하여 배열을 조작하고 검색하면, 더욱 높은 성능의 애플리케이션을 개발할 수 있습니다.

 

 

 

Q. O(k)와 O(n)이 어떻게 다른건지 설명해 줘

 

A.

O(k)는 알고리즘이 k번만큼 실행될 때의 시간 복잡도를 나타냅니다.

이는 입력 크기에 상관없이 k번의 실행만 필요하다는 것을 의미합니다.

따라서 k가 작을수록 알고리즘은 더욱 효율적이라고 할 수 있습니다.

 

반면, O(n)은 알고리즘이 입력 크기 n에 비례하여 실행되는 경우의 시간 복잡도를 나타냅니다.

이는 입력 크기가 클수록 알고리즘의 실행 시간이 증가한다는 것을 의미합니다.

 

따라서 O(k) 알고리즘은 입력 크기가 작을 때에 유용하며, O(n) 알고리즘은 입력 크기가 클 때에 유용합니다.

예를 들어, 배열에서 앞에서 k개의 요소를 가져오는 'prefix(_:) 함수의 경우 O(k)의 시간 복잡도를 가지므로, 가져올 요소의 개수가 적을 때에 더욱 빠른 실행 속도를 보입니다.

반면, 배열에서 특정 요소를 찾는 firstIndex(where:) 함수의 경우 O(n)의 시간 복잡도를 가지므로, 배열의 크기가 크거나 요소를 찾아야 하는 경우에는 실행 시간이 증가할 수 있습니다.

 

 

 

 

출처: ChatGPT(https://chat.openai.com/)