점근표기법, 리스트, 스택, 큐
1. 자료구조 알고리즘 1주차 강의
1-3 점근 표기법
:알고리즘 성능(=효율성=시간복잡도=공간복잡도)을 수학적으로 표기
1-3-1 2개의 점근 표기법
빅 오 표기법: O(N) 최악일 경우 표기
빅 오메가 표기법: Ω(1) 최선일 경우 표기
1-3-2 for문안에 for문이 있을때 시간복잡도: O(N²)
-> 웬만하면 사용하지 말기!
1-5 알파벳 찾기
핵심->소수구하기의 <에라토스테네스의 체>처럼 배열을 하나 만들기
문자를 int(아스키코드값)으로 변환: ord(ch) 아스키코드 범위의 숫자를 char로 변환: chr(i) object를 다른 type으로 변환: int(object), float(object), str(object)
1-6 연결리스트
배열과 연결리스트의 차이
1-7 Stack(LIFO)
한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조
1-9 Queue(FIFO)
한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조
실제는 deque 활용[deque] : https://docs.python.org/ko/3/library/collections.html
arr = [1, 2, 3, 4] arr.pop() => 4 arr.pop(0) => 1 print(arr) => [2, 3]
np.array([0.724, 0.724, 0.724]) == None array([False, False, False]) '==' 으로 비교하는 경우는 객체의 요소와 비교. np.array([0.724, 0.724, 0.724]) is None False 'is' 으로 비교하는 경우는 객체 자체와 비교.
python에서 __eq__, __lt__ 등의 함수는 두 객체를 비교할 때 불리게 되는 함수들입니다. x<y calls x.__lt__(y) x<=y calls x.__le__(y) x==y calls x.__eq__(y) x!=y calls x.__ne__(y) x>y calls x.__gt__(y) x>=y calls x.__ge__(y). lt는 less than 으로 < 를, le는 less or equal로 <= 를, eq는 equal로 ==를, ne는 not equal로 !=를, gt는 great than으로 >를, ge는 great or equal로 >=를 의미합니다.
opener = "abcd" if char in opener: 가능!
문제풀이
2-1 1110문제 더하기 싸이클
10보다 작을 때, 클 때를 분리해서 생각import sys n = int(sys.stdin.readline()) 속도가 input()보다 빠르다.
2-2 1011문제 Fly me to the Alpha Centauri
규칙을 찾는 것이 중요!!!
1.n의 값 알아내기
n = 1;
while( 거리 > n^2+n)
n++;
2.횟수의 조건
거리 <= n^2 -> 횟수 = 2n-1
거리 > n^2 -> 횟수 = 2n
2-3 1002문제 터렛
반지름과 두원의 중심을 이용
-> 동심원, 한점에서 만날 때, 두점에서 만날때, 안 만날 때(나머지)
2-4 10828문제 Stack
파이썬의 리스트 내장 함수를 이용
2-5 10773문제 제로
2-5의 Stack을 활용
2-6 18258문제 Queue
collections의 depue를 사용deque의 count 함수는 비어있을 때 사용하지 않기!
