앞서 정리한 세션에서는 completion handler 기반의 비동기 코드를 async/await로 작성하면서, 비동기 코드에서도 return, throw, try-catch와 같은 일반적인 제어 흐름을 사용할 수 있게 되었다. 이번 포스팅에서는 WWDC21의 Explore Structured Concurrency in Swift 세션을 정리한다. async/await가 비동기 코드의 제어 흐름을 구조화했다면, structured concurrency는 여기서 더 나아가 동시에 실행되는 여러 task의 관계와 수명을 구조화한다. Explore Structed Concurrency in Swift Swift Concurrency는 구조화된 프로그래밍(structured programming)의 아이디어에 기반한 structured concurrency라는 개념을 활용한다. 옛날에는 프로그램에서 명령어를 나열하고, 컨트롤 플로우가 여기저기로 자유롭게 점프해서 코드를 읽기가 매우 어려웠다. (C의 goto를 생각해보자) ...

문제 https://codeforces.com/problemset/problem/276/C 풀이 크기 n인 수열 a와 쿼리 q개가 주어진다. 각 쿼리는 인덱스 $[l, r]$ 범위를 지정하며, 해당 범위의 원소 합을 구한다. 수열 a를 적절히 재배열하여 모든 쿼리의 합의 총합을 최대화 한 수를 출력하면 된다. 쿼리가 여러번 나오고 어떤 원소들은 쿼리 안에 중복되어서 포함되어 있을 수 있다. 쿼리의 범위 안에 가장 많이 포함된 원소의 순서대로, 높은 값을 배치하는 정렬 문제로 환원된다. 어떤 원소 $a_i$가 쿼리 내부에 포함되어 있는지를 일반적으로 판단하게 되면 $O(q \times n)$이 되는데, q, n의 범위가 $1 \leq q 2 \times 10^5$ 이므로, 시간 안에 문제를 해결하기 어려워진다. ...

문제 https://leetcode.com/problems/longest-subsequence-with-non-zero-bitwise-xor 풀이 수열 nums가 주어지고, 이 nums의 서브시퀀스 중, 모든 원소를 XOR해서 0이 아니게 되는 서브시퀀스의 최대 길이를 리턴하면 된다. 이 문제는 XOR 연산의 특성을 잘 알아야 한다. 만약 XOR이 아니라 $+$이었다면, 모든 $\text{nums}$의 원소들을 더해보고, 0이 아니라면 $\text{nums}$ 전체를, 0이라면 원소 중 0이 아닌 것 하나를 제외하면 된다. $+$의 역연산은 $-$이므로, 어떤 원소 $x$를 제외했을 때 다음과 같이 된다. $$\sum \text{nums} - x \neq 0$$ 만약 모든 원소가 0이라면 답은 0이 된다. ...

오늘 한 내용 PS Codeforces 550A. Two Substrings LeetCode 3090. Maximum Length Substring With Two Occurrences Stack Day HabitRepository, CompletionRepository 인터페이스 추가 CreateHabitUseCase와 RecordCompletionUseCase 구현 StackDay. UseCase와 Entity는 각각 어디까지 책임져야 할까 StackDay. Repository의 save를 insert와 update로 나눈 이유 배운 내용 UseCase와 Entity의 책임 CreateHabitUseCase와 RecordCompletionUseCase를 구현하면서, Entity가 스스로 유효한 상태를 보장하고 UseCase는 객체를 조합해 작업 흐름을 만드는 쪽으로 책임을 나눴다. 이름 정규화와 유효성 검증은 Habit에, 저장 순서와 중복 확인은 UseCase에 뒀다. 자세한 고민은 개발일지에 정리했다. ...

CreateHabitUseCase를 시작으로 여러 유즈케이스를 구현하면서, 도메인 규칙을 어디에 두어야 할지 계속 고민하게 됐다. Habit을 생성할 때 이름의 유효성을 누가 검증해야 하는지, Completion을 남길 때 해당 날짜에 기록할 수 있는지는 누가 판단해야 하는지처럼 비슷한 문제가 반복해서 나타났다. 처음에는 유즈케이스가 사용자의 작업을 처리하니 이런 검증도 함께 담당하면 된다고 생각할 수 있었다. 하지만 구현을 진행할수록 엔티티가 스스로 보장해야 하는 규칙과 유즈케이스 작업의 흐름을 위해 판단해야 하는 규칙을 구분할 필요가 있었다. 이 포스트에서는 Habit의 생성과 Completion 기록을 중심으로 어떤 고민을 했는지와 어떻게 해결했는지를 정리한다. ...

