[Python] Algorithm & Data Structures

posted by donghyun

11 min read

태그
python algorithms data structures interview

“Data Structures and Algorithms in Python” 책 보면서 공부중

필요할때 찾아봄직한 것들만 메모

1. Python Primer

파이썬 기본 자료형들 immutable 여부 table-1-2

The bool Class

bool constructor: bool(foo) 에 sequences and other container types 넣으면 empty일때만 False

응용: 조건문에서 써먹을 수 있음

int Class

integer constructor int() :

  • default is 0
  • float는 truncate됨
  • string은 parsing 시도. 실패하면 raise ValueError

float Class

int랑 비슷함. default는 0.0. string은 parsing. raise ValueError

Sequence Types: The list, tuple, str

order가 중요한 sequence type들. NOTE: python은 single charactor 표현 class 없음. 길이 1의 string임

list Class

  • referentail structure.
  • array-based sequences, zero-indexed
  • list() constructor

    • default: empty list (same as [])

    • parameter로 iterable type을 받을수 있음(strings, list, tuples, sets, dictionaries) 

        list('hello') = ['h', 'e', 'l', 'l', 'o']

    • list를 parameter 넣어서 backup = list(data) 하면 같은 contents들 reference하는 new list instance 만들어짐

tuple Class

immutable version of a sequence

NOTE 1개짜리 tuple만들려면 (17)이 아니라 (17,) 처럼 comma를 넣어야함

str Class

represent immutable sequence of chracters, based upon the Unicode international character set

set and frozenset Classes

list에 비해 element contain 여부 찾는게 최적화 (hash table 구조임)

대신 order 유지 불가. immutable type만 받을수 있음

syntax: {'red', 'green', 'blue'}

NOTE: { } 는 empty set이 아니라 empty dictionary임. 대신 set()으로 empty set 생성

dict Class

key-values

  • python은 dict를 set하고 거의 비슷하게 구현, 다만 values에 대한 storage가 있을뿐.
  • dict constructor는 mapping을 파라미터로 받음. 혹은 key-value pair sequence도 받음

1.3 Expressions, Operators, and Precedence

Logical, Equality, Comparison Operators

  • 익히 알고있는 내용

Arithmetic Operators

  • / true division
  • // integer division
  • q = n // m 이고 r = n % m 일 때, q * m + r = n 을 보장한다.

Bitwise Operators

  • ∼ bitwise complement (prefix unary operator)

  • & bitwise and | bitwise or

  • ˆ bitwise exclusive-or
  • << shift bits left, filling in with zeros
  • >> shift bits right, filling in with sign bit

Sequence Operators
s[j] element at index j
s[start:stop] slice including indices [start,stop)
s[start:stop:step] slice including indices start, start + step, start + 2 *step,
…, up to but not equalling or stop
s + t concatenation of sequences
k * s shorthand for s+s+s+…(k times)
val in s containment check
val not in s non-containment check
  • in 은 substr에도 사용가능. ex. 'amp' in 'example'
  • sequence는 비교를 lexicographic order로 비교함. [5, 6, 7] < [5, 7] 이 성립하는 이유

Operators for Sets and Dictionaries

  • Set, frozensets

    • key in s
    • key not in s
    • s1 == s2
    • s1 != s2
    • s1 <= s2, s1 < s2
    • s1 >= s2, s1 > s2

    • s1 | s2 : union

    • s1 & s2 : intersection
    • s1 - s2 : 차집합
    • s1 ^ s2 : 상호 차집합

  • Dictionaries

    • d[key]
    • d[key] = value
    • del d[key]
    • key in d
    • key not in d
    • d1 == d2
    • d1 != d2

1.3.1 Compound Expressions and Operator Precedence

연산자 우선순위

1.5 Functions

1.5.1 Information Passing

  • formal parameters와 actual parameters의 구분
  • 함수들 파라미터는 전부 reference로 넘겨짐. object copy는 일어나지 않는다.
  • 반환값도 마찬가지. prizes = count(grades, 'A')에서 caller의 반환받는 identifier(prizes)가 function body의 resturn statement의 object로 assign된다.
  • Mutable Parameters
    • mutable object인 경우, 그 내부 state는 변경 가능
  • Default Parameter Values
    • def foo(a, b=15, c=27):

1.5.2 Python Built-in functions

Common Built-In Functions

