포도가게의 개발일지

Tree란? - 노드들이 나무 가지처럼 연결된 비선형(acyclic) 계층적 자료구조이다. - 트리는 트리 내에 다른 하위 트리(sub tree)가 있고 하위 트리 안에 또 다른 하위트리가 있는 재귀적 자료구도이다. 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다. 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다. 내부 노드(internal): 단말 노드가 아닌 노드 간선(edge): 노드를 연결하는 선, link, branch라고도 부른다. - 간선은 정점의 개수 -1개를 가진다. (노드 5개면 간선 4개) 형제(sibling): 같은 부모를 가진 노드 노드의 크기(size): 자신을 포함한 모든 자식 노드의 수 노..

G = (V,E) G = graph, V = vertex(점), E = edge(선) 그래프란? - 정점과 간선으로 이루어진 자료 구조 그래프의 표현법 1. G의 인접행렬 - 메모리 사용량 O(V^2) - 한정점에 연결된 간선을 모두 순회할 때, 항상 O(V)의 사간을 사용 - 정점에 비해 간선이 몇 개 없는 그래프에서 비효율적으로 작동 - 메모리 사용량이 많음, 작은 메모리의 유리 2. 인접리스트 - 메모리 사용량 O(V+E) - 메모리 사용량이 적으며, 희소 그래프를 표현하는 데 유리 - 한 정점에서 시작하는 간선을 모두 순회할 때, 연결된 정점의 개수만큼의 시간을 소요

Queue 자료구조? - 큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.head = None self.tail = None def enqueue(self, data): new_node = Node(data) if self.isEmpty(): self.tail = new_node self.head = new_node else: self.tail.next = new_node self.tail..

자료구조 Stack - 스택이란 한쪽 끝에서만 자료를 넣고 뺄 수 있는 선형구조(LIFO 특징)로 된 자료구조입니다. - 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다 S.top(): 스택의 가장 윗 데이터를 반환한다. 만약 스택이 비었다면 이 연산은 정의불가 상태이다. S.pop(): 스택의 가장 윗 데이터를 삭제한다. 스택이 비었다면 연산 정의불가 상태. S.push(): 스택의 가장 윗 데이터로 top이 가리키는 자리 위에(top = top + 1) 메모리를 생성, 데이터 x를 넣는다. S.empty(): 스택이 비었다면 1을 반환하고,그렇지 않다면 0을 반환한다. class Node: def __init__(self, data): s..

균형을 이루기 위한 red black tree의 특징 (1) 노드는 레드 혹은 블랙 색상 중 하나를 갖는다. (2) 루트 노드는 블랙이다. (3) 모든 리프 노드(또는 NIL 노드)들은 블랙이다. (4) 레드 노드의 자식 노드들은 모두 블랙이다. (레드 노드는 연달아 나타날 수 없고, 블랙 노드만 레드 노드의 부모가 될 수 있다.) (5) 각 노드로부터 해당 노드가 속한 하위 리프 노드까지의 단순 경로 상에는 블랙 노드 개수가 동일하다. (Black Height) 삭제(Removal) - 이진 탐색 트리에서 두 개의 자식 노드를 가진 노드를 지울 때, 우리는 노드의 왼쪽 서브트리에서 최댓값을 찾거나, 오른쪽 서브트리에서 최솟값을 찾아 해당 값을 지우고자 하는 노드로 옮긴다. 이 때, 최댓값 또는 최솟값에..

레드-블랙 트리란? - BST 이진탐색 트리에서 파생된? 근사적 Balanced binary search tree - 때문에 일반 BST는 최악의 경우 트리의 깊이만큼 탐색시간이 걸리지만 - balanced tree는 최악의 경우여도 lonN의 시간이 걸리게 된다. 균형을 이루기 위한 red black tree의 특징 (1) 노드는 레드 혹은 블랙 색상 중 하나를 갖는다. (2) 루트 노드는 블랙이다. (3) 모든 리프 노드(또는 NIL 노드)들은 블랙이다. (4) 레드 노드의 자식 노드들은 모두 블랙이다. (레드 노드는 연달아 나타날 수 없고, 블랙 노드만 레드 노드의 부모가 될 수 있다.) (5) 각 노드로부터 해당 노드가 속한 하위 리프 노드까지의 단순 경로 상에는 블랙 노드 개수가 동일하다. (B..

#include #include typedef struct Node{ int data; struct Node *next; }Node; typedef struct Info{ int count; struct Node *head; struct Node *tail; }Info; void rearadd1(Info *data, int value); void rearadd2(Node *head , int value); void finding(Node *head, int target); void delete(Node *head, int target); void insert(Node *head, int index, int value); void add_first(Node *head, int value); int main..

다익스트라 알고리즘 : 탐욕법 - 단일 정점에서 모든 다른 정점으로의 최단 경로 구하기 - 최소비용 신장트리 mst의 프림 알고리즘과 유사 - 차이점은 프림 알고리즘은 V-Y집합과 인접한 노드를 넣어준다면 다익스트라는 출발점 v1과 가장 Y의집합을 touch하고 가장 인접한 노드를 넣어준다. 종료 조건문은 if Y == V: 같으면 탐색을 완료했다고 표현 옆에 그림의 경로는 F = {} v1 -> v5 , 1 (v1->)v5 -> v4 , 2 v1 -> v3, 4 (v1->v5->)v4 -> v2, 5 정보가 저장된다.  표를 보면 알 수 있듯이 v1 -> v5로의 경로가 입력되면서 5번은 -1로 방문체크가 완료되며 v1 -> v4로 갈수있는 비용이 6 -> 2로 바뀌게 된다 이건 v1->v5->v4로..