Swift 알고리즘
문자열
접두사, 접미사
prefix, suffix, dropFirst, dropLast
let s = "abcdef"
let s1 = s.prefix(3) // abc
let s2 = s.suffix(3) // def
let s3 = s.dropFirst(3) // def
let s4 = s.dropLast(3) // def
let s5 = s.prefix(100) // abcdef
Swift
복사
이 메서드들은 Array에도 똑같이 적용된다.
인덱스 접근
let s = "abcdef"
let x = s[s.index(s.startIndex, offsetBy: 3)] // "d"
// x의 타입은 String이 아닌 Character
// 배열과 문자열의 인덱스 접근법 비교
let arr = [0, 1, 2, 3, 4]
let str = "abcde"
// 배열은 편하게 인덱스 접근 가능
let arr2 = arr[0..<3]
print(arr2)
// 문자열은 편하게 인덱스 접근이 불가능. String.Index 형으로 접근해야 한다
let i = str.startIndex
let j = str.index(i, offsetBy: 3)
let str2 = str[i..<j]
print(arr2) // [0, 1, 2]
print(str2) // abc
Swift
복사
슬라이싱
문자열 str = abcdef가 있을 때, abc만 남기고 자르고 싶을 경우
파이썬에서는 str[0:3] 문자열 슬라이싱을 하면 되었지만 Swift에서는 지원하지 않는다.
let s5 = s[s.startIndex ..< s.index(s.startIndex, offsetBy: 3)]
// "abc"
// Swift의 Index로 자른 결과는 String이 아닌 SubString 타입
var stringList = [String]()
stringList.append(String(s5)) // 타입 변환 필요
Swift
복사
뒤집기
import Foundation
let s = "abcde"
print(String(s.reversed())) // "edcba"
Swift
복사
곱셈
import Foundation
let str = "abc"
print(String(repeating: str, count: 3)) // "abcabcabc"
Swift
복사
교체
import Foundation
let str = "abcde"
let str2 = str.replacingOccurrences(of: "abc", with: "하이")
// "하이de"
Swift
복사
배열
first, last
first, last 라는 키워드를 제공. 비어있을 시 nil을 반환
let str = "abc"
let arr = [1, 2, 3]
let arr2 = [Int]()
str.last // "c"
arr.last // 3
str.first // "a"
arr.first // 1
arr2.first // nil
Swift
복사
정수 → 배열
map의 결과는 Array 형태이기 때문에 다음과 같은 방법으로 정수 → 배열 변환을 할 수 있다.
import Foundation
var x: Int = 12345
var arr = String(x).map{ Int(String($0))! }
print(arr) // [1, 2, 3, 4, 5]
Swift
복사
배열 초기화
•
여러가지 형태의 배열 초기화 방법
let N = 5
let a = [Int](repeating: 0, count: N)
let b = [Int](0..<N)
let c = [Int](0..<N).map{2 * ($0)}
let d = [Int](0..<N).filter($0 % 2 == 0}
print(a) // [0, 0, 0, 0, 0]
print(b) // [0, 1, 2, 3, 4]
print(c) // [0, 2, 4, 6, 8]
print(d) // [0, 2, 4]
Swift
복사
딕셔너리
원소 확인
원소가 있는지 없는지는 그냥 딕셔너리에 키 값으로 접근했을 때, nil 인지 아닌지로 판단한다.
var myDict = [String : Int]()
if let val = myDict['a'] {
print(val)
}
else {
print("없음")
}
Swift
복사
원소 개수 확인
count로 딕셔너리 원소 개수를 확인할 수 있다. 비어있는 경우는 count == 0 이 아닌 isEmpty를 활용하는 것이 좋겠다.
let myDict = ["a": 1, "b": 2, "c": 3]
print(myDict.count)
if !(myDict.isEmpty) {
print("비어있지 않음")
}
Swift
복사
원소 삭제
key-pair를 삭제하고 싶다면 nil을 대입해주면 된다.
let myDict = ["a": 1, "b": 2, "c": 3]
myDict[a] = nil
Swift
복사
defaultDict
딕셔너리에 없는 값을 조회할 경우, 디폴트 값을 설정할 수 있다.
let myDict = ["a": 1, "b": 2, "c": 3]
print(myDict["d", default: -1])
Swift
복사
딕셔너리 비교
딕셔너리끼리도 == 연산을 할 수 있다.
var a = [String : Int]()
var b = [String : Int]()
a["a"] = 1
a["b"] = 2
b["b"] = 2
b["a"] = 1
print(a == b) // true
b["c"] = 3
print(a == b) // false
Swift
복사
주의점
딕셔너리 결과는 항상 옵셔널이기 때문에 옵셔널 처리에 주의해야한다.
let myDict = ["a": 1, "b": 2, "c": 3]
if let a = myDicct["a"], a > 0 {
print("양수")
}
Swift
복사
큐 (Queue)
Swift에서는 Queue를 지원해주지 않는다.
Array에서 popLast() 라는 메서드와 removeFirst() 라는 메서드가 있기는 하다.
하지만 공식 문서를 읽어보면, removeFirst()의 시간복잡도는 O(N)이기 때문에 비효율적
→ Stack 2개로 Queue를 구현
큐 구현법 1 - 정석
1.
inputStack, outputStack 을 정의한다.
2.
enqueue - inputStack에 삽입한다.
3.
dequeue는 다음 3가지 상황을 고려한다.
a.
inputStack, outputStack이 모두 비어있을 경우
•
nil 리턴
b.
outputStack이 비어있지 않은 경우
•
outputStack에서 popLast()
c.
outputStack이 비어있지만 inputStack이 비어있지 않은 경우
•
inputStack이 빌 때까지 모두 outputStack으로 pop 수행 후, outputStack에서 popLast()
하지만 Swift에서는 비어있는 array에서 popLast()를 수행 시 자동으로 nil을 반환하므로 위 3가지 상황을 고려하지 않고 편하게 코드를 작성해도 된다.
import Foundation
struct Queue<T> {
var inputStack = [T]()
var outputStack = [T]()
mutating func append(_ x: T) {
inputStack.append(x)
}
mutating func pop() -> T? {
var top: T?
while !(inputStack.isEmpty) {
let x = inputStack.popLast()!
outputStack.append(x)
}
top = outputStack.popLast()
return top
}
mutating func head() -> T? {
while !(inputStack.isEmpty) {
let x = inputStack.popLast()!
outputStack.append(x)
}
return outputStack.isEmpty ? nil : outputStack[outputStack.endIndex - 1]
}
func isEmpty() -> Bool {
return inputStack.isEmpty && outputStack.isEmpty ? true : false
}
}
var q = Queue<Int>()
Swift
복사
•
시간복잡도
◦
append: O(1)
◦
pop: 상황에 따라 O(1) or O(N)
이 코드는 기본적인 큐 연산을 지원하며, 제네릭을 사용하여 다양한 타입으로 큐를 구현할 수 있다.
하지만 ‘pop()’ 과 ‘head()’ 메서드에서 모든 요소를 매번 이동시키는 방식은 효율성 면에서 개선될 여지가 있다. 매 연산 때마다 요소를 이동시키는 대신, 필요할 때만 요소를 재배열하는 방법을 고려할 수 있다.
또한, 현재 ‘pop()’이나 ‘head()’ 메서드를 호출할 때마다 ‘inputStack’의 모든 내용을 ‘outputStack’으로 옮기고, 이 과정을 반복하지말고 ‘outputStack’이 비어있을 때만 ‘inputStack’에서 ‘outputStack’으로 요소를 옮기는 방식으로 최적화할 수 있다.
최적화한 코드
import Foundation
struct Queue<T> {
private var inputStack = [T]()
private var outputStack = [T]()
mutating func append(_ x: T) {
inputStack.append(x)
}
mutating func pop() -> T? {
if outputStack.isEmpty {
transferElements()
}
return outputStack.popLast()
}
mutating func head() -> T? {
if outputStack.isEmpty {
transferElements()
}
return outputStack.last
}
func isEmpty() -> Bool {
return inputStack.isEmpty && outputStack.isEmpty
}
private mutating func transferElements() {
while !inputStack.isEmpty {
outputStack.append(inputStack.popLast()!)
}
}
}
var queue = Queue<Int>()
Swift
복사
큐 구현법 2 - reversed 활용
reverse()는 O(N) 소요, reversed는 O(1) 소요된다.
따라서 swift의 reversed를 활용하면 append와 pop 모두 O(1) 소요되는 큐를 구현할 수 있다.
import Foundation
struct Queue<T> {
var inputStack = [T]()
var outputStack = [T]()
mutating func append(_ x: T) {
inputStack.append(x)
}
mutating func pop() -> T? {
var top: T?
if outputStack.isEmpty {
outputStack = inputStack.reversed()
inputStack.removeAll()
top = outputStack.popLast()
}
else {
top = outputStack.popLast()
}
return top
}
mutating func head() -> T? {
if outputStack.isEmpty {
outputStack = inputStack.reversed()
inputStack.removeAll()
}
return outputStack.isEmpty ? nil : outputStack[outputStack.endIndex - 1]
}
func isEmpty() -> Bool {
return inputStack.isEmpty && outputStack.isEmpty ? true : false
}
}
var q = Queue<Int>()
Swift
복사
힙 Heap
•
힙은 각 노드가 하위 노드보다 작은(뜨는 큰) 이진 트리이다.
•
이러한 종류의 이진 트리는 주로 우선순위 큐를 구현하는데 사용된다. 힙에는 두 가지 주요 유형이 있다.
•
최소 힙 (Min-Heap)
◦
부모 노드가 자식 노드보다 작거나 같은 값을 가진다.
•
최대 힙 (Max-Heap)
◦
부모 노드가 자식 노드보다 크거나 같은 값을 가진다.
소스코드
import Foundation
public struct Heap<T> {
// 전체 노드, 힙의 요소를 저장하느 배열
var nodes: [T] = []
// 비교 연산자, 두 요소를 비교하는데 사용되는 비교함수
// 이 함수는 힙이 최소힙인지 최대힙인지 결정한다.
let comparer: (T, T) -> Bool
var isEmpty: Bool {
return nodes.isEmpty
}
// 예를들어, Heap<Int>(comparer: >=)는 Min Heap
init(comparer: @escaping (T, T) -> Bool {
self.comparer = comparer
}
// top 반환
func top() -> T? {
return nodes.first
}
// 삽입
mutating func push(_ element: T) {
var index = nodes.count
nodes.append(element)
// 현재 노드가 루트 노드가 아니며, 현재 노드와 부모 노드 사이의 힙 속성이 위반 되었다면
while index > 0, !comparer(nodes[index], nodes[(index - 1) / 2]) {
nodes.swapAt(index, (index - 1) / 2)
index = (index - 1) / 2
}
}
// 삭제
mutating func pop() -> T? {
// 힙에 노드가 없는 경우, 즉시 함수에서 반환, 빈 힙에서 요소를 제거하려고 시도하는 것을 방지
guard !nodes.isEmpty else {
return nil
}
if nodes.count == 1 {
return nodes.removeFirst()
}
// 제거할 노드(루트 노드)의 값을 저장, 이 값은 마지막에 반환된다.
let result = nodes.first
// 마지막 노드와 루트 노드의 위치를 바꾼다
nodes.swapAt(0, nodes.count - 1)
// 위치를 바꾼 원래의 루트 노드(마지막 위치에 있음)를 제거
_ = nodes.popLast()
// 이제 "down-heap bubbling" 과정이 시작된다.
// 이 과정은 제거된 루트 노드의 자리를 채우기 위해 힙을 재정렬
var index = 0
while index < nodes.count {
let left = index * 2 + 1
let right = left + 1
// 오른쪽 자식이 있는지 확인하는 조건
// 있으면 오른쪽 자식과 왼쪽 자식을 비교하고,
// 더 작은(또는 더 큰) 자식과 현재 노드를 바꾼다.
if right < nodes.count {
if comparer(nodes[left], nodes[right]),
!comparer(nodes[right], nodes[index]) {
nodes.swapAt(right, index)
index = right
}
else if !comparer(nodes[left], nodes[index]) {
nodes.swapAt(left, index)
index = left
}
else {
break
}
else if left < nodes.count {
if !comparer(nodes[left], nodes[index]) }
nodes.swapAt(left, index)
index = left
}
else {
break
}
}
else {
break
}
}
return result
}
}
extension Heap where T: Comparable {
// 초기 설정을 해주지 않으면 Min Heap
init() {
self.init(comparer: >=)
}
}
Swift
복사
힙 활용
파이썬에서는 heapq를 지원하지만, swfit에서는 힙 자료구조를 기본 제공하지 않는다.
Heap 활용 코드
// Min Heap 세팅
var minheap = Heap<Int>(comparer: >=)
// Max Heap 세팅
var maxHeap = Heap<Int>(comparer: <=)
// 100 삽입
minHeap.push(100)
// 삭제
let _ = minHeap.pop()
// top 반환
let top = minHeap.top()
// heap 원소 개수
let heapCount = minHeap.nodes.count
Swift
복사
Reference
