나의 큰 O는 log x야

c/c++로 코딩하다 보면 매우 간결한 조건문이 필요할 때가 있다. (예를 들어 인수가 잘못되어서 에러값을 리턴하는 경우처럼) 이럴 때는 {}를 사용하지 않고 한 줄 짜리 if문을 만드는 경우가 있다. 그런데 가끔씩 한 줄 짜리 if문에 두 가지 명령을 쑤셔넣으려고 다음과 같이 한다. if(cond)a++,b++; 이는 아무 문제가 없다. 하지만 다음과 같은 경우는 문제가 발생한다. if(error)free(ptr),return -1; (아마 에러가 발생해서 그 전에 할당해놓은 메모리를 해제하고 리턴을 하는 모양이다.) 결국 다음과 같이 코드를 고치게 된다. if(error) { free(ptr); return -1; } 왜 위의 경우는 되는데 아래의 경우는 안될까? 이는 c의 쉼표 연산자(,)를 잘못 ..

프로그래밍/테크닉 2009. 9. 13. 23:14

5차 정사각행렬 같은 경우는 어떻게 역행렬을 구할수 있을까??? 간단한 방법은 5차를 억지로 8차로 늘려버리는 것이다. 남는 자리에 0 (대각선은 1)을 채우면 된다. 그리고 얘의 역행렬을 구하고 왼쪽위에서 5x5개만 찝어내면 그게 원래의 역행렬이다. 그러면 이제 할일은 2^n꼴이 아닌 matrix를 2^n꼴로 확장시키는 것. template class roundbit { public: enum{value=roundbit::value*2}; }; template class roundbit { public: enum{value=2}; }; 2^m꼴이 아닌 수 n을 n이상의 2^m꼴로 바꿔주기 위해서 만든 클래스이다. roundbit::value하면 8이 되고, roundbit::value하면 64가 되겠다..

프로그래밍/테크닉 2009. 6. 28. 04:03

행렬을 작은 크기의 행렬 4개로 나눠어서 계산하는 것에 대해서는 이미 수학자들이 많이 연구해 놓았다. 그러나 글쓴이는 그걸 모르고 공책 한 바닥을 써가며 역행렬 구하는 공식을 구해는 삽질을 했다. (아이구 시간 아까워라.) 무궁한 지식의 원천 위키백과님에게 도움을 요청합니다. 그 공식은 위키백과에 상세히 나와있다. 이제 그럼 본격적으로 역행렬을 구하는 함수를 짜보자. bool has_inverse() { if(a.has_inverse() && (d-c*a.inverse()*b).has_inverse()) { return true; } if(d.has_inverse() && (a-b*d.inverse()*c).has_inverse()) { return true; } return false; } 역시나 te..

프로그래밍/테크닉 2009. 6. 28. 03:41

