방향 그래프 (간선에 방향이 있는 그래프)사이클이 없는 방향그래프DAG가 갖는 가장 큰 특징은 Topological Order(위상 순서)가 있다는 것이다.나와 간선으로 연결되지 않은 정점인 경우, 나보다 순서가 먼저 나와도 상관X나에게서 다음 정점으로 가는 간선이 있

시작 정점으로부터 가까운 정점을 먼저 방문하고 떨어져있는 정점을 나중에 방문깊게 탐색하기 전에 넓게 탐색방문한 노드들을 차례대로 저장할 수 있는 큐(Queue) 를 사용초기화 작업은 DFS와 동일그래프 G의 모든 vertex와 edges 들에 대해 setLabel()

그래프 G(V, E) 에 대해 S(V', E') 가 그래프이면서 V' ⊂ V 와 E' ⊂ E 를만족할 때, S 를 G 의 부분 그래프라고 한다.subgraph 중 기존 그래프 G의 모든 정점을 포함하는 그래프=> V' = V(단, 기존 그래프 G의 모든 정점을 가지되

지난 포스팅에 이어 빅오 표기법을 계속해서 알아보겠습니다.

unsorted list 로 PQ 를 구현삽입(insert) : O(1)탐색(min) : O(n)삭제(removeMin) : O(n)sorted list 로 PQ 를 구현삽입(insert) : O(n)탐색(min) : O(1)삭제(removeMin) : O(1)Sele

그래프 구현 방법은 3가지가 있다.간선 리스트(Edge List structure)인접 리스트(Adjacency List structure)인접 행렬(Adjacency Matrix structure)그래프의 구성은 정점과 간선이지만, 우리가 실제로 그래프라고 인식하는

지난내용복습해싱의 기대수행시간 : O(1) / 사용공간 : O(n)load factor α = 2/3 만 되더라도 성능 좋아짐=> 담겨있는 데이터수보다 배열의 크기가 1.5 배 정도 크면 된다.=> 평균 연산횟수가 1 - (1 - 2/3) = 3이 된다.탐색, 삽입,

해싱을 linear probing 으로 구현했을때 insert 연산은 지난시간에 살펴봤다. 이번엔 find 연산을 살펴보자.k 에 해시함수를 적용해 hash value 값인 h(k)로 바꿔준다.k에 해당하는 key 를 찾거나,못 찾은채로 비어있는 인덱스를 발견하거나,(

지난내용 복습딕셔너리 구현 방법BST : 탐색, 삽입, 삭제연산 모두 최악의 경우 O(n)AVL Tree : 탐색, 삽입, 삭제연산 모두 최악의 경우 O(log n)Log file : 삽입은 O(1), 탐색과 삽입은 O(n) - 링크드리스트로 구현Search Tabl

entry 를 저장데이터가 들어가고 나가는 문이 존재하지 않음데이터 순서에 대한 조건 없음.임의의 key를 이용해 탐색이 가능하다동일한 key 를 중복 저장 가능 ( But, 보통은 key 값이 유일함 )앞서 배운 BST, AVL 트리도 딕셔너리를 구현하는 방법중 하나

서브트리의 높이를 적절히 제어해, 전체 트리가 어느 한쪽으로 늘어지지 않는 균형 BST 의 일종인 AVL 트리에 대해 알아봅시다.

모든 데이터가 internal 노드에 저장되는 이진트리인 BST 에 대해 알아봅시다.

우선순위 큐와 관련한 정렬 알고리즘(PQ Sort) 과, 배열을 활용한 구현방법인 Bottom-up Heap Construction 에 대해 알아봅시다.

자료구조 힙(Heap) 과 구현방법에 대해 알아봅시다.

우선순위가 있는 Queue 인 우선순위 큐에 대해 알아봅시다. 그리고 이를 활용한 대표적인 정렬 알고리즘인 선택정렬(Selection Sort) 과 삽입정렬(Insertion Sort) 에 대해 알아봅시다.

트리의 핵심적인 연산들을 pseudocode 로 표현해봅시다.

트리로 Arithmetic Expression (수식표현) 을 하는방법, 오일러 투어(Euler Tour), 그리고 일반트리를 이진트리로 변환하는 방법에 대해 알아봅시다.

bool empty()void append(int data)예외: if(empty())tail의 다음에다 append한다void insertion(int idx)예외 : if(idx == 0), if(idx == listSize), if(idx < 0 || idx

이진트리와 그를 구현하는 방법인 linked Structure 에 대해 알아봅시다.

트리의 기초적인 이론들과 3가지 순회방식 중 2가지 (preOrder, postOrder) 에 대해 알아봅시다.