메모리구조
2진법은 앞에 0b를 붙여 표현하고 16진법은 0x를 붙여 표현한다
어렸을때 게임엔진을 이용해서 일정한 수치 값을 바꿀때 주로 16진법을 이용했다.
List는 4byte를 할당하고 각데이터는 가장 작은 데이터를 대표 주소로 설정한다
Linked List는 8byte를 할당하고 값고 주소를 저장한다 값과 주소를 묶어서 Node라고 표현합니다 그러므로 하나의 node는 8byte입니다.
시간 복잡도
big-O 표기법
상수 시간은 O(1)
n에 대한 시간은 O(n)
차수가 높은 순서는 다음과 같아
O(n!) > O(2^n) > O(n^2) > O(nlogn) > O(n) > O(logn) > O(1)
log2 4 = 2
Worst case On2
Average case On2
Best case On
보통의 시간 복잡 계산도를 애기하면 Average case를 얘기하는 경우가 많다
하지만 구하기 힘들다
Worst case와 Average case 가 비슷한 경우가 많다
시간복잡도가 10^8이 넘으면 시간 초과할 가능성이 있다면
10^5은 n! n제곱으로는 10^8이 넘어 시간 초과할 수 있다
10^4은 n제곱은 간당하고 10^3은 n제곱은 가능하다
1~7의 숫자면 n!로도 충분히 가능해서 문제의 답을 도출만 하면된다
list
set과 list는 매우 유사하다 set은 순서가 상관이 없다
set 은 맞고 [1,2,3] == [3,1,2] list 는 아니다
Python list와 자료구조의 List는 다르다
Array List는 Dynamic Array List로 구현되있는것 이고 파이썬에서는 Dynamic Array로 구성되어있다
Array
int arr[5] - {1,2,3,4,5}크기가 5인 배열
4byte(int형 데이터) * 5(size) = 20byte
이처럼 고정된 크기를 가지기 때문에 static array라고 부른다
또한 배열의 데이터를 연속적이고 순차적으로 메모리에 저장한다
arr의 첫번째 데이터의 주소가 arr의 주소다
array는 O(1) :
linked List는 O(n) : 주소를 찾아가야 해서
시간 복잡도를 가지고 있다
static array는 시간복잡도면에서 우위를 가지고 있지만
정한 크기보다 더 많은 데이터를 저장해야하는 경우는 공간이 부족해서 문제가 발생할 수 있다
이런 문제점을 해결하는게 dynamic array입니다
dynamic Array
10개의 크기를 가진 배열에 11개를 넣을 수 있다
Resizing 이라고 한다 이 과정은 오래 걸리는 과정이다
보통 기존의 배열의 2배의 큰 배열을 새로 할당한다
0 4 8 16 224 32 40 52 순서대로 리사이즈한다
기존에 있던 배열을 지우고 크기가 큰 배열에 옮겨담는다
O(n)의 복잡도를 거친다
a = [1,2,3] //O(n)
a[0] // O(1)
a[1] = 9 // O(1)
a.append(5) //O(1)
Resizing a.append(7) // O(n) 분할 상환을 하면 O(n)이 될 수 있다
a.pop() // O(1)
a.insert(1,10) //O(n)
a.pop(2) //O(1)
내부적으로 어떻게 동작되는지 알아야함
반복문
def twoSum(nums, target):
n = len(nums)
for i in range(n-1):
for j in range(i+1,n):
if nums[i] + nums[j] == target:
return True
return False
print(twoSum(nums=[4,1,9,7,5,3,16], target=14))
print(twoSum(nums=[2,1,5,7], target=4))
list를 정렬하는데에는 nlogn의 복잡도가 든다
