문제 https://codeforces.com/problemset/problem/279/B 풀이 책을 읽는데 걸리는 시간이 담긴 크기 n 배열 a가 주어지고, 책을 읽을 수 있는 시간 t가 주어진다. 특정 인덱스를 정해서 그 인덱스부터 책을 순서대로 읽었을때, 최대로 읽을 수 있는 책의 개수를 출력하면된다. 모든 경우의 수를 탐색하려면 $O(n^2)$의 시간 복잡도를 가지는데 책의 개수가 10만개 이므로, 시간 내로 해결하기는 힘들다. ‘순서대로’라는 조건이 있으므로, 투 포인터를 이용하면 쉽게 풀 수 있다. 단 배열 a의 원소의 크기가 t보다 클 수 있으므로, 단 한권의 책도 읽지 못하는 경우가 있다. 그래서 책을 0권 읽는 경우의 수도 생각해서 코드를 짜야 한다. ...

문제 https://leetcode.com/problems/minimum-number-of-pushes-to-type-word-i 풀이 휴대전화의 2에서 8까지의 숫자에 문자를 배치할 수 있고, 2개 이상의 수가 배치되었을 땐 여러번 눌러야 뒤에 있는 숫자를 타이핑 할 수 있다. 스트링 word가 주어졌을 때, 버튼을 가장 적게 눌러 word를 타이핑 했을 때의 타이핑 수를 리턴하면 된다. 각 키의 첫 번째 문자는 1번, 두 번째는 2번… 눌러야 하므로 많이 등장하는 문자일수록 누름 횟수가 적은 앞자리에 배치해야 한다. 빈도수 내림차순 정렬 후, 인덱스를 8로 나눈 몫 + 1이 해당 문자의 누름 횟수가 된다. ...

오늘 한 내용 LeetCode 3518: Smallest Palindromic Rearrangement II Codeforces 189A: Cut Ribbon 블로그 깃 훅 제거 블로그 스크립트 구조화 블로그 커밋 목록 정리 해결 내용 PS 두 문제를 푼 이후에, 블로그에서 스크립트와 깃 훅을 교체하고, 하루종일 깃과 씨름했다. Hugo 프로젝트의 커밋 로그가 너무 더러웠고, Squash, Rebase로 한 번 정리하려는데, 중간에 워킹 트리가 한번 꼬여버렸다. 블로그 깃 훅 일시 제거. 블로그 깃 훅에는 두 가지 문제가 있다. 첫 번째는 타이밍 문제다. pre-commit에 뭔가 내용을 수정하는 훅을 넣으면, 커밋이 멈추지 않고. 변경사항을 유지한채로 커밋되어버린다. ...

문제 https://codeforces.com/problemset/problem/189/A 풀이 길이가 n인 리본이 하나 주어지고, 이를 a, b, c 의 크기로만 조각낼 수 있을 때, 최대로 만들 수 있는 조각의 개수를 출력하는 문제이다. 잘린 리본 조각의 크기가 정해져 있으므로, 그리디가 아니라 DP로 접근해야 한다. 그리디로 접근하면 마지막에 남은 리본 조각의 크기를 확정할 수 없기 때문이다. dp[i]를 길이 i인 리본을 조각냈을 때의 최대 조각 수로 정의하면, 점화식은 다음과 같다. $$dp[i] = \max_{x \in {a, b, c}}(dp[i - x] + 1) \quad \text{if } i \geq x \text{ and } dp[i-x] \neq -1$$ ...

문제 https://leetcode.com/problems/smallest-palindromic-rearrangement-ii 풀이 1번 문제와 마찬가지로 팰린드롬의 성질상 절반만 결정하면 전체가 결정된다. 따라서 이 문제는 절반 문자열의 k번째 사전순 순열을 구하는 문제로 단순화된다. 각 문자의 등장 횟수를 세고, 홀수 번 등장하는 문자는 팰린드롬의 가운데에 배치한다. 나머지는 2로 나눠 halfTable을 만든다. 절반 문자열에는 중복 문자가 있을 수 있으므로, 전체 순열 수는 단순히 $n!$이 아니라 중복 순열 공식으로 구해야 한다. $$\frac{n!}{\prod_{i} n_i!}$$ 여기서 n은 절반 문자열의 길이, n_i는 각 문자의 개수이다. 이 값이 k보다 작으면 k번째 순열이 존재하지 않으므로 빈 문자열을 반환한다. ...

오늘 한 내용 Codeforces 230B. T-Primes Leetcode 3517. Smallest Palindromic Rearrangement I 배운 내용 C++ 배열 vs 벡터 Codeforces에서는 C++로만 코드를 작성하는데, 최근에는 벡터보다 C 스타일 배열을 선호했다. 그런데 오늘 T-Primes 문제를 풀면서 다시 벡터를 쓸까 고민했다. 가장 큰 이유는 보일러플레이트 때문이다. push_back 같은 벡터에서 편리한, 다른 언어에서는 당연히 있는 메소드가 배열에 없다. 결국 추가 코드를 작성하고 어느정도의 비효율이 생긴다. 그 외에도 배열은 함수에 넘길 때 크기를 같이 넘겨줘야 하는 번거로움이 있다. 글로벌 변수를 선호하지 않아서 레퍼런스를 파라미터로 와르르 넘기는 스타일을 쓰는데, 배열이면 크기도 같이 들고 다녀야 한다. ...

