'[아는게 힘이다] > [프로그래밍]' 카테고리의 다른 글
[C++] 부분 문자열 검사 (Substring) (0) | 2010.03.19 |
---|---|
[C++] 전화 번호 문자열 변환 (Telephone Words) (0) | 2010.03.19 |
[C] 회전된 문자열인지 판별 (0) | 2010.03.10 |
[C] 문자열에서 반복되는 가장 긴 부분 문자열 (8) | 2010.03.06 |
생각하는(?) 실용주의(?) 프로그래머 (2) | 2010.03.04 |
[C++] 부분 문자열 검사 (Substring) (0) | 2010.03.19 |
---|---|
[C++] 전화 번호 문자열 변환 (Telephone Words) (0) | 2010.03.19 |
[C] 회전된 문자열인지 판별 (0) | 2010.03.10 |
[C] 문자열에서 반복되는 가장 긴 부분 문자열 (8) | 2010.03.06 |
생각하는(?) 실용주의(?) 프로그래머 (2) | 2010.03.04 |
[C++] 전화 번호 문자열 변환 (Telephone Words) (0) | 2010.03.19 |
---|---|
[C] 회전된 문자열인지 판별 (0) | 2010.03.10 |
[C] 문자열에서 반복되는 가장 긴 부분 문자열 (8) | 2010.03.06 |
생각하는(?) 실용주의(?) 프로그래머 (2) | 2010.03.04 |
[CS] 연결 리스트 뒤집기 (Reverse Linked List) (6) | 2010.02.28 |
블로그를 참고하면서 공부하고 있는 1인입니다.
좋은 컨텐츠를 제공해 주셔서 감사를 드립니다, 많은 도움이 되고 있어요.
(char*)대신 *(char**)을 쓰는 이유를 알 수 있을까요?
실제로 코딩해봤는데 strcmp에서 정렬이 안되더군요.
답변이 너무 늦었지만, 훗날을 위해 답변 달아봅니다.
buf 배열은 대상 문자열(e.g., banana)을 담고 있고, sa 배열은 대상 문자열의 각 문자를 가리키는 포인터를 담고 있습니다. 예를 들면, sa[2]는 첫번째 "n"의 주소를 갖고 있습니다. 따라서 buf는 char* 타입이고, sa는 char** 타입입니다.
*(char**)을 살펴보면 일단 (char**)는 const void* 타입을 캐스팅한 것인데, a가 sa의 원소(element)를 가리키는 포인터가 되어야 하므로, sa의 타입인 char**로 캐스팅합니다.
앞에 있는 *는 역참조(dereferencing)를 하기 위한 것인데, 우리가 비교하려는 대상은 sa 배열의 값 자체가 아니라 그것이 참조하고 있는 문자열 자체이므로 *를 사용해서 비교되는 대상이 buf 배열에 있는 문자열의 일부가 되도록 하기 위해서입니다.
비교 대상은 sa의 각 원소가 가리키고 있는 문자열인데, 정렬되어야 하는 값은 sa의 각 원소입니다.
본문에서 '문자열 비교에서 n'이라고 한 것은 sorting 내에서 2개의 문자열 간 비교를 말한 것입니다. sorting 후 인접 문자열 간의 비교가 아닙니다. 본문 문장에 오해의 소지가 조금 있었을 수도 있겠는데, 원래 의도는 이렇습니다.
보통 sorting의 예에서는 element 개수가 dominant하고 각 element간의 비교는 O(1)입니다. (e.g., 문자열의 길이가 상수) 그런데 이 문제에서는 element 개수가 문자열의 길이와 같기 때문에 아래와 같이 계산해야 합니다.
element 개수를 n이라 할 때 우리가 사용한 sorting에서 비교 횟수는 O(nlogn)라고 합시다.
이 문제에서는 두 element를 비교하는 compare 함수도 O(n)가 됩니다.
따라서 이 sorting에서 문자(char) 비교 횟수는 총 O(n*nlogn)이 됩니다.
감사합니다.
C는 CS의 기초중에 기초라고 할 수도 있다.
하지만 C만 제대로 다 알아도 사실상 거의 다 안다고 할 수 있다.
컴프 마지막 숙제는 malloc과 free와 거의 동일한 기능을 하는 함수를 만드는 것인데
이게 사실 ANSI C 책에 그대로 나온다는 사실을 나중에 알았다. (누가 공개를 해버려서...)
문득 예전에 사 놓고 책꽂이에 쳐박혀 있던 이 책의 가치가 새삼스럽게 느껴진다.
책을 얼추 훑어보니 각종 기초 라이브러리에 대한 설명 및 구현 방법들이 있다.
예를 들면 printf는 어떻게 만들어져 있을까라든지 file I/O는 어떻게 하는 것인지...
무턱대고 쓸 줄만 알았지 사실 어떻게 구현되어 있는지는 잘 모르는게 사실이다.
문득 틈틈히 이 책부터 공부해야지... 하는 생각이 들었다.
몇 가지 기초적인 언어들을 기반으로 이렇게 복잡하고 다양한 프로그램들을 짜내는 것...
그게 바로 프로그래밍 언어의 묘미(?)가 아닐까 한다.
당분간 CS와 굿바이해야 해서 그런지
은근 잼있는 것 같다. ㅋㅋ
교수님과의 졸업논문 최종 미팅... (0) | 2007.06.20 |
---|---|
이메일의 신뢰성(reliability) (0) | 2007.06.20 |
ANSI C 공부... (0) | 2007.06.19 |
내신 실질 반영률 문제... (3) | 2007.06.18 |
대학교 공식 종강 (0) | 2007.06.15 |
댓글을 달아 주세요