�ݺ�ߣ

Memoization
동일한 계산을 반복해야 할 경우,
한 번 계산한 결과를 메모리에 저장,
꺼내 씀으로써 중복계산 방지 가능.
Dynamic Progamming 의핵심이 되는 기술
=> 메모리라는 공간 비용을 투입
계산에 소요되는 시간 비용을 감소
f(4)= f(1) + f(0) + f(1) + f(1) + f(0)
함수 f를 호출하는 횟수는 총 9번
9번의 계산 중에 무려 4번을 중복계산
시간복잡도는 피보나치 수열의 값에 따라
폭발적으로 증가

Fibonacci
출처: https://new93helloworld.tistory.com/92
Recursive Recursive + Memoization

Fibonacci
출처: https://www.youtube.com/watch?v=L53nqHCSSFY

Tower of Hanoi
Ex) n = 3 일때
Non-recursive

Array & List
Array
Array 생성 시 반드시 크기를 알아야함
Array의 원소에는 index값을 이용해서 직접 access할 수 있다
Array 전체가 이미 사용 중인 경우, 원소 추가 시 크기를 늘린다 how?
(=>step 1: former array 우선 두고, 새로운 크기의 array을 위한 메모리 탐색
step 2: step 1의 결과에 따라, new array assign
step 3: Copy
step 4: former array 삭제)
ArrayList
Array이다! 위의 재할당 방법을 사용
새로운 원소를 추가할 때마다, 자동으로 더 큰 크기의 array로 재할당
원소를 많이 삭제해도 크기는 줄어들지 않는다.
Index를 사용하여 원소에 random access할 수 있다
LinkedList
Array가 아님, list 안에서 다음 원소를 가리키는
내부 객체를 이용
Index를 이용해 원소에 access할 경우, 해당
index에 access할 때까지 List를 순회
배열 재할당 과정이 없음으로, 거기에 따른 손실
(리소스 낭비+메모리)을 막아줌
원소 개수가 계속 변경되는 상황에서 유리, 크기
에 따라 메모리 용량 결정
https://opentutorials.org/module/1335/8636

Array & List
연산 Array Linked List
Access O(1) O(n)
Search O(n) – linear search
O(log n) – binary search
O(n)
Insertion
(첫번째, 마지막, 중간)
O(n)
O(n), O(1), O(n)
O(1)
O(1), O(1), O(1)
Deletion O(n)
O(n), O(1), O(n)
O(1)
O(n), O(1), O(n)
Python은 list를 제공, array를 제공하지 않음(numpy에서는 제공)
But Python의 list는 사실상의 array에다가 list의 기능을 합쳐놓은 것
그래서 C의 array보다는 메모리를 더 많이 필요로 한다는 단점

LinkedList 예시
7
0x123134
Prev
0x60..
Next
0x93..

LinkedList 예시
Sparse Matrix
• Let us represent each column of a sparse matrix as a circularly linked
list with
a head node.
• Also, let us represent each row of a sparse matrix similarly.
• We will define two types of nodes: header node and element node.
• Each column will have a head node (header) and element nodes
(element).
• Each row will have a head node (header) and element nodes (element).
• The list of head nodes (for all columns and all rows) will also have a
head
node, which is an element node type.
– The head of head node will contain number of rows (row), number of columns
(col), and number of element nodes (value).

�ݺ�ߣ

Effective Python, Clean Code

Recommended

More Related Content

What's hot (20)

Similar to Effective Python, Clean Code (20)

Effective Python, Clean Code