힙은 완전 이진트리로 구현된다. 우선순위 큐를 구현할때 힙을 사용한다.

이진 탐색 트리와 다르게 중복 값을 허용한다.

최소, 최대값만 루트 노드에 있고 그 외엔 큰 값이 상위레벨, 작은 값이 하위레벨에 있다는 정도의 반 정렬 상태를 유지한다.

pop 호출시 항상 루트노드가 제거되고 최소, 최대값이 나오게 된다.

삽입과 삭제에 시행되는 재정렬 과정이 O(NlogN) 이기 때문에 O(NlogN)을 보장한다.

보통 배열을 사용한다.

[트리]

계층적인 자료구조이다.

노드와 간선으로 이루어져서 그래프의 일종으로 볼 수 있고 최소 연결 트리 라고도 불린다. (N=N, E=N-1)

간선의 비용은 따로 없고 사이클이 존재할 수 없다.

트리는 그래프의 일종이므로 인접 배열 또는 인접 리스트로 구현된다.

이진 트리, 이진 탐색 트리, 균형 트리(AVL, red-black), 최대/최소 힙 등이 있다.

좌, 우의 순회를 재귀적으로 수행할 때 먼저 수행하면 전위 순회, 재귀함수 사이에 수행하면 중위 순회, 재귀함수 뒤쪽에 수행하면 후위 순회가 된다

트라이(trie, Prefix Tree) : n-차 트리의 변종. 각 노드에 문자를 저장하기 때문에 아래쪽으로 순회하면 단어 하나가 나온다.

접두사를 빠르게 찾아보기 위한 흔한 방식이다.

[그래프]

노드와 간선을 하나로 모아놓은 자료구조이다.

오일러 경로 : 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다.

트리와 달리 부모/자식, 루트 노드라는 개념이 없다.

순회는 DFS 또는 BFS로 이루어진다.

무방향 또는 방향 그래프로 나뉜다. 여기에 가중치가 붙을수도 있다.

트리에서는 특정 노드 하나로 다른 모든 노드에 접근이 가능했지만 그래프는 그렇지 않을수도 있다.

인접 리스트 또는 인접 행렬로 구현된다.

보통 인접 리스트로 구현된다.

인접 행렬로 구현되는 경우 2차원 배열을 써야하기 때문에 공간 복잡도는 항상 O(N²)이다.

[내장 함수]

sorted : O(NlogN)

리스트의 탐색, 중간 요소 추가, 삭제 : O(N)

min, max : O(N)

eval : 문자열 자체를 코드로 실행한다고 생각하면 된다

enumerate : 인덱스와 요소로 이루어진 튜플을 반환한다. for문에서 사용함. start를 이용해 시작 인덱스를 지정할수도 있다

[itertools - 순열과 조합]

iterable한 객체만 인자로 넘겨줄 수 있다

# 중복 없는 순열
from itertools import permutations
# 중복 없는 조합
from itertools import combinations
# 중복 있는 순열 / 각 집단에서 추출
from itertools import product
# 중복 있는 조합
from itertools import combinations_with_replacement as com

permutations : 순열. O(N!)

combinations : 조합

product : 중복을 허용하는 순열. repeat 인자를 통해 앞의 리스트의 반복 횟수를 지정할 수 있다

combinations_with_replacement : 중복을 허용하는 조합

클래스로 반환되기 때문에 리스트나 튜플로 형변환을 해주어야 한다. 반환된 값들은 튜플로 구성되어있다.

[heapq - 힙, 우선순위 큐]

대표적으로 다익스트라 알고리즘에 사용된다.

최소 힙으로 구현되어 있기 때문에 최대힙으로 사용할 때는 push, pop 실행시 부호를 바꿔주면 된다

[bisect - 이진 탐색]

[collections]

deque : 원소를 앞뒤에 모두 추가하거나 제거할 수 있어서 스택/큐 두가지 모두 응용 가능하다. 주로 큐를 이용한 BFS 구현에 자주 이용됨. rotate라는 메소드 이용시 옛날 전화 다이얼을 돌리듯이 원소들을 밀거나 땡길수 있음

