재민

Graph는 연결되어 있는 원소들 사이의 다대다 관계를 표현하는 비선형 자료구조로서, 버스노선도나 지하철 노선도와 같이 여러 원소들이 맞물려 있는 경우에 사용하는 자료구조형이다. 그래프는 두개의 집합 V와 간선 E로 구성되어 있다. 표기는 G = (V,E)로 한다. 그래프는 무방향 그래프와 방향그래프, 부분그래프, 가중 그래프로 나눌 수 있다. 무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프로서, 간선을 나타내는 쌍에 순서가 없다. 즉 간선을 통해서 양방향으로 갈 수 있는 그래프이다. 방향 그래프는 모든 간선이 방향을 가지는 그래프로서, 방향은 정점의 쌍 의 정점의 순서로 표시한다. 간선을 통해서 한 쪽 방향으로만 갈 수 있다. 부분그래프는 원래의 그래프에서 정점이나 간선을 일부만 제외하여..

Tree는, 하나 이상의 노드로 이루어진 유한집합으로서, 하나의 루트 노드와 분리 집합으로 분할된 다른 노드들의 집합이다. 앞서 다루었던 다른 자료구조와 달리(stack,queue,linkedlist) 원소들 간에 1:n 관계를 가지는 비선형 자료구조이며, 원소들 간에 계층 관계를 가지는 계층형 자료구조이다. [Tree의 주요 용어 및 개념] node: 트리의 구성 요소 서브트리: 하나의 노드와 그 노드들의 자손으로 이루어진 트리 노드의 차수: 노드의 서브트리 개수 루트 노드: 부모가 없는 노드(최상위 노드) 단말 노드: 자식이 없는 노드, 차수 0 형제 노드: 부모가 같은 자식들 트리의 차수: max{노드의 차수} 노드 레벨: 트리의 각 층의 번호 트리의 높이: max{노드 레벨} 조상: 루트까지의 경..

연결리스트를 이용하여 큐를 구현하는 예제이다. Node class와 Queue class를 이용하여 queue를 구현하였다. class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.front = None self.rear = None def is_empty(self): return self.front is None def enqueue(self, data): new_node = Node(data) if self.is_empty(): self.front = self.rear = new_node else: self.rear.next = new_node self.rear..

스택을 구현하기 위해 배열을 사용할 경우, 일차원 배열 stack[MAX_STACK_SIZE] 를 사용한다. 스택의 변수 top은 가장 최근에 삽입된 요소를 가리키는 변수로, 초기값을 -1로 세팅한다(공백 스택을 의미) 스택에서 가장 먼저 삽입된 요소는 stack[0]에, 가장 최근에 삽입된 요소는 stack[top]에 저장된다 (스택의 개념) [c코드로 스택 구현] #include #define MAX_STACK_SIZE 100 typedef struct { int stack[MAX_STACK_SIZE]; int top; } Stack; // 스택 초기화 void initializeStack(Stack *s) { s->top = -1; // 초기값으로 -1을 설정하여 공백 스택을 나타냄 } // 스택이..

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있어서, 양방향으로 탐색이 가능하며, 삭제 시 양쪽의 연결을 수정해야 한다. Doublely Linked List에서 노드의 삭제는 다음과 같은 순서로 이루어진다. 1) 삭제할 노드의 오른쪽 노드와 왼쪽 노드를 탐색한다. 2) 삭제할 노드의 오른쪽 주소를 삭제할 노드의 왼쪽 노드의 rlink에 저장한다. 3) 삭제할 노드의 왼쪽 노드 주소를 삭제할 노드의 오른쪽 노드의 llink에 저장한다. 4) 삭제할 노드를 삭제한다. [코드로 구현하기] #include #include // 이중 연결 리스트의 노드 구조체 정의 struct Node { int data; struct Node* llink; // 왼쪽 노드를 가리키는 포인터..

