Built in Type in Python
- NoneType: None . 실수형도아니고 정수형도 아니고,..
- Int : 컴퓨터 메모리에서는 2진수로 표현되고있는데, 10진수를 2진수로 표현하고있음. -inf ~ int로 표현할 수 없다.
- Float: 실수조차도 메모리에서는 2진수로 표현하기하는데, 0과 1사이의 무수히 많은 수가 있는데, 이를 표현하긴 불가능하다. 즉, 표현할수 있는 실수가 정해져있다. 유효숫자가 16자리가 이상이면 정확도가 떨어진다.
- Complex: 복소수를 표현
- Bool: True, False
조금 복잡한 구조: str, list (아직 만들지 않은 타입도 저장할 수 있다), tuple, dict, set <- Data structure: 한번에 여러개를 저장할 수 있게한다.
Algorithm
입력을 받아 출력으로 변환하는 계산 과정.
Correct: 모든 입력에 대해 항상 올바른 출력을 내토 끝남. 어떤숫자든.
Solve: 타당한 알고리즘은 문자를 푼다.
Theta, Big-O, Omega Noation
Theta noat : f(n)으로 표현한 수식으로 표햔한 것같으로... g(n)으로. 정확하게 알고있는 것을 세타임. 양측 바운더리를 알고 있을 때 표기
이미 대표적으로 알고있는 함수들 g(n)이라고 할 떄, log n
내가 만든 알고리즘은 f(n) = theta(g(n))
Big-O: g(n)에 대표적인 함수를 알고있을 떄, 상한을 알고있을 때. 최악의 경우의 표기법
Omega: g(n)에 대표적인 함수를 알고있을 떄, 상한을 알고있을 때
Approach
Incremental approach:
Divide and conquer Approach (분할/정복/결합): 예, 왼쪽 반과 오른쪽과 따로따로 나눠서 생각해보자, 또 왼쪽반을 1/2, 1/2으로 나눠보자. 2개로 나눴을 때는 해결하기가 쉽다, 이를 정복(Conquer)한다고 한다. 예) Mergeg sort
Doubly Linked list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | Doubly Linked list def delete(self, data): here = self.search(data) # 어디 있는지 찾아야함. bool으로 받음. if here: if here.prev != None: # 맨앞에 노드가 잇으면 here.prev.next = here.next # 나보다 전노드가 잇으면교체 else: self.head = here.next if here.next != None: # Tail node here.next.prev = here.prev else: # tail인경우 here.next | cs |
Ciruclar lists
Stack (LIFO:last in First Out ) vs Queue (FIFO)
stack은 파이썬의 list 을 쓰면된다. 굳이 구현할 필요 없다.
원소를 넣는 것은 push한다고하고, 원소를 뺼떄는 pop하면된다.
스텍예제)
infix notation: 수식은 operand, opertor가 필요한데, 파이써든 C언어든 오퍼랜드 사이에 오퍼레이터를 넣어서 작성한다. 이를 infix natation이라 한다.
그러나, 예를 들어서 CPU을 동작시키려면 postfix-expression줘야한다. 이렇게 만들면 괄호가 필요가 없다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | # postfix expression def eval_post(e); 'e: string. operand : 1자리수, operator:4칙연산' stack = [] for k in e: if k not in ('+', '-', '*', '/'): stack.append(int(k)) else: op2 = stack.pop() op1 = stack.pop() if k == '+': stack.append(op1 + op2) return stack.pop() | cs |
Queue:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | # Queue class ListQueue: def __init__(self): self.size = 0 self.items = [] def enqueue(self, data): self.items.insert(0, data) self.size += 1 def dequeue(self, data): data = self.items.pop() self.size -= 1 return def __str__(self): return str(self.items) | cs |
Tree
Hierachical form of data strucutres (<->sequential form)
- Parent-child relationship between the items
- Root: the ancestor of all other nodes in the tree. (최상위 조상)
- Application: Parsing expression, Sorting, Searches, Document(XML, HTML)
Parent Node: 부모 노드
Root node:최상위 노드
Subtree: tree내 그 하위 트리,
Degree: children node의 수
Leaf Node: children이 없는 노드
Edge: 노드-노드의 연결선
Sibling: 부모가 같은 노드. 형제노드
Level: root에서 몇개 내려왔는가? (e.g root level = 0임)
Height of tree: 트리의 길이. 가장 긴 노드의 (e.g. A-B-F-L : height 4이다)
Depth: 루트로부터 몇개내려왔는지?
Binary: 각 노드의 children이 최대 2개이다. children이 없을수도있고(leaf), 하나 있을수도있고 2개있을 수도 있다.
Quick-sort
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | def partition(A, first, last): '마지막 원소보다 큰애들은 뒤로 작은애들은 앞으로 보내는 함수' x = A[last] i = first - 1 for j in range(first, last): # last 전까지만 봄. last 은 이미 어사인함 if A[j] <= x: i += 1 A[i], A[j] = A[j], A[i] A[i+1] ,A[last] = A[last], A[i+1] return i+1 def quicksort(A, first, last): 'first, last : int. index number' if last - first > 0 p = partiion(A, first, last) quicksort(A, first, p-1) quicksort(A, p+1, last) | cs |
'Data science' 카테고리의 다른 글
| 구글드라이브 파일 wget 사용하기 (0) | 2022.11.11 |
|---|---|
| 오토마우스: 간호사, 의사 보수교육 사이버연수 자동클릭 (0) | 2022.10.29 |
| 데이터사이언티스트 면접 (0) | 2020.01.15 |
| Network analysis (0) | 2019.11.20 |
| Undersampleing & Oversampling (0) | 2019.07.08 |
