iTrans를 업데이트하면서 이미지의 해상도를 읽어야 할 상황이 생겼다.IJG 및 libpng를 사용하면 되긴 하지만, 고작 해상도 정보 얻자고 라이브러리까지 쓰긴 좀 그래서 간단한 방법을 쓰기로 했다. 간단히(응?) 파일을 뒤져서 해상도 정보를 찾는 것. cplusplus.com에서 관련된 소스를 찾을 수 있었다.그런데, 이 코드에는 사소한 문제들이 있다. - GIF도 포함된 소스인데, 난 GIF는 안 쓰기 때문에 제거 가능 - 파일 크기를 얻기 위해 fseek() 등을 쓰는데, 필요 없음- JPEG 헤더를 읽을 때 EXIF가 앞에 들어있는 경우는 제대로 처리하지 못함- 파일의 형식은 알려주지 않음 아래 코드는 이 내용이 반영된 코드이다. // itype: 1=JPEG 2=PNG bool getImag..
\(\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..
6. IEEE 부동소수점에서 유효숫자 추출 이 문제에 대해선 아예 설명을 추가해달라고 했던데, 설명해줘도 못 알아먹는다는 데 한 표. 그리고, 이 문제는 사실 검증이 좀 어렵다. Visual Studio에서는 IEEE 16비트 부동 소수점은 아예 구현이 되어있지 않기 때문이다. IEEE에서는 부동소수점을 \(1.nn \cdot 2^m\) 형태로 표현한 뒤 유효숫자(mantissa)에서 1을 뺀 부분을 저장한다. 이 유효숫자를 추출하는 것이 문제의 요구사항이다. 그런데, 문제에는 함정이 하나 있다. 리턴값은 unsigned int형이며, 최대값이 \(2^{23}-1\), \(2^{10}-1\) 이라는 점이다. 즉, 유효숫자 부분을 추출한 뒤 값의 변화 없이 unsigned int로 강제 형변환을 해서 읽은..
4. 연산자 끼워맞추기 연산자 7개를 일일이 끼워맞춰보는 문제다.루프 7개를 중첩시켜서 돌려서 풀어도 되고, 트리를 구성해서 DFS 등으로 푸는 방법도 있을 것 같다. 그런데, 조금만 생각해보면 루프를 복잡하게 만들 필요가 없다.연산자가 +/- 둘 밖에 없으니 그냥 각 연산자를 비트 단위로 놓고 단일 루프를 돌려도 된다. #include #include int main(int argc, char* argv[]) { printf("-= plus or minus =-\n"); int nums[] = { 1, 6, 7, 6, 1, 4, 5 }; int count = 0; for (int i = 0; i < 0x80; i++) { int sum = 0; int digit = 1; for (int j = 0; j..
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..
어떤 정신 나간 녀석이 네이버 지식인에 코딩 질문을 올렸다. 문제 수준이 좀 애매했다 싶더니 역시 모 회사 입사 테스트 문제라고 한다. 이제 시간도 좀 지났으니 데드라인도 지났을 것이라 판단해서, 그간 작성해본 풀이를 공개함… 1. 파스칼의 삼각형의 합 사실, 파스칼의 삼각형의 합은 간단한 일반식이 나와있다. \(sum = 2^n-1\) 그런데, 이런 식으로 만들라는 얘긴 아닌 것 같다. ㅋ #include #include int *makeNewRaw(int *oldRaw, int oldLen) { int *ret; if (oldLen < 1) { ret = new int[1]; ret[0] = 1; return ret; } ret = new int[oldLen + 1]; for (int i = 1; i..
페북에 재미있는 질문이 올라왔다.아래와 같이 16개의 데이터를 정렬한 뒤 지그재그 형태로 출력하려면 어떻게 해야 되는가가 골자였다. 사실 이 문제는 멀티미디어 쪽 종사자라면 굉장히 자주 접하는 문제다.정석적인 풀이는 지그재그 테이블을 생성하고 그 테이블에 따라 값을 출력하는 것이다. 4행부터 시작되는 MakeZigzagTable() 함수가 그 테이블을 생성해주는 함수이다. #include #include int *MakeZigzagTable(int nWidth) { int *table = new int[nWidth*nWidth]; bool directionIsUp = true; int x = 0, y = 0; int val = 0; while (true) { table[y*nWidth + x] = val..
0. 발아점 (재활용) 이전 포스트 임의의 숫자가 제곱수인지 빠르게 판별하는 법에 이어지는 포스트임. 1. 문제에 대한 나의 접근(실패) \(a^2+b^2+4a^2b^2 = c^2\) 을 아래와 같이 변형한 뒤 \(a^2+b^2+2ab+4a^2b^2-2ab = c^2\) 아래와 같이 정리했다. \((a+b)^2+2ab(2ab-1) = c^2\) 여기서 모든 제곱수(\(c^2\))에 대해 이러한 관계를 만족시키는 a, b를 찾는 거다. 하지만, a, b는 Brute-Force하게 루프를 돌려야 되는데, 효율성이 낮다. (c가 100일 때 돌렸던 루프를 c가 1000일 때도 또 돌려야 함) 따라서 실패. 2. 치욱님 솔루션 a, b의 최대값은 \(\sqrt {20} \cdot 10^9\)이다. 여기서, a를..
0. 발아점 @chiw00k 님께서 트윗에 올린 질문을 해결하는 과정에서… @zaeku 님의 솔루션을 공부하면서 의문점이 생겼다. 제곱수인지를 식별하는데 갑자기 아래의 식이 튀어나온 것이다. h = n & 0xF 1. 기본형 임의의 숫자가 제곱수인지 판별하는 건 사실 그리 어렵지 않다. 대략 아래와 같은 함수만 하나 만들면 된다. bool IsSquare(unsigned int num) { unsigned int temp = (unsigned int)(sqrt((double)num)+0.5); return temp*temp == num; } 하지만, 아무리 컴퓨팅 파워가 좋아져도 sqrt()는 느린 함수다. 위의 함수를 돌리기 전에 제곱수가 아닌 경우를 배제하는 방법을 찾아봤다. 2. 10진수 두 수를 ..