Doubly Linked List는 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트이다. linked list에서와 마찬가지로 중간노드, 첫번째 노드, 마지막 노드 삽입을 나누어서 보도록 하겠다. https://imsunbow.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Linked-List-%EC%82%BD%EC%9E%85%EC%A4%91%EA%B0%84-%EB%85%B8%EB%93%9C-%EC%B2%AB%EB%B2%88%EC%A7%B8-%EB%85%B8%EB%93%9C%EB%A7%88%EC%A7%80%EB%A7%89-%EB%85%B8%EB%93%9C%EB%A1%9C-%EC%82%BD%EC%9E%85 [같이 보면 좋은 자료: linked lis..

Linked List에서 삭제는 다음과 같은 순서로 이루어진다. 1) 삭제할 노드의 앞 노드를 찾는다. 앞 노드를 찾는 이유는 크게 두가지인데, 연결관계를 해제하기 위해서이자 노드를 효율적으로 찾아 해제시키는 방법이기 때문이다. 2) 앞 노드의 링크필드에 삭제할 노드의 링크 필드값을 저장한다. 3) 삭제할 노드를 삭제하고, 메모리를 해제한다. 삭제 연산을 c로 구현하면 다음과 같다. #include #include // 단일 연결 리스트의 노드 정의 struct Node { int data; struct Node* next; }; // 연결 리스트의 헤드를 전역 변수로 선언 struct Node* head = NULL; // 연결 리스트에 노드 추가 void insertNode(int val) { str..

연결 리스트에서 삽입은 어느 위치에 노드를 삽입하느냐에 따라 다르다. [중간 노드 삽입] 1. 삽입할 노드를 준비한다 2. 새 노드의 데이터 필드에 값을 저장한다. 3. 새 노드의 링크값을 지정한다. 이 때 링크값은 삽입할 위치 앞 노드의 링크값이 된다. 4. 삽입할 위치 앞 노드에 새 노드를 연결한다. [첫번째 노드 삽입] 1. 삽입할 노드를 준비한다. 2. 새 노드의 데이터 필드에 값을 저장한다. 3. 새 노드의 링크값을 지정한다. 이 때 링크값은 head가 가리키고 있는 노드의 주소값이 된다. 4. head에 새 노드를 연결한다. [마지막 노드로 삽입] 1. 삽입할 노드를 준비한다. 2. 새 노드의 데이터 필드에 값을 저장한다. 3. 새 노드가 마지막 노드이므로 링크값으로 NULL을 지정한다. 4...

리스트는 자료를 구조화하는 가장 기본적인 방법으로서, 값들을 나열한다. 리스트에서는 새로운 항목을 리스트의 처음, 중간,끝에 삽입하여 저장할 수 있다. 그리고 리스트의 특정 부분을 추출하거나 특정 값을 삽입 혹은 삭제할 수 있다. 리스트는 구현이 간단하지만 삽입 삭제시 오버헤드가 발생할 가능성이 있는 Linear List와, 삽입 삭제가 효율적이지만 구현이 복잡한 Linked List로 나뉜다. Linked List에서 한 원소가 삽입되면, 그 이후의 원소들은 한 자리씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시켜야만 한다. 삽입을 위해서는 먼저 원소를 삽입할 빈 자리를 만들어서, 빈 자리에 원소를 삽입한다. (빈 자리를 만들기 위해 기존의 원소들은 한칸씩 뒤로 이동시킨다) 즉 n+1개의 ..

[알고리즘 소개] 1) 이진탐색 알고리즘에서는 배열 인덱스의 시작과 끝을 각각 0과 마지막 값으로 둔다. 그리고 0과 마지막 값을 더한 값을 2로 나눈 결과값을 인덱스값으로 하여, 인덱스 값이 target값보다 큰지 작은지를 판단한다. 2) 1의 결과를 토대로 target값보다 크다면 오른쪽을, target값보다 작다면 왼쪽 절반을 취한다. 이를 반복한다. 3) 순차 탐색하는 것 보다 좋은 성능임을 확인한다.(순차 탐색보다 탐색량이 줄음) [구현] int Bsearch(int arr[],int len, int target) { int first = 0; int last = len - 1; int mid; while(first