유즈케이스를 구현하면서 Habit과 Completion을 저장할 Repository 계약을 좀 정리했다. 처음에는 create와 update 둘 다 save 하나로 저장하면 간단해 보였지만, 두 기능이 기대하는 실패 조건이 서로 다르다는 점에서 계약을 나눌 필요가 있었다. save는 어떤 동작인가 save를 upsert로 구현하면 호출하는 쪽은 편하다. ID가 없으면 삽입하고, 이미 있으면 갱신하면 된다. protocol HabitRepository { func save(_ habit: Habit) async throws } 문제는 이 동작이 실패해야 하는 상황까지 조용히 성공으로 바꾼다는 점이다. (물론 UUID라 현실적으로 겹칠 일은 없지만) Habit을 생성하는 작업은 같은 ID가 이미 있으면 실패해야 하고, 보관처럼 기존 Habit을 바꾸는 작업은 대상이 없으면 실패해야 한다. ...

문제 https://codeforces.com/problemset/problem/550/A 풀이 스트링 s가 주어지고, 이 s 안에서 서브스트링 "AB"와 "BA"가 겹쳐지지 않은 상태로 존재하면 "YES" 아니라면 "NO" 출력하면 된다. 문제에서 주어진 예시인 "ABA" 같은 경우는 "NO"가 된다. "AB"와 "BA"가 서로 따로 존재하지 않기 때문이다. 하지만 "ABCABA" 같은 경우에는 "AB"와 "BA"가 "BA"는 겹쳐져 있지만 이미 앞에서 "AB"가 존재하기 때문에, "YES"가 된다. 이런 예외들을 알아내면, 문제를 푸는 방식은 단순하다. "AB"를 찾은 후, 그 이후("B" 이후)에 있는 인덱스부터 "BA"를 찾고, 만약 존재한다면 "YES", 존재하지 않는다면 다시 "BA"를 먼저 찾은 후, "A"의 인덱스 이후에 있는 인덱스부터 "AB"를 찾으면 된다. 둘 다 불가능하다면 "NO"가 된다. ...

문제 https://leetcode.com/problems/maximum-length-substring-with-two-occurrences 풀이 스트링 s가 주어지고, 스트링 s의 서브스트링 중에서 같은 문자가 최대 2번 까지만 등장하는 서브스트링의 최대 길이를 리턴하는 문제이다. 투 포인터를 이용해서, 서브스트링 내부의 각 문자의 개수는 frequencies 딕셔너리로 추적하고, 같은 문자가 2개를 초과하면 start, 그렇지 않다면 end를 증가시키는 방향으로 s를 탐색하면 된다. 문제의 제약조건이 널널해서 $O(n^2)$ 방식의 브루트 포스로도 풀 수 있지만 투 포인터를 이용하면 $O(n)$으로 쉽게 풀 수 있다. 코드 class Solution: def maximumLengthSubstring(self, s: str) -> int: frequencies = {} answer = 0 start = 0 for end in range(len(s)): frequencies[s[end]] = frequencies.get(s[end], 0) + 1 while frequencies[s[end]] > 2: frequencies[s[start]] -= 1 start += 1 answer = max(answer, end - start + 1) return answer

오늘 한 내용 Data Structure. Segment Tree LeetCode 2213. Longest Substring of One Repeating Character StackDay. 책임 분리와 타입 분리 배운 내용 StackDay 통계 계산 HabitStatistics를 구현하면서 계산 결과를 표현하는 타입과 계산 로직을 분리했다. 다만 HabitStatisticsCalculator가 HabitStreakCalculator에 의존하게 되면서, 여러 Calculator가 같은 날짜 정규화와 완료 기록 필터링을 반복하는 문제가 보였다. 타입을 나누는 것만으로 항상 구조가 좋아지는 것은 아니고, 공유하는 계산 맥락까지 함께 살펴봐야 한다는 점을 배웠다. 자세한 고민은 StackDay 개발일지에 정리했다. ...

문제 https://leetcode.com/problems/longest-substring-of-one-repeating-character 풀이 스트링 s에 대해 여러 번의 문자 변경 쿼리가 주어진다. 각 쿼리마다 특정 인덱스의 문자를 변경하고, 같은 문자가 연속되는 가장 긴 부분 스트링의 길이를 리턴하면 된다. 스트링의 길이와 쿼리의 개수가 최대 $10^5$이므로, 문자를 변경할 때마다 스트링 전체를 탐색하는 방식으로는 해결할 수 없다. 문자 하나를 변경하는 업데이트가 반복되고, 변경 이후 스트링 전체에서 가장 긴 연속 스트링의 길이를 구해야 한다. 따라서 변경된 구간만 갱신할 수 있는 Segment Tree를 사용했다. 다만, 단순히 concat을 하면 안되고, 두 접합부의 경계를 확인한 다음 처리를 해줘야 한다. ...