🔥🫡 저를 포함한 이직러들을 생각하며 만든 cheat sheet 입니다. 정리 및 리마인드겸 작성했습니다.
🔥🫡 [23.10월 기준 미완성]
빠른 찾기와 리마인드를 위한, python 코딩테스트 전용 cheat sheet
설명을 위한 글이 아닌점 유의 부탁드립니다.
deque
쓰는게 좋음for loop
하나와 쓰는 경우 O(NlogN) 이며 중첩 for loop
대신 최적화를 한다고 생각하자. heapq
를 활용O(N)
O(N)
이 걸릴 탐색을 O(logN)
으로 줄여준다.O(N^2)
이다. 그래서 이분탐색 을 활용해 최적화를 한다. Divide
): 원래 문제를 동일한 유형의 작은 하위 문제로 분할합니다.Conquer
): 각 하위 문제를 재귀적으로 해결합니다. 하위 문제가 충분히 작으면 직접적인 방법으로 해결합니다.Combine
): 하위 문제의 해결 방법을 결합하여 원래 문제의 해결 방법을 도출합니다.a: list[int] = [0] * 1000 # >= 4KB
a: list[int] = [0] * 1000000 # >= 4MB
a: list[list[int]] = [[0] * 2000] * 2000 # >= 16MB
# 공백을 기준으로 구분된 데이터를 입력 받을 떄
data = list(map(int, input().split()))
# 공백을 기준으로 구분된 데이터가 많지 않다면
a, b, c = map(int, input().split())
import sys
# 공백으로 구분된 2개 숫자 입력 받기
N, M = map(int,sys.stdin.readline().split())
# 2차원 리스트 입력 받기
board = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
# 문자열 입력 받기
data = sys.stdin.readline().rstrip()
import sys
input = sys.stdin.readline
print = sys.stdout.write
# sys.stdin.readline()은 개행문자 "\n"까지 읽어들이기 때문에
# .rstrip()등으로 지워주어야 하고
n = input() # "1"을 입력 할 때,
print(list(n)) # ['1', '\n']
print([int(n)]) # [1]
print(list(n.rstrip())) # ['1']
# print()는 출력 방식이 다음과 같이 바뀌어 버린다.
print("%s\n" % "123") # 123
print("%s\n" % ("12" + "3")) # 123
print("%d + %d = %d\n" % (1, 2, 1 + 2)) # 1 + 2 = 3
import string
string.ascii_lowercase # 소문자 abcdefghijklmnopqrstuvwxyz
string.ascii_uppercase # 대문자 ABCDEFGHIJKLMNOPQRSTUVWXYZ
string.ascii_letters # 대소문자 모두 abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
string.digits # 숫자 0123456789
# str method tip
str.isupper()
str.islower()
s = '가나다라'
n = 7
s.ljust(n) # 좌측 정렬
s.center(n) # 가운데 정렬
s.rjust(n) # 우측 정렬
mylist = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
new_list = [[], [], []]
for i in range(len(mylist)):
for j in range(len(mylist[i])):
new_list[i].append(mylist[j][i])
# 위와 동일 #
list(map(list, zip(*mylist)))
# +a zip으로 list 2개 각 key:value 만들기
animals = ['cat', 'dog', 'lion']
sounds = ['meow', 'woof', 'roar']
answer = dict(zip(animals, sounds)) # {'cat': 'meow', 'dog': 'woof', 'lion': 'roar'}
# zip 함수에 서로 길이가 다른 리스트가 인자로 들어오는 경우에는 길이가 짧은 쪽 까지만 이터레이션이 이루어집니다.
def solution(mylist):
answer = []
for number1, number2 in zip(mylist, mylist[1:]):
answer.append(abs(number1 - number2))
return answer
if __name__ == '__main__':
mylist = [83, 48, 13, 4, 71, 11]
print(solution(mylist))
# list element 모두 int 로 형 변환
list1 = ['1', '100', '33']
list2 = list(map(int, list1))
a = list(map(str, range(10)))
# ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
# input에서 map object 활용하기
>>> a = map(int, input().split())
10 20 (입력)
>>> a
<map object at 0x03DFB0D0>
>>> list(a)
[10, 20]
my_list = [[1, 2], [3, 4], [5, 6]]
# 방법 1 - sum 함수
answer = sum(my_list, [])
# 방법 2 - itertools.chain
import itertools
list(itertools.chain.from_iterable(my_list))
# 방법 3 - itertools와 unpacking
import itertools
list(itertools.chain(*my_list))
# 방법 4 - list comprehension 이용
[element for array in my_list for element in array]
# 방법 5 - reduce 함수 이용 1
from functools import reduce
list(reduce(lambda x, y: x+y, my_list))
# 방법 6 - reduce 함수 이용 2
from functools import reduce
import operator
list(reduce(operator.add, my_list))
# 각 원소 길이가 모두 동일한 경우, numpy 사용가능
# 방법 7 - numpy 라이브러리의 flatten 이용
import numpy as np
np.array(my_list).flatten().tolist()
import collections
my_list = [1, 2, 3, 4, 5, 6, 7, 8, 7, 9, 1, 2, 3, 3, 5, 2, 6, 8, 9, 0, 1, 1, 4, 7, 0]
answer = collections.Counter(my_list)
print(answer[1]) # = 4
print(answer[3]) # = 3
print(answer[100]) # = 0
테스트 변수(flag)
를 둬서 확인하는 등으로 처리합니다.import math
if __name__ == '__main__':
numbers = [int(input()) for _ in range(5)]
multiplied = 1
for number in numbers:
multiplied *= number
if math.sqrt(multiplied) == int(math.sqrt(multiplied)):
print('found')
break
else:
print('not found')
a = 3
b = 'abc'
temp = a
a = b
b = temp
# 아래와 같이 사용가능
a = 3
b = 'abc'
a, b = b, a
min_val = float('inf')
min_val > 10000000000
# inf에는 음수 기호를 붙이는 것도 가능합니다.
max_val = float('-inf')
tmp = string.digits + string.ascii_lowercase
def convert(num, base):
q, r = divmod(num, base)
if q == 0:
return tmp[r]
else:
return convert(q, base) + tmp[r]
# --------------------------------------------- #
def solution(n):
tmp = ''
while n:
tmp += str(n % 3)
n = n // 3
answer = int(tmp, 3)
return answer
int(문자열, 진수)
로 특정 "진수"로 되어있는 "문자열"을 10진수로 바꾼다. 약수가 홀수개인 모든 수는 제곱수
제곱수가 아닌 수는 약수가 짝수개
소수: 1과 자기 자신만으로 나누어지는 수
# 소수 찾기 아라토테네스의 채
def solution(n):
MAX_NUM = 1_000_000
answer = 0
d = [True]*MAX_NUM
d[0] = False
d[1] = False
d[2] = True
for i in range(2, n + 1):
if d[i]:
answer += 1
for j in range(2, n + 1):
if (j * i) >= MAX_NUM:
break
d[j * i] = False
return answer
A,B 의 최대공약수를 G, 최소공배수를 L => AB=LG
AB / G = L
a != 0, r != 0
이다. https://ourcstory.tistory.com/414
items = ['1', '2', '3', '4', '5']
from itertools import permutations
list(permutations(items, 2))
# [('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '1'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '1'), ('3', '2'), ('3', '4'), ('3', '5'), ('4', '1'), ('4', '2'), ('4', '3'), ('4', '5'), ('5', '1'), ('5', '2'), ('5', '3'), ('5', '4')]
from itertools import combinations
list(combinations(items, 2))
# [('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '4'), ('3', '5'), ('4', '5')]
# 두 개 이상의 리스트에서 모든 조합
from itertools import product
items = [['a', 'b', 'c,'], ['1', '2', '3', '4'], ['!', '@', '#']]
list(product(*items))
# [('a', '1', '!'), ('a', '1', '@'), ('a', '1', '#'), ('a', '2', '!'), ('a', '2', '@'), ('a', '2', '#'), ('a', '3', '!'), ('a', '3', '@'), ('a', '3', '#'), ('a', '4', '!'), ('a', '4', '@'), ('a', '4', '#'), ('b', '1', '!'), ('b', '1', '@'), ('b', '1', '#'), ('b', '2', '!'), ('b', '2', '@'), ('b', '2', '#'), ('b', '3', '!'), ('b', '3', '@'), ('b', '3', '#'), ('b', '4', '!'), ('b', '4', '@'), ('b', '4', '#'), ('c,', '1', '!'), ('c,', '1', '@'), ('c,', '1', '#'), ('c,', '2', '!'), ('c,', '2', '@'), ('c,', '2', '#'), ('c,', '3', '!'), ('c,', '3', '@'), ('c,', '3', '#'), ('c,', '4', '!'), ('c,', '4', '@'), ('c,', '4', '#')]
import itertools
iterable1 = 'ABCD'
iterable2 = 'xy'
iterable3 = '1234'
print(list(itertools.product(iterable1, iterable2, iterable3)))
def solution(n):
answer = 0
dp = [0]*100_001
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 2] + dp[i - 1]
return dp[n] % 1234567
# 5로 나누어지면 /5
# 3으로 나누어지면 /3
# 2로 나우어지면 /2
# X = X -1
# 1로 만드는 최소 연산 수
# 답 = min(/5, /3, /2, -1) + 1 (각 경우의 수 의미)
def solution(n):
d = [0] * 30_001
for i in range(2, n + 1):
d[i] = d[i - 1] + 1
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1)
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1)
return d[n]
특정 값 x를 log(n, 2)를 취하면 2의 거듭제곱인 것을 알 수 있다. 하지만 math.log() 함수는 부동소수점 계산을 수행
비트연산의 특이점을 활용한다. 2의 거듭제곱인 숫자는 이진수로 표현했을 때 한 비트만이 1이고, 나머지 비트는 모두 0인 패턴을 가진다.
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n>0 and n&(n-1)==0
음이 아닌 정수의 자릿수근(영어: digital root, 반복적 자릿수합(repeated digital sum)이라고도 함)은 자릿수를 더하는 과정을 방금 구한 그 값의 자릿수합에서 자릿수합을 구하도록 반복해서 얻어지는 (한 자리) 값이다. 이 과정은 한 자리 수가 될 때까지 계속된다.
예를 들어, 65,536의 자릿수근은 7이다. 왜냐하면 6 + 5 + 5 + 3 + 6 = 25이고 2 + 5 = 7이기 때문이다.
"어떤 수가 9의 배수라면, 그 수의 모든 자릿수의 합도 9의 배수" 라는 규칙을 통해 자릿수근을 쉽게 구할 수 있다.
class Solution(object):
def addDigits(self, num):
if num == 0:
return 0
return num % 9 or 9
그래프는 정점(Vertex, 또는 노드(Node)라고도 함) 과 이들을 연결하는 간선(Edge)으로 구성된 자료구조
방향성이 있는 방향 그래프(Directed Graph) 와 방향성이 없는 무방향 그래프(Undirected Graph)로 나뉘며, 간선에 가중치(Weight) 가 있을 수도 있다.
[인접 리스트] 는 각 정점에 대해 연결된 모든 정점의 리스트를 저장하는 방식 으로, 특정 정점과 인접한 정점들을 바로 알 수 있다는 장점
[인접 행렬] 은 2차원 배열을 사용하여 노드 간의 연결 관계를 행렬 형태로 나타내는 방식.
노드 간의 연결 여부를 빠르게 확인할 수 있다는 장점이 있지만, 모든 각 정점에 관한 관계를 기록하기 때문에 메모리 소비가 더 크다는 단점이 있다.
따라서 인접 행렬은 그래프 간선이 많은 그래프에 주로 사용하고, 인접 리스트는 상대적으로 간선이 적은 그래프에서 주로 사용
from collections import deque
graph = dict(
A=['B', 'C'],
B=['A', 'D'],
C=['A', 'G', 'H', 'I'],
D=['B', 'E', 'F'],
E=['D'],
F=['D'],
G=['C'],
H=['C'],
I=['C', 'J'],
J=['I']
)
def bfs(graph, node, visited=[]):
'''
- deque를 활용한 bfs
'''
# 큐 구현을 위한 deque 라이브러리 활용
queue = deque([node])
if not visited:
visited = [False] * (len(graph) + 1)
visited[node] = True # 현재 노드를 방문 처리
# 큐가 완전히 빌 때까지 반복
while queue:
v = queue.popleft() # 큐에 삽입된 순서대로 노드 하나 꺼내기
sys.stdout.write(str(v)) # 탐색 순서 출력
# 인접한 행렬 체크 여부, 구현하기에 따라 달라짐
if isinstance(graph[v], int):
continue
# 현재 처리 중인 노드에서 방문하지 않은 인접 노드를 모두 큐에 삽입
for i in graph[v]:
if not (visited[i]):
queue.append(i)
visited[i] = True
def dfs_deque(graph, start_node):
'''
- deque 활용한 stack, DFS
'''
visited = []
need_visited = deque()
# 시작 노드 설정해주기
need_visited.append(start_node)
# 방문이 필요한 리스트가 아직 존재한다면
while need_visited:
# 시작 노드를 지정하고
node = need_visited.pop()
# 만약 방문한 리스트에 없다면
if node not in visited:
# 방문 리스트에 노드를 추가
visited.append(node)
# 인접 노드들을 방문 예정 리스트에 추가
need_visited.extend(graph[node])
return visited
def dfs_recursive(graph, start, visited=[]):
'''
- 재귀를 활용한 dfs
'''
sys.stdout.write(str(start))
visited.append(start)
# 인접한 행렬 체크 여부, 구현하기에 따라 달라짐
if isinstance(graph[start], int):
return visited
for node in graph[start]:
if node not in visited:
dfs_recursive(graph, node, visited)
return visited
def preorder(root):
return [root.val] + preorder(root.left) + preorder(root.right) if root else []
def inorder(root):
return inorder(root.left) + [root.val] + inorder(root.right) if root else []
def postorder(root):
return postorder(root.left) + postorder(root.right) + [root.val] if root else []
def binary_search(arr, target, low=None, high=None):
low, high = low or 0, high or len(arr) - 1
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] > target:
return binary_search(arr, target, low, mid)
if arr[mid] == target:
return mid
if arr[mid] < target:
return binary_search(arr, target, mid + 1, high)
class Node:
def __init__(self, value: int):
self.value = value
self.left: Node = None # 왼쪽 서브노드
self.right: Node = None # 오른쪽 서브노드
class BinarySearchTree:
def __init__(self, root: Node):
self.root = root # root node
def insert_node(self, value):
'''
- 왼쪽 자식 노드 값 < 부모 노드 값 < 오른쪽 자식 노드 값 규칙을 지키면서 append (추가) 하는 method
'''
curr: Node = self.root # 연산의 기준 노드 변수 선언
while True:
# 기준 노드 값이 삽입하고자 하는 값보다 큰 경우 (삽입 값은 좌측 노드로 내려간다)
if curr.value > value:
if curr.left: # 기준 노드의 좌측 자식노드가 존재한다면
curr = curr.left # 다음 연산을 위해 기준노드를 좌측 자식노드로 초기화
else: # 기준 노드의 좌측 자식노드가 존재하지 않는다면
curr.left = Node(value) # 좌측 자식노드에 값 삽입
break
# 기준 노드 값이 삽입하고자 하는 값보다 작은 경우
else:
if curr.right: # 기준 노드의 우측 자식노드가 존재한다면
curr = curr.right # 다음 연산을 위해 기준노드를 우측 자식노드로 초기화
else: # 기준 노드의 우측 자식노드가 존재하지 않는다면
curr.right = Node(value) # 우측 자식노드에 값 삽입
break
def search_node(self, value):
'''
- BST의 특성을 생각하면서 탐색하는 method
'''
curr = self.root # 연산의 기준 노드 변수 선언
while curr: # 기준 노드가 존재하는 동안
if curr.value == value: # 기준 노드의 값이 검색하고자 하는 값과 같다면
return True # True 반환
break
elif curr.value > value: # 기준 노드의 값이 검색하고자 하는 값보다 클 때
if curr.left: # 기준 노드의 좌측 자식노드가 존재한다면
curr = curr.left # 다음 연산을 위해 기준 노드를 좌측 자식노드로 초기화
else: # 기준 노드의 좌측 자식노드가 없다면
return False # False 반환(검색하고자 하는 값이 없음)
elif curr.value < value: # 기준 노드의 값이 검색하고자 하는 값보다 작을 때
if curr.right: # 기준 노드의 우측 자식노드가 존재한다면
curr = curr.right # 다음 연산을 위해 기준 노드를 우측 자식노드로 초기화
else: # 기준 노드의 우측 자식노드가 없다면
return False # False 반환(검색하고자 하는 값이 없음)
def debugPrint(self, start: Node, level: int) -> None:
'''
- 깊이 우선 탐색의 특성으로 그래프 출력하기
'''
print(f'Node: {start.value}, childs:')
for node in [start.left, start.right]:
if not node:
continue
print(' ' * level, end='')
self.debugPrint(node, level+1)