Arrays and Structures

배열

• 연속된 메모리 집합
• 인덱스 및 값으로 구성
• 새로운 배열 생성, 값 확인, 값 저장 등

import Foundation

struct FixedSizeArray {
    let count: Int
    private var array = [Int]()
    
    init(count: Int) {
        self.count = count
    }
    
    mutating func push(value: Int) {
        guard array.count < count else { return }
        array.append(value)
    }
    
    mutating func pop() -> Int? {
        guard !array.isEmpty else { return nil }
        return array.removeFirst()
    }
    
    mutating func setValue(index: Int, value: Int) {
        guard index < count && index < array.count else { return }
        array[index] = value
    }
    
    func getValue(index: Int) -> Int? {
        guard index < count && index < array.count else { return nil }
        return array[index]
    }
    
    func printArray() {
        print(array)
    }
}

var fixedSizeArray = FixedSizeArray(count: 5)
fixedSizeArray.push(value: 1)
fixedSizeArray.push(value: 2)
fixedSizeArray.push(value: 3)
fixedSizeArray.push(value: 4)
fixedSizeArray.push(value: 5)
fixedSizeArray.printArray()
// [1, 2, 3, 4, 5]
fixedSizeArray.push(value: 5)
fixedSizeArray.push(value: 4)
fixedSizeArray.push(value: 3)
fixedSizeArray.push(value: 2)
fixedSizeArray.push(value: 1)
fixedSizeArray.printArray()
// [1, 2, 3, 4, 5]
fixedSizeArray.pop()
fixedSizeArray.pop()
fixedSizeArray.pop()
fixedSizeArray.pop()
fixedSizeArray.pop()
fixedSizeArray.push(value: 5)
fixedSizeArray.push(value: 4)
fixedSizeArray.push(value: 3)
fixedSizeArray.push(value: 2)
fixedSizeArray.push(value: 1)
fixedSizeArray.printArray()
// [5, 4, 3, 2, 1]

구조체 내 private으로 배열 선언, 외부 접근을 통제했다!

동적 할당 배열

• C 언어: malloc, calloc 함수를 통해 특정한 양의 메모리를 할당한다.

  파이썬, 스위프트 등 대부분의 언어에서는 특정한 개수의 배열을 생성한다 하더라도 값을 추가할 때 동적으로 새로운 자리가 생겨난다!

import Foundation

var array = Array(repeating: 2, count: 1)
print(array)
// [2]
array.append(1)
print(array)
// [2, 1]

구조체 및 유니온

C 언어에서뿐만 아니라 스위프트 등 기타 언어에서도 사용자가 직접 정의 가능한 데이터 타입이다!

문자열

• 캐릭터를 원소로 하는 컴포넌트
• 새로운 빈 문자열을 생성하기
• 문자열 읽기
• 문자열 출력
• 문자열 합성
• 문자열 복사
  
  

문자열 삽입

import Foundation

public func strInsert(str: String, index: Int, value: String) -> String {
    var str = str
    let value = Character(value)
    let stringIdx = str.index(str.startIndex, offsetBy: index)
    str.insert(value, at: stringIdx)
    return str
}

var str = "abcde"
let result = strInsert(str:str, index: 2, value: "1")
// ab1cde

스위프트의 문자열 삽입은 대체적으로 불편한 것 같다. 개인적으로 문자열 배열로 변환한 뒤 삽입, 이후 문자열로 변환하는 것을 즐겨 사용한다.

패턴 매칭

• 브루트포스

import Foundation

public func getPatternBruteforce(str: String, pat: String) -> Int {
    let strArray = Array(str)
    let patArray = Array(pat)
    for idx in 0..<strArray.count-pat.count+1 {
        let curString = Array(strArray[idx..<idx+pat.count])
        if curString == patArray {
            return idx
        }
    }
    return -1
}

let str = "abcabcabcabc"
let pat = "cab"
let idx = getPatternBruteforce(str: str, pat: pat)
// 2

패턴의 길이 $n$, 문자열의 길이 $m$에 따라 시간 복잡도 $O(nm)$

• KMP 알고리즘

import Foundation

public func KMP(source:[String], target:[String]) -> [Int] {
    let sourceCnt = source.count
    let targetCnt = target.count
    var answers = [Int]()
    
    var LPS = Array(repeating: 0, count: targetCnt)
    LPS = LPScompute(target:target, LPS:LPS)
    
    var sourceIdx = 0
    var targetIdx = 0
    
    while (sourceIdx < sourceCnt) {
        if target[targetIdx] == source[sourceIdx] {
            sourceIdx += 1
            targetIdx += 1
        } else {
            if targetIdx == 0 {
                sourceIdx += 1
            } else {
                targetIdx = LPS[targetIdx - 1]
            }
        }
        if targetIdx == targetCnt {
            targetIdx = LPS[targetIdx - 1]
            answers.append(sourceIdx - targetCnt + 1)
        }
    }
    return answers
}

public func LPScompute(target:[String], LPS:[Int]) -> [Int] {
    var length = 0
    var idx = 1
    var LPS = LPS
    while (idx < target.count) {
        if target[idx] == target[length] {
            length += 1
            LPS[idx] = length
            idx += 1
        } else {
            if length == 0 {
                LPS[idx] = 0
                idx += 1
            } else {
                length = LPS[length - 1]
            }
        }
    }
    return LPS
}

let source = Array("abcdefghijklmnabcabcdef").map{String($0)}
let target = Array("def").map{String($0)}
let answers = KMP(source: source, target: target)
// [4, 21]

• 문자열 내 패턴을 확인한 이전 정보를 활용하는 알고리즘. 반복할 필요 없는 내용은 반복하지 않는다. 패턴 매칭이 실패한 부분을 알아낸다면 어디서부터 탐색을 다시 시작할지 효율적으로 택할 수 있다는 데에서 출발한 알고리즘이다.