이전글 : SwiftData 알아보기 (2)

위 글에서 @Query 에 대해 짚어보다가 @Query는 정렬, 정렬, 필터링 및 애니메이션 변경을 구성하는 간단한 구문을 제공합니다.

@Query (sort: \.created) private var cards: [Card]

이 코드를 만났는데요!

sort: \.created

이 부분! 샘플 코드의 Card 구조체에는 created 라는 프로퍼티가 없고 creationDate은 존재했는데 뭘 기준으로 정렬하는건지 궁금해서 이것저것 찾아봤습니다!

그래서 Query 공식문서를 탐방했고..?

'음 sort는 [SortDescriptor<Element>] 형식이구나..'

'Compared.type에 의해 결정한다고?' 그건 또 뭐지..? 하면서 타고타고 가다가

SortOrder까지 왔는데요.

현재는 forward(오름차순)와 reverse(내림차순) 정도만 정의되어 있었고

영상에서 소개됐던 created는 볼 수 없었습니다. 😅

셋 다 코드를 쳐봐도 제대로 동작하지 않았고, 오류는 동일했습니다.

  Cannot infer key path type from context; consider explicitly specifying a root type
  컨텍스트에서 키 경로 유형을 유추할 수 없으므로 루트 유형을 명시적으로 지정하는 것이 좋습니다.

결과적으로 문제가 해결되진 않았지만 보라색, 하얀색을 보아하니 어느정도는 공식 문서에 있는대로 forward, reverse 만 있는 상태가 맞는 것 같고 created 는 추후에 업데이트 되지 않나 기대해봅니다. 오류를 어떻게 해결하면 좋은지 아직 몰라서 때문에 패스! SortDescriptor를 이용한 코드가 없었기 때문인지 아닌지도 아직 모르겠네요. 조금 더 사용해봐야겠습니다 ㅎㅎ 삽질 끝!

짧은 결론 : 아직 안되더라!

23.07.02 수정 : 됩니다!

import Foundation
import SwiftData

@Model
class Note {
    @Attribute(.unique) var id: String
    var content: String
    var createdAt: Date

    @Relationship(inverse: \Tag.notes) var tags: [Tag]

    init(id: String, content: String) {
        self.id = id
        self.content = content
        self.createdAt = .now
    }
}

라는 모델 객체를 선언하고

struct NoteListView: View {

    @Environment(\.modelContext) private var context
    @Query(sort: \.createdAt , order: .reverse) var allNotes: [Note]

    var body: some View {
        // 생략
    }
}

이렇게 Note 객체에서 Sort할 수 있는 기준인 Date 타입을 선택하면 된다.

• 영상 : Build an app with SwiftData
• 이전글 : SwiftData 알아보기 (1)

안녕하세요! 오늘부터 닉네임을 바꾼 구 비비(BIBI) 현 _토브(Tov)_입니다.

iOS 개발자 커뮤니티에서 활동하시는 `비비`분들이 저 포함 4명이더라구요..
'흔들리는 비비들속에서 내 샴푸향 ... 느낄 수 있을까 ...?'

?? : 아니

... 그래서 바꿨습니다...

...네

각설하고 이전글에 이어 SwiftData를 마저 탐방해보겠습니다! 이번엔 SwiftUI 환경에서 앱을 빌드하는 방법에 대해 설명해볼게요!

🌲 Meet the app : FlashCard

Apple에서 제공하는 샘플코드와 함께 살펴볼게요! SwiftData를 사용하여 카드 덱 데이터를 유지하고, 카드를 터치할 때마다 앞면과 뒷면을 Filp 할 수 있는 간단한 단어장 앱이에요!

🖐🏻 잠깐!

들어가기에 앞서 SwiftData를 적용하는데에 딱 3가지 매크로를 기억하면 됩니다!

1. @Model
2. @Binable
3. @Query

이외에는 아래 개념도 같이 다뤄볼게요!

• ModelContainer
• ModelContext

🌲 @Model & @Bindable & @Query

먼저 아주 간단하게 모델 객체를 만들어볼게요!

파일명 : Card.swift

1. import SwiftData
2. @Model

이 2가지만 하면됩니다.

🪄 @Model 적용 코드

// BEFORE Not using SwiftData
import Foundation

final class Card: ObservableObject {
    @Published var front: String
    @Published var back: String
    var creationDate: Date
    // ...
}

// AFTER: Using SwiftData
import Foundation
import SwiftData

@Model
final class Card {
    var front: String
    var back: String
    var creationDate: Date
    // ...
}

위와같이 @Model 매크로를 사용하면 Card가 Observable 프로토콜을 준수하게 되므로 ObservableObject로 사용할 수 있습니다. 따라서 Observable 및 @Published 속성 래퍼를 사용할 필요가 없어집니다.

@Observable

새롭게 업데이트된 @Observable 매크로로 인해 조금 더 쉽게 데이터 바인딩 방식이 바뀌었다고 하네요! ObservedObject 속성 래퍼를 Bindable로 변경하는것만으로 적용된 걸 확인할 수 있었습니다!

이와 관련된 세션이 따로 있어서 보긴 했지만, 직접적으로 SwiftData 와의 관련 여부를 설명해 주진 않았던 것으로 기억해요. 하지만 @Binable을 채택하여 바인딩 하는 걸로 보아서는 @Model 매크로 안에 @Observable 매크로가 포함되어 있을 수도 있겠다고 추측됩니다. 개인적인 견해일 뿐입니다!ㅎㅎ

파일명 : CardEditorView.swift

1. import SwiftData
2. @ObservedObject → @Bindable

어때요, 참 쉽죠?

🪄 @Bindable 적용 코드

// BEFORE Not using SwiftData
struct CardEditorView: View {
    @ObservedObject var card: Card

// AFTER: Using SwiftData
struct CardEditorView: View {
    @Bindable var card: Card

@Query를 적용하기 전에 간단하게 개념을 짚고 넘어가보겠습니다!

🌿 @Query 란?

• SwiftData에서 모델을 쿼리하는 새로운 Property wrapper 입니다.
• @State가 수행하는 방식과 유사하게 _모델이 변경될 때마다 업데이트된 뷰를 트리거_합니다.
• 모든 View는 필요한 만큼 @Query 프로퍼티를 가질 수 있습니다.
• @Query는 모델 컨테이너에서 모델 컨텍스트를 가져와 데이터 소스로 사용합니다.
• @Query는 정렬, 정렬, 필터링 및 애니메이션 변경을 구성하는 간단한 구문을 제공합니다.

@Query (sort: \.created) private var cards: [Card]

🙄 Sort 되긴 하는거야 ..? 갑자기 이런 궁금증이 생겨 알아보았는데요. 삽질이 조금 길어졌네요 😅 접기 기능을 이용하려고 했는데 velog는 적용이 안되네요...! 궁금하신 분들만 보세요 !

🪄 @Query 적용 코드

파일명 : ContentView.swift

1. import SwiftData
2. @State → @Query

// BEFORE Not using SwiftData
import SwiftUI

struct ContentView: View {
    @State private var cards: [Card] = SampleDeck.contents
    // ...
}

// AFTER: Using SwiftData
import SwiftUI
import SwiftData

struct ContentView: View {
    @Query private var cards: [Card]
    // ...
}

위와같이 @Query 를 통해 Observable 유형의 속성이 변경되면 데이터를 자동으로 View에 업데이트 됩니다.

우선 여기까지는 SwiftData와 관련된 매크로 3가지를 사용하는 방법에 대해서 소개했습니다! 이 아래부터는 모델 컨테이너와 모델 컨텍스트를 이용하여 실질적인 데이터 처리를 다뤄보겠습니다.

🌲 ModelContainer & ModelContext & Preview

🌿 modelContainer

새로운 View Modifier입니다.

🌱 모델 컨테이너 설정하기

모델 컨테이너를 지정하지 않으면 뷰에서 데이터를 가져올 수 없습니다.

루트뷰에서 설정하는 경우 하위뷰에서 모델 컨텍스트를 이용해 데이터를 바인딩할 수 있습니다.

하위 뷰에서 설정할 경우 그보다 더 하위에 해당하는 뷰에 한하여 모델 컨테이너가 적용됩니다.

🌱 스토리지 스택 생성하기

.modelContainer(for: Card.self)

이 코드만 작성하면 하위 뷰에서 @Query가 사용할 컨텍스트를 포함하여 전체 스토리지 스택을 생성합니다.

🌱 하나의 뷰는 하나 이상의 모델 컨테이너를 포함할 수 있습니다.

.modelContainer(for: [Trip.self, BucketListItem.self, LivingAccommodation.self])

🌿 modelContext

새롭게 출시된 Swift의 Environment variable 입니다.

@Environment (\.modelContext) private var modelContext

이건 modelContainer를 지정할 때 자동으로 환경 변수가 설정된다고 하네요.

🌱 모델 컨텍스트에 대한 액세스를 제공합니다.

modelContext.뭐시기 로 접근할 수 있습니다.

let newCard = Card(front: "Sample Front", back: "Sample Back")
modelContext.insert(object: newCard)

🌱 원하는 만큼 가질 수 있습니다.

이것또한 modelContainer와 마찬가지로 각 View에는 단일 컨텍스트가 있지만, 일반적으로 Application은 필요한 만큼 많이 가질 수 있다고 합니다.

Model your schema with SwiftData세션에서 modelContainer를 배열형태로 선언하는 걸 봤는데 modelContext는 다중으로 어떻게 사용하는건지 아직 못봤네요! 다음 글에서 설명할 수 있게 찾아보겠습니다!

특별한점은 CoreData에서 save()를 작동시켜야만 저장되었던것과 달리, insert, update, delete 와 같은 UI 관련 이벤트에 의해 자동 저장 트리거가 발생합니다! 편리하네요 😀

🌿 Preview에 DummyData 띄우기

import SwiftData

@MainActor
let previewContainer: ModelContainer = {
    do {
        let container = try ModelContainer(
            for: Card.self, ModelConfiguration(inMemory: true)
        )
        for card in SampleDeck.contents {
            container.mainContext.insert(object: card)
        }
        return container
    } catch {
        fatalError("Failed to create container")
    }
}()

@MainActor 매크로를 통해 프리뷰에서 보여줄 ModelContainer 를 정의합니다. 매크로에 대해서는 Write Swift macros 세션을 통해서 깊이 공부해봐야겠습니다.

Apple이 미리 만들어놓은 샘플 데이터는 아래와 같았습니다.

#Preview {
    ContentView()
        .frame(minWidth: 500, minHeight: 500)
        .modelContainer(previewContainer)
}

위에서 정의한 previewContainer를 불러오기만 프리뷰에서 볼 수 있게됩니다!

하지~만? 버그인지 현재 해당 코드는 프리뷰가 작동하지 않아서 피드백 넣어놓은 상태입니다…🥲

🌲 [Bonus] Document-based apps

SwiftData를 통해 간편하게 문서 기반 앱을 개발 할 수 있게되었습니다.

문서 기반 앱은 사용자가 다양한 유형의 문서를 작성, 열기, 보기, 편집할 수 있는 애플리케이션입니다.

예를 들어 pages, keynote 와 같이 하나의 파일 형태로 FlashCard 묶음을 저장할 수 있게 된다는거죠!

문서 기반 앱을 설정하기 위해 DocumentGroup 이니셜라이저를 사용하여 앱을 해당 형식의 앱으로 전환합니다. 모델 유형(Card.self), 콘텐츠 유형 및 뷰 빌더를 전달합니다.

import SwiftUI
import SwiftData

@main
struct SwiftDataFlashCardSample: App {
    var body: some Scene {
        #if os(iOS) || os(macOS)
        DocumentGroup(editing: Card.self, contentType: .flashCards) {
            ContentView()
        }
        #else
        WindowGroup {
            ContentView()
                .modelContainer(for: Card.self)
        }
        #endif
    }
}

contentType은 SwiftData 문서의 고유한 표현을 나타내는 데 사용됩니다. 이는 파일 확장자와 연결됩니다.

잠깐 ! 여기서 콘텐츠 유형이란 크게 2가지로 나누어 볼 수 있는데

JPEG 와 같은 Binary data document 와 Xcode 프로젝트 파일 같은 Package document가 있습니다.

SwiftData 문서는 패키지 형식이며, 외부에 표시된 속성은 문서 패키지의 일부가 됩니다.

import UniformTypeIdentifiers

extension UTType {
    static var flashCards = UTType(exportedAs: "com.example.flashCards")
}

UTType을 init 할 때 exportedAs 파라미터에는 앱의 identifier String을 넣어주면 됩니다.

그리고 info.plist - Exported Type Identifiers 를 아래와 같이 설정합니다.

*이때 extension에서 작성한 identifier와 String이 일치하지 않으면 에러가 발생할 수 있습니다.

설정을 마치면

.sampledeck 이라는 확장자를 가진 패키지 형식의 Flash Cards Deck 파일을 따로 저장할 수 있게됩니다.

🌲 마무리하며 …

설명이 좀 길었지만, 생각보다 SwiftData를 사용하는 것 자체는 쉽다는 생각을 했습니다! 하지만 아직 베타라서 그런지 WWDC 세션에서 제공된 프리뷰 코드나, sort 코드가 잘 작동하지 않아서 아쉬웠습니다. 포럼에도 프리뷰 오류에 대한 질문들이 있어서 적용해봤고 그것도 해결되진 않았습니다..ㅎㅎ 얼른 안정적으로 자리 잡아서 관계형 데이터를 이용한 앱을 조금 더 쉽게 만들어보고 싶네요!

긴 글 읽어주셔서 감사합니다..! 언제나 지적이나 질문 환영합니다!

WWDC 영상 바로가기 : Meet SwiftData

안녕하세요 비비입니다! WWDC23 영상을 탐방하다가 SwiftData에 관심이 생겨 보던 중 보기만하면 기억에 남지 않을 것 같아서 기록을 시작해봅니다.

개인적으로는 JAVA의 SpringBoot 프레임워크가 생각나서 뭔가 CoreData 보다 친숙한 느낌이라 얼른 사용해보고싶네요!

정리한 내용 중 오역이 있다면 언제든지 말씀해주세요 😄

🌲 SwiftData란?

데이터 모델링 및 관리를 위한 프레임워크입니다. SwiftUI와 마찬가지로 외부 파일 형식이 없는 코드에 전적으로 집중하고, 원활한 API 경험을 위해 _새로운 Swift 매크로_가 제공하는 표현력에 의존합니다. 또한 SwiftUI와 자연스럽게 통합되며 CloudKit 및 Widgets와 같은 다른 플랫폼 기능과 함께 작동합니다.

🌲 Using the model

@Model 매크로 사용하기

• Swift 코드에서 모델의 스키마를 정의하는 데 사용됩니다.
• 클래스를 장식하는걸로 간단하게 스키마를 생성할 수 있습니다.

import SwiftData

@Model
class Trip {
    var name: String
    var destination: String
    var endDate: Date
    var startDate: Date

