주요 라이브러리 ・DFS ・BFS

내장 함수

- eval

result = eval("(3+5) * 7")	# 56

 

- sorted

result = sorted([9,1,8,5,4])	# [1,4,5,8,9]
result = sorted([9,1,8,5,4], reverse=True)	# [9,8,5,4,1]

result = sorted([('홍길동', 35), ('이순신', 75), ('아무개', 50)], key=lambda x: x[1], reverse=True)	# [('이순신', 75), ('아무개', 50), ('홍길동', 35)]

 

- .sort(): 내부 값이 바로 변경됨

data = [9,1,8,5,4] 
data.sort()	# [1,4,5,8,9]

 

 

 

itertools

- permutations(순열): 서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 상관 있음)

from itertools import permutations

result = list(permutations(data, 3))	# 3개 뽑는 모든 순열

 

- combinations(조합): 서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 상관 없음)

from itertools import combinations

result = list(combinations(data, 2))	# 2개 뽑는 모든 조합

 

- product: 중복 포함 permutations

from itertools import product

result = list(product(data, repeat=2))	# 2개 뽑는 모든 순열 (중복 포함)

 

- combinations_with_replacement: 중복 포함 combinations

from itertools import combinations_with_replacement

result = list(combinations_with_replacement(data, repeat=2)) # 2개 뽑는 모든 조합 (중복 포함)

 

 

heapq

- 우선순위 큐 기능을 구현할 때 사용

- 시간 복잡도: O(NlogN)

import heapq

heap.heappush(리스트, value) # 오름차순
heap.heappop(리스트)

heap.heappush(리스트, -value) # 내림차순
heap.heappop(리스트)

 

 

bisect

- left_value ≤ x ≤ right_value 원소의 개수 구하기

- 시간 복잡도: O(logN)

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
	right_index = bisect_right(a, right_value)
	left_index = bisect_left(a, left_value)
	return right_index - left_index

 

 

collections

- deque: 

• 인덱싱과 슬라이싱 불가 
• 데이터 삽입, 삭제: O(1)

from collections import deque

data.appendleft(x)
data.append(x)
data.popleft()
data.pop()

 

- Counter

from collections import Counter

counter = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue'])

counter['red']	# 2
counter['blue']	# 3
counter['green'] # 1
dict(counter)	# {'red': 2, 'blue': 3, 'green': 1}

 

 

 

math

- factorial

import math

math.factorial(5)	# 120

 

- sqrt(제곱근)

import math

math.sqrt(7)	# 2.645751...

 

- gcd(최대공약수)

import math

math.gcd(21, 14)	# 7

 

- pi & 자연상수 e

import math

math.pi # 3.141592...
math.e # 2.718281...

 

---

스택(Stack)

- LIFO(후입선출)

- 파이썬에서는 list 자료형을 스택으로 사용할 수 있음

stack = []

stack.append(5)	
stack.pop()

 

큐(Queue)

- FIFO(선입선출)

- 파이썬에서는 deque를 사용해 큐를 구현하는 것이 가장 빠른 방법

from collections import deque

queue = deque()

queue.append(5)	
queue.popleft()

 

 

재귀 함수

- 자기 자신을 다시 호출하는 함수

- 파이썬 인터프리터는 호출 횟수 제한이 있어서 무한대로 재귀 호출을 진행할 수 없음

 

DFS

- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

- 재귀 함수를 이용

- 인접 행렬(adjacency matrix) 방법은 메모리 낭비가 심함

- 인접 리스트(adjacency list) 방법은 연결된 데이터를 하나씩 확인해야 하므로 정보를 얻는 속도가 느림

def dfs(graph, v, visited):
    visited[v] = True
	
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

 

 

BFS

- 그래프에서 가까운 노드부터 탐색하는 알고리즘

- 큐 자료구조를 이용

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
		
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True