You Lead!!

요즘 보고 있는 책이다. 전반적으로 C++ 코드도 깔끔하고 볼만한 책이다. 텍스트 패턴 매칭부분을 보면서 Boyer-Moore알고리즘을 보는데, 와~ 하고 감탄했다. BM패턴을 보기전에 과연 어떻게 패턴을 찾는 알고리즘을 개선시킬까 잠깐 고민하고 봐서 그런지 더 와닿은거 같다. BM알고리즘의 원리는 간단하다. 1. 비교하는 문자열을 뒤에서 부터 확인 2. 비교하는 문자열에 없는 문자가 오면(last(c) == -1), 문자열 개수만큼 건너뛰기 원리는 간단한데, 효과는 강력한 알고리즘.. 멋진 패턴 중 하나인거 같다. Moore의 홈페이지 http://www.cs.utexas.edu/users/moore/ 관련 ppt 자료

오늘 새벽 0시에 Topcoder 를 드디어 시작했다. Topcoder를 위해 C++ 서적을 뒤벼서 문법이나 STL을 1주일간 공부하고 참여했던만큼 의미가 남달랐다. ㅎㅎ C++을 대학 졸업하고부터 거의 코딩한 적이 없었기 때문에 책을 보면서 생소하게 느껴지는 부분도 좀 있었다. 특히 그동안 몇가지 문제들을 C로 직접 Linked List같은 걸 구현해가며 풀었었는데, STL을 보고 나서는 입이 딱 벌어지는 느낌이었다. STL이나 boost나 이런 좋은 라이브러리들이 있는데.. 아직도 C로만 짜고 있는 우리회사 기술력이 한심하게 느껴지는 순간이었다. C++을 제대로 공부해보고자 Effective시리즈 책들도 주문해서 책장에 꽂아놨다. ㅡㅡㅋ; Topcoder 문제를 어제 오후에 몇개 풀어봤는데, Div2..

Google codejam Round 1A 문제를 풀어봤다. 주어진 v1, v2 수들에 대해 임의로 두개씩 곱한 합이 가장 작은 경우를 구하는 문제. v1, v2를 크기로 정렬한 후에 가장 큰값과 가장 작은 값을 쌍을 지으면서 곱해서 풀면 된다. ㅇ #include #include #include #define INPUT_SIZE 100000 void insertion_sort(int list[], int n) { int i, j, key; for(i=1; i= 0 && list[j] > key; j--) list[j+1] = list[j]; list[j+1] = key; } } int main() { FILE *fp; char sLine[INPUT_SIZE]; int loop_cnt; int array..

장장 7시간 정도 걸려서 푼 문제다.. 문제해법을 고민하는데 1/3정도는 고민을 한 듯.. sin, cos같은 함수를 안본지가 꽤나 오래돼고.. 원넓이 구하는 공식같은거도 기억이 안나서 찾아보면서 풀었다. 문제 요지는 파리채 구멍 영역중 파리의 중심이 위치했을때 살 수 있는 면적을 구하는 문제. 파리채의 왼쪽아래좌표와 오른쪽 위 좌표를 구해서, 면적의 모양에 따라 일일이 구해주면서 풀었다. 음 그런데. 예시의 내용이나 Smaill.in은 맞게 나오는데, Large.in을 넣으면 InCorrect가 뜬다. 무슨 이유일까 싶어 고민해 봤지만, 구체적으로 머가 틀리다는 건지가 안나와서 그냥 스킵하기로.. 소스파일 #include #include #include #define SQ(X) ((X)*(X)) #de..

푼지는 좀 됐는데.. 기록상 올려둔다. Google codejam 2008 Qualification Round B 문제로 기차의 출발, 도착시간이 나오고, 필요한 기차대수를 구하는 문제다. NA로 가는 것들에 대해 도착시간이 늦은 순으로 정렬하고, NB로 가는 것들에 대해 출발시간이 빠른 순으로 정렬한 후, 최대한 안기다리고 바로바로 출발하도록 짝을 지어주면, 필요대수가 나옴.. list.c 소스 #include #include #include #include "link.c" #define INPUT_SIZE 100 void readList(ListNode *list_head, ListNode *list_head_R, int type, FILE *file_ptr, int list_cnt, int t); ..

