Jenikeju

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42579

내가 푼 풀이

[장르: (인덱스: Int, 재생수: Int)]의 딕셔너리 한개와, [장르: 총재생수] 딕셔너리를 구현하여 만들었습니다.

주어진 jenres 문자열 배열을 위 딕셔너리 두개로 먼저 파싱한 뒤, 총 재생수가 많은 순으로 정렬하여 해당 장르를 접근하였습니다.

[장르: (인덱스: Int, 재생수: Int)]의 value에서 재생수가 많은 순으로 정렬한 다음, 장르 key값으로 (인덱스: Int, 재생수: Int) 튜플 value에 접근하여 가장 재생수가 높은 두개의 곡을 뽑아서 배열에 저장한 뒤 리턴하였습니다.

코드로 구현하면 다음과 같습니다.

import Foundation

func solution(_ genres:[String], _ plays:[Int]) -> [Int] {
    var played = [String: [(index: Int, plays: Int)]]()
    var totalPlayedGenres = [String: Int]() 
    var album = [Int]()
    
    for i in 0..<genres.count {
        let genre = genres[i]
        let playCount = plays[i]
        if played[genre] == nil {
            played[genre] = [(index: i, plays: playCount)]
            totalPlayedGenres[genre] = playCount
        } else {
            played[genre]!.append((index: i, plays: playCount))
            totalPlayedGenres[genre]! += playCount
        }
    }
    
    let sortedGenres = totalPlayedGenres.sorted { $0.value > $1.value }
    
    sortedGenres.forEach { element in
        let songs = played[element.key]!.sorted{ $0.plays > $1.plays}
        
        for i in 0..<songs.count {
            album.append(songs[i].index)
            if i == 1 { break }
        }
    }
    return album
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/388352

내가 푼 방법

비밀코드의 범위가 주어지면 해당 범위에서 만들 수 있는 모든 조합을 먼저 구한 뒤,

각 ans의 응답값을 비교해서 모두 일치하는 경우 하나의 비밀코드로 간주했다.

조합과 이중반복문으로 시간초과가 걸릴 것 같았지만, 가까스로 통과한 느낌이였다.

import Foundation

func solution(_ n:Int, _ q:[[Int]], _ ans:[Int]) -> Int {
    let targetArr = Array(1...n)
    var total = 0
    var results = [[Int]]()
    // 조합
    func combi(targetArr: [Int], targetNum: Int, index: Int, arr: [Int]) {
        if arr.count == targetNum {
            results.append(arr)
            return
        }
        for i in index..<targetArr.count {
            combi(targetArr: targetArr, targetNum: targetNum, index: i+1, arr: arr + [targetArr[i]])
        }
    }
    combi(targetArr: targetArr, targetNum: 5, index: 0, arr: [])
    
    // 각 응답값 비교
    results.forEach { element in
        for i in 0..<q.count {
            let arr = q[i]
            if !compare(lhs: arr, rhs: element, correct: ans[i]) {
                break
            }
            if i == q.count-1 {
                total += 1
            }
        }
    }
    return total
}

func compare(lhs: [Int], rhs: [Int], correct: Int) -> Bool {
    var count = 0
    for i in 0..<lhs.count {
        if rhs.contains(lhs[i]) { count += 1}
    }
    if count == correct { return true }
    return false
}

문제 설명 ▼

내가 푼 풀이

• 주어진 players배열과 크기가 같은 servers 배열을 만들었습니다.
• players배열을 반복문으로 순회하면서 각 시간마다 서버 증설이 필요한지 조건을 달았습니다.
• 증설이 필요하다면 그리디 기법으로 현재 시간의 인원을 수용할 만큼만의 서버를 증설하고 k시간까지 최대 이용자 수를 증가시켰습니다.
• 증설이 필요할 때 서버를 증설하고 증설된 수를 count 변수에 담아서 리턴했습니다.

import Foundation

func solution(_ players:[Int], _ m:Int, _ k:Int) -> Int {
    var servers = Array(repeating: 0, count: players.count)
    var count = 0
    
    for i in 0..<players.count {
        let allowPlayerCount = (servers[i] * m) + m
        if players[i] >= allowPlayerCount {
            let needServerCount = abs(servers[i] - (players[i] / m))
            count += needServerCount
            for j in i..<i+k {
                if j >= players.count { continue }
                servers[j] += needServerCount
            }
        }
    }
    
    return count
}

타입 Type

타입이란 직역하면 어떤 부류의 형, 유형, 모양, 생김새 입니다.

프로그래밍에서 타입은 값이 가질 수 있는 형태와 그 값에 대해 수행할 수 있는 연산을 정의하는 개념입니다.

더 나누면 정적타입, 동적타입이 존재하지만 이 글에서는 다루지 않습니다

이 글에서는 Swift에서 존재하는 타입들을 살펴볼 것 입니다.

더 자세한 내용은 Swift.org에 있습니다

Swift의 타입

Swift의 타입은 두가지 종류가 있습니다.

• 명명된 타입 (named type): 특정 이름을 부여할 수 있는 타입으로 클래스, 구조체, 열거형, 프로토콜, 배열, 딕셔너리, 옵셔널 모두 해당됩니다. 필요에따라 확장할 수 있습니다.
• 복합 타입 (compound type): 정의된 이름이 없는 타입으로 함수와 튜플이 있습니다. 복합 타입은 말 그대로 다른 명명된 타입과 다른 복합 타입을 합칠 수 있습니다.

Swift에서 정의된 타입은 아래와 같이 있습니다.

Grammar of a type

type → function-type 	(함수)
type → array-type		(배열)
type → dictionary-type	 	(딕셔너리)	
type → type-identifier		(타입 식별자)
type → tuple-type		(튜플)
type → optional-type	(옵셔널 타입)
type → implicitly-unwrapped-optional-type	(묵시적 언래핑 옵셔널)
type → protocol-composition-type	(프로토콜 조합 타입)
type → opaque-type (불투명 타입)	(some 키워드를 붙이는 것)
type → boxed-protocol-type	(existential type) (프로토콜 타입으로 선언한 것)
type → metatype-type (타입의 타입) (.self .Type)
type → any-type  
type → self-type
type → ( type )

타입 식별자 (Type Identifier)

타입 식별자는 타입 별칭(type alias)를 나타냅니다.

대부분은 식별자와 명명된 타입이 같아서 직접 참조합니다 (Int타입은 Int에 참조, Dictionary<String,Int>타입은 Dictionary<string,int></string,int>에 참조)

명명된 타입과 식별자가 같지 않은 두가지 경우가 있습니다.

첫번째로는 복합타입의 타입별칭입니다.

typealias Point = (Int, Int)
let origin: Point = (0, 0)

두번째로는 다른 모듈에 선언되거나 다른 중첩된 명명 타입입니다.

var someValue: ExampleModule.MyType

튜플 타입 (Tuple Type)

튜플 타입은 소괄호로 묶인 콤마로 구분되는 타입의 리스트입니다.

타입의 요소에 이름을 정할 수 있고, 이름과 타입을 구별하기 위해 세미콜론(:)을 사용합니다.

var someTuple = (top: 10, bottom: 12)
someTuple = (top: 4, bottom: 42)
someTuple = (9, 99)

튜플 타입에서 중요한건 요소들의 타입입니다.

someTuple의 타입은 (Int, Int) 이기 때문에 (Int, Int, Int)나 (Int, String)같은 타입은 someTuple에 할당할 수 없습니다.

함수 타입 (Function Type)

함수 타입은 함수, 메서드, 클로저의 타입을 나타냅니다.

함수 타입은 화살표(->)로 구분된 파라미터 타입과 리턴 타입으로 구성됩니다.

(<#parameter type#>) -> <#return type#>

문서에 따르면 함수타입 () -> T 의 파라미터는 autoclosure 속성을 적용하여 호출 부분에서 암시적으로 클로저를 생성할 수 있습니다. 라고 설명되어 있습니다.

autoclosure이란 함수에 인수로 전달되는 표현식을 래핑하기 위해 자동으로 생성되는 클로저입니다.

간단하게 파라미터에 클로저 () -> T 타입이 있다면, 해당 함수를 호출할 때, 대괄호( { )를 사용하지 않고 표현식만 사용해도 자동으로 클로저로 변환됩니다.

func someFun1(closure: () -> String) {
    print(closure())
}
someFun1 { "hello" }

func someFun2(closure: @autoclosure () -> String) {
    print(closure())
}
someFun2(closure: "hello")

함수도 타입으로 정의되면 autoclosure처럼 대괄호 { } 없이 호출 할 수 있습니다.

func someFun2(closure: @autoclosure () -> String) {
    print(closure())
}

let functionSomeFun2 = someFun2
functionSomeFun2("hello")

또한 가변파라미터와 inout파라미터를 갖는 함수도 타입으로 구현할 수 있습니다.

func swap(_ num1: inout Int,_ num2: inout Int) {
    let temp: Int = num1
    num1 = num2
    num2 = temp
}
let swap1 = swap
var numA = 10
var numB = 15
swap1(&numA, &numB)
print(numA, numB)
// 출력
// 15 10
func printRange(range: Int...) {
    for i in range {
        print(i)
    }
}
let printRange1 = printRange
printRange1(1, 2, 3)
// 출력
// 1
// 2
// 3

함수 타입은 위에 서술했듯이 파라미터 타입과 리턴 타입이 같으면 다른 같은 타입의 함수로도 변경할 수 있습니다.

someFunction을 변수 f에 할당하게 되면 f의 타입은 위 사진과 같이 (Int, Int) -> ()으로 설정됩니다.

f의 타입처럼 파라미터 타입은 (Int, Int), 리턴 타입은 Void인 함수라면 f에 다른 함수로 초기화 할 수 있습니다.

func someFunction(left: Int, right: Int) {}
func anotherFunction(left: Int, right: Int) {}
func functionWithDifferentLabels(top: Int, bottom: Int) {}

var f = someFunction
f = anotherFunction
f = functionWithDifferentLabels

위 세가지 함수는 인자의 이름이 달라도 파라미터 타입과 리턴 타입이 같기 때문에 f로 선언된 변수가 세 가지 함수로 타입을 지정 및 변경하여도 에러가 발생하지 않습니다. (모두 같은 타입이기 때문에)

다른 함수의 종류로 에러를 반환할 수 있는 throw 함수, async 함수 역시 타입으로 지정할 수 있습니다.

위 사진처럼 자동 완성으로 볼 때 해당 변수의 타입들은 throws, async 함수타입으로 지정된 것을 볼 수 있습니다.

배열 타입 Array Type

이미 많이 사용해봤던 배열 타입입니다.

[T], 혹은 Array<T> 형식으로 선언합니다.

let someArray1: Array<String> = ["Alex", "Brian", "Dave"]
let someArray2: [String] = ["Alex", "Brian", "Dave"]
let someArray3: Array<Array<String>> = [["Alex", "Brian"], ["Dave"]]
let someArray4: [[String]] = [["Alex", "Brian"], ["Dave"]]

딕셔너리 타입 Dictionary Type

Dictionary를 선언하는 방식은 아래와 같습니다!

let someDictionary1: [String: Int] = ["Alex": 31, "Paul": 39]
let someDictionary2: Dictionary<String, Int> = ["Alex": 31, "Paul": 39]

옵셔널 타입 Optional Type

Swift에서는 Optional<Wrapped>에 대해 접미사 ? 구문을 정의합니다.

옵셔널 타입을 다음과 같이 설정할 수 있습니다.

// enum Optional<Wrapped>
var optionalInteger1: Int?
var optionalInteger2: Optional<Int>

암시적 언래핑 옵셔널 타입 Implicitly Unwrapped Optional Type

암시적 언래핑 옵셔널 타입은 스토리보드에 있는 UI를 코드영역으로 드래그하면 자동으로 생성되는 모습을 볼 수 있었습니다.

@IBOutlet var button: UIButton!

이는 해당 인스턴스가 옵셔널 타입이지만, 강제 언래핑 동작을 자동으로 추가하기 위해 타입 뒤에 접미사 ! 를 추가하여 선언합니다.

button이 nil이라면 런타임 에러를 발생하고, nil이 아닌 값이 존재한다면 따로 옵셔널 바인딩 없이 접근할 수 있습니다.

프로토콜 혼합 타입 Protocol Composition Type

프로토콜 혼합 타입은 말 그대로 다중 프로토콜이 혼합된 하나의 타입으로 나타내게 되고 타입은 아래와 같이 나타냅니다.

<#Protocol 1#> & <#Protocol 2#>

protocol Nameable {
    var name: String { get }
}

protocol Ageable {
    var age: Int { get }
}

typealias Person = Nameable & Ageable

class Jenikeju: Person {
    var name: String
    
    var age: Int
    
    init(name: String, age: Int) {
        self.name = name
        self.age = age
    }
}

혼합된 프로토콜은 protocol1 & protocol2 로 나타낼 수도 있지만, 이를 typealias를 통해 새로운 타입으로 별칭하고 사용할 수 있습니다.

혼합된 프로토콜이여도 하위클래스에 상위클래스를 상속하고 다른 프로토콜을 사용할 때, 상위클래스와 프로토콜을 혼합할 수 있습니다.

protocol Nameable {
    var name: String { get }
}

protocol Ageable {
    var age: Int { get }
}

class Animal {
    func feed() { }
}

// class & protocol1 & protocol2
typealias CatCompositionType = Animal & Nameable & Ageable

class Cat: CatCompositionType {
    var name: String
    var age: Int
    
    init(name: String, age: Int) {
        self.name = name
        self.age = age
    }
}
let cat = Cat(name: "meow", age: 5)
cat.feed()

클래스는 하나의 클래스만 상속받을 수 있기 때문에 최대 하나의 클래스만 혼합할 수 있습니다.

또한 혼합 과정에서 중복된 프로토콜은 자동으로 무시됩니다.

// 중복된 프로토콜 혼합
// Ageable & Nameable & Ageable & Ageable = Ageable & Nameable
typealias ManyCompositionType = Ageable & Nameable & Ageable & Ageable

class SomeClass: ManyCompositionType {
    var age: Int
    var name: String
    
}

불투명한 타입 Opaque Type

불투명한 타입은 기본 타입 지정없이 프로토콜 또는 프로토콜 구성을 준수하는 타입을 정의합니다.

some <#constraint#>

constraint는 클래스, 프로토콜, 프로토콜 구성 타입, Any 입니다.

불투명한 타입을 이해하기위해 some 키워드를 먼저 이해해봅시다.

some

불투명한 타입에서 불투명한이란 의미는 어떤 타입인지 정확히 명시하지 않지만, 컴파일러는 내부적으로 알고 있다는 의미로 생각할 수 있습니다.

Swift에서는 프로토콜을 직접 반환할 수 없습니다.

그래서 아래 코드는 컴파일 에러를 발생합니다.

protocol Shape {
    func area() -> Double
}

struct Circle: Shape {
    var radius: Double = 0.0
    func area() -> Double { return .pi * radius * radius }
}

// protocol을 리턴해서 에러 발생
func makeShape() -> Shape {
    return Circle()
}

★ 하지만 Swift5부터 값 타입도 프로토콜 타입을 리턴할 수 있게되어서 위 코드는 이제 오류가 발생하지 않습니다.

그전에 protocol 타입을 리턴할 수 없어서 some 키워드를 추가하여 해당 프로토콜을 준수하는 객체를 리턴하도록 구현할 수 있습니다.

protocol Shape {
    func area() -> Double
}

struct Circle: Shape {
    var radius: Double = 0.0
    func area() -> Double { return .pi * radius * radius }
}

// some 키워드 추가
func makeShape() -> some Shape {
    return Circle()
}

some 키워드가 없을 땐 Shape 프로토콜을 준수하는 많은 객체중 어떤 객체가 리턴되는지 정확하게 명시되어 있지 않아서 컴파일러가 오류를 발생시켰습니다.

some 키워드를 추가하여 something?과 비슷한 의미로 'Shape 프로토콜을 준수하는 어떤 클래스나 구조체, 열거형 등의 타입'을 리턴하겠다고 지정하는 것입니다.

some 키워드는 프로토콜 뿐만 아니라 클래스도 사용 가능합니다.

상위 클래스를 리턴할 때 some 키워드와 함께 사용할 수 있습니다.

class Animal {
    func feed() { }
}

class Cat: Animal { }
class Dog: Animal { }

func returnAnimalClass() -> some Animal {
    return Cat()
}

박스형 프로토콜 타입 Boxed Protocol Type

문제 설명▼

내가 푼 풀이

BFS를 사용해서 풀었습니다.

• 1번으로부터 가장 먼 노드의 갯수를 구하기 때문에, 인접한 그래프를 이동하는 움직임을 하나의 단위로 생각했습니다.
• 한번의 움직임을 담은 needToVisit 배열과, 움직임을 통해 도착한 노드의 인접그래프가 담긴 saveNextVisitList 배열을 선언해 주었습니다.
• 한번 이동을 통해 needToVisit의 배열이 비었다면, 도착 노드와 인접한 노드들이 담긴 saveNextVisitList를 needToVisit에 할당하고 saveNextVisitList를 빈배열로 초기화했습니다.
• 이미 방문한 노드들은 다시 갈 필요가 없으므로 노드 갯수만큼의 visited 배열 크기를 만들고 선언했습니다.
• saveNextVisitList에는 Set 형변환을 통해 중복 노드들을 제거하고 다시 Array배열로 형변환 후 visited 배열을 통해 방문하지 않은 노드들로 필터링을 했습니다.
• needToVisit은 인접한 그래프로의 한 움직임 단위 이므로 이를 lastNode 2차원 배열에 담았습니다. lastNode 배열은 needToVisit의 기록을 담고있습니다.
• 최종적으로 모든 노드를 도달했다면 needToVisit은 빈 배열이 되고 빈 배열이 lastNode배열에 담기게 되므로 결과로 lastNode의 마지막에서 두번째 원소의 갯수를 리턴하도록 설계하였습니다.

import Foundation

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    var graph: [Int: [Int]] = [:]
    // 그래프를 딕셔너리에 담기
    edge.forEach { (element) in
        if graph[element[0]] == nil {
            graph[element[0]] = [element[1]]
        } else {
            graph[element[0]]!.append(element[1])
        }
        if graph[element[1]] == nil {
            graph[element[1]] = [element[0]]
        } else {
            graph[element[1]]!.append(element[0])
        }
    }
    
    // 인접한 그래프로의 한번 이동을 담은 배열
    var needToVisit = [1]
    // 인접한 도착노드들의 인접노드들을 담은 배열
    var saveNextVisitList: [Int] = []
    // 방문기록
    var visited = Array(repeating: false, count: n+1)
    // needToVisit의 이전 기록들을 담는 배열
    var lastNode = [[Int]]()
    
    // BFS
    while !needToVisit.isEmpty {
        let node = needToVisit.removeFirst()
        visited[node] = true
        var nextNodes = graph[node]!
        saveNextVisitList += nextNodes
        
        if needToVisit.isEmpty {
            if saveNextVisitList.isEmpty {
                break 
            }
            let setVisitList = Array(Set(saveNextVisitList))
            for element in setVisitList {
                if !visited[element] {
                    needToVisit.append(element)
                    
                }
            }
            lastNode.append(needToVisit)
            saveNextVisitList = []
        }
    }
    return lastNode[lastNode.count-2].count
}

문제 설명

내가 푼 풀이

첫번째 방법 - DFS

한개의 물건이 주어졌을 때, 두가지 경우의 수가 있습니다.

1. A가 훔치기

2. B가 훔치기

또한 경찰에게 걸리지 않게 모든 물건을 훔쳤기에 물건을 훔치지 않는 옵션은 없습니다.

결국 A가 최소로 도둑질을 하면 흔적도 자연스럽게 최솟값을 가질 것이라 생각하고, B에게 먼저 조건을 걸어주었고, B가 최대한 훔치도록 구현하였습니다.

import Foundation

func solution(_ info:[[Int]], _ n:Int, _ m:Int) -> Int {
    var min = Int.max
    var informations = info
    
    func dfs(count: [Int], currentIndex: Int) {
        if currentIndex >= info.count {
            min >= count[0] ? min = count[0] : nil
            return
        }
        let theifACount = [count[0] + info[currentIndex][0], count[1]]
        let theifBCount = [count[0], count[1] + info[currentIndex][1]]
        if theifACount[0] < n && theifACount[0] < min {
            dfs(count: [count[0] + info[currentIndex][0], count[1]],
            currentIndex: currentIndex + 1)
        }
        if theifBCount[1] < m {
            dfs(count: [count[0], count[1] + info[currentIndex][1]],
            currentIndex: currentIndex + 1)
        }
    }
    dfs(count: [0, 0], currentIndex: 0)
    
    return min == Int.max ? -1 : min
}

결과는 시간초과가 발생하였습니다.

이유를 확인해보면, 만약 m,n이 매우 넉넉하다면, 큰 수라면 bfs의 실행은 $2^{40}$ 번 실행되어 시간초과가 발생하였습니다.

그러면 시간만 줄여서 될까 해서 테스트케이스를 몇 개 추가했더니, 해당 케이스도 실패하는걸 볼 수 있었습니다.

info = [[1, 2], [3, 1], [3, 2]]
n = 5
m = 3
// 결과는 4가 나와야 하지만 1이 나왔습니다.

이를 통해 매번 탐색할 때 최적해를 갱신해야 할 필요가 있구나 싶었습니다.

두번째 방법 - DP

이전까지의 최적해를 저장하여 그다음 최적해를 구하기 위해 DP를 사용했습니다.

info배열을 돌면서 한번으로 최적해가 구해질 수 있을까? 해서 작성해보았는데 위 테스트 케이스도 통과하지 못했습니다.

B도둑이 알뜰살뜰하게 m을 넘지 않으면서 m과 가까운 수만큼 흔적을 남기는 방법이 뭐가 있을까 하다가 배낭문제가 생각났습니다.

(도둑이 배낭에 보석을 담을 때 정해진 배낭무게, 보석무게와 가치에 맞춰서 가장 가치있는 보석만 골라담는 문제)

B도둑이 최대한 흔적을 많이 남길 수 있게 배낭문제처럼 m값을 갱신하고 A흔적의 최솟값을 구하려고 합니다.

이를 1번 입력을 예시로 2차원배열로 나타내보겠습니다.

행은 m, B가 남길 수 있는 흔적 입니다. 열은 index로 info의 물건을 접근하기위한 인덱스입니다.

조건을 다시 살펴보자면,

1. 모든 물건을 훔쳤다.(물건을 훔치지 않고 건너뛰는건 불가능)

2. A는 n, B는 m 보다 같거나 클 수 없다. 만약 같거나 크다면 훔칠 수 없다고 판단한다.

위 조건을 바탕으로 배낭문제 처럼 2차원 배열을 채워가며 A의 최솟값을 구하겠습니다.

dp[i][j] = 0 은 물건을 하나도 훔치지 않을 때 값입니다.

행은 무게를 뜻하고, 열은 물건의 순서를 뜻하고, 해당 위치의 원소는 A의 흔적입니다.

첫번째는 아무것도 훔치지 않았기때문에 dp[0][1...3] = 0 입니다.

이제 첫번째 물건을 훔치겠습니다. 물건의 정보는 [1, 2] 입니다.

이때, 두가지 경우의 수가 있습니다. (1. A가 훔치기 2. B가 훔치기)

해당 DP인덱스의 원소는 A의 흔적을 의미하기에 A가 훔친다면 이전 값에서 A의 흔적을 더한값이 될 것입니다.

B가 훔친다면, (현재열 + 2) 인덱스에 이전 값을 넣게 됩니다.

이렇게 이전의 저장된 값을 바탕으로 최적해를 구하기위해 갱신하면 다음과 같습니다.

그 다음 두번째 물건을 훔치겠습니다. 물건의 정보는 [2,3] 입니다.

두번째 물건도 두가지 경우가 있습니다.

dp[2][0]에는 3이 들어가고 이 의미는 두번째 물건까지 A가 훔치는 경우입니다.

두번째 물건을 B가 훔치는 경우는 (현재 열 + 3) 인덱스에 넣게 되는데, 이 때 첫번째 물건을 넣은 값과 비교를 해야합니다.

dp[2][j + 3] = min ( dp[2][j + 3], dp[1][j] )

j = 0일때, dp[2][3] = min(dp[2][3], dp[1][0]) 을 비교하게 됩니다. (INF  > 1)

이를 m = 3까지 갱신해줍니다.

dp[2][1], dp[2][2]는 첫번째는 B, 두번째는 A가 훔친경우입니다. 첫번째와 두번째 둘다 A가 훔친 경우(dp[2][0])보다 작은 수 이므로 갱신했습니다.

마지막으로 세번째 물건을 훔치겠습니다. 물건 정보는 [2,1]입니다.

세번째 물건까지 A가 훔치면 dp[3][0] = 5입니다.

세번째 물건을 B가 훔치는 경우라면 현재 인덱스 + 1의 자리를 갱신해줍니다.

dp[3][1] = min (dp[3][1], dp[2][1]) = 3

m = 3까지 갱신해주면 아래와 같습니다.

최종적으로 dp[3][3]에 구하는 값을 나타낼 수 있음을 알 수 있습니다.

여기까지 살펴본 결과 2차원 배열의 의미를 다음과 같이 나타낼 수 있습니다.

dp[i][j]

• i : 현재 물건의 인덱스
• j : 현재 B의 흔적
• dp[i][j]의 원소: i번째 물건까지 훔쳤고 현재 B의 흔적이 j일때 A의 흔적 값

점화식은 아래와 같습니다.

1. A가 훔쳤을 때 : dp[i][j] = min(dp[i][j], dp[i-1][j] + a) (a는 해당물건의 A흔적)
2. B가 훔쳤을 때 : dp[i][j+b] = min(dp[i][j+b], dp[i-1][j]) (b는 해당물건의 B흔적)

코드로 나타내면 다음과 같습니다.

import Foundation

func solution(_ info:[[Int]], _ n:Int, _ m:Int) -> Int {
    let INF = 100000000
    
    // DP
    var dp = Array(repeating: Array(repeating: INF, count: m),
                   count: info.count+1)
    for i in 0..<m {
        dp[0][i] = 0
    }
    
    for i in 1...info.count {
        // 현재 물건에 대한 A의 흔적과 B의 흔적
        let aThief = info[i-1][0]
        let bThief = info[i-1][1]
        
        for j in 0..<m {
        	// A가 훔친 경우 값 갱신
            dp[i][j] = min(dp[i][j], dp[i-1][j] + aThief)
            
            // B가 훔친 경우 값 갱신
            if j + bThief < m { 
                dp[i][j + bThief] = min(dp[i][j + bThief], dp[i-1][j])
            }
        }
    }
	// 마지막 물건과 B의 흔적이 m보다 크거나 같지 않게 훔쳤을 때의 최소값 리턴
    return dp[info.count][m-1] >= n ? -1 : dp[info.count][m-1]
}

ARC는 Automatic Reference Counting으로 참조타입의 참조 횟수를 자동으로 카운팅 되며 참조 수가 0이 되면 메모리에서 자동으로 해제하여 메모리 사용량을 관리합니다.

자동으로 참조횟수를 트래킹 하지만, 강한 참조 사이클 같은 경우에는 각 객체가 소멸해도 강한 참조가 남아있어 메모리에 계속 유지되어 버리는 메모리 누수 현상이 발생하곤 합니다.

그래서 메모리 누수 방지를 위해 weak, unowned 키워드를 종종 사용하곤 했습니다.

강한 참조 사이클 예시

// 서로 참조하는 클래스 두개 생성
class Person {
    let name: String
    init(name: String) { self.name = name }
    var apartment: Apartment?
    deinit { print("\(name) is being deinitialized") }
}

class Apartment {
    let unit: String
    init(unit: String) { self.unit = unit }
    var tenant: Person?
    deinit { print("Apartment \(unit) is being deinitialized") }
}

// 인스턴스 생성 (Person의 강한참조: 1, Apartment의 강한참조: 1)
var person: Person? = Person(name: "john")
var apartment: Apartment? = Apartment(unit: "")

// person.apartment는 Apartment 클래스를 강한참조
// apartment.tenant는 Person 클래스를 강한참조
// (Person의 강한참조: 2, Apartment의 강한참조: 2)
person?.apartment = apartment
apartment?.tenant = person

// person과 apartment 소멸하여 강한참조가 1 줄어들지만, 서로 참조하는 카운팅은 남아있음
// 메모리에 계속 유지되는 Person클래스와 Apartment클래스는 어떤 방법으로도 접근할 수 없음
// (Person의 강한참조: 1, Apartment의 강한참조: 1)
person = nil
apartment = nil

weak? unowned?

강한참조 사이클 발생을 방지하기 위해 두 가지 키워드 중 하나를 선택하여 사용할 수 있습니다.

결과적으로 메모리 누수를 피하기 위해 사용되지만 두 키워드의 차이점은 있습니다.

weak: 옵셔널 타입으로 명시하며, 참조하는 객체가 소멸되면, 해당 값은 nil이 됩니다.

// 서로 참조하는 클래스 두개 생성
class Person {
    let name: String
    init(name: String) { self.name = name }
    var apartment: Apartment?
    deinit { print("\(name) is being deinitialized") }
}

class Apartment {
    let unit: String
    init(unit: String) { self.unit = unit }
    weak var tenant: Person?
    deinit { print("Apartment \(unit) is being deinitialized") }
}

// 인스턴스 생성 (Person의 강한참조: 1, Apartment의 강한참조: 1)
var person: Person? = Person(name: "john")
var apartment: Apartment? = Apartment(unit: "")

// person.apartment는 Apartment 클래스를 강한참조
// apartment.tenant는 Person 클래스를 약한참조
// (Person의 강한참조: 1, Apartment의 강한참조: 2)
person?.apartment = apartment
apartment?.tenant = person

// person객체가 소멸되면 apartment.tenant가 약한참조로 nil이 된다.
// (Person의 강한참조: 0, Apartment의 강한참조: 0)
person = nil
apartment = nil

unowned: 옵셔널 형식이 아니며, 참조하는 클래스보다 수명이 같거나 긴 경우에만 사용합니다. Swift5 업데이트 이후로 unowned도 옵셔널 형식을 가질 수 있지만, 참조하는 클래스가 nil이고 접근할 때 앱 크래시가 여전히 발생합니다.

앱크래시를 방지하기 위해 보통 절대로 메모리 해제하지 않는 객체를 참조할 때 사용합니다.

// 서로 참조하는 클래스 두개 생성
class Customer {
    let name: String
    var card: CreditCard?
    init(name: String) {
        self.name = name
    }
    deinit { print("\(name) is being deinitialized") }
}

class CreditCard {
    let number: UInt64
    unowned let customer: Customer
    init(number: UInt64, customer: Customer) {
        self.number = number
        self.customer = customer
    }
    deinit { print("Card #\(number) is being deinitialized") }
}

// 인스턴스 생성
var john: Customer?

// (Customer 강한참조: 1, CreditCard 미소유 참조)
// CreditCard의 수명은 Customer과 같기때문에 미소유 참조를 하였다.
// 만약 CreditCard 인스턴스를 생성하고, Customer가 nil일때 CreditCard.customer을 접근하면 앱 크래시 오류가 발생한다
john = Customer(name: "John Appleseed")
john!.card = CreditCard(number: 1234_5678_9012_3456, customer: john!)

서로 참조하는 객체의 수명이나 기획의도에 따라 키워드를 선택할 수 있다.

모든 서로 참조는 weak 키워드와 함께 쓰면 되지않을까?

unowned는 치명적인 오류를 발생하기 때문에 사용하지 않고 모든 서로참조를 weak 키워드와 함께 사용하면 되는 거 아닌가? 생각이 들었다. 기본적으로 weak는 옵셔널 형식의 약한 참조이다. 이에 따라 접근하기 위해 옵셔널 체이닝을 통해 접근하며, 언래핑이 필요하다.

그렇기 때문에 사용함에 있어서 값이 nil이 아님을 항상 증명해야 하고, 참조하는 객체가 메모리에서 내려가면 nil이 되므로 사이드 이펙트 발생 가능성 또한 존재하게 된다.

객체가 nil이 되지 않는 경우에는 weak보다 unowned 키워드가 더 적절하다.

둘 다 쓸 수 있는 상황에선 단순 취향 차이로 사용될 수 있을까?

두 개의 키워드는 사용목적은 같지만 성능면에서 차이가 드러납니다.

그전에 직접 앱을 돌려보면서 reference count를 알아봅시다.

class Person {
    let name: String
    init(name: String) { self.name = name }
    var apartment: Apartment?
    deinit { print("\(name) is being deinitialized") }
}


class Apartment {
    let unit: String
    init(unit: String) { self.unit = unit }
    var tenant: Person?
    deinit { print("Apartment \(unit) is being deinitialized") }
}

먼저 두 개의 서로참조 클래스를 만들었습니다.

이를 lldb의 refCount를 확인하는 명령어를 통해 참조 카운트가 어떻게 진행되는지 알아보겠습니다.

명령어는 아래와 같습니다.

language swift refcount (클래스 변수명)

첫 번째로는 인스턴스 생성만 구현된 경우입니다.

var person: Person? = Person(name: "john")
var apartment: Apartment? = Apartment(unit: "unit")

중단을 통해 참조카운팅을 확인해 보니 세 가지 유형의 참조가 카운팅되는걸 볼 수 있었습니다.

ARC를 공부했을 때 Strong Count만 세면 되는 줄 알았는데 실제로는 세가지 유형이 존재하는 걸 알 수 있었습니다.

근데 왜 인스턴스만 생성하고 서로 참조하지 않고 있는데 strong count = 3이 될까요?

-> lldb에서 해당 참조카운팅을 확인하기 위해 참조하고 일시적으로 메모리에 남겨두기 때문에 strong count = 3이 됩니다. 실제로는 그렇지 않습니다.

두 번째로는 서로 참조를 구현한 경우입니다.

person?.apartment = apartment
apartment?.tenant = person

서로 참조하니 strong 카운트가 1 증가했습니다.

바로 person변수와 aparment에 nil을 주입시키겠습니다.

세 번째로 nil을 할당한 경우

person = nil
apartment = nil

변수에 nil을 대입하니 lldb에서 더 이상 접근할 수 없었습니다. 대신 Debug Memory Graph를 통해 메모리가 누수되었다는 것을 확인할 수 있습니다.

위 카운팅처럼 weak, unowned도 모두 카운팅이 되고 있었습니다.

- strong: 객체에 대한 강한 참조의 개수를 셉니다. 강한 참조의 카운트가 0이 되면 deinit이 호출됩니다. 이 시점에서 unowned 접근은 앱크래시, weak 접근은 nil을 리턴합니다.

- unowned: unowned의 참조 개수를 셉니다. 강한 참조가 존재하면 +1이 추가됩니다. deinit이 완료되면 추가된 1이 차감됩니다. unowned가 0이 되면 최종적으로 메모리에서 해제합니다.

- weak: weak의 참조 개수를 셉니다. unowned 참조가 존재하면 +1이 추가됩니다. 객체가 메모리 할당 해제가 되면 추가된 1이 차감됩니다.

Side Table

추가적인 정보가 여기서 나오는데, Side Table은 Swift4.0에서부터 도입되었습니다.

객체 인스턴스가 생성됐을 때, ARC 카운팅과 함께 Side Table이 생성됩니다.

이는 객체의 간단한 정보들을 담고 있습니다. (참조 주소와 같은)

Side Table은 weak/unowned참조가 존재할 때 생성되고, 최종적으로 weak카운트가 0이 될 때 소멸됩니다.

weak 접근은 사이드 테이블을 통해 객체 참조 주소에 접근하게 됩니다. 이는 간접접근이라 볼 수 있습니다.

unowned은 별도로 사이드테이블을 통한 것이 아닌 직접 접근하게 됩니다.

weak와 unowned의 성능차이는 눈에 띌 정도로 나타나진 않지만, weak를 통한 접근은 추가적인 비용이 발생하기 때문에, 굳이 비교하자면 weak보다 unowned가 더 빠르다고 볼 수 있습니다.

메모리 누수 방지를 위해 strong 참조만 신경 썼지만, 더 많은 카운팅이 존재했고, weak와 unowned의 차이를 알 수 있었습니다!

클로저가 아직 익숙하지 않아서 함수에서 사용된 후행클로저를 좀 자세히 알고 싶어서 작성합니다.

후행 클로저

함수의 마지막 인수에 클로저 표현식을 전달해야 하고 클로저 표현식이 긴 경우 후행 클로저로 작성하면 가독성이 더 좋아집니다.

func someFunctionThatTakesAClosure(closure: () -> Void) {
    // function body goes here
}


// Here's how you call this function without using a trailing closure:


someFunctionThatTakesAClosure(closure: {
    // closure's body goes here
})


// Here's how you call this function with a trailing closure instead:


someFunctionThatTakesAClosure() {
    // trailing closure's body goes here
}

자주 사용했던 고차함수 map도 후행클로저로 더 가독성 있게 표현할 수 있습니다.

let num = arr.map{ $0.description }

이는 파라미터로 인자를 받아서 클로저에 실행할 수도 있고, 받지않고 실행할 수 있습니다.

// 인자 없이 후행 클로저
func calculate(_ closure: (Int, Int) -> String ) {
    print(closure(10, 20))
}
// 인자를 전달하는 후행클로저
func calculate2(_ num1: Int,_ num2: Int,_ closure: (Int, Int) -> String) {
    let result = closure(num1, num2)
}

// 후행 클로저의 구현부는 함수의 호출부에서 구성
calculate { num1, num2 in
    return "\(num1 + num2)"
}

calculate2(10, 20) { num1, num2 in
    return "\(num1 + num2)"
}