문제 https://leetcode.com/problems/sum-of-gcd-of-formed-pairs 풀이 문제에서 지시한 내용을 그대로 구현하면 되는 문제다. 문제의 지시사항은 다음과 같다: 인티저 배열 nums의 누적 최대값 배열 mx를 만든다. prefixGcd[i] = gcd(nums[i], mx[i]) 으로 이루어진 배열을 만든다. prefixGcd를 오름차순 정렬한다. prefixGcd의 제일 큰 값과 제일 작은 값의 쌍을 만들어, GCD를 구하는 것을 더 이상 만들지 못할 때 까지 반복한다. 만약 prefixGcd의 원소의 개수가 홀수라서 페어을 만들지 못한 하나가 남는다면 무시한다. ‘4’에서 구한 모든 GCD 값의 합을 리턴한다. 페어을 만드는건 간단한 형태의 투 포인터로 해결했다. 정렬과 유클리드 호제법을 제외하곤 모두 $O(n)$에 해결되기 때문에, 시간복잡도는 $O(n \log n + n \log V) = O(n \log (nV))$이다. ...

문제 https://leetcode.com/problems/gcd-of-odd-and-even-sums 풀이 인티저 n이 하나 주어지고 작은 짝수 n개, 가장 홀수 n개를 각각 모두 더한 합 간의 GCD를 구하는 문제이다. 문제에서 요구하는 내용이 너무 간단해서, gcd()를 쓰지 않고, 유클리드 호제법을 직접 작성해서 GCD를 구했다. 코드 class Solution { public: int gcdOfOddEvenSums(int n) { int sumOdd = 0; int sumEven = 0; for (int num = 1; num <= n * 2; num++) { if (num % 2 == 0) sumEven += num; else if (num % 2 != 0) sumOdd += num; } while(sumEven) { sumOdd %= sumEven; swap(sumOdd, sumEven); } return sumOdd; } };

문제 https://leetcode.com/problems/find-the-number-of-subsequences-with-equal-gcd 풀이 수열 nums이 주어지고, nums에서 서로 원소가 겹치지 않게 부분 수열을 두 개 만든 뒤, 각 부분 수열(이하 A, B라 함)의 GCD가 같은 경우의 수를 찾는 문제이다. 만약 브루트 포스를 시도한다면, 원소의 개수 n, 각 원소가 가질 수 있는 상태가 3개(부분 수열 A, 부분 수열 B, 아예 미포함)이므로, 시간 복잡도가 $O(n \times 3^n)$ 이 되는데, nums의 최대 크기가 200이므로 유효한 시간 내에 해결할 수 없다. 하지만 부분 수열을 점점 채워나가면서 두 부분 수열을 비교할 수 있으므로, DP를 사용하면 O(n * 부분 수열A의 최대 gcd * 부분 수열B의 gcd 최대값)이 된다. 문제의 제약조건에서 원소의 최대 크기는 200이고, GCD는 원소보다 클 수 없으므로, $O(n \times 200 \times 200)$으로 줄일 수 있다. ...

문제 https://leetcode.com/problems/rank-transform-of-an-array 풀이 배열의 각 원소를 크기 기준으로 순위로 변환해 리턴하는 문제이다. 배열을 정렬한 뒤 각 원소에 순위를 매핑하고, 원본 배열 순서대로 순위를 꺼내 리턴한다. 문제에서 주의점이 하나 있는데, 같은 숫자는 같은 순위를 가진다는 것이다. 따라서 매핑할 때, 중복처리를 해줘야 한다. 코드 class Solution: def arrayRankTransform(self, arr: List[int]) -> List[int]: sortedArr = sorted(arr) rankDict = {} rank = 1 for element in sortedArr: if not element in rankDict: rankDict[element] = rank rank += 1 return list(map(lambda x: rankDict[x], arr))

문제 https://leetcode.com/problems/sequential-digits 풀이 low와 high 사이의 수 중, 각 자릿수가 123, 3456 처럼 연속으로 이어지는 수를 모두 리턴하는 문제이다 문제와 제약조건을 보고 바로 DFS 백트래킹로 풀어야겠다는 생각을 했다. 구간의 크기가 최대 1억이기 때문에, 하나하나 확인하는 것은 무리가 있다. 따라서 수를 하나씩 붙여나가면서 확인하고, 조건에 벗어나면 프룬닝 하면 되는 전형적인 문제로 생각했다. 백트래킹으로도 충분히 빠른 속도로 문제를 풀 수 있지만, 문제를 제출하고 난 뒤 효율성을 검증해보니. high 크기가 최대 1억이기 때문에, 후보들의 수가 몇개 되지 않기 때문에, 실제로 자리수가 연속되는 모든 숫자들을 만들고 확인하는 방식이 더 빠를수도 있다고 한다. ...