Counter : 원소의 등장 횟수를 센다. 리스트의 count와 비슷하다고 볼 수도 있는데 다른점은 딕셔너리처럼 key-value 형태로 보관이 된다. 

most_common 메소드를 추가로 사용하면 데이터가 많은(value값이 높은)순으로 정렬 된 배열을 리턴한다.

인자로 자연수를 넘기면 그 숫자만큼 리턴시켜준다.

from collections import Counter

e_lst = ['red', 'blue', 'green', 'red', 'blue', 'yellow']
e_tuple = tuple(e_lst)

lst_cnt = Counter(e_lst)
tuple_cnt = Counter(e_tuple)

# red 원소의 발생횟수 조회 -> 딕셔너리처럼 key값으로 조회
print('Red:', lst_cnt['red'], tuple_cnt['red'])
print('Blue:', lst_cnt['blue'], tuple_cnt['blue'])

[math]

팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 등.

파이썬 3.9 이상 최소공배수는 lcm, 미만은 (a*b)//gcd(a,b)로 구할수 있다

divmod : 2개의 수를 받아서 몫과 나머지를 튜플 형태로 반환해준다.

eval : 실행 가능한 문자열을 입력으로 받아 문자열을 실행한 결과값을 돌려준다.

보통 입력받은 문자열로 파이썬 함수나 클래스를 동적으로 실행하고 싶을 때 사용한다.

eval('1+2') # 3
eval("'hi' + 'a'") # 'hia'
eval('divmod(4, 3)') # (1, 1)

filter : 첫 번째 인자로 함수명, 두 번째 인자로 해당 함수에 차례로 들어갈 반복 가능한 자료형을 받는다.

그리고 두 번째 인자인 반복 가능한 자료형 요소가 첫 번째 함수에 입력되었을 때 반복값이 참인 요소만 묶어서 돌려준다

# 아래 세 코드는 기능이 완벽히 동일하다

def positive(l): 
    result = [] 
    for i in l: 
        if i > 0: 
            result.append(i) 
    return result

print(positive([1,-3,2,0,-5,6]))
# [1, 2, 6]

def positive(x):
    return x > 0

print(list(filter(positive, [1, -3, 2, 0, -5, 6])))
# [1, 2, 6]

list(filter(lambda x: x > 0, [1, -3, 2, 0, -5, 6]))
# [1, 2, 6]

zip : 동일한 개수로 이루어진 자료형을 묶어준다

list(zip([1, 2, 3], [4, 5, 6]))
# [(1, 4), (2, 5), (3, 6)]

list(zip([1, 2, 3], [4, 5, 6], [7, 8, 9]))
# [(1, 4, 7), (2, 5, 8), (3, 6, 9)]

list(zip("abc", "def"))
# [('a', 'd'), ('b', 'e'), ('c', 'f')]

s1 = set([1, 2, 3]) # 1, 2, 3
s2 = set(["Hello"]) # 'e', 'H', 'l', 'o'

set 키워드를 붙여서 만들 수 있다.

중복을 허용하지 않으면서 순서가 없기때문에 앞선 자료형들과 달리 index를 통한 접근이 불가능하다.

접근을 하려면 리스트나 튜플로 변환 후 접근해야한다.

s1 = set([1, 2, 3, 4, 5, 6])
s2 = set([4, 5, 6, 7, 8, 9])

# 교집합
s1 & s2 # {4, 5, 6}
s1.intersection(s2) # {4, 5, 6}

# 합집합
s1 | s2 # {1, 2, 3, 4, 5, 6, 7, 8, 9}
s1.union(s2) # {1, 2, 3, 4, 5, 6, 7, 8, 9}

# 차집합
s1-s2 # {1, 2, 3}
s1.difference # {1, 2, 3}

s2-s1 # {8, 9, 7}
s2.difference # {8, 9, 7}

[집합 자료형 관련 함수들]

add : 1개의 값을 추가한다

update : 여러개의 값을 추가한다

remove : 특정 값을 제거한다