오랜만에 머리도 식힐(?) 겸 프로젝트 오일러를 하나 풀어봤다. 문제의 골자는 세제곱수 중에 순열을 이루는 것이 다섯 개 있는 것을 찾아내는 것. 이 문제는 사실 unsigned long long을 사용하면 그닥 어렵지 않게 만들 수 있다. 몇 가지 포인트만 잡으면 꽤 빠르게 동작하는 프로그램을 만들 수 있다. 1. 모든 자릿수의 모든 숫자를 대상으로 계산하면 너무 복잡해짐 2. 세제곱수의 자릿수를 결정한 뒤 그 범위에 해당되는 세제곱근들만 계산 #include #include #include using namespace std; bool ArePermutated(unsigned long long b1, unsigned long long b2) { int cnt[10]; memset(cnt, 0, siz..
\(\sqrt{2}\)는 아래와 같이 근사화시킬 수 있다. \(\sqrt{2} = 1+\frac{1}{2+ \frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{ \cdots }}}}}\) 여기서, 1,000 자리까지 전개한 결과에서 분모와 분자의 자릿수가 다른 것이 몇 번 나오는가를 계산하는 문제이다. 위의 전개를 조금만 다르게 써 보면 아래와 같이 된다. \(\sqrt{2} = 1+\frac{1}{1+1+ \frac{1}{1+1+\frac{1}{1+1+\frac{1}{1+1+\frac{1}{ \cdots }}}}}\) 이렇게 하면 첫번째 전개에서의 분모/분자를 두 번째 전개의 특정 부분에 쉽게 적용할 수 있다. 1,000 자리까지의 전개 결과를 화면에 출력하려면 대략 아래와 같…..
현대 암호화 기법 중엔 XOR을 이용하는 방법도 널리 쓰인다. 이 문제는 주어진 데이터가 XOR로 암호화되어있고, 키의 길이가 소문자 3자리일 때 원문을 구하는 문제이다.키가 3개이므로 aaa~zzz 까지의 17576(263) 가지의 키를 일일이 대입해봐도 되지만, 3부분으로 나누어 78(26×3)번만 돌려도 된다. 문제에는 좀 모호하게 적혀있긴 하지만, 원문은 일반적인 영단어로 구성되어 있다고 한다.즉, 키의 후보값을 넣고 돌렸을 때 결과가 일반적인 영단어에 포함되지 않는 기호가 나타나면 키가 아니라고 볼 수 있는 것이다. 이러한 점을 고려해서 대략 아래와 같은 코드를 작성했다. #include #include using namespace std; inline bool isDecrypedChar(int..
정규수(Normal number)라는 개념이 있다.그리고, 극단적인 정규수로 챔퍼나운 상수(Champernowne's constant)가 있다. 이 문제는 챔퍼나운 상수의 1, 10, 100, 1000, 10000, 100000, 1000000 자리 숫자의 곱을 구하는 문제다.근데, 정규수와 챔퍼나운 상수의 수학적 의미와 별개로 이 문제는 숫자만 나열하면 되는 문제라 의외로 쉽다. 처음부터 일일이 다 늘어놓는 방법도 있지만, 그건 좀 심하고, 조금만 생각을 해보면 계산을 많이 줄일 수 있다. 1. 1~9자리는 그대로 1~9임2. 10~99의 90개는 2자리임3. 100~999의 900개는 3자리임, 이후도 같은 규칙임 이런 규칙들을 염두에 두면 대략 아래와 같은 코드가 나온다. #include #incl..
언뜻 보기엔 평범한 문제로 생각하기 쉽다.그냥 long double에다 대입한 뒤에 결과를 문자열 형식으로 출력해서 문자열을 비교하면 될 것 같은 생각착각이 든다. 그런데, 이 바닥 문제 중에 그런 만만한 건 없다. 이 문제의 요지는 아무리 긴 숫자도 일일이 나누어 저장하여, 순환 여부를 정확히 비교할 수 있는 코드를 만드는 것이다.순환 여부를 확인하려면 숫자를 나누면서 각 자리의 몫과 그 때의 나머지를 모두 저장하고 이를 모두 비교해야 한다. 아래의 divide() 함수가 이 기능을 수행하는 함수다.quotient[]에는 각 자리의 몫을, remain[]에는 해당 자리의 나머지를 저장한다. #include #include #include using namespace std; // a / b int di..
문제는 간단하다. 100!을 계산해서 각 자리수의 합을 구하는 것.이게 대체 몇 자리나 되는지를 간단히 알아보기 위해 계산기를 돌려봤다. 9.3326....E+157이니까 158자리 숫자다.당연한 얘기지만, long long int 같은 건 아이고 의미 없다… 앞으로도 계속 써먹기 위해 CBigInt 같은 클래스를 하나 만들어볼까 하다가 그냥 간단히 만드는 것으로 방향 전환… 팩토리얼은 승수와 피승수가 모두 큰 정수일 필요가 없기 때문에 최대한 간단히 만들어봤다. #include #include #include // 각 자리에 0~9999를 저장하는 것으로... // 즉 10000진수 개념을 적용 const unsigned nDigit = 10000; unsigned *assign(int data, in..
뭔 이런 문제가 프로젝트 오일러에 나오나 모르겠다…1부터 1000까지를 영어로 읽은 것의 알파벳 수를 세라니… ㅋㅋㅋ 곰곰 생각해보면 짚어야 할 포인트가 몇 개 있다. 1. 단어를 그대로 쓸 필요는 없다. 단지 알파벳 개수만 세면 된다. 2. 1~20은 그냥 대입하는 거다. 3. 30, 40, 50 ~ 90은 13~19에서 teen을 ty로 바꾼 것이니 2를 빼면 된다. 단, forty와 fourteen은 이 규칙에서 예외 4. 100이 넘으면 100자리 뒤에 and가 붙는다. 5. 필요한 함수들을 별도로 짜면 더 복잡해지고, 하나를 재귀적으로 짜는 게 더 깔끔하다. 대략 이 정도로 짜면 괜찮은 거 아닐까 생각된다… #include int getWordCount(int num) { // 1~20의 글자수..
요즘 프로젝트 오일러에 필이 꽂혀 하나씩 풀어보고 있다.역시 흥미를 끄는 재미있는 문제들이 많다. 13번 문제는 50자리 숫자 100개를 더하는 문제다.이건 unsigned long long int 같은 데 때려박아봤자 답이 없고, 별도의 자료형을 만들거나 문자열 자체에서 연산을 해야 된다. 그런데, 갑자기 옛 생각(?)이 나서 BCD로 코딩해보고 싶어졌다.요즘은 거의 쓰이지 않는 것 같은데, MSX 시절에는 연산 속도를 끌어올리기 위해 BIOS 내에서도 사용됐던 인코딩이다.16진수 값을 그대로 10진수로 적용해서 비트의 낭비가 있다는 게 단점… #include #include #include // 50자리 숫자 100개. ㄷㄷㄷ const static char * nums[] = { "371072875..
3. 삼각수의 약수의 개수 문제 중에 처음 호기심을 자극한 문제가 이것이다. 이 문제는 언뜻 보면 기초적인 문제 같지만, 동작 성능을 고려하면 상당히 고난이도 문제다. 물론, 단순무식하게 아래와 같이 만들어도 동작은 한다… #include #include int countOfDivisors(int num) { if (num = 2; i--) { if (num % i == 0) ret++; } return ret; } int main(int argc, char* argv[]) { printf("-= count of divisors of triangular numbe..