    var bucketList: [BucketListItem]? = []
    var livingAccommodation: LivingAccommodation?
}

*스키마(Schema): Database의 구조와 제약조건에 관해 전반적인 명세를 기술한 것. 즉 어떤 속성(Attribute)들로 이루어진 개체(Entity)들과, 그 개체들끼리의 관계(Relation)에 대한 정의 및 제약조건들을 기술한 것 입니다.

🌿 속성(Attributes)

🌱 Attributes inferred from properties 속성으로 즉시 사용할 수 있도록 값 유형 속성을 조정합니다.

🌱 Support for basic value types String, Int 및 Float와 같은 기본 값 유형이 포함됩니다.

🌱 Complex value types

• Struct
• Enum
• Codable
• Collections of value types

컬렉션을 포함하여 구조체, 열거형 및 코딩 가능한 유형과 같은 보다 복잡한 값 유형을 포함할 수 있습니다. 즉, @Model 매크로만으로 속성을 쉽게 정의할 수 있습니다.

🌿 관계(Relationships)

🌱 Relationships are inferred from reference types

• Other model types
• Collections of model types

SwiftData 모델은 유형을 관계로 참조합니다. 관계 및 모델 유형 컬렉션을 사용하여 모델 유형 간에 연결할 수 있습니다.

🌿 Additional metadata

🌱 @Model 은 저장된 모든 속성을 수정할 수 있습니다.

🌱 아래의 매크로를 이용해 속성과 관계를 정의합니다.

• @Attribute
• @Relationship

🌱 @Transient로 속성을 제외할 수 있습니다. 👉🏻 이건 Model your schema with SwiftData 에서 자세히 봐야겠습니다!

@Model
class Trip {
    @Attribute(.unique) var name: String // Unique 지정
    var destination: String
    var endDate: Date
    var startDate: Date

    @Relationship(.cascade) var bucketList: [BucketListItem]? = [] // Trip 객체 삭제시 같이 삭제되도록 설정
    var livingAccommodation: LivingAccommodation?
}

🌲 Working with your data

데이터 바인딩에 사용되는 2가지 주요 개체 ModelContainer 및 ModelContext 를 살펴볼게요!

🌿 Model Container

저장하려는 모델 유형 목록을 지정하기만 하면 모델 컨테이너를 만들 수 있습니다. 컨테이너를 설정하여 모델 컨텍스트로 데이터를 가져오고 저장할 준비를 할 수 있습니다.

🌱 Persistence Backend 모델 유형에 대한 영구 백엔드 제공

🌱 Customized with configurations & Provides schema migration options configurations 속성으로 URL, CloudKit 및 그룹 컨테이너 식별자, 마이그레이션 옵션 등을 커스터마이징할 수 있습니다.

// Initialize with only a schema
let container = try ModelContainer([Trip.self, LivingAccommodation.self])

// Initialize with configurations
let container = try ModelContainer(
    for: [Trip.self, LivingAccommodation.self],
    configurations: ModelConfiguration(url: URL("path"))
)

🧐 이 부분에서는 Trip과 LivingAccommodation을 동시에 container에 담는 것 같은데 DeepDive하면서 어떻게 정의되는건지 한번 더 살펴봐야겠습니다.

🌱 SwiftUI에서 사용하는 방법

import SwiftUI

@main
struct TripsApp: App {
    var body: some Scene {
        WindowGroup {
            ContentView()
        }
        .modelContainer(
            for: [Trip.self, LivingAccommodation.self]
        )
    }
}

🌿 Model Context

🌱 Tracking updates 🌱 Fetching model 🌱 Saving changes 🌱 Undoing changes

업데이트 추적, 데이터 가져오기, 변경 사항 저장하기, 변경 사항 실행 쉬소하기 기능의 인터페이스입니다.

import SwiftUI

struct ContextView : View {
    @Environment(\.modelContext) private var context
}

import SwiftData

// 1. 일반적으로 모델 컨테이너를 생성한 후 뷰의 환경에서 modelContext를 가져오는 경우
let context = container.mainContext

// 뷰 계층 구조 외부에서 공유된 기본 액터 바인딩 컨텍스트를 제공하도록 모델 컨테이너에 요청하거나
// 2. 주어진 모델 컨테이너에 대한 새 컨텍스트를 간단히 인스턴스화 하는 경우
let context = ModelContext(container)

컨텍스트가 있으면 데이터를 가져올 준비가 된 것입니다.

🧐 라고 소개는 되어있지만, 정확하게 context가 뭘 의미하는건지는 조금 더 알아봐야겠습니다. 왜냐하면 위에서 modelContainer 가 [Trip.self, LivingAccommodation.self]으로 2개의 model을 동시에 가지고 있는데 context를 활용하여 데이터를 어떻게 가져온다는건지 이 코드만 보고 확신할 수는 없네요..!

🌿 Fetching your data

🌱  새로운 Swift 기본 유형

• Predicate
• FetchDescriptor

🌱  SortDescriptor의 개선 사항

🪴 Predicate

let today = Date()
let tripPredicate = #Predicate<Trip> { 
    $0.destination == "New York" && // 목적지 : 뉴욕
    $0.name.contains("birthday") && // 키워드 : 생일
    $0.startDate > today // 오늘 이후, 계획된 여행 탐색
}

메모리의 데이터를 필터링 하여 가져오기 위한 쿼리 조건이라고 해야할까요 CoreData 에서 사용하던 NSPredicate의 iOS 17 버전이라고 할 수 있습니다.

🪴 FetchDescriptor

let descriptor = FetchDescriptor<Trip>(predicate: tripPredicate)

let trips = try context.fetch(descriptor)

FetchDescriptor는 SwiftData 쿼리를 맞춤화하는 방법을 제공합니다. 위와같이 _필터 조건을 지정_한 후 FetchDescriptor를 통해 가져올 수 있습니다.

🪴 SortDescriptor

🌱 Updated to support all Comparable types Swift native keypaths 기본 Swift 유형 및 키 경로를 지원하기 위해 모든 비교 유형을 지원하도록 업데이트 되었습니다.

let descriptor = FetchDescriptor<Trip>(
    sortBy: SortDescriptor(\Trip.name),
    predicate: tripPredicate
)

let trips = try context.fetch(descriptor)

SortDescriptor를 사용하여 가져온 여행을 구성할 순서를 지정할 수 있습니다.

🌿 More FetchDescriptor options

Predicate 및 SortDescriptor 외에도 prefetch할 관련 개체를 지정하고 결과 수를 제한하고 결과에서 저장되지 않은 변경 사항을 제외하는 등의 작업을 수행할 수 있습니다.

