자료구조 (34) 썸네일형 리스트형 [ 자료구조 ] 정렬 - 01 . 정렬 알고리즘 [ 정렬 알고리즘 ] [ 알고리즘 ] 문제를 해결하기 위한 일련의 명령이나 반복되는 절차 . [ 해결 할 일 ] 3만명의 학생의 성적 데이터중 석차 17,213등인 학생의 번호를 알아내라 =>학생들을 점수 오름차순으로 정렬한 후 ,17213번째를 고르면 된다 . [ 정렬 ] 정렬은 "물건 등을 가지런히 늘어 세우다"라는 뜻을 가지고 있다 . =>정렬의 목적은 찾으려고 하는 것을 쉽게 찾는 것이다 . 정렬 알고리즘 역시 데이터의 나열이 목적이 아닌 찾고자 하는 데이터를 빠르고 쉽게 찾을 수 있게 함이 목적이다 . 정렬 알고리즘 중 활용도가 높은 3가지는 다음과 같다 . 버블 정렬 삽입 정렬 퀵 정렬 [ 자료구조 ] 트리 - 04 . 분리 집합 [분리집합이란] [분리집합] 교집합을 갖지 않는 집합 (원소의 모임)을 말한다 . 분리집합은 두개 이상의 집합을 일컬을때만 사용 가능한 개념이다 . [분리집합과 트리] 분리집합은 집합들간의 교집합을 허락하지 않기 때문에 서로 구분되어야 하는 데이터 집합을 다룰때 유용하다 . 원소 혹은 개체가 어느 집합에 소속되어 있는가?라는 정보를 바탕으로 하는 알고리즘에 응용 가능하다. 이와같이 어떤 한 원소가 속한 집합을 알아내는 것을 집합 탐색이라고 한다 . [분리집합의 표현] [분리집합의 표현] 지금까지 본 일반 / 이진트리는 모두 부모가 자식을 가리키는 포인터를 가지고 있었다 . 분리집합은 이와 다르게 자식이 부모를 가리킨다 . 즉 , 루트 노드는 집합 그 자체이고 , 루트 노드를 포함한 트리 내의 모든 노드들.. [ 자료구조 ] 트리 - 03 . 수식트리 [수식트리] [수식트리] 수식을 표현하는 이진트리 . 수식 이진 트리라고 부르기도 한다 . 일반적으로 수식트리는 하나의 연산자가 두개의 피연산자를 취한다는 가정하에 다음 두가지 규칙을 가진다 . 피연산자는 잎 노드이다 . 연산자는 루트노드 / 혹은 가지노드이다 . [예제] 1*2+(7+8) 루트노드/가지노드는 피연산자 (수 / 식)를 양쪽 자식으로 둔다 . 이런 방법으로 수식트리는 가장 아래에 있는 하위 수식 트리로부터 수 또는 계산결과를 병합해 올라가는 과정을 반복하며 계산을 수행한다 . 이러한 수식트리의 성질에는 후위순회(왼쪽 노드- 오른쪽 노드 - 루트 노드)가 알맞다 . 양쪽 하위 트리에서부터 결과값을 병합해 올라와야 하기때문이다 . [수식트리의 구축] [수식트리] 컴퓨터가 처리하기 좋은 후위 표.. [ 자료구조 ] 트리 - 02 . 이진트리 [이진트리] [이진트리] Binary(이진) Tree는 모든 노드가 최대 2개의 자식을 가질 수 있는 트리 . 데이터를 담는 용도 보다는 이진 구조를 활용한 알고리즘이 있다 . 수식을 트리 형태로 표현하여 계산하게 하는 수식 이진 트리 . 빠른 데이터 검색을 가능하게 하는 이진 탐색 트리 . [이진트리의 형태] 이진트리는 컴파일러나 검색등에 사용되는 특수 구조 자료이다 . 이진트리를 이용한 검색에서 높은 성능을 위해서 트리의 노드들은 가능한 완전한 모습으로 배치되어야 한다 . 다음은 완전한 모습의 트리의 목록이다 . [포화 이진트리] 잎 노드를 재외한 모든 노드가 자식을 둘 씩 가지고 있는 이진트리 잎 노드들이 모두 같은 깊이에 존재한다 . [완전 이진트리] 잎 노드들이 트리의 왼쪽부터 차곡 차곡 채워진.. [자료구조] 트리 - 01 . 트리 기초 다지기 [트리 기초 다지기] [트리] 트리는 나무를 닮은 자료구조 .회사의 조직체계 : 사장 (뿌리) - 부장 (가지) - 사원 (잎) 를 예로 들 수 있다 . 활용도가 높은 트리는 아래의 다양한 분야에 이용 되고 있다 . 운영체제의 파일 시스템 HTML,XML 문서를 다룰 때 사용하는 DOM(Document Object Mode) 검색 엔진 데이터 베이스 [트리의 구조] 트리는 뿌리(Root) / 가지(Branch) / 잎(Leaf) 세가지 요소로 이루어져 있다. 모두 같은 노드이지만 트리 내의 위치에 따라 명칭이 달라진다 . 뿌리(Root) - 트리 자료구조의 가장 위에 있는 노드 가지 (Branch) - 뿌리와 잎 사이에 있는 모든 노드 잎 (Reaf) - 끝에 있어 단말 노드 (Terminal)라고 부르.. [자료구조] 큐 - 03 . 링크드 큐 [링크드 큐] [링크드 큐] =>각 노드는 앞 노드에 대한 포인터를 이용하여 구성되어 있기에 삽입은 새 노드의 포인터에 후단을 연결, 제거는 전단 바로 이후의 노드에서 전단에 대한 포인터를 거두는 것으로 끝난다 . =>또한 용량의 제한이 벗어 가득 차 있는지에 대한 체크가 필요 없다 . [링크드 큐가 순환 큐보다 우월한가 ? ] =>성능은 순환큐가 더 빠르다 . 노드를 생성,삭제하기 위한 malloc()을 호출할 필요가 없기 때문 . 크기가 예측 가능하고 고성능이 필요한 버퍼와 같은 사례는 순환큐가 더 적절하다 . [링크드 큐 구현하기] [노드의 선언] typedef struct tagNode { char* Data; struct tagNode* NextNode; } [링크드 큐의 선언] typedef .. [자료구조] 큐 - 02 . 순환큐 [순환큐] [배열로 큐를 구현했을때 문제점] =>큐를 배열로 구현해야 한다면 ? 전단을 제거 후 나머지 요소를 한칸씩 앞으로 옮기는 비용이 들 것이다 . [해결과 문제] =>전단을 가리키는 변수를 도입하여 배열 내의 요소를 옮기는 대신 변경된 전단의 위치만 관리한다 . =>후단을 가리키는 변수 역시 도입하여 변경되는 후단의 위치를 관리한다 . (후단의 위치는 실제 후단의 위치 +1) =>해당 방식 역시 제거 연산을 할 수록 큐의 가용 용량이 줄어드는 문제가 있다. [순환큐] =>배열의 마지막 요소가 후단이었을때 , 데이터를 삽입하면 후단은 배열의 첫번째 요소로 변경시킨다 . 이렇게 시작과 끝을 연결해서 순환하도록 고안된 큐를 "순환큐"라고 한다. =>그러나 이렇게 끝난다면 비어있는 상태 , 가득 찬 상태.. [자료구조] 큐 - 01 . 큐 [큐] [큐] =>FIFO (First In First Out) 선입선출의 구조를 가지고 있는 자료구조 . =>큐의 가장 앞 요소를 전단 (Front) / 가장 마지막 요소를 후단 (Rear)라 부른다 . [큐의 주요기능] [삽입] =>삽입은 후단 (Rear)에서 이루어진다 . 삽입은 후단에 노드를 덧붙여서 새로운 후단을 만드는 연산이다 . [제거] =>제거는 전단 (Front)에서 이루어진다 . 제거는 전단의 노드를 엎애 전단 뒤의 노드를 새로운 전단으로 만드는 연산이다. 이전 1 2 3 4 5 다음
