본문 바로가기

Language/C18

[자료구조] 그래프 구현 1. 그래프 구현 방법 인접 행렬(adjacent matrix) : 2차원 배열 사용 인접 리스트(adjacency list) : 연결리스트 사용 1) 인접 행렬 방법 if(간선 (i, j)가 그래프에 존재) M[i][j] = 1. 존재하지 않으면 M[i][j] = 0 2. 인접 행렬 행렬에 대한 2차원 배열을 사용하는 순차 자료구조 방법 그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장 n개의 정점을 가진 그래프 : n * n 정방 행렬 행렬의 행 번호와 열 번호 : 그래프의 정점 행렬값 : 두 정점이 인접되어 있으면 1, 인접되어있지 않으면 0 1) 인접 행렬 예 2) 무방향 그래프 행 i의 합 = 열 i의 합 = 정점 i의 차수 3) 방향 그래프 행 i의 합 = 정점 i의 진출 차수(Out) 열.. 2020. 6. 28.
[자료구조] 그래프 1. 정의 그래프 G는 정점 V(Vertex)와 간선 E(Edge)로 구성되며 G = (V, E)로 표시된다 V는 정점(Vertices)들의 집합이다. E는 간선(Edge)들의 집합이다. 정점과 간선은 모두 관련되는 데이터를 가질 수 있다. 트리는 사이클이 없는 그래프의 한 종류이다. 1) 그래프 종류 G1과 G2는 무방향 그래프다. G2는 Tree다. G3은 방향성 그래프다. 2. 무방향 그래프(Undirected Graph) 두 정점을 연결하는 간선의 방향이 없는 그래프 정점 Vi와 정점 Vj를 연결하는 간선을 (Vi, Vj)로 표현 (Vi, Vj)와 (Vj, Vi)는 같은 간선을 나타낸다. V(G1) = {A, B, C, D} E(G1) = {(A, B), (A, D), (B, C), (B, D),.. 2020. 6. 27.
[자료구조] 힙(Heap) 1. 개념 완전 이진 트리에 있는 노드 중에서 킷값이 가장 큰 노드나 킷값이 가장 작은 노드를 찾기 위해서 만든 자료구조 힙은 완전 이진 트리이므로 배열로 표현 가능 힙(Heap)이란 완전 이진 트리로써 각 노드의 값은 자신의 자식 노드의 값보다 크거나 같다. 따라서 힙은 언제나 루트의 값이 최댓값이 된다. 힙에서 최댓값을 삭제하게 되면 힙의 마지막(배열 마지막 인덱스) 원소를 삭제된 위치인 루트에 넣고 힙을 하나 줄인 뒤 힙이 되도록 자식들과 크기를 비교하며 필요한 값을 서로 교환한다. 힙 정렬은 힙을 활용하여 정렬하는 방식이다. 1) 최대 힙(Max Heap) 킷값이 가장 큰 노드를 찾기 위한 완전 이진 트리 {부모 노드의 킷값 ≥ 자식 노드의 킷값} 루트 노드 : 킷값이 가장 큰 노드 2) 최소 힙.. 2020. 6. 27.
[자료구조] 이진 탐색 트리 (Binary Search Tree) 1. 이진 탐색 트리(Binary Search Tree) 이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조 1) 정의 모든 원소는 서로 다른 유일한 키를 가진다. 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다. 오른쪽 서브 트리에 있는 원소들의 키들은 그 루트의 키보다 크다. 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리다. 2. 탐색 연산 루트에서 시작 탐색할 킷값 x를 루트 노드의 킷값과 비교 킷값 x = 루트 노드의 킷값인 경우 - 원하는 원소를 찾았으므로 탐색 연산 성공 킷값 x 루트 노드의 킷값인 경우 - 루트 노드의 오른쪽 서브 트리에 대해서 탐색 연산 수행 - 서브 .. 2020. 6. 26.
[자료구조] 이진트리의 순회 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.

티스토리툴바