🌱 Relationships to prefetch 🌱 Result limits 🌱 Exclude unsaved changes

🌿 Modifying your data

ModelContext를 사용하여 이러한 작업을 구동함으로써 데이터를 쉽게 생성, 삭제 및 변경할 수 있습니다.

🌱 Basic operations (CRUD)

• Inserting
• Deleting
• Saving
• Changing

var myTrip = Trip(name: "Birthday Trip", destination: "New York")

// Insert a new trip
context.insert(myTrip)

// Delete an existing trip
context.delete(myTrip)

// Manually save changes to the context
try context.save()

@Model 매크로는 ModelContext가 변경 사항을 자동으로 추적하고 다음 저장 작업에 포함하도록 돕는다고 합니다.

🌲 Using SwiftData with SwiftUI

• SwiftUI와의 원활한 통합
• 쉬운 구성
• 자동으로 데이터 Fetching

🌿 View Modifiers

데이터 저장소를 구성하고, 옵션을 변경하고, 실행 취소를 활성화하고, 자동 저장을 전환할 수 있습니다.

🌱 Leverage scene and view modifiers (뭐라고 해석하면 좋을지 혹시 아시는 분 계실까요 ?) 🌱 .modelContainer를 사용하여 데이터 저장소 구성 🌱 SwiftUI environment로 등록하여 사용하기

설정한 후 데이터 사용을 시작하는 가장 쉬운 방법은 새로운 @Query 속성 래퍼입니다. 한 줄의 코드로 데이터베이스에 저장된 모든 항목을 쉽게 로드하고 필터링할 수 있습니다.

import SwiftUI

struct ContentView: View  {
    @Query(sort: \.startDate, order: .reverse) var trips: [Trip]
    @Environment(\.modelContext) var modelContext

    var body: some View {
       NavigationStack() {
          List {
             ForEach(trips) { trip in 
                 // ...
             }
          }
       }
    }
}

🌲 마무리하며…

Meet SwiftData는 소개하는 내용이 많아 구체적인 코드를 살펴보기엔 짧은 감이 있네요 ! 다음은 Build an app with SwiftData를 보고 조금 더 DeepDive 해보겠습니다! 부족한 글이지만 읽어주셔서 감사합니다 😊

WWDC 영상 바로가기 : What's new in Screen Time API

🔵 지난 iOS15 릴리즈 주요 사항

🔹 Family Controls

• Screen Time API에 대한 엑세스 권한을 부여하는 역할. 본질적 게이트웨이
• 자녀 보호 앱 제거 & 우회 방지
• 가족이 사용하는 앱을 위한 개인 정보 보호 토큰

🔹 Managed Setting

• 기기에 지속적인 제한 설정 기능
• 웹 콘텐츠 필터링 제공
• 맞춤형 UI로 앱&웹 보호

🔹 Device Activity

• 디바이스 활동 일정의 시작 및 종료 시 코드 실행
• 사용 한계치 도달 시 코드 실행

🔵 iOS16 데모 앱 : Worklog

특정 수치들이 충족될 때까지 특정 앱의 사용을 제한하는 기능

🔹 NEW Family Controls

iOS15 iCloud 승인을 통해서만 자녀의 기기를 승인할 수 있었음

→ iOS16 자신의 기기에서 개별 사용자를 승인할 수 있게 되었음

• 개별 사용자가 스스로 인증
• 여러 개의 개별 인증
• 개별 인증에 대한 앱 제거 또는 iCloud 로그아웃 제한 없음

import FamilyControls

let center = AuthorizationCenter.shared

Task {
    do {
        try await center.requestAuthorization(for: .individual)
    } catch {
        print(error)
    }
}

기존 코드보다 훨씬 간결해졌다.

🔹 Managed Settings Store

현재 사용자나 기기에 설정을 적용하는 데이터 저장소

iOS15 프로세스당 하나의 ManagedSettingsStore 만 허용됨, 또한 앱과 DeviceActivity의 확장 프로그램은 별도로 ManagedSettingsStore가 필요해서 DeviceActivity에 대한 응답에서 설정을 변경하기 어려웠음

→ iOS16 프로세스마다 고유한 이름을 가진 ManagedSettingsStore를 최대 50개 만들 수 있음. 이렇게 명명된 ManagedSettingsStore들(Named stores)은 앱과 모든 앱 확장프로그램에서 자동으로 공유됨. 모든 Named stores에서 한번에 설정 제거도 가능해짐

import ManagedSettings

extension ManagedSettingsStore.Name {
    static let youTube = Self("YouTube")
}

final class BlockingManager {
    func managedSettingStoreSetup() {
        let youTubeCategory = ActivityCategoryToken() // 이거 안됨
        let youTubeStore = ManagedSettingsStore(named: .youTube)
        youTubeStore.shield.applicationCategories = .specific(except: [youTubeCategory])
        youTubeStore.shield.webDomainCategories = .specific(except: [youTubeCategory])
    }
}

영상에선 ActivityCategoryToken에 대한 사용 방법을 알려주지 않아서 따로 찾아봤다.

How to use categories in Managed S… | Apple Developer Forums

ActivityCategoryToken | Apple Developer Documentation

FamilyActivitySelection | Apple Developer Documentation

FamilyActivityPicker | Apple Developer Documentation

여기까지 보고 이전에 작성했던 예제를 살펴봤다.

FamilyActivityPicker 에서 유저가 선택한 앱들의 정보를 FamilyActivitySelection에 담아 model에 전달한다.

// APP: Choose the Apps to Discourage

import FamilyControls
import SwiftUI

@StateObject var model = MyModel()
@State var isPresented = false

var body: some View {
        Button("Select Apps to Discourage") {
                isPresented = true
        }
        .familyActivityPicker(isPresented: $isPresented, selection: $model.selectionTpDiscourage)
}

Is it possible to use familly acti… | Apple Developer Forums

문제는 SwiftUI 코드라서 UIHostingController를 사용해야한다.

Use SwiftUI in UIKit View Controllers with UIHostingController

UIHostingController in SwiftUI 2020 (Use in UIViewController) - How To Bridge UIKit with SwiftUI.

아무튼 나머지 코드를 먼저 살펴보자면

import SwiftUI
import DeviceActivity

extension DeviceActivityName {
        static let activity = Self("activity")
}

let deviceActivityCenter = DeviceActivityCenter()

Button("Allow for Evening") {
                try? deviceActivityCenter.startMonitoring(
                    .activity,
                    during: DeviceActivitySchedule(
                        intervalStart: DateComponents(hour: 18),
                        intervalEnd: DateComponents(hour: 20),
                        repeats: true)
                )
            }

import DeviceActivity
import ManagedSettings

final class BlockingMonitor: DeviceActivityMonitor {

    // let database = BarkDataBase() //TODO: Make database for Token of the published category
    override func intervalDidStart(for activity: DeviceActivityName) {
        super.intervalDidStart(for: activity)
        let youTubeStore = ManagedSettingsStore(named: .youTube)
        youTubeStore.clearAllSettings() //youTube 제약이 시작되면 이전의 제약을 모두 clear한다.
    }
    override func intervalDidEnd(for activity: DeviceActivityName) {
        super.intervalDidEnd(for: activity)

        let appStore = ManagedSettingsStore(named: .youTube)
//        let appCategory = database.appCategoryToken //TODO: Make database for save&load `youTubeCategoryToken`
        youTubeStore.shield.applicationCategories = .specific([youTubeStore])
        youTubeStore.shield.webDomainCategories = .specific([youTubeStore])
    }
}

🔹 DeviceActivity

현재 사용자나 기기에 설정을 적용하는 데이터 저장소

iOS15 앱과 웹 사이트에 대한 사용량 허용치와 사용 시간대에 반응했음

→ iOS16 SwiftUI를 사용한 사용자 지정 사용량 보고서를 만들 수 있게 됐음. 사용량 데이터는 새로운 확장 포인트를 통해 사용자에게 표시될 데이터와 화면에 표현될 방식을 사용자 정의 할 수 있음. 이를 DeviceActivityReport는 최종 사용자의 개인정보 보호를 보장함

이걸 이용해서 보고서를 개인화하여 뷰에 표시할 수 있고, 원하는 차트타입 뷰를 구현해서 보여주면 된다는데 끝까지 다 보고 적용시켜보려고 SwiftUI 프로젝트 예제도 해봤는데, 코드를 너무 일부만 보여주고 샘플 코드조차 공개를 해놓지 않아서 도대체 어떻게 사용하라는 건지 모르겠다!

나머지는 공식문서를 보고 직접 이해하고 적용해보는 수 밖에 없는 듯 하다.

Screen Time API

참고 자료 : 원본 영상 / 공식 문서

스크린 타임은

1. 사용자와 가족이 앱과 웹사이트를 얼마나 자주 사용하는지 추적하고,
2. 제한을 설정하여 시간을 관리하고,
3. 가족 구성원과 사용량을 공유하여 기기 사용 현황을 파악할 수 있으며,
4. 마지막으로 자녀가 누구와 소통하는지 등을 관리할 수 있다.

📱 사용 환경

• iOS 15
• iPadOS 15

✅ 3가지 기본 원칙

1. 기존 제한에 대한 직접 API 액세스를 위한 최신 on Device 프레임워크 제공
2. 사용자 개인 정보 보호
3. 개발자가 새롭고 환상적인 동적 자녀 보호 환경을 만들 수 있도록 보장하는 것

🎞️ 3가지 프레임워크

✨ 1) Managed Setting Framework(관리 설정)

앱에서 스크린 타임에서 사용할 수 있는 제한 사항에 직접 액세스할 수 있다.

• 제한 설정할 수 있는 것
  • 계정 잠금
  • 비밀번호 변경 방지
  • 휍 트래픽 필터링
  • 애플리케이션 차단

✨ 2) Family Controls Framework(가족 제어)

가족 제어는 트위터의 개인정보 보호정책을 주도한다. 가족 공유를 활용하여 보호자 승인 없이 스크린 타임 API에 액세스 할 수 없도록 한다. 보호자의 승인을 받은 앱은 보호자 승인 없이 기기에서 제거할 수 없다. 또한 앱과 웹 사이트를 나타내는 _토큰_을 제공하여 _스크린 타임 API 전체에서 사용량을 모니터링하거나 제한_하는 데 사용된다. (가족 그룹 외부에서는 볼 수 없도록 정보가 모두 보호된다.)

✨ 3) Device Activity(디바이스 활동)

디바이스 활동은 _앱을 실행하지 않고도 코드를 실행할 수 있는 기능_을 제공한다. 앱에 웹 & 앱 사용을 모니터링하고 필요할 때 코드를 실행할 수 있는 새로운 방법을 제공한다. 디바이스 활동 일정과 이벤트