어제에 이어 오늘은 UVA 101 번을 풀어봤다. 100번과 비슷한 난이도겠지 싶었는데.. 꽤 시간이 걸렸다. 문제이해하는 것도 좀 오래걸리고;; 힘들게 linked list 이용해서 풀어서 제출했는데.. Time 초과라고 나오네;; 수행시켜보니 포인터로 처리해서 시간 별로 안걸리는데.. UVA쪽하고 환경이 안맞거나 머 그런듯하다.. 머 문제는 풀었으니.. 푼 것으로 하고 넘기기로.. list.c 소스 #include #include #include #include "link.c" #define INPUT_SIZE 10000 int main() { char sLine[INPUT_SIZE]; int i; char delim[] = "' '"; char command[10]; char command_to[1..

UVA 라는 사이트를 알게 됐다. 알고리즘 문제들이 있고, 소스를 올려서 본인의 랭킹같은거도 나온다. 재미삼아 제일 첫번째 100번 문제를 풀어봤는데.. 그리 어렵지 않았다. include #include #include #define INPUT_SIZE 10000 int cycleLength(int n, int len) { len++; if(n == 1) return len; if( (n % 2) == 0 ) n = n / 2; else n = 3 * n + 1; return cycleLength(n, len); } int main() { char sLine[INPUT_SIZE]; int i; char delim[] = "' '"; int value1, value2; int small, large, l..

어제 Google code jam(GCJ) Qualification Round가 있었다. 어제는 업무때문에 볼 여력이 없었는데, 오늘 시간이 좀 나서 어제 기출문제(?)를 한번 풀어봤다. 문제는 A, B, C로 나오고 각 문제별로 Smaill Input, Large Input 으로 나와있다. 문제 A는 비교적 금방 이해되어서 C 문법도 공부해볼겸 C로 짜봤다. 처음에 그냥 배열로 하다보니 반복처리하는거도 잘 안되고 해서 Linked List를 간단하게 구현해서 완성했다. ㅋㅋ 나온 output을 검증해보니 smaill 과 large 모두 한번에 Correct 다. 오호; 이맛에 프로그래밍을 하는군..싶다. 문제는 다음과 같고 Smaill파일과 Large 파일이 제공됐다. Problem The urban ..

임백준씨가 쓴 "임백준의 소프트웨어 산책"이란 책을 최근에 읽었다. 그중에 뒷부분에 '프로그래머 K씨의 하루'라는 짧막한 소설이 있었는데, 거기에 흥미로운 내용이 있었다. 구글에서 2004년쯤인가에 사진과 같은 광고판을 어느 고속도로에 붙였다고 한다. {e의 연속된 숫자중에서 10개로 이루어진 첫번째 소수}.com이라는 문구는 유능한 프로그래머를 찾고자 하는 구글의 작은 이벤트였던 것이다. 흥미로워서 실제로 저 수를 구하는 소스를 C로 짜봤다. ㅋㅋ 숫자가 10자리라 int형으로 안되서 double로 처리했음.. #include #include #include #include #define TOTAL_ROW 10000 #define EACH_UNIT 10 #define LOOP_CNT 2000 int i..

회사에서 인증등 보안이 필요한 부분에 대해 php내에서 zend기능을 통해 c확장기능을 구현해 놓고 쓴다. 그런데, 기존에 구현되어 있는 부분이라 소스도 복잡하고, 이 부분이 왜 들어갔을까 하는 부분을 알기 힘들기 때문에, 기존 소스에 구애받지 않고, 직접 간단하게 c확장기능을 구현하는 부분을 테스트 해보았다. 참고로, zend라고 검색을 하면 주로 php성능향상을 위해 zend사에서 내놓은 엔진에 대한 내용이 많은데, http://kr.php.net/manual/en/zend.php#zend.intro 위 사이트에서 보면 php에서 c와 같은 다른 언어의 함수등을 호출해서 쓸 수 있는 기능으로도 불린다.. 우선 다음과 같이 c로 test.c를 만든다. #include "php.h" ZEND_FUNCTI..