Wrap up!
알고리즘: 3장 파이썬, 4장 자료형 & 5장 리스트, 딕셔너리 & 6장 문자열 조작 & 7장 배열
개념 이해
--This book will focus specifically on Python standard built-in library, data structure, and algorithm (so will not focus on OOP or non-standard libraries like NumPy)
Pseudocode: 컴퓨터 프로그램의 작동원리 또는 알고리즘이 정해져 있지 않은 고차원 언어로 기술한 것을 말한다. 다시 말하면 수도코드는 알고리즘이 수행될 내용을 (로직을) 우리 언어로 설명한다.
I. 파이썬
파이썬: 1) 읽기 쉽다. (예. 중괄호로 묶기보다 인덴트로 묶임) 2) 사용자가 원하는 모듈 패키지를 다른 프로그램에서 사용 가능. 3) 동적 타이핑 언어이다 (dynamic programming language)
동적 (dynamic) vs. 정적 (static)
- 동적할당: 대체로 Heap영역에 메모리를 할당
- 정적할당: 대체로 Stack영역에 메모리 할당
동적타이핑 (Dynamic typing):
동적타이핑은 코드를 작성하는데 있어서 컴퓨터적 구조를 생략한다. 따라서 변수를 지정할 때 해당 변수의 데이터 타입 등을 명시하지 않아도 컴퓨터가 알아서 해석하도록 냅둔다. (실행 시간에 자료형을 검사한다.)
코드를 작성하는 시간이 빠르지만 실행하는 속도가 느리다. 그래서 속도를 중요시하는 작업에선 사용하기 부적합하지만 작고 단순한 프로젝트를 하기엔 적합하다.
코드의 내용, 로직을 파악하기 쉽다.
동적 타이핑을 사용하는 언어 - 파이썬, 루비, php 등..
객체의 멤버에 무제한으로 접근할 수 있다. (속성이나 전용의 메서드 훅을 만들어 제한할 수는 있음.)
모듈, 클래스, 객체와 같은 언어의 요소가 내부에서 접근할 수 있고, 리플렉션을 이용한 기술을 쓸 수 있다.
출처: https://crystalcube.co.kr/44 [유리상자 속 이야기]
정적타이핑 (Static typing):
정적타이핑은 동적타이핑과 정반대로 코드를 작성할 때 컴퓨터적 구조를 명시해준다. 즉, int a = 15 라는 식으로 변수의 데이터 타입을 직접 명시하며 컴퓨터가 해야할 일을 덜어주는 것이다.
코드를 작성하는 시간이 느리지만 실행하는 속도가 빠르다. 그래서 크고 복잡하며 여러 사람들이 함께 참여하는 프로젝트에 적합하다.
코드의 구조를 파악하기 쉽다.
정적 타이핑을 사용하는 언어 - C, C++, 자바 등...
https://seongonion.tistory.com/17?category=869672
문법:
Indent (acc. to PEP8)
- 4 spaces in
Naming Convention
- snake case (ex. snake_case) !For Java, it's camel case (ex. camelCase)
Type Hint (acc. to PEP484)
- 파이썬은 동적 타이핑 언어이기 때문에 타입을 지정하지 않아도 된다. 하지만 타입 힌트를 통해 함수 패러미터의 데이터 타입이 무엇인지 잘 명시하면, 파이썬 interpreter가 잘못해서 틀린 데이터타입으로 넘겨 버그가 발생하는 일을 방지할 수 있고, 또 인터프리터가 더 수월하게 코드를 읽을 수 있게 한다.
a: str = "1" (str 타입 선언)
b: int = 1 (int 타입 선언)
def fn(a:int) -> bool:
- 이 코드를 설명하자면, a 패러미터를 int타입이라 선언하고 화살표로 return 값의 타입이 bool이라는 것을 명시한다. 그래서 either True or False로 리턴이 주어진다는 것을 알 수 있다. 이와 같이 명시적으로 선언하게 되면 가독성이 좋아지면 버그 발생 확률을 줄일 수 있다. (물론 실제로는 강제 제약/규약이 아니니 여전히 동적으로 할당될 수도 있다)
- 예. a:str =1 >>> type(a) >>> <class 'int'>
List Comprehension
- 파이썬은 map, filter와 같은 함수형 기능을 지원하며 람다 표현식 (lambda expression)도 지원한다.
- Haskell같은 함수형 언어에서 기능을 차용해온 파이썬의 대표적인 특징.
리스트 컴프리헨션 안 쓴 예)
1)
a = [] for n in range(1,10+1): if n%2==1: a.append(n*2) print(a)2)
a = {} for key, value in original.items(): a[key]=value
List Comp 쓴 예)
1) [n*2 for n in range(1,10+1) if n%2==1]
2) a={key:value for key, value in original.items()}
Generator
- 루프의 반복 동작을 제어하는 루틴 형태
예. 숫자 1억개 만들어내는 프로그램은 만약 제너레이터가 없다면 숫자 1억개를 메모리에 보관하고 있어야한다. 하지만 제너레이터를 이용해 그것만 생성해두고 필요할 때 언제든 숫자를 만들어낼 수 있다.1억개 중에 100개만 쓰면 이득이다. - yield로 제너레이터를 리턴할 수 있다. 함수가 return을 맞딱드리면 값을 리턴하고 모든 함수의 동작을 종료한다. 그에 비해 yield는 제너레이터가 여기까지 실행중이던 값을 내보낸다는 의미로, 중간값을 리턴한 후에도 계속 끝에 도달할 때까지 실행된다.
- 다음값을 생성하려면 next()로 추출하면 된다.
예. g = generator()
next(g) >>> 1 >>> next(g) >>> 'apple'
Range
- 생성 조건만 정해두고 나중에 필요할 때 꺼내 쓰는 제너레이터 역활을 하는 range class. 그래서 메모리 점유율이 적다.
예. a = [n for n in range(1000000]
b = range(1000000)
둘이 똑같이 100만이 출력된다.
len(a) >>> 1000000
len(b) >>> 1000000
len(a) == len(b) >>> True
하지만 a에는 이미 생성된 값이 담겼고, b는 생성해야한다는 조건만 다르다.
sys.getsizeof(a) >>> 8697464
sys.getsizeof(b) >>> 48
Enumerate
- '열거하다'뜻을 가진 함수로 여러 자료형 (list, set, tuple등)을 인덱스를 포함한 enumerate객체로 리턴한다.
ex.
a = [1,2,3,2,45,2,5] enumerate(a) >>> <enumerate object at ...> list(enumerate(a)) >>> [(0,1),(1,2),(2,3),(3,2),(4,45),(5,2),(6,5)]
^위처럼 인덱스 숫자와 value 숫자가 튜플로 묶여서 리턴된다.
나숫셈
// (int - floor division) vs. / (float) vs. % vs. divmod (몫과 나머지)
ex.
5/3 >>> 1.6666667 >>> type(5/3) >>> <class 'float'>
5//3 >>> 1 >>> type(5//3) >>> <class 'int'>
5%3 >>> 2 (나머지)
divmod(5,3) >>> (1,2)
Print
ex. print('A1', 'B2') >>> A1 B2
ex. print('A1', 'B2', sep=',') >>> A1,B2
ex.
print('aa', end=' ')
print('bb') >>> aa bb
ex. a = ['A','B']
print(' '.join(a)) >>> A B
defaultdict 객체
- 존재하지 않는 키를 조회할 경우, 에러 메시지 대신 디폴트 값을 준 다음 해당 키에 대한 딕셔너리 아이템을 생성해줌.
Counter 객체
- 아이템에 대한 개수를 계산해 아이템 값을 key, 개수를 value로 넣어준다.
ex.
a = [1,2,1,1,2,3]
Counter(a) >>> [(1,3),(2,2),(3,1)]
II. 자료형
빅오
- 입력값이 커질 때 알고리즘 실행시간(시간 복잡도)과 공간 요구사항(복잡도)이 어떻게 증가했는지 분류하는 데 사용되며 효율성을 분석할 때도 유용하게 쓰인다. 또는 빅오(Big-O)란 입력값이 무한대로 향할때 (점근적 실행 시간asymptotic running time == 시간 복잡도time complexity) 함수의 상한을 설명하는 수학적 표기 방법이다.
- O(1): 입력값이 아무리 커도 실행시간 일정. constant
- O(log n): 실행시간이 입력값에 영향을 받는다. 하지만 로그는 매우 큰 값에도 크게 영향을 받지 않아 왠만한 n의 크기에도 매우 견고.
- (O(n): 실행시간이 입력값에 비례한다.
- O(n log n): 효율 좋은 정렬 알고리즘. (Timsort가 뭐지?)
- O(n^2): 버블 정렬, 비효율적. 루프 (for문 두개, while문 두개, 또는 각 for문 while문이 있는 형태)
- O(2^n): 피보나치 수를 재귀로 계산하는 알고리즘. n^2보다 2^n이 훨씬 크다.
- O(n!): 가장 느린 알고리즘. TSP (Travelling Salesman Problem)를 브루트 포스로 풀 때.
상한 (Big-O) vs. 하한 (Big-Omega) vs. 평균 (Big-Theta)
분할 상환 분석
- 시간, 메모리를 분석하는 알고리즘의 복잡도 계산 때, 알고리즘 전체를 보지 않고 최악의 경우만 보는 것은 비관적이다 생각해 등장한 방법. 예로 아이템 삽입 시간 복잡도는 '동적 배열'에서 O(n).
파이썬 자료형 사진 (p. 107)
mapping (복합 자료형 - dictionary), set (dict과 동일하게 {}사용, but key,value대신 그냥 값만 선언.
sequence 수열: immutable (str, tuple, bytes) vs. mutable (list)
파이썬은 모든 것이 객체다: Immutable Object (str, tuple) vs. Mutable Object (list, set, dict)
-
immutable object은 고유 id가 있어 값이 같더래도 다르다.
ex.
a = 10
b = 10
b = a
id(10), id(a), id(b) >>> (123, 456, 789) 각자 다르다 -
mutable object
ex.
a = [1,2,3,4,5]
b = a
a[2] = 4
a >>> [1,2,4,4,5]
b >>> [1,2,4,4,5]
^리스트 a요소 하나를 조작해 값을 변경하니 b의 값이 참조되어 같이 변경됬다.
III. 리스트, 딕셔너리
p.122-3
List
- append, insert,slicing, del, remove, pop
IV. 문자열 조작
Deque (double-ended queue): 양쪽 끝을 모두 추출할 수 있는 큐를 일반화한 추상 자료형(Abstract Data Type)이다.
- 양쪽에서 삭제와 삽입을 할 수 있으며, 스택과 큐의 특징을 모두 갖고 있다. 이 추상 자료형 ADT의 구현은 배열이나 연결리스트 모두 가능하지만, 특별히 doubly linked-list로 구현하는 게 좋다. head와 tail형식으로 두 포인터를 가지고 있다가 새로운 아이템이 추가될 때마다 앞 또는 뒤에 연결시켜준다.
- p. 140, 203 (HELP!!)
Two-pointer
- 두 개의 포인터로 범위를 조정해 좁혀가는 식으로 푸는 방식; use Swap
Lambda
p.149 (HELP!!)
V. 배열