• 기기 활동 일정 : 시작될 때와 끝날 때 애플리케이션의 확장 프로그램을 호출하는 시간 창
• 이벤트 : 유저가 기기 활동 일정의 사용 임계값에 도달할 때 내선 번호를 호출하는 사용량 모니터.

앱은 어떤 유형의 사용량을 언제 모니터링할지 선언하기만 하면 된다.

🙄 세 가지 프레임워크를 결합하면?

1. 보호자와 자녀의 기기 모두 앱을 설치
2. 보호자가 자녀 기기에서 앱을 열기
3. 앱은 가족 제어를 통해 승인됨
4. 추후 보호자 기기의 앱에서 설정, 제한 및 규칙을 선택
5. 앱이 해당 정보를 자녀 기기로 보냄
6. 자녀 기기에서 앱이 장치 활동으로 일정 및 이벤트를 생성
7. 일정이 발생하거나 이벤트가 발생하면 앱의 장치 활동 확장이 호출됨
8. 확장 프로그램에서 관리 설정으로 제한 설정

📲 Demo App : Homework

보호자가 원하는 다른 앱의 사용량이 누적될 때까지 특정 앱에 대한 자녀의 액세스를 제한하여 좋은 습관을 장려하는 것이 주 기능이다.

✨ 1. Setup and authorizing Family Controls

가족 제어에 대한 승인을 요청하는 방법: 프로젝트 설정과 패밀리 컨트롤 승인

먼저 Xcode의 해당 Taget에서 Capability를 추가한다.

// APP: 권한 요청하기
import FamilyControls

AuthorizationCenter.shared.requestAuthorization { result in
        switch result {
        case .success():
                ...
        case .failure(let error):
                ...
        }
}

내 앱이 이전에 이 iPhone에서 실행된 적이 없기 때문에 요청 승인은 경고와 함께 보호자의 승인을 요청한다. 허용을 탭하면 계속하려면 보호자에게 Apple ID와 비밀번호로 인증하라는 메시지가 표시된다.

이때 보호자가 인증에 성공하면 요청인증을 호출하면 다시 경고 메시지를 표시하지 않고 자동으로 성공 여부를 반환한다.

오용을 방지하기 위해 로그인한 iCloud가 가족 공유를 사용하는 자녀가 아닌 경우 요청 승인은 실패를 반환한다.

앱에서 스크린 타임 API를 사용할 수 있도록 준비하는 것은 이렇게 쉽다.

가족 제어로 인증하면 앱에 다른 권한도 부여된다.

• 기기가 인증되면 사용자는 더 이상 iCloud에서 로그아웃할 수 없음
• 네트워크 확장 프레임워크로 구축된 on-device web content filters는 앱에 포함될 수 있으며 자동으로 설치되고 제거할 수 없음
• 이를 통해 앱에서 기기의 웹 트래픽을 필터링할 수 있음

자녀 보호 앱은 자녀가 앱을 실행하지 않을 가능성이 높은데도 자녀의 기기에서 코드가 실행되도록 하는 것이 어려운 부분이다.

스크린 타임 API의 경우, 기기 활동으로 백그라운드 코드 실행을 수행할 수 있는 새로운 방법을 만들었다.

기기 활동 확장은 나머지 스크린 타임 API와 상호 작용하는 주요 방법이 될 것이다.

✨ 2. Shield discouraged apps

반복되는 일정에 따라 보호자가 선택한 사용 금지 앱을 보호

자녀의 기기에서 앱이 실행되지 않고있어도, 보호자가 금지한 앱이 실행되지 않도록 스케줄을 설정하여 반복적으로 작동하게 하는 기능이다.

이 Extension을 구현하려면 DeviceActivityMonitor를 기본 클래스로 서브 클래싱 하여 모니터를 만들어주자.

// EXTENSION: Create a DeviceActivityMonitor

class MyMonitor: DeviceActivityMonitor {
        override func intervalDidStart(for activity: DeviceActivityName) {
                super.intervalDidStart(for: activity)
        }
        override func intervalDidEnd(for activity: DeviceActivityName) {
                super.intervalDidEnd(for: activity)
        }
}

이 함수들은 내 일정이 시작되고 종료된 후 기기를 처음 사용할 때 호출된다.

이제 DeviceActivityName과 DeviceActivitySchedule을 만들어야 한다.

// APP: Monitor a DeviceActivitySchedule

import DeviceActivity

// 1. 활동을 참조할 수 있는 이름 생성
extension DeviceActivityName {
        static let daily = Self("daily")
}

// 2. 활동을 모니터링할 시간 범위 설정
let schedule = DeviceActivitySchedule(
        intervalStart: DateComponents(hour: 0, minute: 0),
        intervalEnd: DateComponents(hour: 23, minute: 59),
        repeat: true
)

// 3. center를 통해 방금 생성한 이름과 일정으로 `startMonitoring` 호출
let center = DeviceActivityCenter()
try center.startMonitoring(.daily, during: schedule)

위 코드를 통해 일정이 시작되고 끝날 때마다 MyMonitor가 활동 이름(DeviceActivityName)과 함께 호출된다.

// APP: Choose the Apps to Discourage

import FamilyControls
import SwiftUI

@StateObject var model = MyModel()
@State var isPresented = false

var body: some View {
        Button("Select Apps to Discourage") {
                isPresented = true
        }
        .familyActivityPicker(isPresented: $isPresented, selection: $model.selectionTpDiscourage)
}

FamilyControls 프레임워크에는 작업을 위한 SwiftUI 요소인 familyActivityPicker (가족 활동 선택기)가 있다.

기본 앱의 UI에서 이 피커를 표시하고 보호자가 앱 or 웹을 카테고리 목록에서 선택한다.

이 피커의 반환값인 불투명 토큰(?)을 사용하여 제한 설정을 할 수 있다.

버튼을 통해 불러온 피커는 반환값을 모델의 속성에 바인딩한다.($model.selectionTpDiscourage)

// EXTENSION: Shied the Discouraged Apps

import DeviceActivity
import ManagedSettings // 추가

class MyMonitor: DeviceActivityMonitor {
        let store = ManagedSettingsStore() // 추가

        override func intervalDidStart(for activity: DeviceActivityName) {
                super.intervalDidStart(for: activity)

                let model = MyModel() // 모델 인스턴스
                let applicationos = model.selectionToDiscourage.applications // 선택된 앱 List

                store.shield.applications = applications.isEmpty ? nil : applications // store 등록
        }

        override func intervalDidEnd(for activity: DeviceActivityName) {
                super.intervalDidEnd(for: activity)

                store.shield.applications = nil
        }
}

// APP: Adding a DeviceActivityEvent
import DeviceActivity

extension DeviceActivityName {
        static let daily = Self("daily")
}

extension DeviceActivityEvent.Name { // 이벤트 이름 등록
        static let encouraged = Self("encouraged")
}

let schedule = DeviceActivitySchedule(
        intervalStart: DateComponents(hour: 0, minute: 0),
        intervalEnd: DateComponents(hour: 23, minute: 59),
        repeat: true
)

let model = MyModel()
let events = [DeviceActivityEvent.Name: DeviceActivityEvent] = [
        .encouraged: DeviceActivityEvent( // 이벤트 이름에 맞는 이벤트 생성
                    applications: model.selectionToEncourage.applicationTokens
                    threshold: DataComponents(minute: minutes)
        )
]

let center = DeviceActivityCenter()
try center.startMonitoring(.daily, during: schedule, events: events) // 이벤트 등록

✨ 3. Remove shields for meeting goal

권장 앱 사용 시간을 충분히 누적한 다음 차단을 해제하는 방법

// EXTENSION: Implement theh Threshold Function
import DeviceActivity
import ManagedSettings

class MyMonitor: DeviceActivityMonitor {
        let store = ManagedSettingStore() // store 인스턴스
        ...

        // 허용된 앱의 사용량이 누적되었을 때 호출됨
        override func eventDidReachThreshold(_ event: DeviceActivityEvent.Name, activity: DeviceActivityName) {
                super.eventDidReachThreshold(event, activity: activity)

                store.shield.applications = nil // 해당 이벤트가 충족되면 제한 해제
        }
}

✨ 4. Customize the shields

앱의 브랜딩과 기능에 맞게 shields를 커스텀 가능

• Material
• Title
• Icon
• Body
• primaryButton → Ask for Access
• secondaryButton → Open App
• Completion Handler

// EXTENSION: Create a ShieldConfigurationProvider

import ManagedSettings
import ManagedSettingsUI

class MyShieldConfiguration: ShieldConfigurationProvider {
        override func configuration(for application: Application) -> ShieldConfigutaion {
                return ShieldConfiguration(
                        backgroundEffect: ...
                        backgroundColor: ...
                        icon: ...
                        title: ShieldConfiguration.Label(
                                text: ...
                                color: ...
                        ),
                        subtitle: ShieldConfiguration.Label(
                                text: ...
                                color: ...
                        )
                )
        }
}

위 함수를 통해 Block 되었을 때의 화면을 커스텀할 수 있다.

// EXTENSION: Create a ShieldActionHandler

import ManagedSettings

class MyShieldActionExtension: ShieldActionHandler {
        override func handle(action: ShieldAction,
                                                     for application: Application,
                                                     completionHandler:
                                @escaping (ShieldActionResponse) -> Void {
                switch action {
                case .primaryButtonPressed:
                        completionHandler(.defer)
                case .secondaryButtonPressed:
                        completionHandler(.close)
                @unknown default:
                        fatalError()
                }
        }
}

위 함수를 통해 커스텀 핸들러를 지정할 수 있다.

📝 회고

현재 진행중인 Tublock 앱을 완성하기 위해 필요한 Screen Time API! 위 내용에서는 가족 공유가 사용된 예시만 있어서 없는 경우는 내가 직접 만들어봐야한다. 이 API를 사용하여 앱이 완성되면 어떻게 사용했는지도 문서화시켜 공유해볼 예정이다.

yeni가 초대해주신 WWDC 스터디 덕분에 한 주에 4개씩 공부할 수 있게됐다. 헤헤😁

이번엔 이진탐색 챕터를 공부하기로 했다. 4명 중 2명씩 나누어 2번 3번 실전 문제를 풀기로 했다. 나는 3번 문제에 당첨되어 파라메트릭 서치에 대해 배우게 됐다!

이진탐색에 대한 간략한 소개

이진탐색이란 이미 정렬되어있는 데이터 안에서 특정 값을 찾아내기 위해 반으로 나눠가며 찾는 탐색 알고리즘이다.

나는 CS50강의에서 전화번호부 찾기에 빗대어 설명하는 것을 들었다. 인덱스만으로 찾고자 하는 값에 금방 접근할 수 있으며, 찾고자 하는 값과 인덱스를 비교하여 앞으로 탐색할지, 뒤로 탐색할지 선택하고 반복하는 것 만으로 정보를 얻을 수 있기 때문이다.

(물론 이진탐색은 기본적으로 중간값을 기준으로 탐색해나가기 때문에 완벽하게 전화번호부 찾기 알고리즘이라고 단정지을 수는 없다.)

이진탐색의 원리

기본 원리는 입력된 정보의 반을 나누어 각각의 절반의 값에 더 근접한 쪽을 찾는 것이다. 즉 시작과 중간과 끝을 계속 바꿔가며 범위를 좁혀나간다.

이진탐색의 구현

1. 배열의 중간 값을 찾는다
2. 찾고자 하는 타겟과 일치한다면 즉시 종료 2-1. 타겟보다 작다면 중간 값을 끝으로 설정하여 다시 탐색 2-2. 타겟보다 크다면 중간 값을 시작으로 설정하여 다시 탐색
3. 위 과정을 반복한다

파라메트릭 서치에 대한 간략한 소개

이진탐색 중 중 파라메트릭 서치 알고리즘은 최적화 문제를 결정 문제로 바꾸어 해결하는 과정이다. 즉, 많은 데이터를 가지고 최적화가 필요한 문제라면 이 방법을 고려해야한다.

파라메트릭 서치의 원리

1. 구하고자 하는 값을 얻을 때 시도해야하는 방법 정하기
2. 그 값을 변경해가며 최적해인지 확인하기

🌀 뭐라는거야

이건 문제를 보면서 설명하는게 좋을 것 같다.

[문제] 떡볶이 떡 만들기

동빈이네 떡볶이 떡은 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 손님이 요청한 총 길이가 M일때, 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력조건

• 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1 <= N <= 1000000, 1 <= M <= 2000000000)
• 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.

