문제 https://leetcode.com/problems/find-missing-elements 풀이 연속된 정수 구간에 속한 모든 정수가 들어 있’던’ 수열 nums가 주어진다. 일부 원소가 사라진 상태인 상태인데, 이 사라진 원소들을 배열에 오름차순으로 담아 리턴하면 된다. 최대값과 최소값은 사라지지 않았다고 하니까, 정수 구간의 크기를 구할 수 있다. 그 정수 구간을 순회하면서 빠진 원소들을 찾으면 된다. 정렬을 이용해서 풀 수도 있는데, 이러면 시간 복잡도가 평균 $O(n \times \log n)$이 된다. 큰 차이는 안나지만 Hast Set을 이용하면 평균 $O(n)$에 풀 수 있다. ...

오늘 한 내용 LeetCode 1406 Stone Game III Codeforces 520B Two Buttons WWDC Meet async/await in Swift 세션 시청 및 정리. 배운 내용 PS LeetCode 1406은 현재 차례인 플레이어가 상대보다 확보할 수 있는 최대 점수 차이를 DP로 정의해 풀었다. 누가 Alice인지 Bob인지에 따라 상태를 나누지 않아도, 현재 상태를 점수 차이로 표현하면 같은 점화식으로 문제를 풀 수 있다. 점화식이 안떠올라서 힌트를 보고 풀었다. Codeforces 520B는 두 연산을 그래프의 간선으로 보고 BFS로 최단 거리를 구했다. 다만 목표값이 시작값보다 작을 때는 2배 연산이 도움이 되지 않으므로, 단순히 1씩 감소시키는 경우를 분리해 처리했다. ...

1편에서는 async await를 어떻게 사용했는지 알아봤다면, 여기서는 테스트와 실제 앱 코드에서 async/await를 사용하는 법을 알아본다. 또한 기존에 존재하는 completion handler 기반 API를 continuation을 사용하여, async/await를 사용하는 async alternative로 변환하는 방법을 알아본다. 비동기 코드 테스트하기 async/await를 쓰면 비동기 코드도 동기 코드만큼 쉽게 테스트할 수 있다. XCTest는 async 테스트를 지원한다. 아래는 completion handler 방식의 비동기 코드를 테스트하는 코드이다. class MockViewModelSpec: XCTestCase { func testFetchThumbnails() throws { let expectation = XCTestExpectation(description: "mock thumbnails completion") self.mockViewModel.fetchThumbnail(for: mockID) { result, error in XCTAssertNil(error) expectation.fulfill() } wait(for: [expectation], timeout: 5.0) } } ifulfill fulfill()은 expectation을 충족된 상태로 표시하는 메소드다. 일반적으로 비동기 작업이 완료되었을 때 호출한다. 기존에는 XCTestExpectation을 만들고, API를 호출한 뒤 expectation을 fulfill 하고, 지정한 시간 동안 기다리도록 작성해야 했다. ...

completion handler로 작성한 비동기 코드는 쉽게 장황해지고, 복잡해지고, 부정확해진다. Swift의 async/await는 비동기 코드를 일반 코드를 작성하는 것처럼 만들어 주고, 아이디어를 더 쉽게 반영하며, 더 안전하게 만든다. async/await는 단순한 비동기 표현 방식이 아니다. 이 세션에서는 async/await가 왜 기존 completion handler 방식보다 좋은지, 그리고 Swift의 컨셉에 왜 잘 맞는지를 계속해서 설명한다. Meet async/await in Swift Foundation 같은 Apple SDK에는 await할 수 있는 수백 개의 메소드가 존재한다. UIKit의 UIImage는 섬네일을 만드는 API를 동기 방식과 비동기 방식으로 모두 제공한다. ...

문제 https://codeforces.com/problemset/problem/520/B 풀이 정수 n, m이 주어지고, 연산 2개 (* 2, - 1)을 이용해서 n을 m으로 만드는데 필요한 연산의 최소 개수를 출력하면 된다. $1 <= n, m <= 10^4$ 제약조건과 2배로 만드는 연산을 생각해보면 만들 수 있는 숫자의 개수는 최대 2만개 정도이다. 이 숫자들을 각각을 노드라 생각하면, 연산으로 정의되는 노드간 연결도 명확한 그래프로 생각할 수 있다. 그러면 이 문제는 최단 거리 문제가 되므로 BFS를 사용해서 쉽게 풀 수 있다. 2배 연산이 있으므로 방문 확인 배열의 크기를 m * 2로 잡고 BFS를 하면된다. (방문 확인 배열도 할 겸 거리를 세는 기능도 넣으면 좋다.) ...