문제 https://codeforces.com/problemset/problem/230/B 풀이 T-Prime을 약수가 3개인 수라고 정의하고, $n$개의 크기의 수열 $x$의 원소 각각에 대해서 그 수가 T-Prime인지 확인하는 문제이다. 약수가 3개라는 뜻은, $1$과 자기 자신 그리고 $\sqrt{x_i}$만을 약수로 가진다는 뜻이다. 즉, T-Prime은 어떤 수의 제곱이어야 한다. 그 ‘어떤 수’의 조건은 무엇일까? 약수의 약수는 결국 약수이다. T-Prime은 $1$, ‘어떤 수’, 자기 자신만을 약수로 가지므로, ‘어떤 수’는 소수여야 한다. 결국 이 문제는 소수 판별 문제로 단순화된다. $x_i$의 최댓값이 $10^{12}$이지만, T-Prime 여부를 판별하려면 $\sqrt{x_i}$가 소수인지만 확인하면 되므로 체는 $\sqrt{10^{12}} = 10^6$까지만 구성하면 충분하다. 에라토스테네스의 체의 시간복잡도는 (거의) $O(N)$이고, 이후 각 쿼리는 $O(1)$에 처리되므로, $n \leq 10^5$인 입력 전체에 대해 전처리 $O(10^6)$ + 쿼리 $O(n)$으로 풀 수 있다. ...

문제 https://leetcode.com/problems/smallest-palindromic-rearrangement-i 풀이 팰린드롬 스트링 s가 주어지고, 이 s의 원소들을 재배열 하여 만들 수 있는 팰린드롬중 가장 사전순으로 빠른 문자열을 리턴하는 문제이다. s가 팰린드롬 스트링인것이 보장되니, 팰린드롬의 성질인 대칭을 이용하면 정렬 문제로 바꿀 수 있다. s의 원소 개수가 홀수인지 짝수인지만 주의하면 된다. 만약 홀수면 대칭의 중심이 존재하니, 원소 중 등장 횟수가 홀수인 원소가 존재한다. s에서 등장하는 모든 원소의 등장 횟수를 센다. s의 원소 개수가 홀수라면, 원소들 중 홀수번 등장하는 원소를 center를 찾는다. 이 원소가 팰린드롬의 중간에 들어가는 문자이다. 원소들의 등장 횟수를 절반으로 줄인 다음, 사전 오름차순으로 정렬한 스트링 half를 만든다. half와 center 그리고 half를 뒤집은 스트링을 합쳐서 결과를 만든다. 코드 class Solution { func smallestPalindrome(_ s: String) -> String { var countTable = [Character: Int]() var half = "" var center = "" for element in s { countTable[element, default: 0] += 1 } for (element, count) in countTable.sorted(by: { $0.key < $1.key }) { if count % 2 == 1 { center = String(element) } half += String(repeating: element, count: count / 2) } return half + center + String(half.reversed()) } }

SwiftUI는 선언형 UI 프레임워크다. Rich Feature Set, 다양한 기능과 기기 고유의 이점을 활용할 수 있는 풍부한 기능 집합 Less Code, 더 적은 코드 Incremental adoption, 필요한 순간에 적절하게 사용 가능. 전체 앱이 반드시 SwiftUI일 필요는 없다. SwiftUI Essentials SwiftUI는 선언형 UI 프레임워크이기 때문에 UIKit 처럼 UIView 객체가 계속 메모리에 상주해있고, 그 객체를 직접 변화시키는게 아니라, View를 보고 SwiftUI가 그리는 방식이다. 즉, View는 그냥 UI 요소를 정의하는 설계도이다. (Demistify SwiftUI 세션에서도 한 말이다!) ...

오늘 한 내용 Codeforces 4C. Registration System Codeforces 25A. IQ Test 각각 Hash Table과 구현 능력을 요구하는 PS 문제였다. IQ Test 부분이 구현이 살짝 번거로운 부분이 있었다. SwiftUI. SwiftUI Essentials WWDC 24에서 나온 SwiftUI Essentials 세션을 봤다. 24분 영상인데 정보 밀도가 엄청 높고 예제에서 보여준 것들도 많아서, 직접 예제를 돌리고 캡처하고, 동영상 녹화하고 하는데 꽤 시간이 들었다. 덕분에 블로그에 이미지 수평 배열, 이미지 캡션과 같은 숏 코드들도 추가했다. 배운 내용 SwiftUI Essentials WWDC 세션을 하나 봤다. 이번에는 SwiftUI의 기본 구조를 다시 정리하는 내용이었는데, 핵심은 View가 실제 UI 객체를 직접 만지는 대상이 아니라 선언형으로 UI를 설명하는 값이라는 점 이었다(Demystify SwiftUI도 마찬가지고 엄청나게 반복되는 내용이다.) ...