출력조건

적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

입력 예시 4 6

출력 예시 19 15 10 17

🌀 풀이

파라메트릭 서치의 원리를 들어 예를 설명해보자면

1. 구하고자 하는 값 : 6cm
2. 떡의 개수 : 4개
3. 시도해야하는 방법 : 절단기 높이 바꾸기

그럼 이걸 가지고 뭘 해야하나?

1. 절단기 높이를 계속 바꿔가며 떡을 자른다.
2. 잘라진 떡의 길이가 6cm인지 확인한다. 2-1. 6cm보다 크다면? 절단기의 높이를 더 높게 설정 2-2. 6cm보다 작다면? 절단기의 높이를 더 낮게 설정
3. 위 과정을 반복한다.

이진탐색을 요약한 과정과 유사하다.

코드

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, target) = (input[0], input[1]) // 떡 개수 : n, 요청한 길이 : m
let array = readLine()!.split(separator: " ").map { Int(String($0))! }

print(parametricSearch(array, target))

func parametricSearch(_ array: [Int], _ target: Int) -> Int {
    var result = 0
    var start = 0
    var end = array.max()!

    while start <= end {
        var total = 0
        let mid = (start + end) / 2

        for ddeok in array {
            if ddeok > mid { // 떡이 지금 자를 높이보다 크다면
                total += ddeok - mid // 잘라진 떡을 누적한다
            }
        }
        if total < target {     // 누적된 떡의 양이 부족하다면
            end = mid - 1       // 높이를 더 낮게 설정한다 (떡이 더 많이 잘리도록)
        } else {                // 누적된 떡의 양이 충분하다면
            result = mid        // 결과를 초기화하고 (최적해)
            start = mid + 1     // 높이를 더 높게 설정한다 (떡이 덜 잘리도록)
        }
    }
    return result
}

가장 작은 데이터와 큰 데이터를 모두 담을 수 있는 빈 배열을 생성한 후, 각 데이터에 맞는 인덱스에 몇개나 있는지 Count하여 새로운 배열을 만드는 정렬이다.

1️⃣ 순서

1. 가장 작은 데이터와 가장 큰 데이터의 범위를 담을 배열을 생성한다.
2. 배열을 1번 순회하여 아까 만든 배열의 index에 count 한다.

2️⃣ 코드

var array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

func countSort(_ array: inout [Int]) -> [Int] {
    let maxValue = array.max() ?? 0                             // 1. 가장 큰 값을 구한다
    var countArray = [Int](repeating: 0, count: maxValue + 1)   // 2. 가장 큰 값 + 1 크기의 배열을 만든다
    for value in array {
        countArray[value] += 1                                  // 3. 순회하며 해당 값이 있는 index에 count한다
    }
    var sortedArray = [Int]()
    for (index, count) in countArray.enumerated() {             // 4. count만큼 index의 값을 append하여 정렬한다
        for _ in 0..<count {
            sortedArray.append(index)
        }
    }
    return sortedArray
}

print(countSort(&array))

3️⃣ 정리

• 안정성 : Stable Sort
  • 각 원소끼리 비교하지 않기 때문에 안정성을 가진다.
• 제자리성 : In-place
  • 기존 배열 이외의 메모리를 거의 사용하지 않는다.
• 시간 복잡도
  • 최선 : 𝛰(𝛮) 𝛮이 𝛫보다 클 경우
  • 최악 : 𝛰(𝛮 + 𝛫)
• 장점 : 퀵 정렬의 평균 속도보다 빠를 수 있음. (단, 데이터의 차이가 1,000,000 미만인 경우에 적합)
• 단점 : 추가적인 메모리가 많이 필요할 수 있다.

[문제] 두 배열의 원소 교체

N개의 원소로 이뤄진 두 배열 A, B가 있다. 최대 K번의 바꿔치기 연산을 할 수 있다. 바꿔치기 연산을 수행하여 만들수 있는 배열 A의 원소 합의 최댓값을 구하여라.

입력 조건

1. 첫째줄에는 N, K가 주어진다. (1 ≤ K ≤ N ≤ 100,000)
2. 둘째줄부터 각각 배열 A, B의 원소들이 주어진다. 모든 원소는 10,000,000보다 작은 자연수이다.

입력 예

5 3
1 2 5 4 3
5 5 6 6 5

출력 예

26

🌀 풀이

// 계수 정렬
func ascendingCountSort(_ array: inout [Int]) -> [Int] {
    let maxValue = array.max() ?? 0
    var countArray = [Int](repeating: 0, count: maxValue + 1)
    for value in array {
        countArray[value] += 1
    }
    var sortedArray = [Int]()
    for (index, count) in countArray.enumerated() {
        for _ in 0..<count {
            sortedArray.append(index)
        }
    }
    return sortedArray
}

func descendingCountSort(_ array: inout [Int]) -> [Int] {
    let maxValue = array.max() ?? 0
    var countArray = [Int](repeating: 0, count: maxValue + 1)
    for value in array {
        countArray[value] += 1
    }
    var sortedArray = [Int]()
    for (index, count) in countArray.enumerated().reversed() {
        for _ in 0..<count {
            sortedArray.append(index)
        }
    }
    return sortedArray
}

계수 정렬은 데이터의 범위가 제한적일 때 효과적인데, 현재 문제 기준으로는 적합하지 않다. 다만, 주어진 예시의 범위가 좁기 때문에 임의로 0부터 7까지로 제한한 후 적용시켜 보았다.

입력 배열에서 각 값이 몇 개 있는지 계수하여 각 값을 인덱스로 하는 countArray를 만들고, 그 다음 countArray를 이용하여 정렬된 배열을 만든다.

주의할 점은 입력 배열에서 최대 값이 maxValue라 가정하고 countArray를 생성하므로 countArray에 없는 값이 입력되면 이 함수는 제대로 작동하지 않는다.

드디어...!

정렬 시리즈가 끝이 났다 🥲🥲🥲 하지만 ... 다음은 이진 탐색 ... 갈길이 멀다.

🫥 글의 복잡성을 줄이기 위해 공통 input과, K번 바꾸기 연산은 첫 글에만 명시했습니다! 궁금하다면 여기를 눌러주세요.

기준(pivot)을 설정하고, 그 기준보다 큰지 작은지 판별하여 위치를 바꾸는 분할 정복 알고리즘이다. 분할 방법이 여러가지 존재하기 때문에 반드시 먼저 명시해야한다. 이번엔 첫번째 데이터를 기준으로 정하는 호어 분할(Hoare Partition)로 설정하여 진행해보자.

1️⃣ 순서

var data = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
1. 탐색할 범위를 설정한다.
2. 피봇을 설정한다.
    data[1] 부터 탐색 -> data[2] = 9
3. 값을 비교하여 피봇 보다 큰지 작은지 여부를 판단한다.
    data[9] 부터 탐색 -> data[8] = 4
4. 피봇보다 큰 데이터와 작은 데이터의 위치를 Swap한다.
    data[2] = 4, data[8] = 9
5. 위의 과정을 재귀로 반복하여 pivot의 왼쪽과 오른쪽을 분할하여 계속 정렬해나간다.

2️⃣ 코드

var array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

func quickSort(_ array: inout [Int], start: Int, end: Int) {
    print("<< quickSort() 실행 >> ")
    print("0. start: \(start), end: \(end)")
    print("실행 전 : \(array)")
    print()
    if start >= end { return }          // -  원소가 1개인 경우 종료

    let pivot = start                   // 0. 기준  : 첫 번째 원소
    var left = start + 1                // 1. 왼쪽  : 시작위치 + 1
    var right = end                     // 2. 오른쪽 : 맨 끝
    print(">> pivot : \(pivot)")
    print(">> left : \(left)")
    print(">> right : \(right)")
    print()

    while left <= right {               // 3. 왼쪽 인덱스가 오른쪽 인덱스와 작거나 같다면 반복
        print(">> array[left] : \(array[left])")
        print(">> array[right] : \(array[right])")
        print()
        while (left <= end) && (array[left] <= array[pivot]) {
            left += 1                   // 4. 왼쪽부터 기준보다 큰 원소 찾기
            print("4. left += 1 >> \(left)")
        }
        while (right > start) && (array[right] >= array[pivot]) {
            right -= 1                  // 5. 오른쪽부터 기준보다 작은 원소 찾기
            print("5. right -= 1 >> \(right)")
        }
        if left > right {
            array.swapAt(right, pivot)  // 6. 엇갈렸다면 작은 데이터와 pivot 교체
            print("6. left가 right보다 커서 right, pivot 스왑 = \(pivot 기준 왼쪽은 작고, 오른쪽은 크도록 정렬 완료)")
        } else {
            array.swapAt(left, right)   // 7. 엇갈리지 않았다면 작은 데이터와 큰 데이터 교체
        }
        print(">> 분할 탐색 시작하기 전 : \(array)")
        print()
        print("------------------------------------------------------------")
        print()
        quickSort(&array, start: start, end: right - 1) // 8. 나머지 왼쪽 탐색
        quickSort(&array, start: right + 1, end: end)   // 9. 나머지 오른쪽 탐색
    }
}

quickSort(&array, start: 0, end: array.count - 1)
print(array)

