지나간 삶

■ 힙 정렬 

힙정렬의 `힙(Heap)`인 이유는 힙(Heap)이라는 자료구조를 사용하기 때문이다. 힙은 기본적으로 이진트리 구성이며, 이 이진트리에 몇 가지 속성을 부여한 것이 힙이 된다. 

다음은 힙의 한 예로서 배열과 이진트리의 관계를 보여준다. 

  힙을 정의하자면 자식노드의 값보다 부모노드의 값이 같거나 큰, 완전 이진트리를 말한다. 즉 어떤 리스트가 힙으로 구성될 수 있다면 배열 상에서 인덱스 1에 해당하는 값인 뿌리노드의 값은 전체 노드의 값들보다 큰 특징을 갖는다.

 힙 정렬의 과정을 요약하면 다음과 같다. 

1. 리스트[배열]를 힙(Heap)으로 만든다.

2. 힙 상에서 정렬을 수행한다. 

우선 리스트를 힙으로 만드는 과정에서는 좌 하위트리와 우 하위트리가 각각 힙인 경우에 뿌리 노드의 재귀적인 이동을 통해 전체 트리를 힙으로 만드는 알고리즘이 사용된다. 즉, 끝 노드들은 그 자체로 힙이기 때문에 끝 노드를 자식노드로 가지는 노드들로부터 위의 알고리즘을 사용해 힙으로 만들면서 차례로 위로 올라오면서 전체가 힙의 구성이 완성 되어진다. 

그림으로 도식하면 다음과 같다.

 다음으로 힙 구조상에서 정렬하는 방법을 살펴보면, 힙은 뿌리노드의 값이 가장 크기때문에, 일단 정렬의 가장 기본이 되는 사항이 완성되어 있는 셈이다. 이 뿌리노드를 저장하고, 리스트 상의 맨 마지막 노드를 뿌리노드로 옮긴다. 이렇게 하면 이 노드는 뿌리노드만 힙이 아니고 좌 하위트리나 우 하위트리가 모두 힙이 된다.    여기에 힙 구조로 만드는 알고리즘을 적용하면 다시 뿌리노드의 값이 가장 큰 값이 된다. 그렇게 되면 이 뿌리노드의 값을 저장하고 다시 마지막 원소를 뿌리노드로 옮긴다. 이 과정을 반복하면 가장 큰 값부터 차례대로 찾아낼 수 있다. 

다음은 처음 두 개의 원소만 찾아내는 과정을 보인다.

void adjust(int *list, int i, int n)

/* i : adjust 알고리즘을시작하는노드의인덱스*/

/* n : 전체노드의개수*/

{

     int j, k, done;

     done = 0; // 아직끝나지않았음을표시

     k = list[i]; // 뿌리노드값, 즉옮겨야할원소의값

     j = 2 * i; // i 노드의좌자식노드

     while(( j <= n ) && (!done)) // 자식노드가있고not done 일때까지반복

     {

          if ( j < n )  // j + 1 < = n 과마찬가지로우자식노드의존재를검사

             if (list[j] < list[j+1])

                j = j + 1;  // 자식노드들중큰노드를선택

          if ( k >= list[j] )

             done = 1; // 자식노드보다크므로수행을중단

          else {

             list[j / 2] = list[j]; // 자식노드를부모노드로끌어올림

                                      // 자식노드에k값을쓰지않는이유는나중에

                                     // 수행이다끝난다음에쓰기때문

             j = 2 * j;

          }

     }

     list[ j / 2] = k; // 수행이끝나면찾아낸위치에맨처음저장한뿌리노드의값을저장

}

 void heap_sort(int *list, int n)

{

     int i, temp;

     for ( i = (n / 2) ; i >= 1 ; i-- ) // 초기힙만들기

         adjust(list, i, n);

     for ( i = (n - 1) ; i >= 1 ; i-- ) // 힙정렬의두번째단계

     {

         temp = list[i + 1];  // 마지막노드와뿌리노드의교환

         list[i + 1] = list[1];

         list[1] = temp;

         adjust(list, 1, i);  // i개의키에대하여adjust 적용

     }
}

이상으로 자주 사용되는 정렬법들을 알아보았는데 알고리즘별 속도를 간략히 도시하면 다음과 같다.

FILE *fp = fopen("..", "r");

해놓고 free(fp); 를 하지 않나

int *ar = (int *)malloc(sizeof(int));

해놓고 fclose(ar); 을 하고 ...'보내지 않음'창만 계속 탓하고...

"나 바보 아냐???"

'발전'과 '발달'의 차이

[질문]

'발전'과 '발달'의 차이를 알고 싶습니다.

[답변]

