본문 바로가기

전체 글115

[자료구조] 이진트리의 순회 1. 이진 트리의 순회 순회(Traversal) : 트리의 노드들을 체계적으로 방문하는 것 1) 기본적인 순회 방법 (1) 전위 순회(Preorder Traversal) : VLR - 자손 노드보다 루트 노드를 먼저 방문 (2) 중위 순회(Inorder Traversal) : LVR - 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문 (3) 후위 순회(Postorder Traversal) : LRV - 루트 노드보다 자손을 먼저 방문 root (V) ↙ ↘ left (L) right (R) 2. 전위 순회(Preorder Traversal) 1) 수행 방법 현재 노드 n을 방문하여 처리 : V 현재 노드 n의 왼쪽 서브 트리로 이동 : L 현재 노드 n의 오른쪽 서브 트리로 이동 : R 2) 알고리즘 pre.. 2020. 6. 24.
[자료구조] 이진 트리 구현 1. 순차 자료구조를 이용한 이진 트리 구현 1) 1차원 배열의 순차 자료구조 사용 높이가 h인 포화 이진 트리의 노드 번호를 배열의 인덱스로 사용 인덱스 0번 : 실제로 사용하지 않고 비워둔다. 인덱스 1번 : 루트 저장 2) 이진 트리의 1차원 배열에서의 인덱스 관계 노드 인덱스 성립 조건 노드 i의 부모 노드 [ i/2 ] 정수로 만듦 (가우스 기호) i > 1 노드 i의 왼쪽 자식 노드 2 * i (2 * i) ≤ n 노드 i의 오른쪽 자식 노드 (2 * i) + 1 (2 * i + 1) ≤ n 루트 노드 1 0 < n 3) 이진 트리의 순차 자료구조 표현 단점 사향(Skewed) 이진 트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생 트리의 원소 삽입, 삭제에 대한 배열의 크.. 2020. 6. 24.
[자료구조] 트리 1. 개념 트리 : 계층적인 구조를 나타내는 자료구조 원소 간에 1 : 다 관계를 가지는 비선형 자료구조 원소 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조(부모 - 자식 관계의 노드로 이루어짐) 응용 분야 - 계층적인 조직표현, 파일 시스템, 인공지능에서의 결정 트리 2. 용어 노드(node) : 트리의 구성요소 루트(root) : 부모가 없는 노드 (A) 서브 트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리 (B, C, D) 단말노드(terminal node) : 자식이 없는 노드 (E, F, G, H, I, J) 비단말노드 : 적어도 하나의 자식을 가지는 노드 (A, B, C, D) 레벨(level) : 트리.. 2020. 6. 24.
[자료구조] 큐(Queue) PART.2 1. 연결 자료구조를 이용한 큐의 구현 1) 단순 연결 리스트를 이용한 큐 큐의 원소 : 연결 리스트의 노드 큐의 원소의 순서 : 노드의 링크 포인터로 연결 변수 front : 첫 번째 노드를 가리키는 포인터 변수 변수 rear : 마지막 노드를 가리키는 포인터 변수 2) 상태 표현 초기 상태와 공백 상태 : front = rear = NULL 3) 연결 큐의 구조 A → B → C → D NULL front rear 4) 연결 큐 알고리즘 (1) 초기 공백 연결 큐 생성 알고리즘 초기화 : front = rear = NULL isEmpty(LQ) if(front = NULL) then return true; else return false; end isEmpty() (2) 공백 연결 큐 검사 알고리즘 .. 2020. 6. 24.
[자료구조] 큐(Queue) PART.1 1. 개념 데이터를 한쪽에서는 입력, 다른 한쪽에서는 출력하는 방식(First In First Out = FIFO) rear(tail) : 삽입 포인터 front(head) : 삭제 포인터 큐의 단점은 한번 사용한 기억공간은 사용할 수 없다. 이 단점을 원형 큐로 보안 큐의 응용 - 작업 스케줄링, 대기 큐, 스풀 운영에 사용 2. 구조 삽입은 뒤에서 일어난다. 삭제(out) ← A B C D ← 삽입(in) 1 2 3 4 5 front(head) rear(tail) 3. 연산 과정 1) 공백 큐 생성 : createQueue(); 삭제(out) ← ← 삽입(in) -1 1 2 3 4 front = rear "front = rear"라는 것은 공백 상태를 말하고 둘 다 -1에 있으므로 초기 상태를 의미한.. 2020. 6. 23.
[자료구조] 스택 응용 1. 역순 문자열 만들기 스택의 후입선출(LIFO) 성질을 이용 문자열을 순서대로 스택에 PUSH 1) 순서 (1) 스택 삽입 String A B C 3 A 삽입 (push A) B 삽입 (push B) C 삽입 (push C) C 2 B B 1 A A A Empty Full (2) pop 하여 문자열로 저장 String C B A 3 C C 삭제 (pop c) B 삭제 (pop B) A 삭제 (pop A) 2 B B 1 A A A Full Empty 2) C언어 실습 #include #include #include // int를 스택 element의 자료형으로 정의 typedef struct STACKNODE {// 스택의 노드 구조 정의 char data;// 문자형 타입 데이터(데이터 필드) str.. 2020. 6. 23.
[자료구조] 스택(Stack) 1. 스택의 개념 스택(Stack)의 구조란 쌓인 접시에 가장 먼저 놓은 것은 제일 아래 있는 접시다. 그러나 사용하려고 접시를 집는다면 제일 위에 있는 접시부터 사용하게 된다. 이처럼 들어온 순서와 정반대로 서비스를 받는 것이 스택의 개념이다. 2. 스택의 특징 데이터의 삽입과 삭제가 한곳에서 이루어지는 방식(Last In First Out = LIFO) - Top : 가장 최근에 삽입된 자료 - Bottom : 스택의 밑바닥 - 삽입 : Push - 삭제 : Pop 다중 스택 - 하나의 기억공간에 여러 개의 스택으로 운영하는 형태로 overflow의 발생방지를 위해 사용 스택의 응용 - 서브루틴호출, 순환 프로그램, 인터럽트 처리, 수식표기, 0-주소, 컴파일러 등 3. 스택의 구조 3 C top 2.. 2020. 6. 22.
[자료구조] 이중 연결 리스트(Doubly linked list) 1. 이중 연결 리스트 특징 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트 2. 이중 연결 리스트 구조 두 개의 링크 필드와 한 개의 데이터 필드로 구성 llink(Left link) 필드 : 왼쪽 노드와 연결하는 포인터 rlink(Right link) 필드 : 오른쪽 노드와 연결하는 포인터 1) C언어 구조체 - C언어 구조체로 본 이중 연결 리스트의 기본구조 struct Dnode{ struct Dnode *llink; int data; struct Dnode *rlink; }; 2) 이중 연결리스트의 구조 head llink Data rlink llink Data rlink llink Data rlink → NULL 10 → ← 20 → ← 30 NULL node1 node2 node3 3).. 2020. 6. 22.
[자료구조] 원형 연결 리스트(Circular linked list) 1. 원형 연결 리스트(Circular linked list) 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트 단순 연결 리스트의 마지막 노드의 링크 필드에 첫 번째 노드의 주소를 저장하여 구성 링크를 따라 계속 순회하면서 이전 노드에 접근 가능 2. 원형 연결 리스트 구조 head Datd Link Datd Link Datd Link → 10 → 20 → 30 ↓ curr ↑ ← node1 node2 node3 원형 연결리스트 구조를 보게 되면 head와 curr은 첫 번째 노드를 가리킨다. 각 노드는 뒤에 있는 노드를 가리킨다. 단순 연결리스트에서 마지막 노드에는 NULL이 들어가지만, 원형 연결리스트에서 마지막 노드의 Link는 .. 2020. 6. 22.
[자료구조] 연결리스트 PART.2 1. 연결리스트로 나타낸 구조에서 삭제하기(중간노드) 연결리스트 PART.1에서 삽입으로 실습했던 구조를 가지고 삭제 실습한다. Data Link Data Link Data Link Data Link Data Link -> 10 -> 20 -> 30 -> 40 NULL head node1 node2 node3 node4 이 구조에서 node3을 삭제한다. 1) 순서 삭제할 노드의 앞 노드(선행자)를 찾는다. 앞 노드의 링크 필드에 사제할 노드의 링크 필드 값을 저장한다. 2. C언어 실습 1) 노드 생성 위 구조의 노드를 생성한다. #include #include typedef struct NODE { int data; struct NODE *link; } NODE; int main() { NODE *h.. 2020. 6. 21.

티스토리툴바