Finn의 개발블로그

1. Graph- 정점과 간선의 집합 2. Graph 의 종류- Undirected Graph - 정점과 간선의 연결관계에 있어서 방향성이 없는 그래프- - Directed Graph - 간선에 방향성이 포함되어 있는 그래프- 3. Degree- Undirected Graph - 각 정점에 연결된 에지의 개수를 Degree라 한다- Directed Graph- 각 정점으로 나가는 간선의 개수를 Qutdegree라 하고 들어오는 간선의 개수를 Indegree라 한다. 4. 가중치 그래프와 부분 그래프- 가중치 그래프- 간선에 가중치 정보를 두어서 구성한 그래프를 - 비가중치 그래프- 모든 간선의 가중치가 동일한 그래프 - 부분 그래프 - 본래의 그래프의 일부 정정 및 간선으로 이루어진 그래프 5. 그래프 ..

1. Hash - hash 는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 속도가 빠름- 특정한 값을 Search할때 데이터 고유의 index로 접근 하기에 평균의 시간 복잡도가 Big-O(1)된다- Collision 때문에 항상 Big-O(1)은 아니다 - 특별한 알고리즘(hash function)을 이용하여 저장할 데이터와 연관된 고유한 숫자를 만들어 데이터의 index에 사용한다 - 특정 데이터의 인덱스는 고유한 위치라서, 삽입 연산 시 다른 데이터의 사이에 끼어들거나, 삭제 연산 시 다른 데이터로 채울 필요가 없기 때문에 추가적인 비용이 들지 않는 자료구조이다 2. Hash function- hash function에 의해 반환된 데이터의 고유의 숫자 값을 hashcode- 어설플 hash..

1. 레드 블랙 트리 - 이진 검색 트리에서 계속해서 높은 값을 넣을경우 트리의 균형이 망가진다 - 최악의경우 Big-O(n)의 시간을 가지게된다- 이러한 일을 방지하기 위해서 rebalance를 해줘야하고 레드 블랙 트리는 rebalance를 해주는 트리 중 하나 이다 2. 레드 블랙 트리 의 조건- 각 노드는 Red or Black 이라는 색깔을 갖는다 - Root Node의 색은 Black이다- null node를 포함한 각 leaf node는 black 이다- 어떠한 노드의 색이 red라면 children의 색은 모두 black이다 = 빨간색 노드는 연속해서 나올 수 없다- root node에서 어떠한 리프 노드 사이에는 똑같은 black 노드의 수를 가진다 3. 레드 블랙 트리 의 삽입- 이진 ..

1. 힙- 배열을 기반한 완전 이진 트리 형태의 자료구조- 최대힙, 최소힙 두가지 종류가 있다- 최대힙은 루트 노드 값이 자식들 보다 큰 힙을 말하고 최소힙은 반대 이다- 최대힙 에서는 루트 노드 값이 가장 크기에 최대 값을 찾는 연산은 Big-O(1) 시간을 가진다- 삽입, 삭제시에 heapify 과정을 거쳐야 해서 Big-O(logn)의 시간을 가진다 2. Max Heap ADT- init(self)- heap을 초기화 한다- insert(self, data)- 힙에 데이터를 부모 노드가 자식 노드 보다 큰 상태로 저장한다- pop(self, data)- 힙의 첫 요소(가장큰) 데이터를 반환하고 heapify 진행한다 - peek(self) - 힙의 가장 큰 데이터를 반환한다. - count(self..

1. 트리- 비선형 자료구조- 계층적 관계를 나타내기 위한 자료구조 2. 트리의 구성 요소- Node - 트리를 구성하는 각각의 요소- Edge- 노드와 노드를 연결하는 선 - Root Node- 트리의 최상위 노드- Leaf Node- 하위에 다른 노드가 연결되어 있지 않은 노드- Internal Node- leaf node를 제외한 모든 노드 3. 이진 트리- 루트 노드를 중심으로 두 개의 서브 트리로 나누어 진다- 서브 트리도 모두 이진 트리여야 한다- 각 층별로 레벨을 정하고, root node의 레벨은 0 또는 1, 최고 레벨을 height(높이) 라고 한다- Full Binary Tree(포화 이진 트리)- 단말 노드를 제외한 모든 노드가 2개의 자식을 갖는 트리- 노드의 개수는 2^n - 1..

1. 큐- 선형자료구조 - 먼저 들어간 것이 먼저 나옴(선입선출) - 은행 고객이나 마트에서 계산을 기다리는 고객에 대한 일의 처리 순서라고 생각하자 2. 큐 ADT- init(self, size)- 큐를 초기화 한다- 큐의 사이즈를 지정한다- enqueue(self, data)- 큐에 데이터를 저장한다- dequeue(self)- 큐의 첫 데이터를 반환 하고 삭제한다.- is_full(self)- 큐가 가득 차 있는지 확인한다- is_empty(self)- 큐가 비어 있는지 확인한다- peek(self)- 큐의 첫 데이터를 반환 한다.- count(self)- 큐에 모든 데이터 수를 반환 한다. class Queue: def __init__(self, size): self.list = [] self.s..

1. Stack- 선형 자료구조- 먼저 들어간 것이 가장 마지막에 나옴(선입후출) 2. Stack ADT- init(self, size) - 스택을 초기화 합니다.- 스택의 크기를 지정합니다.- put(self, data)- 스택에 데이터를 저장합니다- pop(self)- 스택의 제일 위의 데이터를 반환 하고 삭제합니다.- peek(self)- 스택의 제일 위의 데이터를 반환 합니다.- is_full(self)- 스택이 가득 차 있는지 확인합니다 class Stack: def __init__(self, size): self.list = [] self.size = size def put(self, data): if self.is_full(): return False self.list.append(data)..

1. Linked List- 각각의 원소들은 자기 자신의 다음을 알고 있어서 삽입,삭제 시에 Big-O(1) 시간을 소모- 원하는 위치에 삽입을 하려면 Search 과정이 생겨 Big-O(n) 시간을 소모, 삭제도 동일한 시간을 소모- Search, 삽입, 삭제 에도 결국 Big-O(n) 시간을 소모 1-1. Linked List ADT- init(self, sort) - 링크드 리스트 초기화 - sort는 sort 함수 지정- append(self, data)- data값을 node에 전달하여 저장- append_with_sort(self, data)- data값을 오름 차순으로 정렬하며 저장- remove(self, index):- 지정한 인덱스의 데이터를 삭제한다.- search(self, sear..