'발전'과 '발달'의 의미 차이를 명확하게 가르는 것은 쉽지 않습니다. 다만 대체적인 차이는 다음과 같습니다.
  '발전'은 보다 못한 상태에서 더 나은 상태로 넘어가는 과정에 주된 의미가 있습니다. 반면에 '발달'은 주로 일정한 수준에 이른 상태를 가리킵니다. 즉 '발달'은 과정이 아닌 상태라는 점에서 '발전'과 구별됩니다. 아래 (1)의 예를 보십시오.(표시는 문법적으로 매우 이상함을 뜻합니다.)

(1) 가. 원시농경사회는 상업이 발전/    발달하였다.
     나. 소규모의 정치적 모임을 정당으로 발전/    발달시키겠다.

  원시농경사회에서 상업은 그리 성행하지 않았습니다. 그러나 그 시대도 이전 시대에 비해서는 상업이 여러모로 더 나아진 것은 분명합니다. 이 경우 (1 가)에서 보듯 이전 시대에 비해 상업이 '발전'했다고 할 수 있습니다. 그러나 일정한 수준에는 이르지 못한 미미한 수준이었기에 '발달'했다고는 하지 않습니다. 비슷한 경우로 조선 초기는 고려에 비하여 불교가 '발전'하지는 않았지만 그런대로 '발달'했다고는 할 수 있습니다. 이러한 차이를 생각하면 (1 나)에서도 그 모임을 '발달'시킨 것이 아니라 '발전'시킨 것이라고 하는 까닭을 이해할 수 있습니다.
  그런데 '발전'이 대부분의 경우 보다 못한 상태에서 더 나은 상태로 가는 것을 가리키나, 경우에 따라 작은 상태에서 더 큰 상태로 가는 것을 가리키기도 합니다.

(2) 단순한 소요가 폭동으로 발전/    발달하였다.

  (2)에서 소요라는 작은 상황이 폭동이라는 크고 심각한 상황으로 변한 것을 가리켜 '발전'하였다고 하였습니다. 그러나 이것도 그 쓰임이 다소 넓어진 것일 뿐 (1)에서 본 기본적인 의미는 그대로 유지하고 있습니다.
 

   '발전'과 '발달'은 많은 경우에 같이 쓸 수 있는데 주로 이상의 의미 차이에 따라 구분됩니다. '기술의 발전, 대학의 발전, 제도의 발전' 등은 기술, 대학, 제도 등이 이전보다 더 나아졌다는 의미이고, '기술의 발달, 대학의 발달, 제도의 발달'은 그것들이 현재 상당한 수준에 이른 것을 의미합니다.
 

   '발전'이 아닌 '발달'이 자연스러운 경우를 보면 다음과 같습니다.

(3)
가. 오늘날 과학의 발달/    발전은 지구를 한마을로 만들었다.
나. 신체의 발달/??발전, 고기압의 발달/    발전

  지구를 한마을로 만들기 위해서는 과학이 상당한 수준에 이르러야 합니다. 그런데 (3 가)는 지구촌(地球村)이 가능해진 것이 단지 과학이 이전 시대에 비하여 나아졌기 때문이 아니라 과학이 상당한 수준에 이르렀기 때문이라는 뜻이므로 '발전'이 아닌 '발달'이 자연스럽습니다.

  (3 나)에서 보듯 신체가 일정한 수준으로 성장한 상태를 나타내기 위해서 신체의 '발달'이라고 합니다. "인간의 신체 발달은 청소년기에 거의 이루어진다."라는 말을 흔히 들을 수 있습니다. 고기압도 일정한 수준으로 형성된 상태를 가리키는 의미에서 고기압의 '발달'이라고 합니다.

이것들은 표현의 초점을 어떠한 상태에 두는 것이지 과정에 두는 것이 아닙니다.  
  한편 '발달'도 어떤 단계에서 다음 단계로 넘어가는 과정을 뜻하기도 합니다. 그러나 이 경우 단순히 과정이 넘어가는 데 주된 의미가 있을 뿐 '발전'처럼 보다 못한 단계에서 더 나은 단계로 나아간다는 의미는 없습니다.

  이 점에서 '발달'이 '발전'과 매우 유사하면서도 차이점이 있습니다. 아래 (4)의 예를 보십시오.

(4) 언어의 발달/    발전

  언어는 시간에 따라 단지 한 단계에서 다음 단계로 이행하는 것이지 점점 나아진다는 의미는 없습니다. 따라서 '언어의 발달'이라고 하지 '언어의 발전'이라고 하지는 않습니다.

 문학이나 종교 등이 시대에 따라 변화한 모습을 연구하는 학문도 "문학/종교의 발달사"라고 하지 "문학/종교의 발전사"라고 하지는 않습니다. 왜냐하면 이들이 시대의 흐름에 따라 반드시 더 나은 상태로 가는 것은 아니며, 학문의 관점은 이들의 발전 여부와 상관없이 그 변모한 모습을 살펴보는 것이기 때문입니다. 그래서 이들은 "문학/종교의 변천사"로 바꾸어 말할 수도 있습니다.
 

  이와 같은 '발전'과 '발달'의 차이점을 충분히 이해하지 못하여 잘못 쓴 경우를 종종 발견할 수 있습니다. 아래는 실제 글들에서 뽑은 것입니다.

