전체 글20 [노트] 모든 약수를 구하는 알고리즘은 O(sqrt(n))이다. 학원 학생들이 약수를 모두 찾는 (또는 약수의 합, 개수를 구하거나, 소수 판별 등등) 코드를 어떻게 짜는지 살펴보면, 백이면 백 \(O(n)\) 알고리즘을 사용한다. 하지만 어떤 수의 모든 약수를 구하는 일은 \(O(\sqrt n)\) 시간만에 할 수 있다. 대부분의 사람들이 이 사실을 모르거나 알더라도 적극적으로 이용하지 않는 것 같아 적어본다. 우선 다음 두 정리를 살펴보자. 약수랑 제곱근이 뭔지만 안다면, 직관적으로 "그렇겠구나" 정도는 생각할 수 있는 것들이다. 1. 자연수 \(d\)가 자연수 \(n\)의 약수이면, \(n/d\)도 \(n\)의 약수이다. 2. 양수 \(d\)와 \(n\)에 대해 \(d\le\sqrt n \Longleftrightarrow n/d\ge\sqrt n\). 1 증명).. 2021. 4. 23. 순정률과 중간음률, 그리고 그 너머 (2) 이 글은 시리즈이다. 이전 글을 못 봤다면 보고 오는 게 좋다. 5. 중간음률 (Meantone Temperament) 중간음률에도 여러 종류가 있지만, 보통 중간음률이라 하면 "1/4콤마 중간음률"(quarter-comma meantone temperament)을 말한다. 이 무시무시한 이름에 들어있는 의미는, 중간음을 만들 때 syntonic comma의 1/4만큼씩을 보정하겠다는 뜻이다. 중간음이라는 것은 무엇이고, 뭘 보정한다는 것일까? 피타고라스 음률이 기억 나는가? 피타고라스 음률을 사용해 C에서 E까지 가보자. $$ C4 \xrightarrow{ \times \frac{3}{2} } G4 \xrightarrow{ \times \frac{3}{2} } D5 \xrightarrow{ \times.. 2021. 4. 16. 순정률과 중간음률, 그리고 그 너머 (1) 우선 당신이 이 글을 우연이 아니라 정말로 흥미나 필요에 의해 찾게 되었다면 하이파이브를 쳐주고 싶다. 중간음률이라는 단어를 아는 사람이 몇 명이나 될까. 전공생은 제외하고, 취미가 음악(감상이든, 연주든, 작곡이든)이라는 사람들의 수를 100명이라 하면, 그 중 순정률이라는 단어를 들어본 사람들의 수는 넉넉잡아야 한 10명 정도 될 것 같다. 그리고 그중 중간음률이라는 단어를 들어본 사람의 수는 많아야 1~2명 정도 되지 않을까 생각한다. 물론 자랑하는 것은 아니다. 그만큼 매니악한 분야이고, 특히 한국어로 된 것 중에서는 수학적인 원리와 음악적인 면을 모두 잘 나타낸 정보를 얻을 수가 없었다는 뜻이다. 그래서 이 글을 적어보게 되었다. 1. 기본 개념 이 글의 배경이 되는 개념들을 아주 기본적인 것부.. 2021. 3. 23. [노트] 최소공통조상(LCA) 찾기 문제: www.acmicpc.net/problem/11438 알고리즘을 나름 오랫동안 공부해왔던 나도 그래프와 트리 관련 문제는 많이 풀어보지 못한 것 같아, 요즘 가끔 생각날 때마다 관련 알고리즘들을 찾아보고 있다. 최근에는 LCA를 찾는 효율적인 알고리즘을 찾아보았는데, 경로에 대한 정보 없이 간단히 LCA만 딱 찾아내고 싶을 때는 복잡한 알고리즘이나 자료구조 없이 아주아주 간단한 테크닉으로도 가능하다는 것을 알게 되어 짧게 적어본다. 다음 사실을 관찰하는 순간 게임이 끝난다. 관찰: 노드 a와 b의 LCA는 a와 b 사이를 Euler tour로 방문하는 동안 지나친 노드들 중 가장 상위에 있는 노드이다. (솔직 고백을 하자면, Euler tour of tree라는 개념도 이걸 배우면서 처음 알게 되.. 2021. 3. 1. xlogx 꼴의 합의 상한 프로그래밍 문제를 풀다 보면 a개의 정수들을 정렬하는 일이 굉장히 많은데, 이 a개의 정수들을 한꺼번에 정렬하는 것(이때의 시간복잡도는 \(O(a\log a)\))과, 정수들을 n개의 그룹으로 분할해서 각 그룹끼리만 n번 정렬하는 것 중에 어떤 것이 빠를지 궁금해졌다. n=10일 때만 간단한 프로그램으로 확인해보니 대부분의 경우 항상 각 그룹을 정렬하는 것이 빠른 것을 확인할 수 있었다. 이 현상을 조금 더 일반화해서 다음과 같은 수학적인 가설을 세울 수 있었다. 양수 \(x_{1}, x_{2}, \cdots , x_{n}\)에 대해 \( x_{1}+x_{2}+\cdots+x_{n}=a\)일 때, \( x_{1} \log x_{1} +\cdots+x_{n} \log x_{n} < a \log a\)이다... 2020. 4. 4. 이전 1 2 3 4 다음
