목록Data Structure (7)
코딩하는 해맑은 거북이
[자료구조] 정렬(Sort)
정렬 - 물건을 크기 순으로 나열하는 것 (오름차순 또는 내림차순) - 정렬은 키(key)가 포함된 레코드들을 순서대로 나열하므로 정렬의 단위는 레코드가 된다. * 키 : 정렬의 기준 (비교의 대상) * 레코드 : 하나의 정보단위 (교환의 대상) ex) 직원정보를 사번으로 정렬 → (키 : 사번, 레코드 : 직원정보 전체) 정렬 알고리즘 - 단순한 코드에 긴 수행시간 : 삽입정렬, 선택정렬, 버블정렬 등 - 복잡한 코드에 짧은 수행시간 : 퀵정렬, 히프정렬, 합병정렬, 기수정렬 등 - 모든 경우에 최적인 정렬 알고리즘은 없다! → 사용되는 환경에 맞추어 선택한다. - 정렬 알고리즘의 평가로는 (비교횟수, 이동횟수, 안정성)이 있다. 1) 삽입 정렬 (insertion sort) - 정렬 안 된 부분의 숫..
[자료구조] 트리(Tree), 이진트리, 이진트리 순회, 이진탐색트리(BST)
트리 - 계층적인 구조 - 사이클을 포함하지 않음 (부모-자식 관계) - 특별 노드(root)가 존재 - 서로 독립적인 서브트리를 가짐 트리의 종류 - 일반 트리 : 자식 노드의 수가 제한이 없음 - 이진 트리 : 자식 노드의 수가 2개 이하이다. 트리 기초 용어 - 루트(root) : 최상위 노드 (ex) A - 단말노드(terminal node) : 자식이 없는 노드 (ex) E,F,G,H,I,J - 형제노드(sibling) : 같은 층에 있는 노드 (ex) E,F,G - 레벨(level) : 트리의 각층의 번호 - 높이(height) : 트리의 최대 레벨 (ex) 3 - 차수(degree) : 노드가 가지고 있는 자식 노드의 개수 (ex) B의 차수는 3 트리의 표현 - 일반적인 구조 → 문제점 :..
[자료구조] 큐(Queue), 원형 큐, 회문 판정
큐(Queue) : FIFO (First-in-First-Out) 삽입(rear)과 삭제(front)가 다른 장소에서 이루어지는 순서 리스트 배열 큐 구현 - 큐 구조 정의 #define Max_Queue_Size 10 // 최대 큐크기 typedef int element; element queue[Max_Queue_Size]; int rear = -1; int front = -1; - 큐의 구현 방식 1) 선형 큐 : 단순 선형 배열로 구현한 큐로 포화 상태(Full)일 경우 배열을 조정해야 한다. 2) 원형 큐 : 선형 큐의 해결방법으로 큐의 시작과 끝이 마치 원으로 연결된 것 같이 사용한다. - 원형 큐는 rear과 front를 최초 0에서부터 시작한다. - rear = (rear+1) mod MA..
[자료구조] 스택(Stack), 괄호검사, 후위식 계산, 중위식의 후위식 변환
스택 : LIFO (Last-In-First-Out) 기본 연산인 삽입(push)과 삭제(pop)가 한쪽 끝(top)에서만 이뤄지는 순서 리스트 배열 스택 구현 - 스택 구조 정의 #define Max_Stack_Size 10 // 최대 스택크기 typedef int element; element stack[Max_Stack_Size]; int top = -1; - 공백 상태 int is_empty() { return (top == -1); } - 포화 상태 int is_full() { return (top == (Max_Stack_Size - 1)); } - 삽입 void push(element item) { if (is_full()) { printf("Stack full\n"); exit(1); } ..
[자료구조] 연결리스트(Linked List)
리스트 동일 특성을 갖는 항목들의 모임 선형리스트 순서에 따른 항목들의 모임 리스트의 구현 1) 배열 구현이 단순하나 삽입/삭제 연산이 비효율적이다. 정적인 구조로 크기가 고정되어 있다. 2) 연결리스트 구현이 복잡하나 삽입/삭제 연산이 효율적이다. 동적인 구조로 크기에 제한을 받지 않는다. 연결리스트의 구조 - 노드 구조 : 데이터 + 다음 데이터를 가르키는 주소(포인터) 필드로 구성 다음 데이터가 없을 경우 포인터의 주소값은 None(또는 Null)이다. ** C/C++언어 - 노드 구조 정의 typedef struct ListNode { int data; struct ListNode* next; } ListNode; - 삽입 1) head가 NULL인 경우 -> 삽입 노드가 head 2) 리스트의 ..
[자료구조] 배열 및 구조체, 다항식 덧셈, 희소행렬 전치
배열 : 연속된 메모리 위치의 집합 배열의 저장방식 - 행 우선 순서 : c, c++, python - 열 우선 순서 : fortran 언어 배열의 표현 (행 우선) - 2차원 배열의 주소 계산 : int a[m][n] a[i][j]의 주소 = base + (i∙n + j) ∙ sizeof(int) - 3차원 배열의 주소 계산 : int a[l][m][n] a[i][j][k]의 주소 = base + ((i∙m∙n + j∙n) + k) ∙ sizeof(int) 구조체 : 타입이 다른 자료들을 그룹화한 것 typedef struct { char name[10]; int age; float salary; } person; 자체참조 구조 그룹의 구성 요소 중 자신을 가리키는 포인터 존재 typedef struc..