Sean :: Dev

Graph (그래프) Traversal / Search (순회,탐색) DFS(Depth First Search) 깊이우선탐색 BFS(Breadth First Search) 너비우선탐색 Spanning Tree (신장트리) DFST(Depth First Spanning Tree) 깊이우선 신장트리 BFST(Breadth First Spanning Tree) 너비우선 신장트리 MST,MCST(Minimum_Cost Spanning Tree) 최소_비용 신장트리 : Kruskal, Prim 's Alg Distance (최단거리 등) Dijkstra 's Alg Floyd-Warshall 's Alg Bellman-Ford 's Alg Etc Network Flow Bipartit..

Binary Search Tree (이진 탐색 트리) def 모든 원소는 서로다른 유일한 값. 왼쪽 subtree의 값은 그 root보다 작다. 오른쪽 subtree의 값은 그 root보다 크다. 왼/오른쪽 subtree도 Binary Search Tree이다. 탐색/삽입/삭제 중 삭제연산이 번거롭다. 노드를 삭제한 후에도 BST를 유지해야하므로 후속조치가 필요하다. 삭제할 노드가 1. degree=0(leaf node)인지 2. degree=1인지 3. degree=2인지에 따라 달라짐. Segment Tree 구간의 정보를 빠르게 구할수있는, Complete Binary Tree 형태의 자료구조 Example) 구간 최소값을 구하는 Segment Tree 구하려는 데이터 배열을 완전이진트리의 최하단에..

Heap (힙) Max Heap / Min Heap Parent Node가 Child Node보다 항상 크거나(작거나) 같은 Complete Binary Tree (완전이진트리) (자식노드끼리는 상관없음) (항상 root가 max/min이므로 최대-최소값을 찾기 편하다) 시간 복잡도 : O(logn) (힙의 삽입-삭제는 최악의 경우, 최하단노드~최상단노드까지 swap이 필요하다) 삽입&삭제 시에도 '완전이진트리'형태를 유지해야한다. 삽입 : 마지막 노드의 다음자리를 확장하고 임시로 저장후, 부모노드와 비교해가며 swap한다. 삭제 : 항상 root를 삭제해 반환한다. 마지막 노드를 root자리에 임시로 저장후 삭제하고, root에 있는 값을 자식들과 비교해가며 적당한 자리까지 swap한다...

Tree 용어 : Root, Child, Parent, Siblings, Leaf=Terminal, Branch=Internal, Degree, Height, Level => 모든 노드의 Degree(차수)가 2이하 Binary Tree 구현 순차 자료구조 (ex. 배열) Node (of Node i)IndexConditionParentfloor( i/2 )i > 1Left Child2i2i ≤ nRight Child2i+1(2i+1) ≤ nRoot10 < n 연결 자료구조 (ex. 하단 코드) class TreeNode { Object data; TreeNode left; TreeNode right; }Traversal (순회) : Pre-order, In-order, Post-order D L R (..

Hash (해시) Input Output 첫 줄에 명령어의 개수 N이 주어집니다. (1 ≤ V ≤ 100,000) 두번째 줄부터 N개의 줄에 걸쳐 아래와 같은 형태로 명령어가 주어집니다. 1 s: 입력받은 문자열 s를 set에 추가합니다. 이미 set에 존재한다면 추가하지 않습니다. 2 s: 입력받은 문자열 s를 set에서 제거합니다. 존재하지 않는다면 아무 동작도 하지 않습니다. 3 s: 입력받은 문자열 s가 set에 있다면 1을, 없다면 0을 출력합니다. 각 명령어에 알맞은 결과를 한줄씩 출력합니다. import java.util.*; public class Test { public static void main(String args[]) { Scanner sc = new Scanner(System...

Stack (스택) LIFO (Last In First Out) push, pop(반환,제거), peek(반환), search ... 배열 or 연결리스트를 이용한 구현 > 자바는 기본 라이브러리로 스택 제공 이용) 역순 문자열 만들기, 시스템 스택(함수 호출,복귀 관리), 수식의 괄호검사, 수식의 후위표기법 등 .. InputOutput첫 줄에 명령어의 개수 N이 주어집니다. (1 ≤ N ≤ 1,000,000)두번째 줄부터 N개의 줄에 걸쳐 아래의 명령어가 입력됩니다.push x : x를 스택에 삽입합니다.pop : 가장 마지막에 들어온 인자를 반환합니다.size : 큐의 크기를 출력합니다.top : 큐의 맨 앞 인자 값을 출력합니다.각 명령 순서에 따라 값을 출력합니다. import java.util..

데이터 표현방식 순차 자료구조 선형 리스트 (Linear/Ordered List) 연결 자료구조 단순 연결리스트 (Linear/Singly Linked List) 원형 연결리스트 (Circular Linked List) 이중 연결리스트 (Doubly Linked List) 이중 원형 연결리스트 (Doubly Circular Linked List) => 그리고 이 자료구조들을 활용한 표현 (다행식, 행렬 등...) Linked List (연결 리스트) 랜덤접근이 가능한 배열과 다른, 순차적 자료구조. 저장할 값과 다음 노트를 가리키는 포인터로 이뤄진 '노드'로 구성. Linked List Doubly Linked List Circular Linked List 배열 vs 리스트 배열 리스트 index로 무작..