키워드 Python 로컬 변수 스코프. Python에서 람다식 정리, Swift 인라인 클로저와 다른점. 블로그 마이그레이션 하면서 이전에 썼던 iOS 관련 글 복습 블로그에서 카테고리를 몇개를 해야하는가? 내용 Python 로컬 변수 스코프 문제 Leetcode 1291번 문제를 푸는 도중에 다음과 같이 코드를 작성했다. 로직에 오류가 있어서 통과는 못하는 코드다. class Solution: def sequentialDigits(self, low: int, high: int) -> List[int]: answer = [] seq = [] def dfs(n: int): if n > 9: return if seq: intSeq = int("".join(seq)) if high < intSeq: seq = [] # 이부분 return ... seq 변수가 sequentialDigits 함수의 로컬 변수인데, if 문 안의 seq = [] 부분 때문에 에러가 났다. ...

오늘 한 내용 Hugo 블로그에서 Mermaid를 외부 CDN 없이 렌더링하도록 변경 Mermaid가 필요한 페이지에서만 스크립트를 로드하도록 최적화 hugo --minify로 빌드 검증 배운 내용 Mermaid 코드 블록은 layouts/_markup/render-codeblock-mermaid.html에서 <pre class="mermaid">로 변환하고, layouts/_partials/extend_footer.html에서 Mermaid가 포함된 페이지에만 스크립트를 삽입하도록 구성했다. 처음에는 ESM 파일 하나만 static/에 복사했지만, 해당 파일이 내부 chunk를 추가로 참조하는 구조라 렌더링이 깨졌다. 브라우저가 다이어그램을 SVG로 바꾸지 못하고 원문 텍스트처럼 보여서, 의존성이 단순한 mermaid.min.js로 교체했다. 외부 CDN을 제거하는 작업도 단순히 파일을 내려받는 것으로 끝나지 않았다. 번들 파일의 의존성과 실행 방식까지 확인해야 실제 정적 사이트에서 안정적으로 동작한다는 것을 배웠다. ...

문제 https://leetcode.com/problems/path-existence-queries-in-a-graph-i 풀이 그래프 각 노드의 연결 조건이 주어지고, 들어오는 쿼리들에 있는 두 노드들이 연결되어있는지 확인하는 문제이다. queries 배열의 길이가 최대 10만이므로, BFS를 이용해서 풀기는 거의 불가능하다. BFS보다 더 빠르게 ‘연결 여부만’ 확인하는 방법은 Union-Find Set을 사용하면 된다. 우선 연결 조건은 두 노드의 절대 차이(노드 번호의 차이의 절대값)가 maxDiff 이하여야 하는데, 문제에서 nums 배열이 오름차순으로 정렬되어 있다고 했으므로, nums[j] - nums[i] <= maxDiff 를 만족하는 연속된 범위를 투 포인터로 찾을 수 있다. ...

문제 https://leetcode.com/problems/find-the-maximum-number-of-elements-in-subset/ 풀이 주어진 배열의 원소들로 만들 수 있는 가장 긴 [x, x², x⁴, ..., x^(2^k), ..., x⁴, x², x] 형태의 부분집합 길이를 반환하는 문제다. 이하에서는 이 형태를 피라미드라고 부른다. 어떤 문제든 제약 조건이 중요하지만, 이 문제는 특히 제약 조건이 중요하다. 주어진 꼴에서 원소들은 급격히 증가하는데, 1 <= nums[i] <= 10^9 라는 제약 조건이 있기에, 배열의 최대 크기를 예상할 수 있다. x가 1일 때는 몇 번을 제곱해도 1이므로, nums 배열 내부에 있는 1의 개수에 따라 달려있다. 피라미드 꼴은 항상 홀수이므로, 1의 개수가 홀수일때는 그대로, 짝수일때는 1을 뺀 값을 문제에서 요구하는 최대값의 초기 값으로 정한다. ...

문제 https://leetcode.com/problems/concatenate-non-zero-digits-and-multiply-by-sum-ii 풀이 1번 문제와 로직은 동일하다. 차이점은 스트링 s의 서브스트링에 같은 작업을 queries마다 반복해야 한다는 점이다. queries의 원소가 최대 10만 개이므로, 매 쿼리마다 부분 문자열을 슬라이싱해서 처리하면 시간 초과가 난다. 따라서 전처리를 통해 각 쿼리를 $O(1)$ 혹은 $O(n \log n)$에 처리할 수 있도록 해야 한다. 전처리 단계에서 네 가지 누적 배열을 만든다. pow10: $\text{pow10}[i] = 10^i \mod (10^9 + 7)$ preSum: 각 인덱스까지 자릿수의 합 preConcat: 각 인덱스까지 0이 아닌 숫자들을 이어붙인 값 nonZeroCount: 각 인덱스까지 0이 아닌 숫자의 개수 쿼리 [l, r]이 들어오면 네 배열로 x와 sum을 $O(1)$에 구해 $x \times \text{sum} \mod (10^9 + 7)$를 리턴한다. 0이 아닌 숫자가 없는 경우는 수식이 자연스럽게 $0$을 리턴하게 된다. ...