Calling Syntax Description
abs(x) Return the absolute value of a number.
all(iterable) Return True if bool(e) is True for each element e.
any(iterable) Return True if bool(e) is True for at least one element e.
chr(integer) Return a one-character string with the given Unicode code point.
divmod(x, y) Return (x // y, x % y) as tuple, if x and y are integers.
hash(obj) Return an integer hash value for the object (see Chapter 10).
id(obj) Return the unique integer serving as an “identity” for the object.
input(prompt) Return a string from standard input; the prompt is optional.
isinstance(obj, cls) Determine if obj is an instance of the class (or a subclass).
iter(iterable) Return a new iterator object for the parameter (see Section 1.8).
len(iterable) Return the number of elements in the given iteration.
map(f, iter1, iter2, ...) Return an iterator yielding the result of function calls f(e1, e2, …) for respective elements e1 ∈ iter1, e2 ∈ iter2, …
max(iterable) Return the largest element of the given iteration.
max(a, b, c, ...) Return the largest of the arguments.
min(iterable) Return the smallest element of the given iteration.
min(a, b, c, ...) Return the smallest of the arguments.
next(iterator) Return the next element reported by the iterator (see Section 1.8).
open(filename, mode) Open a file with the given name and access mode.
ord(char) Return the Unicode code point of the given character.
pow(x, y) Return the value xy (as an integer if x and y are integers); equivalent to x y.
pow(x, y, z) Return the value (xy mod z) as an integer.
print(obj1, obj2, ...) Print the arguments, with separating spaces and trailing newline.
range(stop) Construct an iteration of values 0, 1, . . . , stop − 1.
range(start, stop) Construct an iteration of values start, start + 1, . . . , stop − 1.
range(start, stop, step) Construct an iteration of values start,start+step,start+2 step,…
reversed(sequence) Return an iteration of the sequence in reverse.
round(x) Return the nearest int value (a tie is broken toward the even value).
round(x, k) Return the value rounded to the nearest 10−k (return-type matches x).
sorted(iterable) Return a list containing elements of the iterable in sorted order.
sum(iterable) Return the sum of the elements in the iterable (must be numeric).
type(obj) Return the class to which the instance obj belongs.

1.8 Iterators and Generators

  • Basic container types, list, tuple, set qualify as iterable types
  • string, dictionary, user-defined types also may support iteration
  • the mechanism for iteration
    • iterator : an object that manages an iteration through a series of values. next(i) produces a subsequent element from the underlying series
    • iterable : an object that produces an interator via the syntax iter(obj)
    • By these definitions, an instance of a list is an iterable, but not itself an iterator
    • data = [1, 2, 4, 8] 일때, next(data)는 안되지만 next(iter(data)) 는 됨
  • That iterator does not store its own copy of the list of elements. Instead, it maintains a current index into the original list, represent- ing the next element to be reported.
  • lazy evaluation
    • range()
    • dict.keys()
    • dict.values()
    • dict.items()

Generators

def fibonacci():
  a=0
  b=1
  while True:
    yield a
    future = a + b
    a = b
    b = future

1.9 Additional Python Conveniences

1.9.1 Conditional Expressions

expr1 if condition else expr2

1.9.2 Comprehension Syntax

[ expression for value in iterable if condition ]

  • concrete example 

    squares = []
for k in range(1, n + 1):
  squares.append(k * k)

    with list comprehension, 

    squares = [k*k for k in range(1, n + 1)]

  • syntaxes

    [ k*k for k in range(1, n+1) ] list comprehension
    { k*k for k in range(1, n+1) } set comprehension
    ( k*k for k in range(1, n+1) ) generator comprehension
    { k : k*k for k in range(1, n+1) } dictionary comprehension

1.9.3 Packing and Unpacking of Sequences

  • automatic packing: 괄호 없더라도 콤마로 나열한 시퀀스는 single tuple로 취급됨
    • data = 2, 4, 6, 8 -> data = (2, 4, 6, 8)
    • return x, y
  • unpack
    • a, b, c, d = range(7, 11)
    • right-hand side는 iterable type이면 되고, left-hand side 변수 개수 일치해야함
    • for k, v in mappings.items()

Simultaneous Assignments

  • x, y, z = 6, 2, 6
  • left-hand로 assign되기전 right-hand는 모두 evaluated됨. 덕분에 swap을 편하게 가능
  • j, k = k, j