문제 https://leetcode.com/problems/stone-game-iii 풀이 번호가 적힌 돌이 있고, 두 명(Alice, Bob)이 번갈아 가면서 그 돌을 1개에서 3개까지 가져갈 수 있다. 2명 다 이상적으로 플레이 했을 때, 돌에 적힌 번호를 더한 합이 더 많이 가져간 사람의 이름을 리턴하면 된다. 항상 Alice가 먼저 시작한다. 약간 특이한 DP 문제이다. 점화식을 ‘Alice’ ‘Bob’을 특정하지 않고 ‘현재 차례인 사람이 상대보다 돌을 가질 수 있는 최대 개수’로 정의해야한다. 점화식은 다음과 같다. $$ dp[i] = \max \begin{cases} stoneValue[i] - dp[i+1] \\ stoneValue[i] + stoneValue[i+1] - dp[i+2] \\ stoneValue[i] + stoneValue[i+1] + stoneValue[i+2] - dp[i+3] \end{cases} $$ ...

오늘 한 내용 LeetCode 3016, LeetCode 1979 풀이 Codeforces 455A 풀이 AGENTS.md, SKILL.md 관련 자료 학습 배운 내용 PS LeetCode 3016은 3014와 풀이가 동일했다. 문제의 제약 조건은 달랐지만, 3014를 풀 당시 더 큰 제약까지 고려해서 구현해 두었던 덕분에 그대로 통과할 수 있었다. 왜인지 3014가 Easy 문제치고는 생각보다 까다로운 편이었다. Codeforces 455A는 전형적인 DP 문제였다. 다만 C++에서는 정수 범위를 고려해 long long을 사용해야 하는데, Swift와 Python만 주로 사용하다 보니 이 부분을 자주 놓치는 것 같다. ...

문제 https://leetcode.com/problems/find-greatest-common-divisor-of-array 풀이 수열 nums의 원소 중 가장 큰 원소의 가장 작은 원소의 GCD를 리턴하면 된다. 처음에 max()와 min()을 썼는데, 제출 시간이 거의 최하위권이길래 for loop로 다시 작성했다. GCD 자체는 유클리드 호제법을 이용해서 구한다. 코드 class Solution { func findGCD(_ nums: [Int]) -> Int { func gcd(_ a: Int, _ b: Int) -> Int { b == 0 ? a : gcd(b, a % b) } var min = Int.max var max = 0 for num in nums { min = min > num ? num : min max = max < num ? num : max } return gcd(min, max) } }

문제 https://codeforces.com/problemset/problem/455/A 풀이 풀이 배열a에서 얻을 수 있는 최대 점수를 구하는 DP 문제이다. 어떤 값 x를 선택하면 x만큼의 점수를 얻고, 배열에 있는 x - 1과 x + 1은 모두 제거된다. 여기서 중요한 점은 같은 값을 여러 개 가지고 있다면 하나씩 선택할 이유가 없다는 것이다. x를 선택하는 순간 x - 1과 x + 1은 모두 사용할 수 없으므로, 선택한다면 값이 x인 원소는 모두 선택하는 것이 항상 이득이다. 따라서 입력 배열의 순서는 의미가 없어지고, 각 숫자가 몇 번 등장하는지만 알면 된다. 값 x가 frequencies[x]번 등장한다면, x를 선택했을 때 얻는 점수는 x * frequencies[x]이다. ...

오늘 한 내용 Codeforces 279B LeetCode 3014 과거 Bicubic, Smart CCTV 프로젝트 정리 미방문록 회의, AGENTS 수정. 배운 내용 SKILL 사용하기 프로젝트를 진행하면서 기본적인 개발 원칙은 AGENTS.md에 정리했다. 하지만 View, ViewModel, Test처럼 반복해서 만드는 코드까지 모두 AGENTS.md에 작성하는 것은 적절하지 않았다. 이런 작업은 프로젝트의 규칙이라기보다 반복 작업의 절차에 가깝기 때문이다. 예를 들어 View를 생성할 때는 ViewModel을 어떻게 주입할지, Preview를 어떻게 작성할지 등 항상 비슷한 패턴을 따른다. ViewModel이나 테스트 코드도 마찬가지다. ...