지나간 삶

네이버와 구글지도

만드신 분 대단하시다..

언제 종료될지 모르는 서비스!!

■ 힙 정렬 

힙정렬의 `힙(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)에서 설명드린 대로 역시 '발달'로 고쳐야 자연스럽습니다.
 

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

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