• 손으로 그리다가 너무 오래걸려서 그냥 print를 다 찍어버렸다.
• 아마 눈으로 보는게 가장 빠를 것 같으니 그대로 실행해보길 권장한다.

3️⃣ 정리

• 안정성 : Unstable Sort
  • 동일한 원소에 대한 우선순위가 유지되지 않는다.
• 제자리성 : In-place
  • 기존 배열 이외의 메모리를 거의 사용하지 않는다.
• 시간 복잡도
  • 최선 : 𝛰(𝛮 𝑙𝑜𝑔 𝛮)
  • 최악 : 𝛰(𝛮 ²)

[문제] 두 배열의 원소 교체

N개의 원소로 이뤄진 두 배열 A, B가 있다. 최대 K번의 바꿔치기 연산을 할 수 있다. 바꿔치기 연산을 수행하여 만들수 있는 배열 A의 원소 합의 최댓값을 구하여라.

입력 조건

1. 첫째줄에는 N, K가 주어진다. (1 ≤ K ≤ N ≤ 100,000)
2. 둘째줄부터 각각 배열 A, B의 원소들이 주어진다. 모든 원소는 10,000,000보다 작은 자연수이다.

입력 예

5 3
1 2 5 4 3
5 5 6 6 5

출력 예

26

🌀 풀이

글의 복잡성을 줄이기 위해 공통 input과, K번 바꾸기 연산은 첫 글에만 명시했습니다. 궁금하다면 여기를 눌러주세요.

// 퀵 정렬
private func ascendingQuickSort(_ array: inout [Int], start: Int, end: Int) {
    if start >= end { return }

    let pivot = start
    var left = start + 1
    var right = end

    while left <= right {
        while (left <= end) && (array[left] <= array[pivot]) {
            left += 1
        }
        while (right > start) && (array[right] >= array[pivot]) {
            right -= 1
        }
        if left > right {
            array.swapAt(right, pivot)
        } else {
            array.swapAt(left, right)
        }
        ascendingQuickSort(&array, start: start, end: right - 1)
        ascendingQuickSort(&array, start: right + 1, end: end)
    }
}

private func descendingQuickSort(_ array: inout [Int], start: Int, end: Int) {
    if start >= end { return }

    let pivot = start
    var left = start + 1
    var right = end

    while left <= right {
        while (left <= end) && (array[left] >= array[pivot]) {
            left += 1
        }
        while (right > start) && (array[right] <= array[pivot]) {
            right -= 1
        }
        if left > right {
            array.swapAt(right, pivot)
        } else {
            array.swapAt(left, right)
        }
        descendingQuickSort(&array, start: start, end: right - 1)
        descendingQuickSort(&array, start: right + 1, end: end)
    }
}

이번엔 그냥 함수자체를 나누어주었다! 이제 마지막 계수 정렬로 넘어가보자..!

🫥 글의 복잡성을 줄이기 위해 공통 input과, K번 바꾸기 연산은 첫 글에만 명시했습니다! 궁금하다면 여기를 눌러주세요.

현재 데이터를 적절한 위치에 삽입하는 정렬이다. 자신보다 왼쪽에 있는 데이터는 정렬되어있다고 가정한다.

1️⃣ 순서

var data = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
1. 1번째 데이터가 정렬되어 있다고 판단하고 2번째 데이터부터 탐색한다.
    data[0] = 7 <-> data[1] = 5
2. 이 때, 0번째 인덱스의 왼쪽 or 오른쪽 어디에 삽입될 지 그것만 판단한다.
    data[0] = 5가 삽입된다면 자연스럽게 data[1] = 7이 된다.
3. 나머지도 반복한다.
    data[2] = 9는 현재 data[1]보다 크기 때문에 그대로 있는다.
    data[3] = 0은 앞에있는 5, 7, 9 보다 작기 때문에 data[0]번째에 삽입한다.
    data[4] = 1, data[1]에 삽입한다.
    .
    .

2️⃣ 코드

var array = [0, 5, 9, 7, 3, 1, 6, 2, 4, 8]
for i in 1 ..< array.count {                    // 1. 1부터 배열 끝까지 탐색
    for j in stride(from: i, to: 0, by: -1) {   // 2. i부터 0까지 -1씩, 왼쪽 탐색
        if array[j] < array[j - 1] {            // 3. 현재 값이 왼쪽 값보다 작다면 이동
            array.swapAt(j, j - 1)
        } else {                                // 4. 왼쪽 값이 나보다 작다면 멈춤
            break
        }
    }
}

3️⃣ 정리

• 안정성 : Stable Sort
  • 비교대상의 원소가 새로운 원소보다 큰 경우에만 움직이므로 동일한 값의 위치는 변하지 않는다.
• 제자리성 : In-place
  • 기존 배열 이외의 메모리를 거의 사용하지 않는다.
• 시간 복잡도
  • 최선 : 𝛰(𝛮)
  • 최악 : 𝛰(𝛮 ²)
  • 최악의 경우 선택 정렬과 비슷하나 거의 정렬 된 문제 라면 퀵 정렬보다 빠르다.

[문제] 두 배열의 원소 교체

N개의 원소로 이뤄진 두 배열 A, B가 있다. 최대 K번의 바꿔치기 연산을 할 수 있다. 바꿔치기 연산을 수행하여 만들수 있는 배열 A의 원소 합의 최댓값을 구하여라.

입력 조건

1. 첫째줄에는 N, K가 주어진다. (1 ≤ K ≤ N ≤ 100,000)
2. 둘째줄부터 각각 배열 A, B의 원소들이 주어진다. 모든 원소는 10,000,000보다 작은 자연수이다.

입력 예

5 3
1 2 5 4 3
5 5 6 6 5

출력 예

26

🌀 풀이

// 삽입 정렬
func insertionSort(_ array: inout [Int], _ oper: String) {
    if (oper == "<") || (oper == "") { // 오름차순
        for i in 1..<array.count {
            var j = i
            while (j > 0) && (array[j] < array[j-1]) {
                array.swapAt(j, j-1)
                j -= 1
            }
        }

    } else if oper == ">" { // 내림차순
        for i in 1..<array.count {
            var j = i
            while (j > 0) && (array[j] > array[j-1]) {
                array.swapAt(j, j-1)
                j -= 1
            }
        }
    }
}

insertionSort(&a, "<")
insertionSort(&b, ">")
print("답 : \(exchange(&a, &b, k).reduce(0, +))")

여기서도 "<"와 ">"를 이용하여 오름차순, 내림차순을 구분해주었다. 코드가 예쁘진 않지만 🥲 일단 다음 퀵 정렬로 넘어가자..! 🧐

🫥 글의 복잡성을 줄이기 위해 공통 input과, K번 바꾸기 연산은 첫 글에만 명시했습니다! 궁금하다면 여기를 눌러주세요.

이코테 책에서는 python의 sort함수를 사용하여 비교적 문제 난이도가 낮았다. 따라서 조금 더 알찬 스터디를 위해 선택, 삽입, 퀵, 계수 정렬을 이용하여 문제를 풀어보기로 했다. ( 분량 조절 실패로 인해 글을 4개로 나누게 되었다. )

📝 선택 정렬 (Selection Sort)

매번 가장 작은 원소를 찾아 순차적으로 정렬하는 방법이다.

1️⃣ 순서

var data = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
1. 배열을 순회하여 가장 작은 데이터를 선택한다. data[3] = 0
2. 맨 앞에 있는 요소와 바꾼다.
    data[0] = 7 <-> data[3] 0
    data = [0, 5, 9, 7, 3, 1, 6, 2, 4, 8]
3. 이제 0번째 index의 정렬을 완료했으니 1번째 index의 값도 위의 방식으로 정렬한다.
4. 위 과정을 반복하여 배열 끝까지 정렬한다.

2️⃣ 코드

var array = [0, 5, 9, 7, 3, 1, 6, 2, 4, 8]

for i in 0 ..< array.count {            // 1. 왼쪽부터
    var minIdx = i                      // 2. 가장 작은 원소 찾기
    for j in i + 1 ..< array.count {    // 3. 현재 위치 + 1부터 끝까지
        if array[minIdx] > array[j] {   // 4. 더 작은 값이 있다면
            minIdx = j                  // 5. 더 작은 인덱스로 초기화
        }
        array.swapAt(i, minIdx)         // 6. 현재 위치와 더 작은 값의 위치 Swap
    }
}

3️⃣ 정리

• 안정성 : Unstable Sort
  • 동일한 값을 가지는 원소의 본래 순서를 보장하지 않는다.
• 제자리성 : In-place
  • 기존 배열 이외의 메모리를 거의 사용하지 않는다.
• 시간 복잡도 : 𝛰(𝛮 ²)
  • 방법이나 코드는 단순하지만 2중 반복문으로 인해 비효율적인 편이다.

[문제] 두 배열의 원소 교체

N개의 원소로 이뤄진 두 배열 A, B가 있다. 최대 K번의 바꿔치기 연산을 할 수 있다. 바꿔치기 연산을 수행하여 만들수 있는 배열 A의 원소 합의 최댓값을 구하여라.

입력 조건

1. 첫째줄에는 N, K가 주어진다. (1 ≤ K ≤ N ≤ 100,000)
2. 둘째줄부터 각각 배열 A, B의 원소들이 주어진다. 모든 원소는 10,000,000보다 작은 자연수이다.

입력 예

5 3
1 2 5 4 3
5 5 6 6 5

출력 예

26

// 공통 input
let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, k) = (input[0], input[1])
var a = readLine()!.split(separator: " ").map { Int(String($0))! }
var b = readLine()!.split(separator: " ").map { Int(String($0))! }

// 기본 라이브러리 사용
a.sort()
b.sort(by: >)

for i in 0 ..< k {
    if a[i] < b[i] {
        a[i] = b[i]
        b[i] = a[i]
    } else {
        break
    }
}
print(a.reduce(0, +))

그렇다. 책에서는 기본 라이브만 이용했기 때문에 정렬 챕터에 있는 모든 문제 난이도가 낮았다... 각 정렬로 풀어보기 전까지 이게 이렇게 오래 걸릴 줄 몰랐다...

// k번 바꾸기 연산 - 문제 풀이 로직
func exchange(_ a: inout [Int], _ b: inout [Int], _ k: Int) -> [Int] {
    for i in 0 ..< k {
        if a[i] < b[i] {
            a[i] = b[i]
            b[i] = a[i]
        } else {
            break
        }
    }
    return a
}

