학교 수업
-
알고리즘 ch6 (2) Red-black tree학교 수업/알고리즘 2020. 6. 14. 20:48
Binary Search Tree- Binary Tree + Binary invariant(왼쪽 subtree는 더 작은 값 , 오른쪽 subtree는 더 큰 값)- 각각의 노드들의 key는 unique하며, 완쪽자식의 key는 부모보다 작으며 오른쪽 자식의 key는 부모보다 큰 값이다.- complexity 평균 최악 Insert O(logn) O(n) Remove O(logn) O(n) Search O(logn) O(n) 사슬모양처럼 긴 모양을 경우 최악의 경우고, balanced 모양일 경우 평균의 경우다. - 중회순회(inorder traversal) 시에 오름차순으로 정렬된 key값을 얻을수 있다. Red Black Tree- Binary search Tree 이면서 Balanced Tree이다..
-
알고리즘 ch 6 array doubling학교 수업/알고리즘 2020. 6. 14. 20:02
Dynamic Sets and Searching Array Doubling - 배열의 크기를 늘려야 할 때 원래 배열의 2배 크기를 할당 받아 원래의 배열에 있던 값들을 옮기는 작업. - 값을 하나 옮길 때 t시간이 덜린다고 하면, size n의 배열에 n+1번째 값이 들어올 때 2n개의 새로운 메모리를 할당 받아 n개의 값들을 옮기고 n+1번째의 원소를 입력해야 한다. 이 작업에는 기존 n개의 원소를 옮길 때 t*n의 시간이 필요할 것이다. 그럼 이 작업을 포함해 이전의 총 이동 시간을 생각해보면 t*n + t*n/2 + t*n/4 + ... = t(n + n/2 + n/4 + 1) 의 시간이 걸렸을 것이며 이는 총 2t*n보다는 적게 걸렸을 것이다. Array doubling이 중요한 이유는 1개의 ..
-
알고리즘 ch7 Graph학교 수업/알고리즘 2020. 6. 13. 23:44
Graph and Graph Traversals Graph- 정점과 간선으로 이루어지며 트리와 달리 계층(부모-자식)이 존재하지 않는 자료구조- 주로 G(V,E)로 표현한다. (V:정점, E:간선)- Directed graph : 간선이 방향이 있는 그래프, Digraph라고도 한다. 정점이 v와 w가 있고, v에서 w로 가는 간선이 있다면 directed edge는 (v,w)로 표현한다. 혹은 v→w , 간단하게 vw라고도 한다.v는 source 또는 start라고 부르고, w는 destination 또는 end라고 부른다.(v,w) ≠ (w,v) : 방향간선이므로 둘은 다르다- Undirected Graph : 간선이 방향이 없는 그래프undirected graph는 자기 자신으로 가는 간선을 정의하..
-
알고리즘 ch 1~2학교 수업/알고리즘 2020. 6. 13. 20:15
알고리즘 - Computer Algorithm 알고리즘이란? 컴퓨터를 이용하여 문제를 해결하는 순서적인 절차를 만들어 놓은 것. - 컴퓨터를 이용하여 문제를 해결하는 6단계1) Problem: 문제 파악, 문제의 input과 output확인2) Strategy: 전략 구성3) Algorithm: 알고리즘 설계Input, output에 따라 step별로 어떻게 할 것인지 설계4) Analysis: 알고리즘 분석 기준: correctness(정확성), time&space(효율성), optimality(최적화된 방법인가)5) Implementation: 수행6) Verification: 확인 - Analysis of the Algorithm 알고리즘 분석방법1. 실험적 방식 : 실제 해당 알고리즘을 기계에서 ..
-
유닉스란학교 수업/유닉스 2020. 5. 23. 20:37
UNIX(유닉스)- 미국 벨(Bell) 연구소에서 개발된 운영체제로, 프로그램 대부분이 C언어로 수정되면서 이식성이 높아지고 동시 다중 사용자 및 다중작업의 실행을 지원할 수 있는 대화형 소프트웨어이다. 주로 서버용 컴퓨터에서 사용되는 운영체제 ð 포털이나 대기업의 서버에 사용되며 보안성이 매우 뛰어남 - 특징1. 시분할 시스템(Time Sharing System)을 위해 설계된 대화식 운영체제 à shell 이용2. 대부분 C언어로 작성되어 있어 이식성이 높으며 장치, 프로세스 간의 호환성이 높다.3. 다중 사용자(Multi-user), 다중 작업(Multi-Tasking)을 지원4. 많은 네트워킹 기능을 제공하므로 통신망 관리용 운영체제로 적합 5. 트리구조의 파일 시스템을 가진다 - UNIX 시스템..
-
자료구조 2학교 수업/자료구조 2020. 5. 17. 16:50
저번 포스팅에 이어 자료구조에 대한 설명을 하겠다. 8. heap - 최대값, 최소값을 찾아내는 연산을 쉽게 하기 위해 고안된 자료구조 - 각 node가 (key, element)로 구성 - Heap-Order와 (Almost) Complete Binary Tree조건을 만족하는 binary tree이다. * heap-order: 모든 노드에 대해 각 노드의 키값이 자식 노드의 키값보다 작지 않거나(max heap, 이때 root의 키값이 가장 크다) 자식노드의 키값보다 크지않은(min heap, root의 키값이 가장 작다)을 만족해야 한다. * last node: heap의 maximum깊이의 가장 오른쪽 노드를 의미 - heap의 연산들 (min-heap기준으로 설명) 1) 삽입 연산(insert(..
-
자료구조 1학교 수업/자료구조 2020. 5. 15. 11:45
자료구조에서 배웠던, 여러 자료들에 대해서 간략히 설명하겠다. ADT(Abstract Data Type): 컴퓨터 과학에서 자료들과 자료들에 대한 연산들을 명기한 것. 자료구조의 추상화 1. Array- 장점: 배열에서 특정 위치의 값을 찾기에 편리하다. - 단점: 배열의 크기를 넘는 값을 삽입할 경우 문제 / 배열의 중간에 삽입 or 삭제 연산 시 번거로움 발생 2. Linked List- 선형으로 연결된 노드들을 가지는 자료구조- 노드간 pointer를 이용해 list를 구현하므로 메모리에 연속적으로 값을 저장할 필요 없다.- Array list와 달리, 추가 및 삭제가 쉽지만 데이터 접근 시 최악의 경우 O(n) time 소요- 3가지로 나뉨 1) Single Linked list- 한방향으로 연결..
-
Internet 4. script language학교 수업/인터넷프로그래밍 2020. 5. 14. 18:20
Script Language - 스크립트 언어: 프로그래밍 언어의 한 종류, 기존에 이미 존재하는 소프트웨어를 제어하기 위한 용도 - 스크립트 언어 종류 : 2가지로 나뉜다. ① 클라이언트 사이드 스크립트 언어(client side script language) : 자바스크립트, VB스크립트 ② 서버 사이드 스크립트 언어(server side script language) : JSP, ASP, PHP, Pyhton 웹은 클라이언트가 서버에게 요청한 페이지를 서버에서 잘 가공하여 다시 클라이언트에게 응답하는 구조이다. 여기서 어느 측에서 요청을 처리하느냐에 따라서 클라이언트 사이드 스크립트 언어(Client Side Script Language)와 서버 사이드 스크립트 언어(Server Side Scrip..