이번 떡밥은 템플릿 공부도 하고 수학 공부도 할겸 템플릿을 이용해서 n차행렬의 역행렬을 구해보는것이다. c++를 좀 써본 사람이라면 template어쩌구 하는 문법은 알거라고 생각하고 본론으로 들어간다. 이런 행렬을 이렇게 묶어주고 묶어서 생긴 새로운 행렬들을 A,B,C,D라 하면 이렇게 표현할수 있다. (행렬들의 행렬에 대해서도 덧셈, 뺄셈, 곱셈, 실수배가 똑같이 정의된다.) 이런 방법을 재귀적으로 사용한다면 2^n꼴의 행렬을 2*2행렬의 형태로 표현가능하다. 이 사실을 바탕으로 matrix 클래스를 짜본다. template class matrix { protected: enum{halfdim=dim/2}; matrix a,b,c,d; public: matrix() { } matrix(matrix _..

프로그래밍/테크닉 2009. 6. 28. 03:13

최대공약수를 구하는 알고리즘에는 대표적으로 유클리드 호제법이 있다. 유클리드 호제법을 간단히 설명하면 다음과 같다. 1. 두 수 a,b를 입력받는다. 2. a가 b보다 크면 a를 b로 나눈 나머지를 구한다. b가 a보다 크면 그 반대로 한다. 3. 나누어서 얻는 나머지를 새로운 a, 원래 a,b중 작은값을 b로 하고 2번으로 돌아간다. 4. 만약 a나 b가 0이 되었다면 이 때의 나머지 b나 a의 값이 최대공약수이다. 이 알고리즘은 a와 b의 최대공약수나 a-b와의 최대공약수나 같다는 사실을 이용해서 쉽게 증명할수 있다. int gcd(int a,int b) { if(b==0)return a; return gcd(a,a%b); } 위 코드는 유클리드 호제법을 간단하게 c코드로 짜본것이다. (단 a>=b일..

프로그래밍/테크닉 2008. 12. 20. 22:01

하아 어느덧 여러 수학함수를 구현해보려는 기나긴 장정이 역삼각함수에까지 이르렀다. 아직 쌍곡선 함수를 비롯한 여러 수학함수들이 남아있지만, 거의 쓰이지 않는 관계로(또한 귀찮은 관계로) 글쓰기를 무기한 연기해버리기로 했다. 역삼각함수는 각을 구해내기 위해서 자주 쓰인다. acos,asin,atan 등이 있지만, 가장 유용한 함수는 atan2이다. atan2는 x축 변위,y축 변위를 받아서 -Pi에서 Pi 사이의 각을 구해준다. (acos,asin,atan함수는 제한된 범위의 각만 구해낼수 있다.) 일단 atan2함수도 atan를 이용해 구현될수 있으므로 좀 뒤로 미루자. 먼저 역시 방대한 지식이 담겨있는 위키백과만큼 좋은 참조물도 없다. 영어위키백과: 역삼각함수 역삼각함수들에 대해서 다음 등식이 성립한다..

프로그래밍/테크닉 2008. 12. 8. 00:07

여태까지 제곱근함수와 지수함수, 로그함수를 대충 구현해보았다. 이를 이용하면 어지간한 계산들을 다 할 수 있으나, 한 가지 막히는 부분이 있으니 바로 삼각함수이다. 삼각함수는 약방의 감초라할만큼 안 들어가는 곳 없이 두루두루 들어간다. 삼각함수는 비용이 비싼 측에 낀다. (계산량을 줄일만한 획기적 방법이 별로 없는듯하다.) 그래서 삼각함수 연산을 자주 하는 프로그램에서는 대게 테이블을 만들어놓고 참조하는 방법을 쓴다. 이 방법이 대체로 빠른 방법이어서 추천하는 바이다. (가장 좋은 방법은 FPU의 빵빵한 지원이라고나 할까) 아래에 설명하는 계산법은 그냥 이렇게도 계산할수 있다는 거지, 이 식을 활용해서 계산하면 좋다는 의미는 아니다. 공학용으로 삼각함수계산을 어떻게 하나 궁금해서 영어위키백과를 찾아봤더니..

프로그래밍/테크닉 2008. 12. 7. 01:39

저번 글에서 지수함수를 구현하는 글을 대충 올렸었다. 지수함수를 구현했다면 역함수는 로그함수도 한번 꼭 구현해볼 필요가 있다. 지수함수(exp)와 로그함수(ln)를 이용하면 pow함수를 구현할수 있다. 사실 로그함수가 제곱근 함수 다음으로 널리 쓰인다고 볼 수도 있는데, 지수함수를 먼저 구현한 이유는 로그함수 구현은 꽤 까다롭기 때문이다. 잡소리 그만하고 자연로그란 밑이 e(=2.71828...)인 로그를 일컫는다. 수학적 정의는 다음과 같다. 이면이다. 모든 부동소수점 데이터는 꼴로 나타낼수 있으므로 여기에 로그를 취하면 이렇게 된다. ln2는 상수값이므로 중요하지 않고 n*ln2도 곱셈으로 계산가능하다. 우리가 구현해야할것은 를 계산하는 부분이다. 두고두고 써먹는 테일러 전개를 이용해서 자연로그 함수..

프로그래밍/테크닉 2008. 12. 3. 01:55