// 선택 정렬
func selectionSort(_ array: inout [Int], _ oper: String) {
    if (oper == "<") || (oper == "") {
        for i in 0..<array.count {
            var minIndex = i
            for j in i+1..<array.count {
                if array[j] < array[minIndex] {
                    minIndex = j
                }
            }
            if i != minIndex {
                array.swapAt(i, minIndex)
            }
        }
    } else if oper == ">" {
        for i in 0..<array.count {
            var minIndex = i
            for j in i+1..<array.count {
                if array[j] > array[minIndex] {
                    minIndex = j
                }
            }
            if i != minIndex {
                array.swapAt(i, minIndex)
            }
        }
    }
}

selectionSort(&a, "<")
selectionSort(&b, ">")
print("답 : \(exchange(&a, &b, k).reduce(0, +))")

오름차순과 내림차순을 구분해주기 위해 "<", ">"를 사용했다. 바로 이어서 삽입 정렬로 넘어가보자...!

깊이 우선 탐색(Depth-First Search, DFS)과 너비 우선 탐색(Breadth-First Search, BFS)은 두 가지 널리 쓰이는 그래프 탐색 알고리즘이다. 그래프 탐색의 목적은 그래프 내에서 목표 노드를 찾는 것이다. 이 두가지 모두 사용이 가능한 경우라도 각각의 장단점에 따라 선택하여 문제를 푸는 것이 중요하다.

DFS

DFS는 그래프를 깊게 탐색하는 알고리즘이다. 즉, 한놈만 팬다는 느낌으로 깊게 들어가서 탐색하는 것!

탐색시 시작 노드로부터 방문하지 않은 노드로 가기 위해 스택을 사용한다. 만약 가장 마지막 깊이까지 방문했다면 스택의 가장 위에 있는 노드로 돌아가 스택의 다른 노드들을 방문한다. DFS는 깊이 들어가기 때문에 목표 노드를 빠르게 찾을 수 있지만 메모리 사용량이 많이 든다는 단점이 있다.

BFS

BFS는 그래프를 넓게 탐색하는 알고리즘이다. DFS와는 다르게 그래프를 탐색할 때 큐를 사용한다. 그래프에서 꺼낸 방문하지 않은 노드는 큐에 넣고 방문한 노드는 큐에서 제거된다. BFS는 메모리 사용량이 DFS보다 적지만 목표 노드를 찾는데 시간이 더 오래 걸린다는 단점이 있다.

결론

DFS는 목표 노드를 빠르게 찾을 수 있지만 메모리 사용량이 많이 든다. BFS는 메모리 사용량이 DFS보다 적지만 목표 노드를 찾는데 시간이 더 오래 걸린다.

[문제] 음료수 얼려 먹기

N × M 크기의 얼음 틀이 있다. 0은 얼음칸, 1은 칸막이로 표시한다. 얼음칸끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 주어진 얼음 틀에서 생성되는 총 아이스크림의 개수를 구하는 프로그램 작성하기.

입력 조건

• 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
• 두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
• 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

출력 조건

한 번에 만들 수 있는 아이스크림의 개수를 출력한다.

입력 예시 1

4 5
00110
00011
11111
00000

출력 예시 1

3

입력 예시 2

15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111

출력 예시2

8

풀이

1. 2차원 배열을 만들어 그래프를 입력 받는다.
2. 그래프의 모든 노드를 방문하여 dfs로 탐색한다.
3. dfs 함수 내에서 범위 안에 있고 방문되지 않은 노드를 모두 탐색한다. => if graph[x][y] == 0 이 때 방문처리를 진행한다. => graph[x][y] = 1
4. 범위밖으로 벗어나거나 주변에 0이 없다면 return false로 재귀 함수들을 종료한다.
5. 즉 dfs함수가 true로 반환될 때 뭉쳐있는 한 덩어리를 모두 방문했으므로 result += 1로 count한다.

코드

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (n, m) = (input[0], input[1])

var graph = [[Int]]()
for _ in 0 ..< n {
    graph.append(readLine()!.map { Int(String($0))! })
}

func dfs(_ x: Int, _ y: Int) -> Bool {
    // 범위 벗어나면 종료
    if !isInRange(x, y) {
        return false
    }

    if graph[x][y] == 0 { // 방문하지 않은 노드
        graph[x][y] = 1 // 방문처리

        // 상하좌우 탐색
        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)

        return true // 주변이 다 막혀있다면 true 반환하고 종료
    }
    return false
}

func isInRange(_ x: Int, _ y: Int) -> Bool {
    return (0..<n ~= x) && (0..<m ~= y)
}

var result = 0

for i in 0 ..< n {
    for j in 0 ..< m {
        if dfs(i, j) {
            result += 1
        }
    }
}

print(result)

어떤 공식이 있다기 보다는 말 그대로 "구현"에 초점을 두는 것이다. 아이디어를 떠올리기는 쉽지만 막상 구현하려면 코드가 길어진다거나 하는 문제들!

보통 N x M 칸을 주고 상,하,좌,우로 움직이는 시뮬레이션 문제 또는 00시 00분 00초 단위의 시간 계산같은 완전탐색으로 풀어야하는 문제들이 있을 수 있다.

구현 알고리즘의 중요성

프로그래밍은 기본적으로 어떤 아이디어를 구체화 시켜 문제를 해결하는 것이다. 이 능력을 판별하기 가장 쉬운 문제유형이기에 대기업에서 복잡하고 어려운 구현 문제가 많이 출제 되는 듯 하다.

결론

구현 알고리즘은 구체적인 실행과 효과적인 코드를 만드는 데 도움이 된다. 잘 풀기 위해서는 문제를 빠르게 파악하고 그에 알맞은 해결 방법을 도출하는 연습이 필요하다. 특히 풀이에 맞는 라이브러리, 적절한 함수를 많이 알고있으면 도움이 된다.

[문제] 왕실의 나이트

행복 왕국의 왕실 정원은 체스판과 같은 8 × 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다. 나이트는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

이 때, 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하라. 행 위치를 표현할 때는 1부터 8로, 열 위치를 표현할 때는 a 부터 h로 표현한다.

입력 조건

• 첫째 줄에 8x8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1 처럼 열과 행으로 이뤄진다.

출력 조건

• 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.

풀이

1. 나이트가 움직일 수 있는 8가지 경우를 튜플 형태의 배열로 설정한다.
2. 현재 위치에서 한 번 이동 시 범위 내인지 확인한다.
3. 범위 내라면 +1, 아니라면 through
4. 모든 경우 탐색 후 결과 출력

• 시뮬레이션 + 완전탐색 문제
• 모든 이동 가능한 경우를 체크해야한다.
• 입력받는 문자가 2글자이기에 map은 사용하지 않았다.
• input.last!는 Character 형식이기에 바로 Int로 형변환이 불가능하여 String으로 한 번 더 바꿔주었다.
• (1, 1)이 편해서 'a'의 아스키코드값 97대신 96을 사용했다.
• 튜플 처리 속도가 빠르기 때문에 dx, dy 배열로 각각 나누는 대신 한번에 처리했다.
• 가독성을 위해 isInRange() 를 만들었다.

코드

import Foundation

let input = readLine() ?? ""
let row = Int(String(input.last!))!
let col = Int(input.first!.asciiValue!) - 96 // 97은 'a'의 아스키 코드, a일 경우 1로 표시 되어야 하기 때문에 96을 빼준다.

let moves = [(-2, -1), (-1,-2), (2,-1), (1,-2), (2,1), (1,2), (-1,2), (-2,1)]
var result = 0

for move in moves {
    var nextX = row + move.0
    var nextY = col + move.1

    if isInRange(nextX,nextY) {
        result += 1
    }
}

print(result)

func isInRange(_ x: Int, _ y: Int) -> Bool {
    return (1...8 ~= x) && (1...8 ~= y) // ~= 볌위 연산자 : Bool 값
}

그룹 스터디 피드백

• 처음엔 함수를 (x >= 1) && (x <= 8) .. 이런식으로 작성했는데 만도스님이 사용한 범위연산자 ~=를 보고 고쳤다.
• 구현 문제는 함수를 쪼개서 푸는 방법에 익숙해지는게 좋을 것 같다는 결론을 얻었다.
• 백준의 삼성 기출 문제에 어려운 구현 문제가 많아서 다음엔 그 문제들을 연습해야겠다.

문제 풀이에 앞서 그리디 알고리즘을 간단하게 짚고 넘어가보자. 그리디 알고리즘은 비교적 간단하고 자주 사용되는 알고리즘이다. 이 알고리즘은 특정한 조건 내에서 가능한 가장 좋은 해를 찾기 위해 매번 다른 값을 시도해 보는 방식으로 접근한다. 일반적으로 시간 및 공간 복잡도가 낮아 효율적인 솔루션을 제공한다.

그리디 알고리즘의 종류

일반적으로는 최적 분할 문제, 최대 값 문제 및 최소 값 문제에 적용할 수 있다. 이 외에도 다양한 다른 문제에 대해 그리디 알고리즘을 사용할 수 있다.

예시 문제

예를 들어 다음과 같은 숫자 배열이 있다고 가정해보자 [2, 3, 7, 8, 10] 여기에서 주어진 숫자들을 사용하여 최대 합을 가지는 부분 집합을 찾는 문제를 해결하고자 한다. 이 때 그리디 알고리즘이 적용되는데, 숫자가 적어도 하나 이상 포함되는 부분 집합을 구하기 위해 다음과 같은 과정을 따른다.

1. 첫 번째 원소를 선택한다.
2. 다음 원소를 선택하고 지금까지 선택한 원소의 합과 비교한다.
3. 두 숫자 중 더 큰 값을 선택한다.

결론

그리디 알고리즘은 비교적 간단하고 자주 사용되는 알고리즘이다. 가장 큰 장점은 시간 및 공간 복잡도가 낮아 효율적인 해를 찾는 것!

즉 모든 문제는 완전탐색으로 풀 수 있지만, 이 알고리즘을 채택한다면 더 빠르게 풀 수 있다!

하지만 이 알고리즘을 사용하기 전에 이 방법이 정말 맞는지 판별하기가 어렵기 때문에 꽤 어려운 알고리즘이다.

[문제] 큰 수의 법칙

입력받은 배열을 사용하여 가장 큰 수를 만드는 문제이다.

1. N개의 자연수를 가진 배열은 정렬되어있지 않고 2. 총 M번 더할 수 있으며 3. 하나의 인덱스 당 K번 초과하여 더할 수 없다.

입력 조건

• 첫째 줄에 N(2 <= N <= 1,000), M(2 <= M <= 10,000), K(1 <= K <= 10,000)의 자연수가 주어지며,각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10,000이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

출력 조건

• 첫째 줄에 동빈이의 큰 수의 법칙에 따라 더해진 답을 출력한다.

풀이

1. 입력받은 배열을 정렬한다.
2. 맨 마지막에 있는 수(가장 큰 수)를 K번 더한다.
3. K를 초과할 때 두번째로 큰 수를 한번 더하고 count를 초기화 한다.
4. 2,3번을 M번 반복한다.

코드

