Graph (그래프) 그래프란 정점과 간선으로 구성된 자료구조이다. 일반적으로 G = (V,E)로 나타내는데, V는 vertices로 정점을 말하고, E는 edges인 간선을 의미한다. |V|는 정점의 개수를 의미하고 |E|는 간선의 개수를 의미한다. 그래프는 간선의 종류에 따라 2가지로 구분할 수 있다. 그리고 그 종류에서도 그래프의 특징으로 종...

Binary Search Tree (이진 탐색 트리) 이진 탐색 트리는 앞서서 배운 트리의 확장적인 형태라고 보면 편하다. 일반적인 이진 트리는 탐색의 기준이 없어서 특정 데이터를 찾으려면 모든 노드를 탐색해야한다. 하지만 이진 탐색 트리에서는 평균적으로 훨씬 빠른 시간에 탐색이 가능해진다. Binary Search (이진 탐색) 우선 이진 탐색...

Dictionary (딕셔너리) 딕셔너리는 사실 C++보다는 파이썬에서 더 익숙할 것이라 생각된다. 실제로 딕셔너리라고 아예 명확하게 말을 하기도 하니까… 자료구조에서 딕셔너리는 key와 value를 함께 저장하는 entry 저장 자료구조이다. 대신 key의 중복을 허용한다. 시간 복잡도 딕셔너리의 시간복잡도는 딕셔너리를 리스트 구현을 기준으로 ...

Priority Queue (우선순위 큐) 이전에 큐에 대해서 배운 적이 있다. 이렇게 일반적인 큐를 FIFO Queue라고 한다. FIFO원리를 갖고 있는 큐이기 때문이다. 이번 시간에는 다른 성질을 갖는 우선순위 큐에 대해서 이야기해보겠다. 우선순위 큐는 이름에 특징이 잘 나와있는데, 큐의 pop 연산수행을 진행할 때, 프로그래머가 정해놓은 우...

Binary Tree (이진 트리) 이진트리 개념 이진트리는 우리가 이전에 배운 트리의 특수한 형태이다. 일반 트리가 자식 수에 제한이 없다면, 이진트리는 1부모에 최대 2개의 자식 노드가 존재한다. 보통 왼쪽 노드, 오른쪽 노드라고 부르며 왼쪽 노드가 오른쪽 노드보다 우선하는 성질을 가진다. 일반 트리에서 설명하지 않았지만 트리는 자식간에 순서가...

Tree (트리) 트리 개념 트리는 non linear data structure이다. 앞서서 배운 리스트, 배열, 벡터는 모두 linear data structure이고 이런 선형 자료구조들은 원소들 간에 전/후 관계가 있다. 그러나 non linearr data structure, 즉 비선형 자료구조는 원소들 간에 상/하 관계를 가지고 있다. ...

Vector (벡터) 벡터 개념 벡터는 크기가 동적으로 변하는 배열이라고 생각하면 된다. Array list라고 부르기도 하며 다양한 데이터들이 배열의 형태로 저장된 연속체라고 생각하면 된다. 삽입, 삭제, 접근 연산이 모두 index에의해 이뤄지게 된다. Vector ADT 벡터의 추상자료형은 다음과 같다. at(integer i) : i...

Queue (큐) 큐 개념 큐의 삽입과 삭제의 원리는 First-In First-Out(FIFO, 선입선출)로 작동한다. 가장 먼저 들어온 데이터가 가장 먼저 나가게된다. 큐의 실제 활용 예시는 다음과 같다. 대기열 공유자원의 접근권한, 순서 멀티 프로그래밍 과정 Queue ADT 큐의 추상자료형은 다음과 같다. enqueue(o...

Abstract Data Types (추상 자료형) 추상 자료형 (ADTs)는 한마디로 말하면 알고리즘의 요약본이다. ADT는 correctness와 performance를 독립적으로 생각하게 해줄 수 있다. Correctness는 일반적으로 interface라고도 하는데, input이 들어왔을 때, output의 일치 정확도가 얼마나 높은 가를 말한...

Algorithm Analysis (알고리즘 분석) Asymtotic Analysis (점근적 분석) 알고리즘을 비교, 분석할 때는 일반적으로 점근적 분석방법을 따른다. 점근적 분석방법은 아래의 과정들로 진행된다. 의사코드 (pseudo code) 연산자 개수 카운트 (primitive operation counting) input s...