(5)

  가. 도시 문명이 발전될수록 도시인은 한편으로 전원의 정취를 그리워하며.......
  나. 물론 이것을 우리 한국 역사의 발전 단계에 맞추어 설명해 낼 수는 없겠지.
  다. 시조(時調) 형태의 발생으로부터  그 발전 경로를 검토하고자 하며.......

  '발전'은 앞에서 말씀드렸듯이 더 나은 상태로 나아가는 것입니다. 따라서 도시가 발전한다는 것은 전원을 갖추고 인간답게 살 수 있는 환경을 제공하는 것을 내포할 수 있습니다.

 그러므로 (5 가)에서 도시 문명이 발전할수록 인간이 전원의 정취를 그리워한다는(즉 도시에서 상실감을 느낀다는) 것은 어색합니다. '발달'로 바꾸는 것이 좋습니다. (5 나, 다)도 앞의 예문 (4)에서 설명드린 대로 역시 '발달'로 고쳐야 자연스럽습니다.
 

  이상의 의미 차이를 알고 있으면 '발전'과 '발달'을 가려 쓰는 데 큰 문제는 없으리라 생각합니다. 우리가 개업한 집에 '축 발달'이 아니라 '축 발전'이라고 인사하는 것도 쉽게 이해할 만합니다.

출처 : 네이버 흥미진진 우리말 상식

int __cdecl printf (

        const char *format,

        ...

        )

/*

 * stdout 'PRINT', 'F'ormatted

 */

strstr 함수는 표준 C에서 처음 도입한 함수다. 이는 문자열 str 안에서 문자열 sub가 처음으로 나오는 위치를 찾아 해당 위치를 가리키는 포인터를 반환한다. 문자열 sub가 문자열 src에 한 번도 나오지 않는 경우에는 널 포인터를 반환한다.

strtok 함수는 문자열 str을 문자열 set에 나온 문자로 구분되는 토큰으로 나눌 때 사용한다. 각각의 토큰을 분리하기 위해 strtok 함수를 여러 번 호출하며, 도중에 문자열 set의 내용을 바꿀 수 있다. strtok 함수를 처음 호출할 때는 str에 문자열을 제공하며, 그 뒤에 이어지는 호출에서는 첫 번째 인자로 널 포인터를 주게 된다. 그러면 strtok함수는 이전에 찾은 토큰의 뒷부분부터 이어 검색을 진행한다.(strtok 함수를 사용해서 문자열 안의 토큰을 검색하는 과정에서 처음 제공된 문자열 str을 도중에 수정하면 안 된다.)

과정을 더 자세히 설명하면, 매개 변수 str에 널 포인터가 제공되지 않으면, strtok 함수는 문자열 str에서 set 에 존재하는 모든 문자를 건너뛰게 된다. 만약 문자열 str이 문자열 set의 문자로만 구성되어 있는 경우, strtok 함수는 토큰을 찾을 수 없기에 결과로 널 포인터를 반환한다. 이때 내부적으로 상태를 저장하기 위해 사용하는 포인터는 널 포인터로 설정된다. 문자열 str에 문자열 set에 나오지 않는 문자가 있는 경우, 내부 상태 포인터가 str에서 해당 문자를 가리키게 되고, str로 널 포인터가 제공된 것처럼 함수 실행이 계속된다.

str과 내부 상태 포인터 모두가 널 포인터인 경우, strtok 함수는 널 포인터를 반환하고 내부 상태 포인터는 널 포인터로 남는다.(이는 모든 토큰을 찾은 이후에 추가로 strtok 함수가 호출되는 경우를 위해서다.) str 이 널 포인터고 내부 상태 포인터가 널 포인터가 아닌 경우, 함수는 내부 상태 포인터가 가리키는 위치부터 시작해서 처음 제공된 str의 나머지 부분에서 set에 포함된 문자를 찾게 되고, 그와 같은 문자를 찾으면 해당 문자를 널 문자로 덮어쓴다. 함수의 결과로는 내부 상태 포인터의 값을 반환하고, 반환 이후에 내부 상태 포인터의 값은 저장된 널 문자 바로 뒤의 문자를 가리키도록 수정된다. 그러한 문자를 찾지 못하는 경우, strtok 함수는 내부 상태 포인터의 값을 반환하고 내부 상태 포인터를 널 포인터로 설정한다.

/*
다음프로그램은표준입력스트림으로부터문자열을입력받아strtok 함수를통해입력받은
라인을단어단위로나누어표준스트림으로출력한다. 이때단어는공백, 쉼표, 마침표, 인용부호,
물음표로구분된다고가정한다.
*/

예제 1.