let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
var (N, M, K) = (input[0], input[1], input[2])
var array = readLine()!.split(separator: " ").map{ Int(String($0))! }

array.sort()
let first = array[N - 1] // 가장 큰 수
let second  = array[N - 2] // 두번째로 큰 수

var result = 0
var count = 1

for _ in 0 ..< M {
    if count <= K {
        result += first
        count += 1
    } else {
        result += second
        count = 1
    }
}

print(result)

문제

1678. Goal Parser Interpretation

문제파악하기

• 주어진 문자열 command를 Parse 하여 알맞게 출력하는 문제
• 만약 "G()(al)"으로 주어진다면 G -> G () -> o (al) -> al 이렇게 바꿔주면 된다.

내가 한 방법은

1. 문자열을 인덱스로 탐색하기 좋게 Array로 바꿔준다.
2. 답을 담을 ans 변수 선언
3. 문자열의 길이 -1 만큼 탐색한다.
4. 현재 문자가 "G" 라면 ans += "G" 5-1. 현재 문자가 "(" 라면 그 다음 문자가 ")" 인지 아닌지 구별한다. 5-2. 그 다음 문자가 ")"라면 ans += "o", "a"라면 ans += "al"
5. for문은 맨 마지막 글자를 탐색하지 않기 때문에 한번 더 탐색해주고 ")"이 아니라면 마지막 글자를 넣어준다.

풀이

class Solution {
    func interpret(_ command: String) -> String {
        var str = Array(command)
        var ans:String = ""

        for i in 0 ..< str.count - 1 {
            if str[i] == "G" {
                ans += "G"
            } else if (str[i] == "(") && (str[i+1] == ")") {
                ans += "o"
            } else if (str[i] == "(") && (str[i+1] == "a") {
                ans += "al"
            }
        }
        if str.last! != ")" {
            ans += String(str.last!)
        }

        return ans
    }
}

🤔 FEEDBACK

처음엔 while문으로 문자열을 마지막부터 하나씩 빼가면서 비교했는데 너무 느렸다. 이렇게되면 command의 전체를 확인해야하기 때문에 O(n), 거기에 removeLast()를 계속 반복하기 때문에 O(1)을 또 반복해서 그랬다. 단순 for문을 구현하지 않으려다가 더 늦은 알고리즘을 구현했었다;

문제

음양 더하기

문제파악하기

• 동일한 길이의 배열이 주어진다.
• 한쪽은 양수인지 음수인지만 판별하고 1 또는 -1을 곱하여 더한 것을 누적하면 된다.

풀이

import Foundation

func solution(_ absolutes:[Int], _ signs:[Bool]) -> Int {
    var sum = 0
    for i in 0 ..< absolutes.count {
        let sign = signs[i] == true ? 1 : -1
        sum += absolutes[i] * sign
    }
    return sum
}

🤔 FEEDBACK

• 다른 답들을 보니까 고차함수 써볼걸 하는 후회가 밀려온다 .. 😳
• 내일부터 백준 브론즈 5 도장깨기 하면서 고차함수 연습 실컷 해야겠다.

다른 풀이

import Foundation

func solution(_ absolutes:[Int], _ signs:[Bool]) -> Int {
    return (0..<absolutes.count).map { signs[$0] ? absolutes[$0] : -absolutes[$0] }.reduce(0, +)
}

문제

소수 만들기

문제파악하기

• sum이라는 배열을 만들어 3개의 숫자 합을 전부 담아준다.
• 세개의 합을 구하기 위해 반복문 끝을 배열 길이 -2로 설정한다.
• i보다 한칸 뒤의 위치를 j, 그 뒤를 k로 설정하여 sum.append()
• isPrime 함수를 통해 소수인 것만 배열에 담아 .count를 반환한다.

풀이

func solution(_ nums:[Int]) -> Int {
    var sum = [Int]()

    for i in 0 ..< nums.count - 2 {
        for j in i+1 ..< nums.count {
            for k in j+1 ..< nums.count {
                sum.append(nums[i] + nums[j] + nums[k])
            }
        }
    }
    return sum.filter{isPrime($0)}.count
}

func isPrime(_ n:Int) -> Bool {
    for i in 2 ..< n {
        if n % i == 0 {
            return false
        }
    }
    return true
}

🤔 FEEDBACK

• 소수 만들기 문제는 풀때마다 리셋되는 기분이다.
• 풀이 방법도 다양하기 때문에 이틀에 한번씩 복습하면서 다른 풀이를 연습해보는게 좋을 것 같다.

다른 풀이

func solution(_ nums:[Int]) -> Int {
    var answer: Int = 0
    var combi: [Int] = [Int](repeating: 0, count: 3)
    combination(nums, &combi, 0, nums.count, 0, 3, &answer)

    return answer
}

func checkPrime(_ num: Int) -> Bool {
    var index: Int = 0
    for i in 2...num {
        if num % i == 0 {
            index = i
            break
        }
    }
    if index == num {
        return true
    }
    return false
}

func combination(_ nums: [Int], _ combi: inout [Int], _ target: Int,
                 _ n: Int, _ index: Int, _ k: Int, _ answer: inout Int)
{
    if k == 0 {
        var checkNum: Int = 0
        for i in combi {
            checkNum += nums[i]
        }
        // 소수이면 1 더함
        if checkPrime(checkNum) {
            answer += 1
        }
    }
    else if target == n {
        return
    }
    else {
        combi[index] = target
        combination(nums, &combi, target + 1, n, index + 1, k - 1, &answer)
        combination(nums, &combi, target + 1, n, index, k, &answer)
    }
}

문제

K번째수

문제파악하기

풀이

func solution(_ array:[Int], _ commands:[[Int]]) -> [Int] {
    var answer = [Int]()

    for command in commands {
        let i = command[0] - 1
        let j = command[1] - 1
        let k = command[2] - 1

        let num = array[i...j].sorted()[k]
        answer.append(num)
    }

    return answer
}

🤔 FEEDBACK

다른 풀이

func solution(_ array:[Int], _ commands:[[Int]]) -> [Int] {
    return commands.map({(key) in
        return array[(key[0]-1)...(key[1]-1)].sorted()[key[2]-1]
    })
}

문제

올바른 괄호

방법

1. 문자열을 하나씩 탐색한다.
2. ( 일 때 +1, ) 일 때 -1로 카운트하면
3. 한 쌍을 이룰 때 0이 유지되고
4. 왼쪽부터 카운트 하기 때문에 ) 가 하나라도 더 많을 경우 음수가 되니 바로 false 반환
5. 끝까지 확인한 경우 카운트가 0 이라면 true, 아니라면 false

풀이

import Foundation

func solution(_ s:String) -> Bool {
    var count = 0
    for c in s {
        if c == "(" {
            count += 1
        } else {
            count -= 1
        }
        if count < 0 {
            return false
        }
    }
    return count == 0 ? true : false
}

다른 풀이

문제

모의고사

문제파악하기

• 점수 [수포자 번호 : 맞은 개수]
• 그 value에 1을 누적해가면서 각 수포자의 맞은 개수를 카운팅한다.

풀이

import Foundation

func solution(_ answers:[Int]) -> [Int] {
    let first = [1, 2, 3, 4, 5]
    let second = [2, 1, 2, 3, 2, 4, 2, 5]
    let third = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    var scores = [Int:Int]()

    for i in 0 ..< answers.count {
        if answers[i] == first[i % first.count] { scores[1, default: 0] += 1 }
        if answers[i] == second[i % second.count] { scores[2, default: 0] += 1 }
        if answers[i] == third[i % third.count] { scores[3, default: 0] += 1 }
    }

    return scores.filter { $0.value == scores.values.max() }.keys.sorted()
}

🤔 FEEDBACK

• 한참 Array에 정답 맞춘 개수 카운트해서 따로 만들어서 넣다가 이게 아닌 것 같아서 방법을 바꿨다.
• scores[1, default: 0]은 scores[1] key가 없을 때 0으로 초기화

다른 풀이

import Foundation

func solution(_ answers:[Int]) -> [Int] {
    let answer = (
        a: [1, 2, 3, 4, 5], // index % 5
        b: [2, 1, 2, 3, 2, 4, 2, 5], // index % 8
        c: [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] // index % 10
    )
    var point = [1:0, 2:0, 3:0]

    for (i, v) in answers.enumerated() {
        if v == answer.a[i % 5] { point[1] = point[1]! + 1 }
        if v == answer.b[i % 8] { point[2] = point[2]! + 1 }
        if v == answer.c[i % 10] { point[3] = point[3]! + 1 }
    }

    return point.sorted{ $0.key < $1.key }.filter{ $0.value == point.values.max() }.map{ $0.key }
}

Reference

• [Swift] 프로그래머스 모의고사 (feat. Dictionary)

문제

약수의 개수와 덧셈

문제파악하기

• 주어진 left와 right 사이의 수를 탐색하여 약수의 수를 count하고 그 수가 짝수라면 더하기, 홀수라면 빼는 알고리즘이다.

풀이

import Foundation

func solution(_ left:Int, _ right:Int) -> Int {
    var answer = 0
    for i in left ... right {
        var count = 0
        for j in 1...i {
            if i % j == 0 { // i의 약수 카운트
                count += 1
            }
        }
        if count % 2 == 0 {
            answer += i
        } else {
            answer -= i
        }
    }
    return answer
}

🤔 FEEDBACK

• 처음엔 함수를 만들어서 각 수의 약수를 배열로 반환했고 길이로 판단했다.
• 나름대로 sqrt를 써서 시간복잡도를 줄여 구해보겠다는 발상이었는데 아무리 봐도 이렇게 복잡하게 풀 문제가 아니다 싶어서 문제를 다시 봤다.
• 약수의 개수가 짝수인지 홀수인지만 알면되니까 count가 낫겠다 싶어 방향을 바꿨다.

다른 풀이

func solution(_ left: Int, _ right: Int) -> Int {
    return (left...right).map { i in (1...i).filter { i % $0 == 0 }.count % 2 == 0 ? i : -i }.reduce(0, +)
}

• 난 언제 이렇게 고차함수를 능수능란하게 써보지...
• left부터 right까지 한번에 map을 사용해서 반복해준다. -> Array 생성
• i를 Array에 넣어줄건데 이 i는 1부터 i까지 나눠지는 수일때만 담은 배열의 길이를 카운트
• 그래서 그게 짝수면 그냥 정수로 넣어주고 홀수면 음수로 넣어준다.
• 최종적으로 filter에 걸러진 배열의 총 합을 구한다.
• 아마 map, filter, reduce까지 써서 효율적인 코드는 아닐거라 예상하지만..
• 그래도 고차함수를 잘 다룰 수 있고 많이 풀지 않는 방식이라 높은 점수 받았을 것 같다.

Reference

• [Java] 약수 구하기 알고리즘