두들낙서/수학2 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. 음수 진법이 가능할까? 10진법으로 1234라고 적으면 $$1234=1\times10^3 + 2\times10^2 + 3\times10^1 + 4\times10^0$$ 을 의미한다. 마찬가지로 8진법으로 1234라고 적으면 $$1234_{(8)}=1\times8^3 + 2\times8^2 + 3\times8^1 + 4\times8^0$$ 을 의미하게 된다. 참고로 계산해보면 10진법으로 668이 나온다. 10진법은 자릿수로서 0~9의 숫자를 사용하고, 8진법은 0~7까지의 숫자를 사용한다. 또 10진법에서 한 자리가 올라갈 때마다 자리의 크기(계수)가 10배씩 증가하고, (1의 자리, 10의 자리, 100의 자리, ...) 8진법은 8배씩 증가한다. (1의 자리, 8의 자리, 64의 자리, ...) 즉 n진법은 0부터 n-1까.. 2019. 9. 1. 이전 1 다음
