Are Python lists linked or array?
In most programming languages, there are clear differences in the way linked lists and arrays are stored in memory. In Python, however, lists are dynamic arrays.
dynamic array: 동적 배열. 크기가 고정되지 않음.
자료구조에서 array는 정적배열을 의미함(크기고정)
- index() 또는 값 변경: O(1) → 상수시간
- resize(): O(N) → 선형시간
- append(): O(1)
기존 배열이 꽉 찼을 때 append()를 하면 resize() 를 해야하기 때문에 그 순간은 시간복잡도가 O(N)이지만 평균적으로 봤을 때 O(1)
https://noahlogs.tistory.com/29
프로그래머스 문제풀기
➡️ 예산
def solution(d, budget):
d.sort()
total=0
for idx,dd in enumerate(d):
total+=dd
if total>budget:
return idx
return idx+1나는 정렬해서 앞에서부터 하나씩 더해서 모두 합한 값과 예산을 더 해서 비교
def solution(d, budget):
d.sort()
while budget < sum(d):
d.pop()
return len(d)반대로 총 합에서 하나씩 빼면서 예산이랑 비교
pop에 인덱스를 따로 쓰지 않으면 맨 뒷값부터 삭제됨
len 리턴하는 것도 좋은듯 굳이 idx를 구할 필요가 없으니.. 난 인덱스 없으면 못사나봄..
pop한 나머지 값들을 매번 다 더하는 sum을 써도 어차피 내장함수니까 그렇게 시간복잡도가 높지 않으려나??
컨테이너 메서드
자료형(Data type)의 저장 모델
- 컨테이너(Container): 모든 자료형을 포함할 수 있음
컨테이너를 상속한 자료형: 문자열, 튜플, 리스트, 딕셔너리, 집합- 단일 종류(Literal): 정수, 실수, 복소수
컨테이너 메소드별 시간 복잡도
일반적으로 O(logn)이상으로 느려지지 않는다
- 리스트:
n:컨테이너 내부 원소 수
k: 매개변수 값 또는 매개변수의 원소수
- len:O(1)
- sort:O(nlogn) → 로그선형시간
- pop last:O(1)=append
- pop(i):O(n)->이것도 탐색이라서 그런듯?
- containment,min,max=탐색O(n)
- collections.deque
리스트의 인덱스 값이 작을 경우에 발생하는 삽입과 삭제는 디큐가 더 효율적일 수도 있다고
https://wiki.python.org/moin/TimeComplexity
https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt
시간 복잡도 수행시간 측정하는 코드
https://taltal.tistory.com/m/24
import time
start_time = time.time() # 측정 시작
end_time = time.time() # 측정 종료
print("time : ", end_time - start_time) # 수행 시간 출력공간복잡도는 리스트 크기에따른 메모리의 사용량
looooggi